Re: [討論] Google面試問題

作者: prpure (風速)   2014-04-13 17:22:39
※ 引述《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)

Links booklink

Contact Us: admin [ a t ] ucptt.com