遞推算法

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

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

相對(duì)于遞歸算法,遞推算法免除了數(shù)據(jù)進(jìn)出棧的過程，也就是說,不需要函數(shù)不斷的向邊界值靠攏,而直接從邊界出發(fā),直到求出函數(shù)值.比如階乘函數(shù)：f(n)=n*f(n-1) 在f(3)的運(yùn)算過程中,遞歸的數(shù)據(jù)流動(dòng)過程如下: 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) 由此可見,遞推的效率要高一些,在可能的情況下應(yīng)盡量使用遞推.但是遞歸作為比較基礎(chǔ)的算法,它的作用不能忽視.所以,在把握這兩種算法的時(shí)候應(yīng)該特別注意。

順推法

所謂順推法是從已知條件出發(fā)，逐步推算出要解決的問題的方法叫順推。 如斐波拉契數(shù)列，設(shè)它的函數(shù)為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……直至我們要求的解。

逆推法

所謂逆推法從已知問題的結(jié)果出發(fā)，用迭代表達(dá)式逐步推算出問題的開始的條件，即順推法的逆過程，稱為逆推。

遞推算法的經(jīng)典例子

【案例】從原點(diǎn)出發(fā)，一步只能向右走、向上走或向左走。恰好走N步且不經(jīng)過已走的點(diǎn)共有多少種走法？

樣例輸入：N=2

樣例輸出：result=7

樣例輸入：N=3

樣例輸出：result=17

解題思路：要解決走N步共有多少種走法，我們?cè)谀玫筋}目的時(shí)候最直接的想法就是先畫出當(dāng)N=1、N=2、N=3。。。。。N=n時(shí)對(duì)應(yīng)走法的圖例，由簡(jiǎn)單到復(fù)雜、由特殊到一般的推理過程，找出規(guī)律獲得解題的思路。在數(shù)學(xué)上，我們稱為歸納法。如果用編程的方法來求解這樣的推理題，我們把這樣的求解思路（算法）稱之為遞推法。遞推的精髓在于f（n）的結(jié)果一般由f(n-1)、f(n-2)…..f(n-k)的前k次結(jié)果推導(dǎo)出來。我們?cè)诮鉀Q這類遞推問題時(shí)，難點(diǎn)就是如何從簡(jiǎn)單而特殊的案例，找到問題的一般規(guī)律，寫出f（n）與f(n-1)、f(n-2)…..f(n-k)之間的關(guān)系表達(dá)式，從而得出求解的結(jié)果。在歷年noip的復(fù)賽當(dāng)中，參賽選手對(duì)于這類題目都有這樣的感受，往往花費(fèi)了大量的時(shí)間來分析題目的一般規(guī)律，寫出f（n）的一般表達(dá)式，而編程實(shí)現(xiàn)可能只需要幾分鐘的時(shí)間。所以我們?cè)谄綍r(shí)訓(xùn)練的時(shí)候，對(duì)于這樣的遞推題目，就必須掌握如何分析問題，從特殊推導(dǎo)出一般的規(guī)律，寫出想要的關(guān)系表達(dá)式，問題就迎刃而解了。下面是這道題解題的心得，供大家參考：

（1）當(dāng)N=1時(shí)，繪出走法圖

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

（2）當(dāng)N=2時(shí)，繪出走法圖

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

（3）當(dāng)N=3時(shí)，繪出走法圖

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

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

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

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

         b.    f（n-1）有多少個(gè)終點(diǎn)是有2種走法的

對(duì)于N=3時(shí)，有4個(gè)點(diǎn)D、E、F、G可以走出2種不同走法的，這4個(gè)點(diǎn)又是怎么得到的呢？它與N值有什么聯(lián)系呢？ 實(shí)際上我們?cè)诮鉀Q了上一個(gè)問題的時(shí)候，這個(gè)問題就變得相當(dāng)容易了， f（n-1）減掉剛才有3種走法的點(diǎn)，剩下的點(diǎn)不就是只有2種走法了嗎？即f（n-1）-f（n-2）。

    c. 得出f（n）的一般關(guān)系式

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

化簡(jiǎn)：

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

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

          （本題還有其他的解法，同學(xué)們可以繼續(xù)挖掘！）

代碼：

#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; //初始化當(dāng)n=1和n=2時(shí)的臨界條件    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; //當(dāng)n>=3時(shí)fn的通式         fn_2=fn_1;//更新fn_1和fn_2的值         fn_1=fn;      }    }    printf("一共有%d種走法！/n",fn);  //輸出結(jié)果    return 0; }