100层楼,两个鸡蛋。某层之上扔鸡蛋就会碎。问至少要测试多少次才能试出这个层数。
设x个鸡蛋扔y次可以测试F层,则F=f(x,y).
f(1,1)=1,f(1,2)=2……..f(1,n)=n
f(2,1)=1,对于f(2,2),先测试一次,如果第一个鸡蛋没有破,则测试该层之上的层数为f(2,1),如果第一个鸡蛋破了,则测试该层之下的层数为f(1,1). 所以f(2,n)=1+f(1,n-1)+f(2,n-1).
因此f(2,1)=1, f(2,2)=3, f(2,3)=6, f(2,4)=10, f(2,5)=15, f(2,6)=21
=>f(2,n)=n*(n+1)/2
=>n=14.
动态规划,答案是14。
具体方法是先从14楼开始抛第一次;如果没碎,再从27楼抛第二次;如果还没碎,再从39楼抛第三次;如果还没碎,再从50 楼抛第四次;如此,每次间隔的楼层少一层。这样,任何一次抛棋子碎时,都能确保最多抛14次可以找出临界楼层。