遞推的計算方法

A. 遞推法的一般步驟

所謂遞推關系，通鏈絕培常是指一個數列》的第項a與前面k個項a,a…annn=n2nk
(k為正整數，kn)之間的關系：
an=f(an1,an_2;",an_k)(n>k)

遞推法也常用以處理棚唯正整數為狀宏雀態函數的數學問題，諸如遞歸數列的通項問題，與數列有關的計算問題，證明問題，等等，應用遞推法解答數學問題，一般包括兩個步驟：

第一步：建立遞推關系，根據問題的特點，通過觀察，試驗，歸納，猜想等思維活動，尋求遞推關系
第二步：求遞推關系初始值和相應的遞推關系，求得所需的結論
例1：計算兩類帶組合數C和Ck的器和Shd=ZCAkm，Un(n)=ZCnkm

B. 常見演算法思想2：遞推法

遞推演算法猶如穩重的有經驗的老將，使用「穩扎穩打」的策略，不斷利用已有的信息推導出新的東西。
在日常應用中有如下兩種遞推演算法：
（1）順推法：從已知條件出發，逐步推算出要解決問題的方法。
（2）逆推法：從已知的結果出發，用迭代表達式逐步推算出問題開始的條件，即順推法的逆過程。

例如斐波那契數列就可以通過順推法不斷遞推算出新的數據：

分析:我們要想辦法找規律
兔子對數：
第一個月：1；第二個月:1；第三個月: 2；第四個月: 3；第五個月: 5；第六個月: 8；...
由此可見兔子的對象數據是:1,1,2,3,5,8...

規則:
A:從第三項開始,每一項是前兩項之程
B:而且說明前兩項是已知的

假如相鄰的兩個月的兔子對數是a,b
第一個相鄰的數據:a=1,b=1
第二個相鄰的數據:a=1,b=2
第三個相鄰的數據:a=2,b=3
第四個相鄰的數據:a=3,b=5
看到了:下一次的a是以前的b,下一次的b是以前的a+b;

可採用逆推法分析存錢和取錢的過程，因為按照月為周期取錢，所以4年可以分為48個月，並對每個月進行計算。
如果第48個月後sun大學畢業連本帶息要取1000元，則要求第47個月銀行的存錢金額為：
第47個月月末存款=1000/(1+0.0172/12);
第46個月月末存款=（第47存款+1000）/(1+0.0172/12);
第45月末存款=（第46存款+1000）/(1+0.0172/12);
…….
第2月月末存款=（第3月月末存款+1000）/(1+0.0172/12);
第1月月末存款=（第2月末存款+1000）/(1+0.0172/12);

列印結果：

C. 遞推演算法是怎麼回事

遞推定義
遞推演算法是一種簡單的演算法，即通過已知條件，利用特定關系得出中間推論，直至得到結果的演算法。

遞推演算法分為順推和逆推兩種。

順推法
所謂順推法是從已知條件出發，逐步推算出要解決的問題的方法叫順推。

如斐波拉契數列，設它的函數為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(n)=n*f(n-1)

在f(3)的運算過程中,遞歸的數據流動過程如下:

f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}

而遞推如下:

f(0)-->f(1)-->f(2)-->f(3)

由此可見,遞推的效率要高一些,在可能的情況下應盡量使用遞推.但是遞歸作為比較基礎的演算法,它的作用不能忽視.所以,在把握這兩種演算法的時候應該特別注意.

D. 數列的遞推公式

數列的遞進公式，如下所示：

數列的遞推公式=n/n+1。如果一個數列的第n項an與該數列的其他一項或多項之間存在對應關系的，這個關系就稱為該數列的遞推公式。例如斐波納契數列的遞推公式為 an=an-1+an-2。

等差數列遞推公式：an=d(n-1)+a（d為公差，a為首項）。

等比數列遞推公式：bn=q(n-1)*b （q為公比 b為首項）。

由遞推公式寫出數列的擾世方法：

1. 根據遞推公式寫出數列的前幾項，依次代入計算即可。

2.若知道的是末項，通常將所給公式整理成用後面的項表示前面的項的形式。

數列的含義：

數列是以正整數集或它的有限子集為定義域的函數，是一列有序的數。數列中的每一個數都叫做這個數列的項。排在第一位的數稱為這個數列的第1項，通常也叫喊罩做首項，排在第二位的數稱為這個數列的第2項，以此類推，排在第n位的數稱為鄭李鬧這個數列的第n項，通常用an表示。

E. 數列遞推演算法的原理

什麼是遞推
所謂遞推，是指從已知的初始條件出發，依據某種遞推關系，逐次推出所要求的各中間結果及最後結果。其中初始條件或是問題本身已經給定，或是通過對問題的分析與化簡後確定。
從已知條件出發逐步推到問題結果，此種方法叫順推。
從問題出發逐步推到已知條件，此種方法叫逆推。
無論順推還是逆推，其關鍵是要找到遞推式。這種處理問題的方法能使復雜運算化為若干步重復的簡單運算，充分發揮出計算機擅長於重復處理的特點。
遞推法是一種重要的數學方法，在數學的各個領域中都有廣泛的運用，也是計算機用於數值計算的一個重要演算法。
遞推演算法的首要問題是得到相鄰的數據項間的關系（即遞推關系）。遞推演算法避開了求通項公式的麻煩，把一個復雜的問題的求解，分解成了連續的若干步簡單運算。一般說來，可以將遞推演算法看成是一種特殊的迭代演算法。

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

