hanyeah

题目描述

有一个100层高的大厦，你手中有两个相同的玻璃球。从这个大厦的某一层扔下球就会碎，用你手中的这两个玻璃球，找出一个最优的策略，来得知那个临界层面。

https://www.cnblogs.com/noble/p/4144187.html

https://blog.csdn.net/marleylee/article/details/77602795

解法一：

第一个球扔10层、20层、30层……，第二个球在第一个球最后一次未摔碎的楼层基础上扔+1层、+2层、+3层。

总结：

类似于我们平常用的天平。

这种方式不是效率最高的，但是也已经足够快了，而且很好实现，也很好理解。

解法二：

用动态规划，状态方程是f(m,n) = f(m, n-1) + f(m-1,n-1) + 1，m是球的个数，n是最大测试次数，f(m,n)是最多能测试的楼层数。

m=2时，求使得f(m,n)>=100的最小的n，求得n=14，此时f(m,n)=105。

第一个球扔14层、27层（14+13）、39层（14+13+12）、50层（14+13+12+11）……，第二个球同解法一。

和第一种方法类似，只是第一个球选的楼层不是均匀的，而是递减的。

总结：

效率比解法一高，实现起来比第一种难，不容易理解。

思考：

两种方式的最好、最坏情况是多少次，期望值是多少？

3个球（n个球）的时候的策略？

为什么天平不使用第二种方式？

除了天平，上面提到的两种算法在实际生活中还有哪些应用？

https://github.com/hanyeah/lianxi/tree/master/两个球100层楼