遞推算法
遞推法是一種重要的數學方法，在數學的各個領域中都有廣泛的運用，也是計算機用于數值計算的一個重要算法。這種算法特點是：一個問題的求解需一系列的計算，在已知條件和所求問題之間總存在着某種互相聯系的關系，在計算時，如果可以找到前後過程之間的數量關系（即遞推式），那麼，從問題出發逐漸推到已知條件，此種方法叫逆推。無論順推還是逆推，其關鍵是要找到遞推式。這種處理問題的方法能使複雜運算化為若幹步重複的簡單運算，充分發揮出計算機擅長于重複處理的特點。
遞推算法的首要問題是得到相鄰的資料項間的關系（即遞推關系）。遞推算法避開了求通項公式的麻煩，把一個複雜的問題的求解，分解成了連續的若幹步簡單運算。一般說來，可以将遞推算法看成是一種特殊的疊代算法。
例題1——數字三角形
【例2】滿足F1=F2=1，Fn=Fn-1+Fn-2的數列稱為斐波那契數列（Fibonacci），它的前若幹項是1，1，2，3，5，8，13，21，34……求此數 列第n項（n>=3）。即：f1=1 （n=1） f2=1 （n=2） fn=fn-1 + fn-2 （n>=3）
程式如下：
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int f0=1,f1=1,f2;
int n;
cin>>n;
for (int i=3; i<=n; ++i)
{
f2=f0+f1;
f0=f1;
f1=f2;
}
printf("%d\n",f2);
return 0;
} 有關Fibonacci數列，我們先來考慮一個簡單的問題：樓梯有n個台階，上樓可以一步上一階，也可以一步上兩階。一共有多少種上樓的方法？ 這是一道計數問題。在沒有思路時，不妨試着找規律。n=5時，一共有8種方法：5=1+1+1+1+15=2+1+1+15=1+2+1+15=1+1+2+15=1+1+1+25=2+2+15=2+1+25=1+2+2 其中有5種方法第1步走了1階(背景灰色)，3種方法第1步走了2階，沒有其他可能。假設f(n)為n個台階的走法總數，把n個台階的走法分成兩類。 第1類：第1步走1階，剩下還有n-1階要走，有f(n-1)種方法。 第2類：第1步走2階，剩下還有n-2階要走，有f(n-2)種方法。 這樣，就得到了遞推式：f(n)=f(n-1)+f(n-2),不要忘記邊界情況：f(1)=1,f(2)=2。把f(n)的前幾項列出：1，2，3，5，8，……。 再例如，把雌雄各一的一對新兔子放入養殖場中。每隻雌兔在出生兩個月以後，每月産雌雄各一的一對新兔子。試問第n個月後養殖場中共有多少對兔子。
還是先找找規律。 第1個月：一對新兔子r1。用小寫字母表示新兔子。 第2個月：還是一對新兔子，不過已經長大，具備生育能力了，用大寫字母R1表示。 第3個月：R1生了一對新兔子r2，一共2對。 第4個月：R1又生一對新兔子r3，一共3對。另外，r2長大了，變成R2 第5個月：R1和R2各生一對，記為r4和r5，共5對。此外，r3長成R3。 第6個月：R1、R2和R3各生一對，記為r6～r8，共8對。此外，r4和r5長大。 …… 把這些數排列起來：1，1，2，3，5，8，……，事實上，可以直接推導出來遞推關系f(n)=f(n-1)+f(n-2):第n個月的兔子由兩部分組成，一部分是上個月就有的老兔子f(n-1)，一部分是上個月出生的新兔子f(n-2)(第n-1個月時具有生育能力的兔子數就等于第n-2個月兔子總數)。根據加法原理，f(n)=f(n-1)+f(n-2)。
【例3】 有 2χn的一個長方形方格，用一個12的骨牌鋪滿方格。
編寫一個程式，試對給出的任意一個n(n>0), 輸出鋪法總數。
【算法分析】
（1）面對上述問題，如果思考方法不恰當，要想獲得問題的解答是相當困難的。可以用遞推方法歸納出問題解的一般規律。
（2）當n=1時，隻能是一種鋪法，鋪法總數有示為x1=1。
（3）當n=2時：骨牌可以兩個并列豎排，也可以并列橫排，再無其他方法，如下左圖所示，是以，鋪法總數表示為x2=2；
（4）當n=3時：骨牌可以全部豎排，也可以認為在方格中已經有一個豎排骨牌，則需要在方格中排列兩個橫排骨牌（無重複方法），若已經在方格中排列兩個橫排骨牌，則必須在方格中排列一個豎排骨牌。如上右圖，再無其他排列方法，是以鋪法總數表示為x3=3。
由此可以看出，當n=3時的排列骨牌的方法數是n=1和n=2排列方法數的和。
（5）推出一般規律：對一般的n，要求xn可以這樣來考慮，若第一個骨牌是豎排列放置，剩下有n-1個骨牌需要排列，這時排列方法數為xn-1；若第一個骨牌是橫排列，整個方格至少有2個骨牌是橫排列（12骨牌），是以剩下n-2個骨牌需要排列，這是骨牌排列方法數為xn-2。從第一骨牌排列方法考慮，隻有這兩種可能，是以有：
xn=xn-1+xn-2 （n>2）
x1=1
x2=2
xn=xn-1+xn-2就是問題求解的遞推公式。任給n都可以從中獲得解答。例如n=5，
x3=x2+x1=3
x4=x3+x2=5
x5=x4+x3=8
下面是輸入n，輸出x1~xn的c++程式：
#include<iostream>
using namespace std;
int main()
{
int n,i,j,a[101];
cout<<"input n:"; //輸入骨牌數
cin>>n;
a[1]=1;a[2]=2;
cout<<"x[1]="<<a[1]<<endl;
cout<<"x[2]="<<a[2]<<endl;
for (i=3;i<=n;i++) //遞推過程
{
a[i]=a[i-1]+a[i-2];
cout<<"x["<<i<<"]="<<a[i]<<endl;
}
}
下面是運作程式輸入 n=30，輸出的結果：
input n: 30
x[1]=1
x[2]=2
x[3]=3
........
x[29]=832040
x[30]=1346269
問題的結果就是有名的斐波那契數。 【例4】昆蟲繁殖
【問題描述】
科學家在熱帶森林中發現了一種特殊的昆蟲，這種昆蟲的繁殖能力很強。每對成蟲過x個月産y對卵，每對卵要過兩個月長成成蟲。假設每個成蟲不死，第一個月隻有一對成蟲，且卵長成成蟲後的第一個月不産卵(過X個月産卵)，問過Z個月以後，共有成蟲多少對？0=<X<=20,1<=Y<=20,X=<Z<=50
【輸入格式】
x,y,z的數值
【輸出格式】
過Z個月以後，共有成蟲對數
【輸入樣例】
1 2 8
【輸出樣例】
37
【參考程式】
#include<iostream>
using namespace std;
int main()
{
long long a[101]={0},b[101]={0},i,j,x,y,z;
cin>>x>>y>>z;
for(i=1;i<=x;i++){a[i]=1;b[i]=0;}
for(i=x+1;i<=z+1;i++) //因為要統計到第z個月後，是以要for到z+1
{
b[i]=y*a[i-x];
a[i]=a[i-1]+b[i-2];
}
cout<<a[z+1]<<endl;
return 0;
}
【例5】位數問題
【問題描述】
在所有的N位數中，有多少個數中有偶數個數字3？由于結果可能很大，你隻需要輸出這個答案對12345取餘的值。
【輸入格式】
讀入一個數N
【輸出格式】
輸出有多少個數中有偶數個數字3。
【輸入樣例】
2
【輸出樣例】
73
【資料規模】
1<=N<=1000
【樣例說明】
在所有的2位數字，包含0個3的數有72個，包含2個3的數有1個，共73個
【算法分析】
方法一：排列組合(但需要運用動态規劃)。
可以列出公式,在n個格子中放x個3(其中x為偶數,包括0).。
c(n,x)*9(n-x)-c(n-1,x)*9(n-x-1) 含義為在n個格子中取x個3,且不考慮第一位的特殊情況為c(n,x)*9^(n-x)。
而第一位為0的情況,為c(n-1,x)*9^(n-x-1),兩者減下,就為答案。
方法二：遞推
考慮這種題目,一般來說都是從第i-1位推導第i位,且目前位是取偶數還是取奇數的。
恍然大悟.可以用f[i][0]表示前i位取偶數個3有幾種情況,f[i][1]表示前i位取奇數個3有幾種情況。
則狀态轉移方程可以表示為:
f[i][0]=f[i-1][0]*9+f[i-1][1];f[i][1]=f[i-1][0]+f[i-1][1]*9;
邊界條件:f[1][1]=1;f[1][0]=9;
【參考程式】
#include<iostream>
using namespace std;
int main()
{
int f[1001][2],n,i,x;
cin>>n;
f[1][1]=1;f[1][0]=9;
for(i=2;i<=n;i++)
{
x=f[1][0];
if(i==n)x--;
f[i][0]=(f[i-1][0]*x+f[i-1][1])%12345;
f[i][1]=(f[i-1][1]*x+f[i-1][0])%12345;
}
cout<<f[n][0];
return 0;
} 【例6】過河卒（Noip2002）
【問題描述】
棋盤上A點有一個過河卒，需要走到目标B點。卒行走的規則：可以向下、或者向右。同時在棋盤上的任一點有一個對方的馬（如C點），該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點，如圖3-1中的C點和P1，……，P8，卒不能通過對方馬的控制點。棋盤用坐标表示，A點(0,0)、B點(n, m) (n,m為不超過20的整數),同樣馬的位置坐标是需要給出的，C≠A且C≠B。現在要求你計算出卒從A點能夠到達B點的路徑的條數。
【算法分析】
跳馬是一道老得不能再老的題目，我想每位程式設計初學者都學過，可能是在學回溯或搜尋等算法的時候，很多書上也有類似的題目，一些比賽中也出現過這一問題的變形（如NOIP1997國中組的第三題）。有些同學一看到這條題目就去搜尋，即使你程式設計調試全通過了，運作時你也會發現：當n,m=15就會逾時。
其實，本題稍加分析就能發現，要到達棋盤上的一個點，隻能從左邊過來（我們稱之為左點）或是從上面過來（我們稱之為上點），是以根據加法原理，到達某一點的路徑數目，就等于到達其相鄰的上點和左點的路徑數目之和，是以我們可以使用逐列（或逐行）遞推的方法來求出從起點到終點的路徑數目。障礙點（馬的控制點）也完全适用，隻要将到達該點的路徑數目設定為0即可。
用F[i][j]表示到達點(i,j)的路徑數目，g[i][j]表示點(i, j)有無障礙，g[i][j]=0表示無障礙，g[i][j]=1表示有障礙。
則，遞推關系式如下：
F[i][j] = F[i-1][j] + F[i][j-1] //i>0且j>0且g[i][j]= 0
遞推邊界有4個：
F[i][j] = 0 //g[i][j] = 1
F[i][0] = F[i-1][0] //i > 0且g[i][0] = 0
F[0][j] = F[0][j-1] //j > 0且g[0][j] = 0