程序設(shè)計(jì)基礎(chǔ)11-1-遞推

第11章

遞推與遞歸開(kāi)始1主要內(nèi)容遞推遞歸遞歸與分治遞歸與回溯2

Fibonacci數(shù)列問(wèn)題：

f(1)=0f(2)=1邊界

f(n)=f(n-1)+f(n-2)遞推關(guān)系式簡(jiǎn)潔高效的常見(jiàn)數(shù)學(xué)模型。特點(diǎn)：每個(gè)數(shù)據(jù)項(xiàng)都和它前面的若干個(gè)數(shù)據(jù)項(xiàng)（或后面的若干個(gè)數(shù)據(jù)項(xiàng)）有關(guān)聯(lián)——遞推關(guān)系式。求解方法：

從初始的一個(gè)或若干個(gè)數(shù)據(jù)項(xiàng)出發(fā)——邊界

通過(guò)遞推關(guān)系逐步推進(jìn)得到最終結(jié)果——遞推法遞推法3解決遞推問(wèn)題有三個(gè)重點(diǎn)：如何建立正確的遞推關(guān)系遞推關(guān)系有何性質(zhì)遞推關(guān)系式如何求解按照推導(dǎo)問(wèn)題的方向，遞推分為：順推法倒推法4舉例

猴子第1天摘下若干個(gè)桃子,當(dāng)即吃了一半又一個(gè)。第2天又把剩下的桃吃了一半又一個(gè),以后每天都吃前一天剩下的桃子的一半又一個(gè),到第10天猴子想吃時(shí),只剩下一個(gè)桃子。問(wèn)猴子第1天一共摘了多少桃子?問(wèn)題分析：已知條件第10天剩下1個(gè)桃子，隱含條件每一次前一天的桃子個(gè)數(shù)等于后一天桃子的個(gè)數(shù)加1的2倍。采取逆向思維的方法,從后往前推，可用倒推法求解。#include<stdio.h>intmain(){ inta=1,i; for(i=9;i>=1;i--)

a=(a+1)*2; printf("%d",a);return0;}

逆推法5 舉例猴子分食桃子

五只猴子采得一堆桃子，猴子彼此約定隔天早起后再分食。

不過(guò)，就在半夜里，一只猴子偷偷起來(lái)，把桃子均分成五堆后，發(fā)現(xiàn)還多一個(gè)，它吃掉這桃子，并拿走了其中一堆。

第二只猴子醒來(lái)，又把桃子均分成五堆后，還是多了一個(gè)，它也吃掉這個(gè)桃子，并拿走了其中一堆。

第三只，第四只，第五只猴子都依次如此分食桃子。

那么桃子數(shù)最少應(yīng)該有幾個(gè)呢？逆推法6算法分析：先要找第N只猴子和其面前桃子數(shù)的關(guān)系。如果從第1只開(kāi)始往第5只找，不好找，但如果思路一變，從第N到第1去，可得出下面的推導(dǎo)式：第N只猴

第N只猴前桃子數(shù)目

5

s5=x 4

s4=s5*5/4+1 3

s3=s4*5/4+1 2

s2=s3*5/4+1 1

s1=s2*5/4+1

通過(guò)遞推，求出s1即可。#include<stdio.h>intmain(){ intx,s,k,i; x=6; k=0;//整除標(biāo)志

while(k!=4) { s=x; k=0; for(i=4;i>=1;i--) {if(s%4==0)k++;elsebreak; s=s*5/4+1;} x=x+5; } printf("s=%d\n",s);return0；}7首先，用數(shù)組f(i)來(lái)存儲(chǔ)第i年的母?？倲?shù)，則第n年的母?？倲?shù)為f(n)。F(n)只與兩個(gè)值有關(guān)：一是在本年之前就已經(jīng)出生的母牛數(shù)目；二是在本年新出生的小母牛數(shù)目。順推法前一年的母?？倲?shù):f(n-1)三年前的母?？倲?shù):f(n-3)舉例

母牛的故事有一頭母牛，它每年年初生一頭小母牛。每頭小母牛從第四個(gè)年頭開(kāi)始，每年年初也生一頭小母牛。請(qǐng)編程實(shí)現(xiàn)在第n年的時(shí)候，共有多少頭母牛？關(guān)系很復(fù)雜？需要找規(guī)律！遞推公式：

f(n)=f(n-1)+f(n-3)

(n>=4)遞推的邊界條件：第1、2、3年母?？倲?shù)可知f(1)=1f(2)=2f(3)=38遞推公式：

f(n)=f(n-1)+f(n-3)

(n>=4)遞推的邊界條件：第1、2、3年母?？倲?shù)可知f(1)=1f(2)=2f(3)=3順推法#include<stdio.h>intmain(){intf[50],i,n;while(scanf(“%d”,&n)!=EOF){

