遞推（一）：遞推法的基本思想

? ? ? 所謂遞推，是指從已知的初始條件出發，依據某種遞推關系，逐次推出所要求的各中間結果及最后結果。其中初始條件或是問題本身已經給定，或是通過對問題的分析與化簡后確定。

? ? ? 利用遞推算法求問題規模為n的解的基本思想是：當n=1時，解或為已知，或能非常方便地求得；通過采用遞推法構造算法的遞推性質，能從已求得的規模為1、2、…、i?1的一系列解，構造出問題規模為i的解。這樣，程序可從i=0或i=1出發，重復地由已知至i?1規模的解，通過遞推，獲得規模為i的解，直至獲得規模為n的解。

? ? ? 可用遞推算法求解的問題一般有以下兩個特點：（1）問題可以劃分成多個狀態；（2）除初始狀態外，其它各個狀態都可以用固定的遞推關系式來表示。當然，在實際問題中，大多數時候不會直接給出遞推關系式，而是需要通過分析各種狀態，找出遞推關系式。

? ? ? 利用遞推算法解決問題，需要做好以下四個方面的工作：

? ? ? （1）確定遞推變量

? ? ? 應用遞推算法解決問題，要根據問題的具體實際設置遞推變量。遞推變量可以是簡單變量，也可以是一維或多維數組。從直觀角度出發，通常采用一維數組。

? ? ? （2）建立遞推關系

? ? ? ?遞推關系是指如何從變量的前一些值推出其下一個值，或從變量的后一些值推出其上一個值的公式（或關系）。遞推關系是遞推的依據，是解決遞推問題的關鍵。有些問題，其遞推關系是明確的，大多數實際問題并沒有現成的明確的遞推關系，需根據問題的具體實際，通過分析和推理，才能確定問題的遞推關系。

? ? ? ?（3）確定初始（邊界）條件

? ? ? ?對所確定的遞推變量，要根據問題最簡單情形的數據確定遞推變量的初始（邊界）值，這是遞推的基礎。

? ? ? （4）對遞推過程進行控制

? ? ? 遞推過程不能無休止地重復執行下去。遞推過程在什么時候結束，滿足什么條件結束，這是編寫遞推算法必須考慮的問題。

? ? ? ?遞推過程的控制通常可分為兩種情形：一種是所需的遞推次數是確定的值，可以計算出來；另一種是所需的遞推次數無法確定。對于前一種情況，可以構建一個固定次數的循環來實現對遞推過程的控制；對于后一種情況，需要進一步分析出用來結束遞推過程的條件。

? ? ? ?遞推通常由循環來實現，一般在循環外確定初始（邊界）條件，在循環中實施遞推。

? ? ? ?遞推法從遞推方向可分為順推與倒推。

? ? ? ?所謂順推法是從已知條件出發，通過遞推關系逐步推算出要解決的問題的結果的方法。如求斐波拉契數列的第20項的值，設斐波拉契數列的第n項的為f(n)，已知f(1)=1，f(2)=1；通過遞推關系式f(n)=f(n-2)+f(n-1) （n>=3，n∈N），可以順推出f(3)=f(1)+f(2)=2、f(4)=f(2)+f(3)=3、…直至要求的解f(20)=f(18)+f(19)=6765。

? ? ? 所謂倒推法，就是在不知初始值的情況下，經某種遞推關系而獲知了問題的解或目標，從這個解或目標出發，采用倒推手段，一步步地倒推到這個問題的初始情況。

? ? ? 一句話概括：順推是從條件推出結果，倒推從結果推出條件。

? ? ? ?順推法是從前往后推，從已求得的規模為1、2、…、i?1的一系列解，推出問題規模為i的解，直至得到規模為n的解。順推算法可描述為：

for (k=1; k<=i?1; k++)

? ? ?f[k]= <初始值>；??????? ?????? // 按初始條件，確定初始值

for (k=i; k<=n; k++)

??? f[k]= <遞推關系式>；? ???? // 根據遞推關系實施遞推

cout<<f[n]；?????????????? ??? // 輸出n規模的解f(n)

? ? ? ?倒推法是從后往前推，從已求得的規模為n、n?1、…、i+1的一系列解，推出問題規模為i的解，直至得到規模為1的解（即初始情況）。倒推算法可描述為：

for (k=n; k>=i+1; k--)

? ? ?f[k]= <初始值>；??????? ?????? // 按初始條件，確定初始值

for (k=i; k>=1; k--)

??? f[k]= <遞推關系式>；? ???? // 根據遞推關系實施遞推

cout<<f[1]；?????????????? ??? // 輸出問題的初始情況f(1)

? ? ? ?遞推問題一般定義一維數組來保存各項推算結果，較復雜的遞推問題還需定義二維數組。例如，當規模為i的解為規模為1、2、…、i?1的解通過計算處理決定時，可利用二重循環處理這一較為復雜的遞推。

【例1】RPG涂色問題

? ? ? 有排成一行的n個方格，用紅（Red）、粉（Pink）、綠（Green）三種顏色涂每個格子，每個格子涂一種色，要求任何相鄰的方格不能同色，且首尾兩格也不同色。

? ? ? 編寫一個程序，輸入方格數n（0<n<=30），輸出滿足要求的全部涂法的種數。

? ? ? （1）編程思路

? ? ? 設滿足要求的n個方格的涂色方法數為F(n)。

? ? ? 因為RPG有三種顏色，可以先枚舉出當方格數為1、2、3時的涂法種數。

? ? ? 顯然，? ? ?F(1)=3 ??（即R、P、G三種）

????? F(2)=6? ?（即RP、RG、PR、PG、GR、GP六種）

????? F(3)=6?? （即RPG、RGP、PRG、PGR、GRP、GPR六種）

? ? ? 當方格的個數大于3時，n個方格的涂色方案可以由n-1方格的涂色方案追加最后一個方格的涂色方案得出，分兩種情況：

? ? ? 1）對于已按要求涂好顏色的n-1個方格，在F(n-1)種合法的涂色方案后追加一個方格（第n個方格），由于合法方案的首尾顏色不同（即第n-1個方格的顏色不與第1個方格的相同），這樣，第n個方格的顏色也是確定的，它必定是原n-1個方格的首尾兩種顏色之外的一種，因此，在這種情況下的涂色方法數為F(n-1)。

? ? ? 2）對于已按要求涂好顏色的n-2個方格，可以在第n-1個方格中涂與第1個方格相同的顏色，此時由于首尾顏色相同，這是不合法的涂色方案，但可以在第n個方格中涂上一個合法的顏色，使其成為方格長度為n的合法涂色方案（注意：當n等于3時，由于第1(3-2)個方格與第2(3-1)個方格顏色相同，第3個方格不論怎樣涂都不會合法，因此遞推的前提是n大于3），在第n個方格中可以涂上兩種顏色（即首格外的兩種顏色，因為與它相連的第n-1個方格和第1個方格的顏色是一樣的），因此，在這種情況下的涂色方法數為2*F(n-2)。

由此，可得遞推公式：F(n)= F(n-1) + 2*F(n-2)? (n>=4)

程序中定義3個變量f1、f2和f3分別表示F (n-2)、F(n-1)和F(n)，初始時f1=6、f2=6。

當n<4時，根據初始情況直接輸出結果。

當n>=4時，用循環遞推計算F(n)。程序段描述為：

??? for(i=4;i<=n;i++)

??? {

??????? f3=f1+f2;????????? // 計算當前F(i)

??????? f1=f2;?? f2=f3;??? // 為下一次遞推做準備

??? }

? ? ? （2）源程序及運行結果

#include <iostream>

using namespace std;