Re: [討論] Google面試問題

[cyclone350 (老子我最神)]

※ 引述《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
推 lovdkkkk: +16 就是從最後一段開始當成新 case 跑
→ lovdkkkk: po 前一篇途中有想到, 不過懶了, 跟總次數比都是一咪咪
推 lovdkkkk:痾...我看到 #1JKEWvDC 了, 若是以那篇來說的話
→ lovdkkkk:那這個改進空間不存在 0rz
→ StaticVortex:看起來avg好像可以優化很多啊 為什麼改進空間不存在?
推 lovdkkkk:那一篇是每一步都求最佳的值去加, 不是單純 -1
→ lovdkkkk:沒實際算過, 不過應該會比單純優化最後一段更好
→ StaticVortex:啊, 你4F"改進空間"比較基準是"這篇"啊? 那確實是啊.
→ StaticVortex:剛才以為"改進空間"的比較基準是只優化尾段.
推 lovdkkkk:試過了, 100 的 case 比只優化最後一段再少 1 (y)