最高从哪层楼扔下时鸡蛋不会碎?

一幢 200 层的大楼,给你两个鸡蛋。如果在第 n 层扔下鸡蛋,鸡蛋不碎,那么从第 n-1 层扔鸡蛋,都不碎。这两只鸡蛋一模一样,不碎的话可以扔无数次。最高从哪层楼扔下时鸡蛋不会碎?

递推关系大概是,当前需要扔一次所以加1。当前这一次可能是从1到n层的任意一层扔下,在n种情况中选择扔的次数最少的。当前这一次扔下,如果鸡蛋碎了,就只用试i-1层,鸡蛋剩下m-1个,如果鸡蛋没碎,就试剩下的n-i层,两种情况中取最大的,因为是最差情况。

至于100层时用14+13+12+……+1,大概是第一次选14层,如果鸡蛋碎了,就只能从第一层开始一层一层往上试,最坏情况下一共14次,如果没碎,第二次选14+13=27层,如果碎了,最坏情况下就从15层一直试到26层,一共也是14次,如果没碎,第三次再从27+12=39层试,以此类推……

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 在网上查资料的时候无意间看到了这道谷歌面试题,据说这道面试题刷了好多的大牛(可怕)。读了几篇文章,读懂以后感觉这种...
    进击的诺基亚阅读 5,156评论 1 4
  • 问题 有一栋100层的高楼,一个鸡蛋从第N层及以上的楼层落下来会摔破, 在第N层以下的楼层落下不会摔破。给你2个鸡...
    豆志昂扬阅读 2,789评论 0 0
  • 十里桃花开, 芬芳幽入怀。 曾言三生事, 怎奈一岁哀。
    FLY_93阅读 125评论 0 0
  • 他们八年前开始在一起,第三年她的家人遭遇车祸,只剩她一个人了,于是他把她接到了自己家里,开始像一家人一样生活在一起...
    正齐读道阅读 287评论 0 0
  • 当我毕业步入社会的第一天开始,我觉得我双肩的责任重了,不是那些上学时的无所顾忌了,因为工作,我学会了忍耐,因为工作...
    靳蛋蛋阅读 207评论 0 0