Iterative Method / Recursive Method

Iterative Method

「疊代法」。以確定的部分作為起始點,循序漸進推演,最後求得答案。

「疊代法」也會有無窮無盡的情況,例如以試除法建立質數,質數是越建越多;又例如微積分所學的牛頓法,遇到曲線時,小數位數是越算越多。

寫程式時經常以迴圈來實作。因為迴圈事實上也可以用遞迴來完成,所以讀者也可以利用遞迴來實作,只不過我想大家沒必要這麼無聊。

Recursive Method

「遞歸法」。找出一套縮小問題範疇的規律,以此不斷縮小問題,直到能釐清細節,便可歸納答案。

「遞歸法」也會有無窮無盡的情況,例如碎形是越分越細緻。

寫程式時主要以遞迴來實作。因為遞迴也可以用stack和迴圈來完成,所以讀者也可以利用迴圈來實作,只不過我想大家沒必要這麼累。

UVa 10994 10212 10471 10922

比較Iterative Method與Recursive Method

Iterative Method 與Recursive Method有種對立的味道:Iterative Method是針對已知,逐步累積,直至周全;Recursive是針對未知,反覆拆解,直至精細。

Collatz Conjecture

Collatz Conjecture

就是俗稱的「3n+1問題」,至今尚未有人能證明其正確性。有趣的是,目前也尚未檢查出任何反例。

Iterative Method,用迴圈實作。

只要一步一步地計算,最後便能解出答案來。

Iterative Method,將迴圈改為遞迴。

仍舊是一步一步地計算,但改為遞迴呼叫下一步,可說是吃飽太閒。

Recursive Method

將問題反覆拆解成更小的問題。在Collatz Conjecture中,數字會逐步收斂──這也就是說,數字經過除以二、乘以三再加一的計算後,問題範疇就會縮小。在這裡,我們讓數字做了一次的計算,來縮小問題。

討論

如果就演算法的設計策略來看,這些程式碼使用了不同的策略:前面兩支程式是Iterative Method、後面一支是Recursive Method。

但以實作的角度來看,這些程式碼卻又重新分為兩種樣式:前面一支程式是迴圈、後面兩支是長得差不多的遞迴。

以後面兩支程式來看,或許有人會覺得第二支的遞迴程式碼寫的不漂亮,只要改寫一下就是第三支的簡潔程式了。然而第二支程式和第三支程式,他們的設計理念是截然不同的。

由此可知,只是粗淺地閱讀程式碼,不見得就能夠了解整個解題思路的。設計方法(解題方法)和實作方式,這兩件事得好好的分辨清楚呀!

閒聊

這些程式都還可以再改進,讓執行效率變得更好。各位自行發揮創意吧!

另外,這個問題亦可歸類於是簡單的Simulation問題。

以下是我找到的相關類題:

UVa 100 371 694

Stairs Climbing

爬樓梯

這裡介紹一個知名的爬樓梯問題:眼前有五階樓梯,每次可踏上一階或踏上兩階,那麼爬完五階共有幾種踏法?例如(1,1,1,1,1)是其中一種踏法,(1,2,1,1)是另一種不同的踏法。

Iterative Method

我們先試著只爬少少的幾階樓梯,觀察一下踏法。

爬完一階的踏法很明顯的只有一種:(1)。

至於爬完兩階的踏法有兩種:(1,1)和(2)。

至於爬完三階的踏法:因為一次只能往上踏一階或兩階,所以只可能從第一階或從第二階踏上第三階。只要將(爬完一階的踏法,1),再綜合(爬完兩階的踏法,2),就是爬完三階的踏法。至於踏法種類數可直接相加求得。

同理,只要將(爬完兩階的踏法,1),再綜合(爬完三階的踏法,2),就是爬完四階的踏法。至於踏法種類數可直接相加求得。

迭代下去,就可求出爬完五階的踏法種類。

Recursive Method

我們由踏出的最後一步開始分析。

要「爬完五階」,最後一步一定是踏上第五階。要踏上第五階,只可能從第四階和第三階踏過來,也就是(爬完四階的踏法,1),再綜合(爬完三階的踏法,2)。至於踏法種類數可直接相加求得。

但是我們不知道如何「爬完四階」和「爬完三階」,所以只好再分別研究「爬完四階」與「爬完三階」,反正它們一定又是由更之前的樓梯踏過來。只要不斷追究下去,問題必會漸漸簡單明朗,總有一天會撥雲見日。

追究到「爬完一階」與「爬完兩階」的時候,已經可以確認答案了。現在「爬完五階」的踏法種類也就清楚了!