[問題] 使用遞迴或使用其他迴圈方式

看板C_and_CPP作者 (老柏~)時間12年前 (2013/03/03 23:13), 編輯推噓3(3推 0噓 15→)
留言18則, 7人參與, 最新討論串1/2 (看更多)
開發平台(Platform): (Ex: VC++, GCC, Linux, ...) Dev C 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) 問題(Question)： 假設我有一段布，布長3公分 我可以將這塊布切成 1段 3公分 2段 1公分+2公分 及 2公分+1公分 (這兩種組合是不同的組合) 3段 1公分+1公分+1公分 共有2^(3-1) =4種組合 若我有一塊布，布長4公分 可以將這塊布切割為 1段 4公分 2段 1公分+3公分 2公分+2公分 3公分+1公分 (這3種組合是不同的組合) 3段 1+1+2 1+2+1 2+1+1 4段 1+1+1+1 共有2^(4-1)= 8種組合 組合數目怎麼計算很簡單，但是如何知道有上述這些組合 我的直覺是用遞迴寫，可是遞迴的觀念沒有很強，不知道該如何下手 感覺不是用迴圈寫出來的 想請問版大們，這樣的問題該如何處理 謝謝 -- Poyuan~等待不是件簡單的事 http://blog.pixnet.net/andrew771027 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.119.192
→
03/03 23:17, , 1F
4 => 4 , 1+3, 2+2, 3+1
03/03 23:17, 1F
→
03/03 23:17, , 2F
5 => 5, 1+4, 2+3, 3+2, 4+1
03/03 23:17, 2F
→
03/03 23:20, , 3F
長度n公分的布第一刀切 k 公分, 那剩下的就有 n-k 公分
03/03 23:20, 3F
→
03/03 23:21, , 4F
兩部份各自遞迴處理就ok了
03/03 23:21, 4F
→
03/04 01:15, , 5F
第一刀有多種切法解決就行
03/04 01:15, 5F
→
03/04 01:23, , 6F
還是有點不太懂@@
03/04 01:23, 6F
→
03/04 01:26, , 7F
4公分2段那邊, 你就想成, (a)第一刀1公分, 剩下遞迴
03/04 01:26, 7F
→
03/04 01:27, , 8F
(b)第一刀2公分, 剩下遞迴 (c)第一刀3公分, 剩下遞迴
03/04 01:27, 8F
→
03/04 01:28, , 9F
處理好一些基本的case, 放下去跑就對了, 想那麼多就不
03/04 01:28, 9F
→
03/04 01:28, , 10F
叫遞迴了呀 @_@
03/04 01:28, 10F
→
03/04 01:34, , 11F
我的遞迴觀念不是很好 可以用迴圈的方式寫嗎
03/04 01:34, 11F
推
03/04 02:10, , 12F
這個用遞迴遠比用迴圈好想
03/04 02:10, 12F
→
03/04 02:12, , 13F
說真的用遞迴下去寫你會發現莫名其妙就結束了...
03/04 02:12, 13F
→
03/04 02:13, , 14F
寫了再說吧, 至少經典河內塔先寫寫看
03/04 02:13, 14F
推
03/04 03:14, , 15F
DP
03/04 03:14, 15F
→
03/04 10:41, , 16F
典型遞迴題 @.@
03/04 10:41, 16F
推
03/04 12:11, , 17F
每個切法都可以與另一個二進位數字有一對一的對應關係
03/04 12:11, 17F
→
03/04 12:12, , 18F
所以要用迴圈的話，就從1~2^(n-1)每個數對應到切法即可
03/04 12:12, 18F
‣ 更多 andrew771027 的文章
文章代碼(AID): #1HCsYs-i (C_and_CPP)
‣ 更多 andrew771027 的文章
文章代碼(AID): #1HCsYs-i (C_and_CPP)