【例1】數字三角形。
如下所示為一個數字三角形。請編一個程序計算從頂到底的某處的一條路徑，使該路徑所經過的數字總和最大。只要求輸出總和。

1、 一步可沿左斜線向下或右斜線向下走；
2、 三角形行數小於等於100；
3、 三角形中的數字為0，1，…，99；
測試數據通過鍵盤逐行輸入，如上例數據應以如下所示格式輸入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
【演算法分析】
此題解法有多種，從遞推的思想出發，設想，當從頂層沿某條路徑走到第i層向第i+1層前進時，我們的選擇一定是沿其下兩條可行路徑中最大數字的方向前進，為此，我們可以採用倒推的手法，設a[i][j]存放從i,j 出發到達n層的最大值，則a[i][j]=max{a[i][j]+a[i+1][j]，a[i][j]+a[i+1][j+1]}，a[1][1] 即為所求的數字總和的最大值。

//【參考程序】
#include<iostream>
using namespace std;
int main(){
int n,i,j,a[101][101];
cin>>n;
for (i=1;i<=n;i++)
for (j=1;j<=i;j++)
cin>>a[i][j]; //輸入數字三角形的值
for (i=n-1;i>=1;i--)
for (j=1;j<=i;j++)
{
if (a[i+1][j]>=a[i+1][j+1]) a[i][j]+=a[i+1][j]; //路徑選擇
else a[i][j]+=a[i+1][j+1];
}
cout<<a[1][1]<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
思考
如果要輸出最大和的路徑該怎麼處理呢？

【例2】 骨牌問題
有2 × n的一個長方形方格，用一個1 × 2的骨牌鋪滿方格。
編寫一個程序，試對給出的任意一個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排列方法數的和

F. 什麼是遞推公式

如果數列{an}的第n項與它前一項或幾項的關系可以用一個式子來表示，那麼這個公式叫做這個數列仿笑的遞推公式。

例如斐波納契數列的遞推公式為an=an-1+an-2

由遞推公高宴式寫出數列的方法：

1、根據遞推公式寫出數列的前幾項，依次代入計算即可；

2、若知道的是末項，通常將所給公式整理成用後面的項表示前面的項的形式。

(6)遞推的計算方法擴展閱讀

常見的遞推公式，如等差數列。

等差數列從第二項開始每一項是前項和後項的算術平均數。

如果等差數列的公差是正數，則該等戚大銀差數列是遞增數列；如果等差數列的公差是負數，則該數列是遞減數列；如果等差數列的公差等於零，則該數列是常數列。

對於一個數列al，a2，…，an，…，如果它的相鄰兩項之差a2-a1，a3-a2，…，an+1-an，…構成公差不為零的等差數列，則稱數列{an}為二階等差數列。

運用遞歸的方法可以依次定義各階等差數列：對於數列{an}，如果{an+1-an}是r階等差數列，則稱數列{an}是r+1階等差數列.二階或二階以上的等差數列稱為高階等差數列。

G. 怎樣用遞推法計算行列式

遞推法,主要針對帶形行列式，例如上面這個行列式的通用解法：

H. 遞推的遞推演算法

【例1】
植樹節那天，有五位同學參加了植樹活動，他們完成植樹的棵樹都不相同。問第一位同學植了多少棵時，他指著旁邊的第二位同學說比他多植了兩棵；追問第二位同學，他又說比第三位同學多植了兩棵；... 如此，都說比另一位同學多植兩棵。最後問到第五位同學時，他說自己植了10棵。到底第一位同學植了多少棵樹？
分析：設第一位同學植樹的棵樹為a1,欲求a1，需從第五位同學植樹的棵數a5入手，根據「多兩棵」這個規律，按照一定順序逐步進行推算：
(1) a5=10;
(2) a4=a5+2=12;
(3) a3=a4+2=14;
(4) a2=a3+2=16;
(5) a1=a2+2=18;
Pascal程序：
Program Examl;
Var i,a:byte;
begin
a:=10;
for i:= 1 to 4 do
a:=a+2;
writeln('The Num is' ,a);
readln;
end.
本程序的遞推運算可用下圖示表示：
初始值a:=10 ----- i=1,a=a+2(12) ----- i=2,a=a+2(14) ------ i=3,a=a+2(16) ----- i=4,a=a+2(18) ---- 輸出a值
例2：
十本不同的書放在書架上。現重新擺拍渣唯放，使每本書都不在原來放的梁辯位置。有幾種擺法？
當n個編號元素放在n個編號位置,元素編號與位置編號各不對應的方法數襲培用M(n)表示,那麼M(n-1)就表示n-1個編號元素放在n-1個編號位置,各不對應的方法數,其它類推.
第一步,把第n個元素放在一個位置,比如位置k,一共有n-1種方法;
第二步,放編號為k的元素,這時有兩種情況.1,把它放到位置n,那麼,對於剩下的n-2個元素,就有M(n-2)種方法;2,不把它放到位置n,這時,對於這n-1個元素,有M(n-1)種方法;
綜上得到
M(n)=(n-1)[M(n-2)+M(n-1)]
遞推演算法以初始（起點）值為基礎，用相同的運算規律，逐次重復運算，直至運算結束。這種從「起點」重復相同的方法直至到達一定「邊界」，猶如單向運動，用循環可以實現。遞推的本質是按規律逐次推出（計算）先一步的結果。