Re: [討論] Google面試問題
※ 引述《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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.201.124
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1398084674.A.D91.html
推
04/21 21:01, , 1F
04/21 21:01, 1F
→
04/21 21:02, , 2F
04/21 21:02, 2F
推
04/21 21:16, , 3F
04/21 21:16, 3F
→
04/21 21:17, , 4F
04/21 21:17, 4F
→
04/21 21:23, , 5F
04/21 21:23, 5F
推
04/21 21:25, , 6F
04/21 21:25, 6F
→
04/21 21:26, , 7F
04/21 21:26, 7F
→
04/21 21:47, , 8F
04/21 21:47, 8F
→
04/21 21:48, , 9F
04/21 21:48, 9F
推
04/21 22:00, , 10F
04/21 22:00, 10F
討論串 (同標題文章)