有一个100层高的大厦,你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎,用你手中的这两个玻璃围棋子,找出一个最优的策略,来得知那个临界层面。
[答案:如果手中只有一个棋子,那么肯定只能从第2层依次向上扔到100层,现在手中有2个棋子,那么可以用其中一个的“性命”来换取我们对临界层更快的获取。基本思路是将100层楼分段,先找到临界段,然后再在临界段内一层层的测试找出零界层。同样,我们需要从低层向高层找临界段,不然第一颗棋子的牺牲可能并不能让我们得知临界段在哪。由于每向上一个临界段我们就需要多测试一次,然后我们又需要测试临界段内的楼层。为了保证测试的最优化,即无论任何情况下我们需要的测试次数都不会太多,我们应该保证:
找到零界段的次数 找到临界层
尽量均化,所以我们上一个临界段应该比下一个临界段少1.
由于1 2 3 …… 13 14=105,多出5层来,就是说不能达到完全的均化,我们可以把这5层“消化”到其中一些段,目的还是尽可能地保持平衡。我们可以认为最下面一段为14层(或者13层,假设其中的一层在第一段“消化”),以此开始测试,没有摔碎就向上一段,碎了就在此层中由下向上继续测试。
思路就是这样,无论临界层在哪,我们找到它所需要的次数应该都不多。]