[問題] 遞迴問題

看板C_and_CPP作者 (濕濕)時間7年前 (2016/11/11 23:19), 7年前編輯推噓3(3推 0噓 14→)
留言17則, 7人參與, 最新討論串5/6 (看更多)
macOS 10.12 GCC 無 我想請問遞迴的意思是直接呼叫自己就算嗎 因為做了好幾題還是很不懂 有沒有哪邊有比較多遞迴的CODE可以參考 河內塔 排列組合 我就搞到頭暈了 主要是流程不太清楚 希望板上能推薦一些教材 還有 有哪些題目是用遞迴比較方便的嗎 因為我發現遞迴的題目都是一些很漂亮的 不知道以後實戰用到的機會多不多？ 是這樣的 我想要做一個程式 先給定一個值例如 120 然後給數量 8 (8筆資料) 接著輸入個數 25 30 15 20 30 40 35 10 然後要印出有幾種組合可以使總和=120 我知道把那些資料用陣列來存 但是我要如何用遞迴來找結果 要讓總和等於120 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.105.31.4 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1478877541.A.CAA.html 11/11 23:33 11/11 23:34 11/11 23:35 11/11 23:45 11/11 23:46 ~ ※ 編輯: ptt0720 (59.105.31.4), 11/12/2016 00:03:51
→
11/12 00:12, , 1F
對於數列第一個數字25有兩種情況：取or不取
11/12 00:12, 1F
→
11/12 00:13, , 2F
取：問題變為在30 15 20 30 40 35 10找出總和為95的組合
11/12 00:13, 2F
→
11/12 00:13, , 3F
不取：在剩下七個數字中找出總和為120的組合
11/12 00:13, 3F
→
11/12 00:17, , 4F
剩下的問題就是什麼時候該停止遞迴
11/12 00:17, 4F
推
11/12 00:21, , 5F
這問題你可以查看看dynamic programming的背包問題
11/12 00:21, 5F
推
11/12 03:01, , 6F
這個可以用一個integer 來模擬所有情形 寫成for loop
11/12 03:01, 6F
→
11/12 03:01, , 7F
效率很高
11/12 03:01, 7F
→
11/12 03:02, , 8F
想寫遞迴的話Google subset sum recursion
11/12 03:02, 8F
→
11/12 03:02, , 9F
有很多教學
11/12 03:02, 9F
→
11/12 04:59, , 10F
因為消耗的資源較多 實用上不鼓勵遞迴
11/12 04:59, 10F
→
11/12 05:00, , 11F
但有一些剛好就是用遞迴考慮最簡單的問題 或者規模可以
11/12 05:00, 11F
→
11/12 05:01, , 12F
控制到相對小的問題 用遞迴解決並無不可
11/12 05:01, 12F
→
11/12 05:02, , 13F
把它轉換成iteration可能要浪費更多時間 或不易維護
11/12 05:02, 13F
→
11/12 08:49, , 14F
用 power set 比較快：https://ideone.com/xp9RBc
11/12 08:49, 14F
推
11/12 14:33, , 15F
C程序设计的抽象思维, recursive我覺得是可以投資的技巧
11/12 14:33, 15F
→
11/13 11:18, , 16F
我要讓資料都給使用者輸入 如何讓知道哪些輸字是必須要的
11/13 11:18, 16F
→
11/13 11:28, , 17F
？輸入過濾用迴圈或regex來match就好 跟遞迴有何關聯
11/13 11:28, 17F
‣ 更多 ptt0720 的文章
文章代碼(AID): #1O9U5bog (C_and_CPP)
‣ 更多 ptt0720 的文章
文章代碼(AID): #1O9U5bog (C_and_CPP)