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

[andrew771027 (老柏~)]

開發平台(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
→ CaptainH:4 => 4 , 1+3, 2+2, 3+1
→ CaptainH:5 => 5, 1+4, 2+3, 3+2, 4+1
→ CaptainH:長度n公分的布第一刀切 k 公分, 那剩下的就有 n-k 公分
→ CaptainH:兩部份各自遞迴處理就ok了
→ loveme00835:第一刀有多種切法解決就行
→ andrew771027:還是有點不太懂@@
→ loveme00835:4公分2段那邊, 你就想成, (a)第一刀1公分, 剩下遞迴
→ loveme00835:(b)第一刀2公分, 剩下遞迴 (c)第一刀3公分, 剩下遞迴
→ loveme00835:處理好一些基本的case, 放下去跑就對了, 想那麼多就不
→ loveme00835:叫遞迴了呀 @_@
→ andrew771027:我的遞迴觀念不是很好 可以用迴圈的方式寫嗎
推 suhorng:這個用遞迴遠比用迴圈好想
→ loveme00835:說真的用遞迴下去寫你會發現莫名其妙就結束了...
→ loveme00835:寫了再說吧, 至少經典河內塔先寫寫看
推 wtvwtvwtv200:DP
→ shadow0326:典型遞迴題 @.@
推 littleshan:每個切法都可以與另一個二進位數字有一對一的對應關係
→ littleshan:所以要用迴圈的話，就從1~2^(n-1)每個數對應到切法即可