f[1]=1;f[2]=2;f[3]=3;for(i=4;i<=n;i++){

f[i]=f[i-3]+f[i-1];}printf("%d\n",f[n]);}

return0;}9舉例

骨牌問(wèn)題在2×n的長(zhǎng)方形方格中，用n個(gè)1×2的骨牌鋪滿方格，輸入n，輸出鋪放方案的總數(shù)。

例如n=3時(shí)，為2×3方格，骨牌的鋪放方案有三種方法，如下圖所示：順推法10長(zhǎng)度為n時(shí)的骨牌鋪放方案不容易直接得到，可以從最簡(jiǎn)單的情況開(kāi)始尋找問(wèn)題解決的規(guī)律——遞推解決問(wèn)題的基本途徑。以f(i)表示長(zhǎng)度為i時(shí)的鋪放方案數(shù)目當(dāng)n=1時(shí)，只能是一種鋪法，即f(1)=1，如下左圖所示。當(dāng)n=2時(shí)，只能是兩種鋪法，即f(2)=2，如下右圖所示。順推法11n=3時(shí)骨牌的鋪放方案有三種方法，如下圖所示：順推法這三種鋪放方法可以采用如下的步驟分析得到：n=3時(shí)，第一塊骨牌的鋪法只有兩種可能，橫鋪或者豎鋪，即：(1)橫鋪方式：在第一格橫放一個(gè)骨牌，此時(shí)剩余兩格，在兩格內(nèi)鋪放骨牌有f(2)種鋪法；(2)豎鋪方式：在第一、二格豎放兩個(gè)骨牌，此時(shí)剩余一格，在一格內(nèi)鋪放骨牌有f(1)種鋪法；f(3)=f(2)+f(1)=2+1=3。

12對(duì)于一般的n值，其第一塊骨牌的鋪法也只有兩種可能，橫鋪或者豎鋪:

順推法(1)橫鋪方式：若第一格橫放一個(gè)骨牌，此時(shí)剩余n-1格，在n-1格放n-1個(gè)骨牌有f(n-1)種鋪法；(2)豎鋪方式：若第一、二格豎放兩格骨牌，此時(shí)剩余n-2格，在n-2格放n-2個(gè)骨牌有f(n-2)種鋪法；…………n塊骨牌的鋪法為首塊骨牌橫鋪方式鋪法與豎鋪方式鋪法之和：

遞推公式：f(n)=f(n-1)+f(n-2)邊界條件：f(1)=1f(2)=213順推法#include<stdio.h>intmain(){inti,n;__int64f[50];//VC++__int64OJ和CBlonglong

f[0]=1;f[1]=2;scanf("%d",&n);for(i=2;i<n;i++)

f[i]=f[i-1]+f[i-2];printf("%I64d\n",f[n-1]);

return0；}n塊骨牌的鋪法為首塊骨牌橫鋪方式鋪法與豎鋪方式鋪法之和：

遞推公式：f(n)=f(n-1)+f(n-2)邊界條件：f(1)=1f(2)=214

設(shè)有一個(gè)共有n級(jí)的樓梯，某人每步可走1級(jí)，也可走2級(jí)，也可走3級(jí)，求從底層開(kāi)始走完全部樓梯有多少種走法。（例如：當(dāng)n=3時(shí)，共有4種走法，

即1+1+1，1+2，2+1，3）

思考：上樓問(wèn)題15

算法分析：

n的值

走法

1

1 2

2 3

4

47

從遞推的思想出發(fā)，可以設(shè)想，從第4項(xiàng)開(kāi)始，每1項(xiàng)等于前面3項(xiàng)的和。16#include<stdio.h>voidmain(){intx,n,i,a,b,c; scanf("%d",&n);

a=1;b=2;c=4;if(n==1)x=1; elseif(n==2)x=2; elseif(n==3)x=4;for(i=4;i<=n;i++){ x=a+b+c;a=b;b=c;c=x;} printf("%d",x);}

f(n)=f(n-1)+f(n-2)+f(n-3)特別地，f(1)=1，f(2)=2,f(3)=4。即為本問(wèn)題的遞推公式。17例5

錯(cuò)排公式某人寫(xiě)了n封信和n個(gè)信封，如果所有的信都裝錯(cuò)了信封。求所有的信都裝錯(cuò)信封，共有多少種不同情況？對(duì)n封信以及n個(gè)信封各自按照從1到n進(jìn)行編號(hào)，

