→ adgjl5645: 補充一點 我覺得這種寫法比較像是 divide and conquer 06/09 10:08
→ adgjl5645: 把問題拆成更小的問題 06/09 10:08
※ 引述《ptt0720 (濕濕)》之銘言：
: def combos(n, m = 1):
: if n < m:
: return []
: res = [[n]]
: for i in range(m, n):
: l = [i]
: for j in combos(n - i, i):
: res += [l + j]
: return res
: print (combos(5))
: 我寫題目遇到一題 題目是這樣
: 假如輸入3 要列出所有相加等於3的情況
: [3],[2,1],[1,1,1]
第一次看到這種問題跟寫法的時候心裡一定會有很多問號，但是其實沒有需要這麼害怕，
讓我們冷靜下來看看這個問題
首先讓我們回到題目本身，題目的意思是要我們找到所有數字合等於 n 的解，接著稍微
的看一下程式碼，我們看到他在函數裡面又呼叫了一次自己，這種遞迴的寫法，遞迴的寫
法雖然比較複雜但是邏輯是比較簡單的
一般來說，用到遞迴的情況是在這個計算的過程中會用到相同的計算，這是什麼意思呢？
舉例來說，當你在做費波那契數列的時候，算 n 的值的過程就會要用到 n-1 的值
回到程式碼上，首先 2 3 行是檢查沒有答案的情況，4 初始化了答案 n 本身一定會是一
組解，接著就是關鍵的雙層迴圈
首先，最外層的迴圈從 1 開始到 n ，但在這邊我們可能還沒清楚他想做什麼，於是我們
看向第二個迴圈，這邊出現了 combos(n-i, i)，我們先不管這邊的語法是什麼，我們先
看看 combos 這邊想做的是什麼，這邊算的是由 i 開始總和是 n-i 的解，回傳成一個 l
ist，所以第二層的 for 就是對這些解一個一個再加入 I 然後加進答案裏
到這邊其實整份程式的架構就差不多出來了，怎麼說呢？藉由程式碼我們可以從新理解這
個題目是解法，所有和是 n 的解可以由所有和是 n-k 的解再加上 k ，然後遍歷所有 k
, 這就是這份程式碼在做的事情
: 然後爬文看到一個算式比較簡單的寫法
: 但是還是不太懂
: 第七行為什麼可以讓迴圈在def執行?
至於語法上重點是他要的是 combos 的回傳值，而不是 function 本身
: 還有他的每一層迭代我也不是很了解
: 目前只理解到 第一次執行會留下自己的值
: 接下來把自己的值-1 (ex:3-1=2) 繼續分解2
: 假如輸入是5呢
: [5],[1,4],[1,1,3],[1,1,1,2],[1,1,1,1,1]
: 接下來的
: [1,2,2],[2,3]是如何進行迭代的 我就不太清楚了
: 希望板上神人們可以指導一下
希望有回答到你的問題
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.109.127.9
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1496973905.A.CD9.html