Google面試問題 - 面試

※ 引述《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) ----(a)
所以原式簡化成 f(n) = 1 + k-1 = k
帶回(a)式得 f(n)-1 = f(n-f(n))
至此得到上次，也就是f(n)的關係式

不過這是一個top-to-down的關係式，我們想要down-to-top
再用簡單的變數代換後
得到f(f(n)+n+1) = 1+ f(n)

再回到題目從底層往上建，可知f(n)=1
用n=1帶入關係式得 f(3) = 2 ，再用n=3帶入得f(6)=3，n=6帶入得f(10)=4.........
以此類推，可發現f(1+2+...+n)=n (在最佳解時)

: ※ 引述《cdmdrdtw (昌仔)》之銘言：
: : 我的看法答案是:破掉的樓層/2 小數點有.5的話進位+1次
: : 我的測試方法會是將第一顆蛋以雙數位樓層來丟
: : 當丟到破掉時候已另一顆蛋回推一樓層丟確定前一樓層的但是破還是不會破
: : 舉例:假設九樓破 2.4.6.8.1O十樓破的時候我就拿第二顆蛋在九樓丟
: : 如果沒破就是十樓,如果破了就是九樓
: : 現在假設九樓有破
: : 這樣丟了六次就知道答案了:9/2=4.5進位+1=6
: : 只要十樓有破就要回推一層樓驗證所以要有兩顆蛋
: : 相對的是十樓破,只丟2.4.6.8.10樓拿第二顆蛋測試9樓是否會破
: : 答案就是10/2+1次=6次
: : 我的想法是比較保守因為是兩顆蛋
: : 如果有三顆蛋的話可以以三的倍數去測試
: : 答案是以蛋顆數決定

--