很多答主给出了14次的答案,我尝试写个简单的版本。
不管是扔鸡蛋还是玻璃球,要么碎要么不碎,所以本质上最少次数=最开始扔的楼层。举个例子,如果最少次数为6次,那么你就得从6楼开始,扔碎了,那楼层就锁定在1-5楼,为了保险,只能从最低楼层慢慢往上才能锁定楼层。最倒霉的情况就是在5楼,总共尝试了6次。
首先假定最少x次可以找出,那在这x次里面,我们需要能遍历完这100层楼。
假设第一次没碎,那你就用掉了一次机会了,剩下的就只有x-1次。
以此类推,第二次没碎,那就只剩下x-2次了,第三次没碎,就剩x-3次。
把总共x次能尝试的楼层累加起来,就是一个等差数列:
这时再把题目中的100楼带入进去,也就是累加的值要>=100:
所以最坏情况下的最少次数为14次。
最优策略就是从14楼开始扔,然后27,39,50...
}版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。