Re: [討論] Google面試問題
這題有個能再稍微改進的地方，
就是最後一段不以單純的遞減值 (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
→
04/21 20:26, , 1F
04/21 20:26, 1F
→
04/21 20:36, , 2F
04/21 20:36, 2F
→
04/21 20:38, , 3F
04/21 20:38, 3F
→
04/21 20:38, , 4F
04/21 20:38, 4F
→
04/21 20:45, , 5F
04/21 20:45, 5F
→
04/21 20:48, , 6F
04/21 20:48, 6F
→
04/21 20:49, , 7F
04/21 20:49, 7F
→
04/21 20:50, , 8F
04/21 20:50, 8F
→
04/21 21:02, , 9F
04/21 21:02, 9F
→
04/21 21:04, , 10F
04/21 21:04, 10F
→
04/21 21:04, , 11F
04/21 21:04, 11F
→
04/21 21:09, , 12F
04/21 21:09, 12F
討論串 (同標題文章)