※ 引述《tiwei (学海无涯回头是岸)》之铭言:
: 1 + 2 + ... + N > 100
: 其实不是简单的一题 .. 我第一次被问30分钟内没解出来
: 金融业蛮常问这题的~
题目的意思是求当worst case时的最小值
可以设f(100)为100楼时,丢两颗至少要丢几次的值
所以f(n)为只剩n楼时,丢两颗至少要丢的解
当在k楼丢第1次后,如果:
1.破了,那就只能从最小楼开始丢,还要丢k-1次
2.没破,表示丢的范围缩小到(n-k),还有两颗可以丢
以上可列出 f(n) = 1 + max[k-1,f(n-k)] 其中k为使上式为最小值之解
虽然列出方程式,但还有个k在,要消去才有办法算
以下消去k:
因为k为使max(k-1,f(n-1))成立的最小值
设当在最佳状况时, k-1 = f(n-k)