这几天，脑子里一直是玻璃球从100层落下的面试题。
这是吴军老师说的，很有意思的题，具体问题，听他的得到专栏，谷歌方法论。
1、对于只有两个球的情况
假设第一个球扔了x 次， 那么第二个球，最大的尝试次数y = (100/x) -1
由于需要获得 x+y 的最小值 ， 也就是x + (100/x) -1 的最小值，也就是 x+ (100/x) 的最小值 。
如果能得到函数的图，一目了然，直接用了91maths
函数图两个球.png
也就是两个球，最多19次尝试，一定能找到那层，恰好碎了 。
而后，这几天。琢磨三个球的情况，22，或者4 或5 ， 最佳。
我从答案，开始反推 两个球的情况，，是不是可以把题目改为 ab=100 ，如何确保a+b 最小 ，当a，b都是自然数时？
立马想到了面积。
而后我想，扔三次玻璃球，，那就是体积啦 。
abc =100 如果a,b,c是自然数，那么，4（5x5 ） =100 ，，
基于以上瞎想，
2、分析 三个球的情况 。
假设第一个球扔了k 次，，那么，第二个球扔了a 次，第三个球扔了b次，
他们的关系是
a*b =100/k-1
为了得到的 k+a+b 最小，用面积法，当a=b时 ，边长不变的情况下，正方形面积最大，不能是圆 。
用正方形比喻也不恰当，应该用a^2 =100/k
所以，k+a+b 最小，也就是k+a+a = k+2a ，a=10/k^(1/2) , 所以，我们需要的图像
就是 k+20/k^(1/2) 函数曲线如下
sangeqiu.png
可见，k =5，为好 ，那么 ，基本确定，扔14次，最多，也就能得到结果 。
但为什么是第一个玻璃球 每次22 层 ，不是21 层，我看需要写个python 。
以上就是粗调。。
接下来根据 k=5 ,
用python 写个程序，用list ， 分别对应着，从1到100层，恰好玻璃球碎。
用程序尝试匹配，和猜数字大小一样，记录猜了几次，最后，就形成了一个列表，
而后就是打印输出了。
输出两个数，一个列表中的最大数，也就是该方法的最大尝试次数，
而后是列表的总和，也就是一共需要尝试的总次数。
输入，20，21,22,23,24,25, ，
还有，比如 当在88层不碎，100层，碎了，，只有89---99 这11层楼了，两个球，
立马，又可以微调了，3*4 =12 最靠近11 ，所以，这时候用4 。
这就像测试素数的，筛子算法，不断在迭代过程中，用最小优化算法进行微调 。
网友评论