遞推算法
給定一個數的序列H0,H1,…,Hn,…若存在整數n0，使當n>n0時,可以用等号(或大于号、小于号)将Hn與其前面的某些項Hi(0
遞推算法是一種簡單的算法，即通過已知條件，利用特定關系得出中間推論，直至得到結果的算法。
遞推算法分為順推和逆推兩種。
相對于遞歸算法,遞推算法免除了資料進出棧的過程，也就是說,不需要函數不斷的向邊界值靠攏,而直接從邊界出發,直到求出函數值.
比如階乘函數：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)
由此可見,遞推的效率要高一些,在可能的情況下應盡量使用遞推.但是遞歸作為比較基礎的算法,它的作用不能忽視.是以,在把握這兩種算法的時候應該特别注意。
順推法
所謂順推法是從已知條件出發，逐漸推算出要解決的問題的方法叫順推。
如斐波拉契數列，設它的函數為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……直至我們要求的解。
逆推法
所謂逆推法從已知問題的結果出發，用疊代表達式逐漸推算出問題的開始的條件，即順推法的逆過程，稱為逆推。
遞推算法的經典例子
【案例】從原點出發，一步隻能向右走、向上走或向左走。恰好走N步且不經過已走的點共有多少種走法？
樣例輸入：N=2
樣例輸出：result=7
樣例輸入：N=3
樣例輸出：result=17
解題思路：要解決走N步共有多少種走法，我們在拿到題目的時候最直接的想法就是先畫出當N=1、N=2、N=3。。。。。N=n時對應走法的圖例，由簡單到複雜、由特殊到一般的推理過程，找出規律獲得解題的思路。在數學上，我們稱為歸納法。如果用程式設計的方法來求解這樣的推理題，我們把這樣的求解思路(算法)稱之為遞推法。遞推的精髓在于f(n)的結果一般由f(n-1)、f(n-2)…..f(n-k)的前k次結果推導出來。我們在解決這類遞推問題時，難點就是如何從簡單而特殊的案例，找到問題的一般規律，寫出f(n)與f(n-1)、f(n-2)…..f(n-k)之間的關系表達式，進而得出求解的結果。在曆年noip的複賽當中，參賽選手對于這類題目都有這樣的感受，往往花費了大量的時間來分析題目的一般規律，寫出f(n)的一般表達式，而程式設計實作可能隻需要幾分鐘的時間。是以我們在平時訓練的時候，對于這樣的遞推題目，就必須掌握如何分析問題，從特殊推導出一般的規律，寫出想要的關系表達式，問題就迎刃而解了。
有一點需要補充的就是，任何遞推題，都會有臨界條件。當N=1時，f(n)=3;,當N=2時，f(n)=7,這些都可以看成是臨界條件。隻有當N>=3時，即上上步存在的情況下，就可以得出f(n)的一般通式：f(n)=2*f(n-1)+f(n-2)
【參考程式】
#include
#include
int main()
{
int n;
int i;
int fn_1,fn_2;
printf("please input n=");
scanf("%d",&n); //輸入任意n值
int fn=0;
if(n==1)
fn=3; //初始化當n=1和n=2時的臨界條件
else if(n==2)
fn=7;
else{
fn_1=7;
fn_2=3;
for(i=3;i<=n;i++)
{
fn=2*fn_1+fn_2; //當n>=3時fn的通式
fn_2=fn_1;//更新fn_1和fn_2的值
fn_1=fn;
}
}
printf("一共有%d種走法！\n",fn); //輸出結果
return 0;
}
詳細連結http://www.cnblogs.com/skyme/p/3541863.html