遞推算法

給定一個數的序列H0,H1,…,Hn,…若存在整數n0，使當n>n0時,可以用等號(或大于號、小于號)將Hn與其前面的某些項Hi(0<i<n)聯系起來，這樣的式子就叫做遞推關系。

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

相對于遞歸算法,遞推算法免除了數據進出棧的過程，也就是說,不需要函數不斷的向邊界值靠攏,而直接從邊界出發,直到求出函數值.比如階乘函數：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）的一般表達式，而編程實現可能只需要幾分鐘的時間。所以我們在平時訓練的時候，對于這樣的遞推題目，就必須掌握如何分析問題，從特殊推導出一般的規律，寫出想要的關系表達式，問題就迎刃而解了。下面是這道題解題的心得，供大家參考：

（1）當N=1時，繪出走法圖

（圖1）共有3種不同的走法，也就是黑色線條的數量，即f(1)=3

（2）當N=2時，繪出走法圖

（圖2）共有7種不同的走法，也就是綠色線條的數量，即f(2)=7

（3）當N=3時，繪出走法圖

（圖3）共有17種不同的走法，也就是紅色線條的數量，即f(3)=17

由此，我們不難看出，對于任何一個起點，最多可以走出3種走法，但最少必須走出2種走法。那么我們要求出f(n)，實際上轉換為如果我們能夠得到上一步即f（n-1）有多少個終點是有3種走法的，有多少個點有2種走法的，那么問題就解決了。

a. 上一步，即f（n-1）有多少個終點是有3種走法的。

       對于N=3時，f(n-1)=f(2), 有3個點A、B、C可以走出3種不同走法的，這3個點是怎么得到的呢？它的存在與N值有沒有必然的聯系？如果我們能找到它與N之間的關系，問題也就解決了。有了這樣的思路以后，我們不難找到這樣的規律：如果f（n-2）存在，即上上步存在，那么從上上步出發的線路里面必然會有一條向上走的線路，而這條向上走的線路在到達f（n-1）之后，  向f（n）出發時也必然有左、上、右這三種走法，那么我們就得出了這樣的結論：當f（n-2）存在時，f（n-2）的值實際上就等價于f（n-1）有多少個終點是有3種走法。

         b.    f（n-1）有多少個終點是有2種走法的

對于N=3時，有4個點D、E、F、G可以走出2種不同走法的，這4個點又是怎么得到的呢？它與N值有什么聯系呢？ 實際上我們在解決了上一個問題的時候，這個問題就變得相當容易了， f（n-1）減掉剛才有3種走法的點，剩下的點不就是只有2種走法了嗎？即f（n-1）-f（n-2）。

    c. 得出f（n）的一般關系式

f(n)=3*f(n-2)+2*(f(n-1)-f(n-2) ) (n>=3)

化簡：

f(n)=2*f(n-1)+f(n-2) (n>=3)

      有一點需要補充的就是，任何遞推題，都會有臨界條件。當N=1時，f(n)=3;,當N=2時，f(n)=7,這些都可以看成是臨界條件。只有當N>=3時，即上上步存在的情況下，就可以得出f(n)的一般通式：f(n)=2*f(n-1)+f(n-2)

          （本題還有其他的解法，同學們可以繼續挖掘?。?/p>

代碼：

#include <stdio.h> #include <windows.h> 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; }