時間 (2014-04-21 20:51:11)

推文10則 (4推 0噓 6→)
※ 引述《lovdkkkk (dk)》之銘言：
: 這題有個能再稍微改進的地方，
: 就是最後一段不以單純的遞減值 (N-1) 去加，
: 改加到與最高層的中點。
: 例如 14, 13, 12, ..., 5, 4
: 原本最後那個 4 加上去會從 95 -> 99，改為 +3 到 98 則總次數會再少一，
: 最差次數則不變。

你所計算的是 f(5)，f(5)本身為3

若你要往前推一個，就是計算 f(9)

: 在其它 case 也有可能再少更多，例如最高到 49995001 層的話，
: 原本會是 10000, 9999, 9998, ..., 142
: 原本最後那個 142 加上去會從 49994847 -> 49994989，
: 改為 +77 到 49994924 則總次數會再少個 4000 多。
: 改善的部份是將最後二段平均，

這的確是一個方法，但要如何改善任何情況的方法?

假設 f(n) = a

則代表從 n 層樓要從 a 層開始丟

所以 => 破 => a-1
=> 不破 => f(n-a-1)

但是 f(n-a-1) 本身最優化的方法並非往上加上 (a-1) 層

以這個例子，最後若要完全優化，不該在最後一次才進行優化

若只在最後一次進行優化

也不該 +77，因為 f(134) = 16

應為 +16 才可保證在 16 次內完成，若+77，最多還要77次

可以做個簡單迴圈或是遞迴即可跑出最佳路徑

function runMin(int step, int n) {
int a = cal(n); //ex: if n=100 -> return 14
print("step " + step + " : " + a);
runMin(step + 1, (n-a));
}

若要計算 49995001 層

呼叫 runMin(1,49995001) 即可

: 使區段次數加總由原本相當於一大一小兩個梯形，
: 變成兩個差不多大的梯形。
: 沒什麼大用的改進 @@。
: ※ 引述《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), 來自: 123.193.201.124
※ 文章網址: https://pttweb.tw/Soft_Job/M.1398084674.A.D91

#1推 : +16 就是從最後一段開始當成新 case 跑04/21 21:01

#2 po 前一篇途中有想到, 不過懶了, 跟總次數比都是一咪咪04/21 21:02

#3 痾...我看到 #1JKEWvDC 了, 若是以那篇來說的話04/21 21:16

#4 那這個改進空間不存在 0rz04/21 21:17

#5→ :看起來avg好像可以優化很多啊為什麼改進空間不存在?04/21 21:23

#6推 :那一篇是每一步都求最佳的值去加, 不是單純 -104/21 21:25

#7 沒實際算過, 不過應該會比單純優化最後一段更好04/21 21:26

#8→ :啊, 你4F"改進空間"比較基準是"這篇"啊? 那確實是啊.04/21 21:47

#9 剛才以為"改進空間"的比較基準是只優化尾段.04/21 21:48

#10推 :試過了, 100 的 case 比只優化最後一段再少 1 (y)04/21 22:00