You have two glass balls and a 100-story tower. You would like to determine the lowest floor from which a glass ball will break when dropped. You can reuse a ball if it remains unbroken after a trial. Assume that the value of lowest floor is distributed uniformly and find the strategy which minimizes the expected number of tries.
迷惑ing…高智商的人啊
翻译过来俺有可能有答案
I think binary search will do? I was asked this question once 🙂
Hi Bear, could you plz disclose more details of your idea or the proposed algorithm as binary is a very general idea.
The proposed solution:
Denote the first glass ball as B1, another as B2. Move B1 to search n stories upwards each time. assume B1 breaks after k times. So the minimum number must be
between n*(k-1) and n*k (because it has not broken on the n*(k-1)th floor). Then use B2 for the secondary search (there are n-1 stories need to be checked, not n !).
Therefore, the total number of searches implemented so far is k+n-1. As previously mentioned, the distribution is uniform. So we have: k=100/n/2 (divided by 2 to get average)
Similarly, for the secondary search, the average is: (n-1)/2. The total number now becomes: 50/n+n/2-0.5. Employ the inequality formula (a+b>=2*sqrt(a*b))
we have: 50/n+n/2-0.5>=2*sqrt(50/n*n/2)-0.5=9.5. So the mimimum No is equal to 10.
Dear Jie, I don\’t think the answer is right although I don\’t know the right answer. It\’s really a interesting question and I hope can see the right answer from you sometime. 🙂