Re: [問題] 重複組合遞迴演算法
※ 引述《alfadick (悟道修行者)》之銘言：
: 不是作業，是解 project euler problem 31 時遇到的
: https://projecteuler.net/problem=31
: 我感覺是重複組合的問題。
: 我想強迫自己用遞迴寫，來練習遞迴的思考方式，但寫到卡住..。
: 我感覺用遞迴似乎可以不用flag來記錄執行狀態
: 有什麼SOP嗎這種題目...
像這樣的題目,
可以說是找出怎樣data的組合為解,
每一個data組合,我們可以視為一個state,
簡單說就是找出那一個state或那一些state為解.
剛起步練習的時候,可以試著用紙筆列出每一個state,
如果state太多無法全部列舉,可以試著列某一個範圍就好,
目的在於觀察找出規律.
找規律有幾個要件,
首是分析如何從某一個state轉移到另一個state,
然後是找起點和邊界.
再來是如何走過每一個state.
舉例一個題目:
1到1000之間,有幾個質數?
我們從小到大的經驗來看,
1到1000之間可以想都不用想就知到總共有1000個不同的state,
如果題目稍變化一下,
1到1000之間是指9進位,或13進位這種不常見的命題,
總共有幾個state那可能要想一下了.
話說回來,
首先來看如何從某一個state跳到另一個state,
直覺上來看也很簡單,直接值加上1就好,
透過不斷加1,就可以走過從1到1000之間的所有state,
其實方法不見得只有一條路,
例如說0010透過加10來跳到0020,
換句話說0010跟0020之間有一條路可以一步轉移,
不用經過11,12,...,19.
所以可以想像成
在某一個空間分佈著有許許多多state,
而這些state之間各自就像網路相連,
而我們就像是在這網路中走訪來找出解.
至於怎麼找,有些就是學問了,比如說還有效率高低問題.
其實某些很多演算法就是介紹不同的走訪方式來針對題目求解.
而原po的題目算是比較好分析的,
比如說起點是 0, 0, 0, 0, 0, 0, 0 七個coin,
然後邊界是
0, 0, 0, 0, 0, 0, 200
0, 0, 0, 0, 0, 100, 0
...
1, 0, 0, 0, 0, 0, 0
然後走訪方式如果可以的話
從 0, 0, 0, 0, 0, 0, 0 開始
我想用"+1"這個方法走訪每一個state,
如果可以的話這個方法再多加幾個判斷式
讓我可以
0, 0, 0, 0, 0, 0, 200 跳到 0, 0, 0, 0, 0, 1, 0
而且
0, 0, 0, 0, 0, 100, 200 跳到 0, 0, 0, 0, 1, 0, 0 ..
...以此類推
假設找到這方法,
那就可以像1到1000一樣用一個loop就可解決了.
假設找不到這條路,
那也可以考慮用7層loop也能解.
recursive也是走訪的選擇之一,
只是與loop特性不太相同,
有些情況會比loop好寫, 也有些情況比loop吃效能,
看自己取捨.
在這題
概念上我舉例其中一種純recursive走法:
find ( a, b, c, d, e, f, g )
{
如果全部總和 剛好 200
記錄並離開
如果全部總和 超過 200
離開
find ( a+1, b, c, d, e, f, g );
find ( a, b+1, c, d, e, f, g );
find ( a, b, c+1, d, e, f, g );
find ( a, b, c, d+1, e, f, g );
find ( a, b, c, d, e+1, f, g );
find ( a, b, c, d, e, f+1, g );
find ( a, b, c, d, e, f, g+1 );
}
main()
{
find( 0, 0, 0, 0, 0, 0 ,0 );
}
像這樣就是起點為 0, 0, 0, 0, 0, 0 ,0
邊界判斷是每到一個state都會做的事.
不是邊界的話就繼續走,
然後每一個state因為有7種硬幣所以有7條路出去,
recursive特性就是其中1條路走完會"回到這個state",
簡而言之就是一種渾然天成的state記錄法,
(現在大多數程式語言的原理背後都符合某種state記錄)
接著下一行也是一條recursive方法,
但是用不同的參數轉移方式來走到另一個state.
然後根據每個人的分析能力和角度不同,
也有可能loop跟recursive混用.
看個人取捨,重點在於能否找到路.
如果是某段樹狀的分佈,
意思是說走到某個地方沒有路必須"倒退嚕"才能走別條路的,
就會建議用recursive.
(不用recursive的寫法話就可用自製的stack來記錄state,只是可能比較麻煩)
另外一個議題就是走訪效率,
其中一個方法就是"少走冤枉路",
有種說法就是state修剪,
例如:
如果全部總和 剛好 200
記錄"並離開"
後面的"並離開"可以不寫,也會正確找到解.
只是會多走7個state.
再一個修剪的例子:
find ( a, b, c, d, e, f )
{
如果全部總和 剛好 200
記錄並離開
如果全部總和 超過 200
離開
用 g(1p) 把不足 200 的部分補齊, 並記錄
find ( a+1, b, c, d, e, f );
find ( a, b+1, c, d, e, f );
find ( a, b, c+1, d, e, f );
find ( a, b, c, d+1, e, f );
find ( a, b, c, d, e+1, f );
find ( a, b, c, d, e, f+1 );
}
這樣就可以少走很多路.
總之方法掌握在個人,
不做任何修剪也可以說是暴力法,
但解題不見得要求效率, 總之是先求有再求好,
個人是建議有了基本解題能力再慢慢去累積各種演算法例子.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.34.80.4
※ 文章網址: http://www.ptt.cc/bbs/C_and_CPP/M.1409725422.A.68F.html
推
09/03 15:02, , 1F
09/03 15:02, 1F
討論串 (同標題文章)