首页 > 试题广场 >

腾讯大厦有39层。你手里有两颗一模一样的玻璃珠,当你拿着玻璃

[问答题]
腾讯大厦有39层。你手里有两颗一模一样的玻璃珠,当你拿着玻璃珠在某一层往下扔的时候,一定会有两个结果,玻璃珠碎了或者没碎。大厦有个临界楼层,低于它的楼层,往下扔玻璃珠,玻璃珠不会碎;等于或高于它的楼层,扔下玻璃珠,玻璃珠一定会碎。玻璃珠碎了就不能再扔。现在让你设计一种方式,使得在该方式下,最坏的情况扔的次数比其他任何方式最坏的次数都少。也就是设计一种最有效方式。 请给出正确答案,给出算法代码有加分。
要想知道哪一层是分界点,只有一种方法。那就是用一个球从某一层(我们已经确定是安全层)开始,向上一层一层地往下丢,最开始我们只能确定地面是安全的。因为有两个球,一个用来测定分界点,另外一个当然用来找安全层,测分界点的球只能一层一层丢,但是找安全层的球可以隔若干层丢。比如我们可以按1,2,4,8,16的顺序丢,要是某一层破了,就能确定前一次尝试的层数是安全层,然后开始用另一个球一层一层地找分界点。
因为我们考虑的最坏情况,要是找安全层的间隔过大,那么找分界点最坏情况下需要次数也会越多。所以我们应该把找安全层的间隔固定成相同的层数,而且每次尝试间隔还需要再比上次尝试的层数少一层(因为每一次尝试,探测的次数会+1,间隔不变的话,最坏情况的次数会随探测次数增加,我们要求不论怎样探测,最坏次数都不变的情况)。
假定找安全层时第一次挑的层数是X,那么之后的序列应该是X,2X-1,3X-1-2,4X-1-2-3.5X-1-2-3-4..Nx-1-2-3...-(N-1)(N是最后一次探测的次数);我们的目标就是使总的探测次数最小,然后求x的值。我们只考虑最坏情况,假设在第i次探测时球破裂,探测的是(i*x-(i-1)*i/2)层,上一次是((i-1)*x-(i-2)*(i-1)/2)层。那么找安全层的次数是i,找分界点的次数是(i*x-(i-1)*i/2)-((i-1)*x-(i-2)*(i-1)/2)=x-i次,总共加起来的次数是i+(x-i)=x次(最坏情况x次)。
我们希望第一次选的层数X越小越好,这样最坏情况就是X次,但是X要是太小的话,就会导致最后一次探测的层数不够高(比如第一次选4层,依照我们的策略,选择的序列是4,7,9,10;到10层就结束了,10层以上的部分该策略就失效了)。很明显这是个等差数列求和,第一次选X层,最终能到(X+1)*X/2的层数,使(X+1)*X/2>=39,在这个条件下求取X的最小值,推出min(X)=9。
所以选取的序列是9,17,24,30,35,39,最差需要9次能找到分界点。

编辑于 2017-03-31 20:53:36 回复(6)
第9层。

动态规划求解。
发表于 2017-03-30 12:34:34 回复(0)