PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 數值合併

看板Prob_Solve (計算數學 Problem Solving)作者march20時間18年前 (2006/07/18 14:48)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串15/15 (看更多)

來點補充說明, 因為 step 2 (refine) 不是一個很明顯的動作 (在這幾個 case 裡) ※ 引述《sandwichC (沒回應=掛站)》之銘言： : 投影片中的例子 : S 10 7 2 4 12 6 : ---------------------------------------------------------- : R.M. 10 7 6 12 6 (2,4各加一次) : refine 10 7 6 12 6 2+4 是 RM, 因為 2+4 <= 12, 所以 (2+4) 要被 "移" 到 12 前 order 剛好沒變. : ---------------------------------------------------------- : R.M. 10 7 6 18 (12,6各加一次) : refine 10 7 6 18 同上 : ---------------------------------------------------------- : R.M. 10 13 18 (7,2,4各加一次) : refine 10 13 18 同上 : ---------------------------------------------------------- : R.M. 23 18 (10,7,2,4各加一次) : refine 18 23 注意囉, 這裡不一樣! 10+13 之後, 沒有任何一個 single entry 大於或等於 23, 所以 23 移到最後. : ---------------------------------------------------------- : R.M. 41 (10,7,2,4,12,6各加一次) : total: 10加了兩次 (level = 2) : 7加了三次 (level = 3) : 2加了四次 (level = 4) : 4加了四次 (level = 4) : 12加了兩次 (level = 2) : 6加了兩次 (level = 2) : 故建出的tree： : | : ----------------- : | | : | ------------- : | | | : | | ----------- : | | | | : ------- | | -------- : | | | | | | : 12 6 10 7 2 4 ^^^^^^^^^ 注意到了嗎? 12 6 本來是在 4 之後, 現在跑到最前面來了. 有一件事投影片沒講清楚: "把上面那顆樹變成另一顆樹, 其中各 leaf 的 depth 與在原樹中相同, 但 leaves 的順序與原數列一樣." 至於怎麼變, 這樣為什麼會找到最佳解, 就看看之前給的 link 吧 (其實我沒真的 go through 過, 但這比 windows2k 兄給的 slides 完整些 :P) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 71.137.27.253 ※ 編輯: march20 來自: 71.137.27.253 (07/18 15:00) ※ 編輯: march20 來自: 71.137.27.253 (07/18 15:01) ※ 編輯: march20 來自: 71.137.27.253 (07/18 15:02) ※ 編輯: march20 來自: 71.137.27.253 (07/18 15:02) ※ 編輯: march20 來自: 71.137.27.253 (07/18 15:03)