[問題] 重複組合遞迴演算法

看板C_and_CPP作者alfadick (悟道修行者)時間9年前 (2014/09/02 15:27)推噓2(2推 0噓 4→)

留言6則, 4人參與討論串1/2 (看更多)

不是作業，是解 project euler problem 31 時遇到的 https://projecteuler.net/problem=31 我感覺是重複組合的問題。我想強迫自己用遞迴寫，來練習遞迴的思考方式，但寫到卡住..。小弟不是資工系的，所以這方面訓練頗薄弱，如果把問題簡化成 x1 + x2 + x3 + x4 = 20 這種我的演算法是：先用變數 flag 紀錄目前 run 到哪個位置 (一開始flag = 4 有個四個參數的函數f) x1 x2 x3 x4 0 0 0 0 0 0 0 1 -> 呼叫 f(0,0,0,0+1) (第幾個參數變動，用flag來判定) 0 0 0 2 ... 0 0 0 20 -> 是一個解, 紀錄起來 0 0 0 21 -> 爆掉 0 0 1 0 -> flag-=1, 最後一個重設為0 0 0 1 1 -> flag 重設為4, 扼.. 反正最後兩行有點問題我也是在追蹤flag這裡卡住, 想不下去我感覺用遞迴似乎可以不用flag來記錄執行狀態有什麼SOP嗎這種題目... -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.44.197.231 ※ 文章網址: http://www.ptt.cc/bbs/C_and_CPP/M.1409642849.A.846.html

推

cutekid

09/02 16:10, , 1^F

09/02 16:10, 1^F

→

jackace

09/02 16:37, , 2^F

09/02 16:37, 2^F

→

jackace

09/02 16:37, , 3^F

09/02 16:37, 3^F