一个有趣的问题

前言

  这个问题来自于看到的一个面试题,其中的解题过程比较有趣,有很多值得借鉴的地方,这里写出来作为记录。

题目

假设一栋100层的楼,两个完全一样的鸡蛋。存在某一层N,当鸡蛋从大于或等于N的楼层落下时会碎掉,当鸡蛋从小于N层落下时不会碎。问用两个鸡蛋找到N的最佳方案,以及此时最坏情况下需要实验几次。

  非完美的5分解决方案:

    解决方案一的灵感来自于已知两数的和,求两数的平方和的最小值。即假设两数和为25,求两数的平方和的最小值和最大值。

  这个解法比较简单,直接设一个数位x,则另一个数为(25-x),两数的平方和为 x2 + (x-25)2 = 2x2 - 50x + 625 = 2(x - 12.5)2 + n 可以只当x为12.5的时候取得最小值。当x为25的时候取得最大值。由此可以猜想是否可将100分成10等份,每一等份的层数正好为10层(跟前面的题目没有任何关联,只是一种第六感)。此时方案就是分别从第10层,20层,30层.. 丢第一个鸡蛋,直到第一个鸡蛋碎掉。然后从碎之前的一次丢位子的后面一层开始一直往上一层丢,直到找到刚好第二个蛋碎的位置。此时最坏情况下需要试18次。

  完美的解决方案:

  我们可以假设最坏的情况下需要丢x次鸡蛋。假设刚开始应该在第y层开始丢。此时第一次如果鸡蛋碎了,那么最坏的情况下找到N还需要丢y-1次。所以此时有 1 + y - 1 = x; 可以得到开始应该在第x层丢。假设第一次丢蛋没碎,那么第二次丢肯定要在x层之上丢,假设第二次丢的层数比第一次丢的高z层,同第一次一样假设第二次丢鸡蛋碎了, 那么最坏的情况下找到N需要的次数应该是: 1 + 1 + z - 1 =x;  可以得到 z = x - 1;也就是第二次应该比第一次丢的楼层高x-1层。依此类推知道最后一次就能断定是否是N。所以有下面等式:

  x + (x-1) + ... + 1 >= 100   

  解上面的不等式得 x = 14. 所以完美的解决方案丢的层数应该依次是: 14, 27, 39, 50, 59, 67, 84, 90, 95, 99, 100. 最坏的情况下需要测试14次。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Ceph对象存储方案

Luminous版本PG 分布调优

Luminous版本开始新增的balancer模块在PG分布优化方面效果非常明显,操作也非常简便,强烈推荐各位在集群上线之前进行这一操作,能够极大的提升整个集群...

3265
来自专栏大内老A

The .NET of Tomorrow

Ed Charbeneau(http://developer.telerik.com/featured/the-net-of-tomorrow/) Exciti...

32810
来自专栏转载gongluck的CSDN博客

cocos2dx 打灰机

#include "GamePlane.h" #include "PlaneSprite.h" #include "BulletNode.h" #include...

5706
来自专栏杨龙飞前端

scrollto 到指定位置

2564
来自专栏跟着阿笨一起玩NET

c#实现打印功能

2942
来自专栏张善友的专栏

LINQ via C# 系列文章

LINQ via C# Recently I am giving a series of talk on LINQ. the name “LINQ via C...

2675
来自专栏我和未来有约会

Kit 3D 更新

Kit3D is a 3D graphics engine written for Microsoft Silverlight. Kit3D was inita...

2636
来自专栏我和未来有约会

Silverlight第三方控件专题

这里我收集整理了目前网上silverlight第三方控件的专题,若果有所遗漏请告知我一下。 名称 简介 截图 telerik 商 RadC...

4095
来自专栏闻道于事

js登录滑动验证,不滑动无法登陆

js的判断这里是根据滑块的位置进行判断,应该是用一个flag判断 <%@ page language="java" contentType="text/html...

7248
来自专栏pangguoming

Spring Boot集成JasperReports生成PDF文档

由于工作需要,要实现后端根据模板动态填充数据生成PDF文档,通过技术选型,使用Ireport5.6来设计模板,结合JasperReports5.6工具库来调用渲...

1.3K7

扫码关注云+社区