一种杯子,若在第N层被摔破,则在任何比N高的楼层均会破,若在第M层不破,则在任何比M低的楼层均不会破,给你两个这样的杯子,让你在100层高的楼层中测试,要求用最少的测试次数找出恰巧会使杯子破碎的楼层。
- 思路
由于杯子的个数是确定有限的,所以应该尽可能使得两个杯子测试的次数均衡以达到最少。而自然数列可以实现这一目标,令其和S大于等于100,得出n至少为14。
则第一个杯子可能的投掷楼层分别为:14,27,39,50,60,69,77,84,90,95,99,100;这样可以使得第二个杯子最多需要13次(第一种情况)测试,加上第一个杯子的一次正好是14次。依次往后测试可以发现两个杯子加起来最少需要14次可以确定楼层。
而当不是从14开始时,其他情况都会大于14次。所以最少14次能找出恰巧会使杯子破碎的楼层。
网友评论