主题:【原创】由一个简单的面试题想起的 -- 东方射日
共:💬43 🌺18
这道题似乎源于GOOGLE的一道面试题:
有两个鸡蛋,100级台阶,从台阶上往下掉蛋,怎么样用最少步找出从哪一个台阶开始蛋开始破。
我的答案是:
13 25 36 47 57 65 73 80 85 90 94 97 99 100
平均步数= 10.3
最坏 = 14 (在100级或100级也摔不破)
方法:
f(n) = min(f(n,x)), x in [1,n]
f(n,x) = 1 + [x/(n+1)] * [ (x-1)/2 + (x-1)/x ] + [1-x/(n+1)] * f(n-x);
是典型的动态算法。