Re: [問題] 列出一個整數 所有的分割
可以類比成切木頭：要切一段長度為 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)
→
10/09 00:25, , 1F
10/09 00:25, 1F
討論串 (同標題文章)
完整討論串 (本文為第 2 之 3 篇)：
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
