作者lovdkkkk (dk)
看板Soft_Job
標題Re: [討論] Google面試問題
時間Mon Apr 21 19:35:01 2014
這題有個能再稍微改進的地方，
就是最後一段不以單純的遞減值 (N-1) 去加，
改加到與最高層的中點。
例如 14, 13, 12, ..., 5, 4
原本最後那個 4 加上去會從 95 -> 99，改為 +3 到 98 則總次數會再少一，
最差次數則不變。
在其它 case 也有可能再少更多，例如最高到 49995001 層的話，
原本會是 10000, 9999, 9998, ..., 142
原本最後那個 142 加上去會從 49994847 -> 49994989，
改為 +77 到 49994924 則總次數會再少個 4000 多。
改善的部份是將最後二段平均，
使區段次數加總由原本相當於一大一小兩個梯形，
變成兩個差不多大的梯形。
沒什麼大用的改進 @@。
※ 引述《evanslee (321)》之銘言：
: 可以參考看看
: 假設 我們有N次機會來判定 是否會破
: 我們可以從第N樓開始丟, 可分情況兩種
: 1) 從第N樓丟破=>還有另一蛋但可以從1丟到 N-1樓 檢驗
: 所以情況(1)最多N次
: 2) 從第N樓丟沒破，我們剩下N-1次可以測驗
: 所以 可以往上至N+(N-1)樓丟擲 (丟了之後還剩下N-2次可以試驗)
: 由 (1),(2) 邏輯推斷
: 最多我們需要幾次 N+(N-1)+(N-2)+...+1 > 100樓
: 得到 N=14
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.164.140.153
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1398080103.A.D68.html
→ StaticVortex:worst,avg都沒變. 98:13->11, 99:11->12, 100:12->13 04/21 20:26
→ lovdkkkk:我是 98: 14 -> 11, 99: 11 -> 12, 100: 12 -> 13 @@ 04/21 20:36
→ lovdkkkk:worst 是一定不會變, 因為只有最後一段能用 04/21 20:38
→ lovdkkkk:avg 嘛...這題來說幾乎無感 XDD 04/21 20:38
→ StaticVortex:@@? 摔到95時不是10下了嗎? 再摔3下就到98了吧 04/21 20:45
→ lovdkkkk:照原本的解法, 95 沒破下一個要試 99 (11下) 04/21 20:48
→ lovdkkkk:99 破了才由 96 起一階一階試 04/21 20:49
→ lovdkkkk:原本的解請參照 #1JI2zrVk sealer 的推文 04/21 20:50
→ StaticVortex:看懂了,感謝~ 04/21 21:02
→ StaticVortex:另外若假設蛋硬度分布超出測試極限的比例佔較多的話 04/21 21:04
→ StaticVortex:原本作法留尾段小一點會不會比較好? 04/21 21:04
→ lovdkkkk:這題來說沒有假設前題, 有的話或許有可能 @@ 04/21 21:09