→ calqlus:感謝你詳細的講解~~ 10/09 00:25
可以類比成切木頭：要切一段長度為 n 的木頭有幾種切法 ?
□□□□□ ... □
1 2 3 4 5 n
所以直觀來看，我們可以固定每次把木頭右邊切一段下來，剩下的遞迴列出來
那我們要切多長呢 ? 不知道，枚舉吧！
CUT-WOOD ( dep, n )
1 if n＞1 then do
2 for i←1 to n do
3 cut[dep] ← i
3 CUT-WOOD ( dep＋1, n－i )
4 else do print cut[0 ... dep－1]
但是這樣還不夠，因為會重複列出來
要把重複的去掉很簡單，只要每次切的長度非嚴格遞減就好
CUT-WOOD ( dep, n, max_cut )
1 if n＞1 then do
2 for i←1 to max_cut do
3 cut[dep] ← i
3 CUT-WOOD ( dep＋1, n－i, i )
4 else do print cut[0 ... dep－1]
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.217.33.57
※ 編輯: suhorng 來自: 61.217.33.57 (10/08 23:11)