f（n）表示當(dāng)n個(gè)編號(hào)的信放在n個(gè)編號(hào)位置的信封，信的編號(hào)與信封位置編號(hào)各不對(duì)應(yīng)的方法數(shù)；類似，f（n-1）表示n-1個(gè)編號(hào)的信放在n-1個(gè)編號(hào)位置的信封，各不對(duì)應(yīng)的方法數(shù)。其它類推。18第一步，把第n封信放在一個(gè)信封，比如第k個(gè)信封（k≠n），一共有n-1種方法；第二步，放編號(hào)為k的信，這時(shí)有兩種情況：①把它放到第n個(gè)信封，對(duì)于剩下的n-2封信，需要放到剩余的n-2個(gè)信封且各不對(duì)應(yīng)，就有f(n-2)種方法；②不把它放到位置n，這時(shí)，對(duì)于這n-1封信，放到剩余的n-1個(gè)信封且各不對(duì)應(yīng)，有f(n-1)種方法；19綜上得到本問(wèn)題的遞推公式：

f（n）=（n-1）*（f（n-2）+f（n-1））特別地，f（1）=0，f（2）=1。20例6馬踏過(guò)河卒棋盤(pán)上A點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo)B點(diǎn)。卒行走的規(guī)則：可以向下、或者向右。同時(shí)在棋盤(pán)上的任一點(diǎn)有一個(gè)對(duì)方的馬（如下圖中的C點(diǎn)），該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控制點(diǎn)（如下圖中的C點(diǎn)和P1，P2，……，P8）。卒不能通過(guò)對(duì)方馬的控制點(diǎn)。棋盤(pán)用坐標(biāo)表示，A點(diǎn)(0,0)、B點(diǎn)(n,m)(n,m為不超過(guò)20的整數(shù)),同樣馬的位置坐標(biāo)是需要給出的，C≠A且C≠B。現(xiàn)在從鍵盤(pán)輸入n，m，要你計(jì)算出卒從A點(diǎn)能夠到達(dá)B點(diǎn)的路徑的條數(shù)。21馬踏過(guò)河卒是一道很老的題目，一些程序設(shè)計(jì)比賽中也經(jīng)常出現(xiàn)過(guò)這一問(wèn)題的變形。一看到這種類型的題目容易讓人想到用搜索來(lái)解決，但盲目的搜索僅當(dāng)n,m=15就會(huì)超時(shí)?？梢栽囍眠f推來(lái)進(jìn)行求解。根據(jù)卒行走的規(guī)則，過(guò)河卒要到達(dá)棋盤(pán)上的一個(gè)點(diǎn)，只能有兩種可能：從左邊過(guò)來(lái)（左點(diǎn)）或是從上面過(guò)來(lái)（上點(diǎn)），所以根據(jù)加法原理，過(guò)河卒到達(dá)某一點(diǎn)的路徑數(shù)目，就等于其到達(dá)其相鄰的上點(diǎn)和左點(diǎn)的路徑數(shù)目之和，因此可用逐列（或逐行）遞推的方法求出從起點(diǎn)到終點(diǎn)的路徑數(shù)目。障礙點(diǎn)（馬的控制點(diǎn)）也完全適用，只要將到達(dá)該點(diǎn)的路徑數(shù)目設(shè)置為0即可。22

假設(shè)用二維數(shù)組元素f[i][j]表示到達(dá)點(diǎn)（i，j）的路徑數(shù)目，用g[i][j]表示點(diǎn)（i，j）是否是對(duì)方馬的控制點(diǎn)，g[i][j]=0表示不是對(duì)方馬的控制點(diǎn)，g[i][j]=1表示是對(duì)方馬的控制點(diǎn)。則可以得到如下的遞推關(guān)系式：

f[i][j]=0{g[i][j]=1}f[i][0]=f[i-1][0]{i＞0,g[i][j]=0}f[0][j]=f[0][j-1]{j＞0,g[i][j]=0}f[i][j]=f[i-1][j]+f[i][j-1]{i＞0,j＞0,g[i][j]=0}遞推的邊界為：f[0][0]=123#include<stdio.h>intmain(){inti,j,n,m,f[20][20],g[20][20],x,y;scanf("%d%d%d%d",&n,&m,&x,&y);for(i=1;i<=n;i++) for(j=1;j<=m;j++) f[i][j]=0;for(i=0;i<=n;i++) for(j=0;j<=m;j++)g[i][j]=0;g[x][y]=1; g[x-1][y-2]=1;g[x+1][y-2]=1;g[x-2][y-1]=1;g[x+2][y-1]=1;g[x-2][y+1]=1;g[x+2][y+1]=1;g[x-1][y+2]=1;g[x+1][y+2]=1;24for(i=1;i<=n;i++) if(g[i][0]!=1)f[i][0]=1; elsefor(;i<=n;i++) f[i][0]=0;for(j=1;j<=m;j++) if(g[0][j]!=1)f[0][j]=1;

elsefor(;j<=m;j++) f[0][j]=0; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(g[i