2个鸡蛋,有一栋100层的高楼,鸡蛋从某一个临界楼层丢下会摔碎,请设计方案,能用最小的次数找到临界楼层

  有一栋100层的高楼,一个鸡蛋从第N层及以上的楼层落下来会摔破, 在第N层以下的楼层落下不会摔破。给你2个鸡蛋,设计方案找出N,并且保证在最坏情况下, 最小化鸡蛋下落的次数。(假设每次摔落时,如果没有摔碎,则不会给鸡蛋带来损耗)

  如果只有一个鸡蛋,就只能从第1层逐层往上扔,最坏的情况下,要99次(假如99层还没碎,则是100层)

  如果有两个鸡蛋,则第一个鸡蛋用来缩小查找的范围,因而把100层分成若干段,先利用一个鸡蛋来确定临界层所在的段,再利用另一个鸡蛋确定临界层,关键点在于如何分段。

  比如说,每10层分一段,10,20,30...90,一共扔9次,在第90层碎了,那么第二鸡蛋从81到89,最坏的情况下还得扔9次,这种分段法不一定是最优的。

  假设最坏的情况下,最少要x次才能找到临界楼层

    如果在x层扔了后,没碎,则往上,到x+(x-1)层去扔,还没碎,则到x+(x-1)+(x-2)层去扔

    如果在x层扔了后,碎了,则在1~x-1逐层往上扔

  那么为什么是x+(x-1)层,这里假设x是10,x+(x-1)=19,在10,19层各扔一次,一共两次,11-18,最坏的情况下要8次,8+2正好=10

  所以只要解出x+(x-1)+(x-2)+...+1>=100就行了,x最小为14

原文地址:https://www.cnblogs.com/mengchunchen/p/9877902.html