時間 (2014-04-21 19:35:01)

推文12則 (0推 0噓 12→)
這題有個能再稍微改進的地方，
就是最後一段不以單純的遞減值 (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
--
※ 發信站: 批踢踢實業坊(pttweb.tw), 來自: 1.164.140.153
※ 文章網址: https://pttweb.tw/Soft_Job/M.1398080103.A.D68

#1→ :worst,avg都沒變. 98:13->11, 99:11->12, 100:12->1304/21 20:26

#2→ :我是 98: 14 -> 11, 99: 11 -> 12, 100: 12 -> 13 @@04/21 20:36

#3 worst 是一定不會變, 因為只有最後一段能用04/21 20:38

#4 avg 嘛...這題來說幾乎無感 XDD04/21 20:38

#5→ :@@? 摔到95時不是10下了嗎? 再摔3下就到98了吧04/21 20:45

#6→ :照原本的解法, 95 沒破下一個要試 99 (11下)04/21 20:48

#7 99 破了才由 96 起一階一階試04/21 20:49

#8 原本的解請參照 #1JI2zrVk sealer 的推文04/21 20:50

#9→ :看懂了,感謝~04/21 21:02

#10 另外若假設蛋硬度分布超出測試極限的比例佔較多的話04/21 21:04

#11 原本作法留尾段小一點會不會比較好?04/21 21:04

#12→ :這題來說沒有假設前題, 有的話或許有可能 @@04/21 21:09