第五講--遞推與遞歸

1、第五講第五講 遞推與遞歸遞推與遞歸主要內(nèi)容主要內(nèi)容遞推及其應(yīng)用遞推及其應(yīng)用遞歸及其應(yīng)用遞歸及其應(yīng)用 第五講第五講 遞推與遞歸遞推與遞歸遞推遞推是通過(guò)數(shù)學(xué)推導(dǎo)，將復(fù)雜的運(yùn)算化解為是通過(guò)數(shù)學(xué)推導(dǎo)，將復(fù)雜的運(yùn)算化解為若干重復(fù)的簡(jiǎn)單運(yùn)算，以充分發(fā)揮計(jì)算機(jī)擅長(zhǎng)若干重復(fù)的簡(jiǎn)單運(yùn)算，以充分發(fā)揮計(jì)算機(jī)擅長(zhǎng)重復(fù)處理的特點(diǎn)。重復(fù)處理的特點(diǎn)。遞歸是遞歸是將復(fù)雜的操作分解為簡(jiǎn)單操作的多次將復(fù)雜的操作分解為簡(jiǎn)單操作的多次重復(fù)，一般用函數(shù)調(diào)用完成重復(fù)，一般用函數(shù)調(diào)用完成。 11.1 遞遞 推推11.1 遞遞 推推11.1 遞遞 推推例如：例如：Fibonacci數(shù)列問(wèn)題數(shù)列問(wèn)題 已知：已知：F (1) = 0 ，F(xiàn)(2)

2、 = 1， 若：若： n2，則，則F(n)= F(n-1)+F(n-2)注意：注意： 1）每個(gè)數(shù)據(jù)項(xiàng)都和它前面的若干個(gè)數(shù)據(jù)項(xiàng)（或后面的若干每個(gè)數(shù)據(jù)項(xiàng)都和它前面的若干個(gè)數(shù)據(jù)項(xiàng)（或后面的若干個(gè)數(shù)據(jù)項(xiàng)）有一定的關(guān)聯(lián)個(gè)數(shù)據(jù)項(xiàng)）有一定的關(guān)聯(lián)-遞推關(guān)系式。遞推關(guān)系式。 2）從初始的一個(gè)或若干數(shù)據(jù)項(xiàng)出發(fā)，通過(guò)遞推關(guān)系式逐步從初始的一個(gè)或若干數(shù)據(jù)項(xiàng)出發(fā)，通過(guò)遞推關(guān)系式逐步推進(jìn)，從而得到最終結(jié)果。推進(jìn)，從而得到最終結(jié)果。11.1 遞遞 推推注意：注意：3）遞推必須有）遞推必須有 “邊界邊界”。4）解決遞推類型問(wèn)題有三個(gè)重點(diǎn)：）解決遞推類型問(wèn)題有三個(gè)重點(diǎn)： 如何建立正確的遞推關(guān)系式；如何建立正確的遞推關(guān)系式； 遞

3、推關(guān)系有何性質(zhì)；遞推關(guān)系有何性質(zhì)； 遞推關(guān)系式如何求解。遞推關(guān)系式如何求解?；A(chǔ)，重點(diǎn)基礎(chǔ)，重點(diǎn)11.1 遞遞 推推按照推導(dǎo)問(wèn)題的方向，遞推分為：按照推導(dǎo)問(wèn)題的方向，遞推分為：l 順推法：順推法：從初始數(shù)據(jù)開始推理。從初始數(shù)據(jù)開始推理。 例如：例如：n=0n=0時(shí)，時(shí)，n!=1n!=1； n1n1時(shí)，時(shí)，n!=nn!=n* *(n-1)!(n-1)!l 倒推法：倒推法：從結(jié)果數(shù)據(jù)開始推理。從結(jié)果數(shù)據(jù)開始推理。 例如：例如：n!=nn!=n* *(n-1)! (n-1)! ； 邊界：邊界：n=0n=0，n!=1n!=1例例1：猴子第猴子第1天摘下若干個(gè)桃子，當(dāng)即吃了一半天摘下若干個(gè)桃子，當(dāng)即吃了

4、一半又一個(gè)。第又一個(gè)。第2天又把剩下的桃吃了一半又一個(gè)，以天又把剩下的桃吃了一半又一個(gè)，以后每天都吃前一天剩下的桃子的一半又一個(gè)，到第后每天都吃前一天剩下的桃子的一半又一個(gè)，到第10天猴子想吃時(shí)，只剩下一個(gè)桃子。天猴子想吃時(shí)，只剩下一個(gè)桃子。問(wèn)：?jiǎn)枺汉镒拥诤镒拥?天一共摘了多少桃子天一共摘了多少桃子? 分析：分析：已知條件：已知條件：第第 10 天剩下天剩下 1 個(gè)桃子；個(gè)桃子；隱含條件：隱含條件：每一次前一天的桃子個(gè)數(shù)等于后一天每一次前一天的桃子個(gè)數(shù)等于后一天桃子的個(gè)數(shù)加桃子的個(gè)數(shù)加 1 的的 2 倍。倍。逆向思維：逆向思維：從后往前推，可用倒推法求解。從后往前推，可用倒推法求解。 #inc

5、lude void main( ) int i,a=1;for (i=9; i=1; i-) a=(a+1)*2;printf(a=%dn,a); 例例1：逆推法逆推法-求解猴子吃桃子求解猴子吃桃子例例2：猴子分食桃子：猴子分食桃子1) 五只猴子采得一堆桃子，猴子彼此約定隔天早起后再分五只猴子采得一堆桃子，猴子彼此約定隔天早起后再分食。食。2) 半夜里，一只猴子偷偷起來(lái)，把桃子均分成五堆后，發(fā)半夜里，一只猴子偷偷起來(lái)，把桃子均分成五堆后，發(fā)現(xiàn)還多一個(gè)，它吃掉這桃子，并拿走了其中一堆。現(xiàn)還多一個(gè)，它吃掉這桃子，并拿走了其中一堆。3)第二只猴子醒來(lái)，又把桃子均分成五堆后，還是多了一第二只猴子醒來(lái)，

6、又把桃子均分成五堆后，還是多了一個(gè)，它也吃掉這個(gè)桃子，并拿走了其中一堆。個(gè)，它也吃掉這個(gè)桃子，并拿走了其中一堆。第三只，第四只，第五只猴子都依次如此分食桃子。第三只，第四只，第五只猴子都依次如此分食桃子。問(wèn)：?jiǎn)枺何逯缓镒硬傻靡欢烟易游逯缓镒硬傻靡欢烟易訑?shù)最少應(yīng)該有幾個(gè)呢？數(shù)最少應(yīng)該有幾個(gè)呢？逆推法逆推法算法分析：算法分析： 先要找第先要找第N只猴子和其面前桃子數(shù)的關(guān)系。如只猴子和其面前桃子數(shù)的關(guān)系。如果從第果從第1只開始往第只開始往第5只找，不好找，但如果思路只找，不好找，但如果思路一變，從第一變，從第N到第到第1去，可得出下面的推導(dǎo)式：去，可得出下面的推導(dǎo)式： 第第N只猴只猴 第第N只猴前桃

7、子數(shù)目只猴前桃子數(shù)目5 s5=x4 s4=s5*5/4+13 s3=s4*5/4+12 s2=s3*5/4+11 s1=s2*5/4+1通過(guò)遞推，求出通過(guò)遞推，求出s1即可即可例例2：猴子分食桃子：猴子分食桃子-逆推法逆推法注意：其中的注意：其中的s1、s2、s3、s4、s5必須是整數(shù)必須是整數(shù)/例例2：猴子分食桃子：猴子分食桃子-逆推法逆推法#include void main() int x,s,k,i;x=6; / 最少的初值最少的初值k=0; / 整除標(biāo)志整除標(biāo)志while ( k!=4)s=x;k=0;for ( i=4; i=1; i-) if ( s%4 = 0) k+; els

8、e break; s=s*5/4+1; x=x+5;printf(s=%dn,s);11.1.2 遞推設(shè)計(jì)實(shí)例遞推設(shè)計(jì)實(shí)例例例11.1：母牛的故事：母牛的故事 問(wèn)題描述：?jiǎn)栴}描述：有一頭母牛，它每年年初生一頭小有一頭母牛，它每年年初生一頭小母牛。每頭小母牛從第四個(gè)年頭開始，母牛。每頭小母牛從第四個(gè)年頭開始，每年年每年年初也生一頭小母牛。初也生一頭小母牛。編程實(shí)現(xiàn)：編程實(shí)現(xiàn)：在第在第n年的時(shí)候，共有多少頭母牛？年的時(shí)候，共有多少頭母牛？例例11.1：母牛的故事：母牛的故事-順推法順推法 設(shè)數(shù)組設(shè)數(shù)組f(i)表示第表示第 i 年的母?？倲?shù)，則第年的母?？倲?shù)，則第 n 年的母?？倲?shù)為年的母?？倲?shù)為f

9、(n) 。 f(n) 與兩個(gè)值有關(guān)與兩個(gè)值有關(guān) 在本年之前就已經(jīng)出生的母牛數(shù)目在本年之前就已經(jīng)出生的母牛數(shù)目 在本年新出生的小母牛數(shù)目。在本年新出生的小母牛數(shù)目。1） 本年之前就已經(jīng)出生的母牛數(shù)目，實(shí)際上就是前一年的母牛本年之前就已經(jīng)出生的母牛數(shù)目，實(shí)際上就是前一年的母?？倲?shù)總數(shù)-f（n-1）。）。2） 由于每一頭母牛每年只生育一頭小母牛，所以在本年新出生由于每一頭母牛每年只生育一頭小母牛，所以在本年新出生的小母牛數(shù)目，實(shí)際上是到今年可以生育的母牛的數(shù)目。的小母牛數(shù)目，實(shí)際上是到今年可以生育的母牛的數(shù)目。3) 而每頭小母牛從第四個(gè)年頭才開始生育，所以今年可以生育的而每頭小母牛從第四個(gè)年頭才開始

10、生育，所以今年可以生育的母牛的數(shù)實(shí)際上就是三年前的母牛總數(shù)，即為母牛的數(shù)實(shí)際上就是三年前的母牛總數(shù)，即為f（n-3）。例例11.1：母牛的故事：母牛的故事-順推法順推法遞推公式：遞推公式： f(n)=f(n-1)+f(n-3) （n=4） f (1) =1； f (2) =2; f (3) =3；遞推邊界遞推邊界 若數(shù)組若數(shù)組f(i)表示第表示第 i 年的母?？倲?shù)，則第年的母?？倲?shù)，則第 n 年的母?？偰甑哪概？倲?shù)為數(shù)為f(n) 。 例例11.1：母牛的故事：母牛的故事-順推法順推法#include void main() _int64 f50; / _int64 - 定義大整數(shù)定義大整數(shù) i

11、nt i,n; scanf(%d,&n); f1=1; f2=2; f3=3; for(i=4; i=n; i+) fi=fi-3+fi-1; printf(%I64dn,fi); / %I64d大整數(shù)輸入大整數(shù)輸入/輸出格式輸出格式 例例11.2 骨牌問(wèn)題骨牌問(wèn)題-順推法順推法例例11.2 骨牌問(wèn)題骨牌問(wèn)題-順推法順推法例例11.2 骨牌問(wèn)題骨牌問(wèn)題-順推法順推法 例例11.2 骨牌問(wèn)題骨牌問(wèn)題-順推法順推法因此，因此，n塊骨牌的鋪法塊骨牌的鋪法是是首塊骨牌橫鋪方式的首塊骨牌橫鋪方式的鋪法與豎鋪方式的鋪法之和。鋪法與豎鋪方式的鋪法之和。 即：即： f(n)=f(n-1)+f(n-2)邊界：邊

12、界： f(1)=1 ，f(2)=2例例11.2 骨牌問(wèn)題骨牌問(wèn)題-順推法順推法遞推公式遞推公式 #include int main() int i,n, f20; f0=1; f1=2; / 邊界邊界 scanf(%d,&n); for(i=2;in;i+) fi=fi-1+fi-2; / 遞推遞推 printf(%dn,fi); 例例11.2 骨牌問(wèn)題骨牌問(wèn)題#includevoid main() int i,n; _int64 f50; f0=1; f1=2; / 邊界邊界 scanf(%d,&n); for(i=2;in;i+) fi=fi-1+fi-2; / 遞推遞推 printf(%

13、I64dn,fn-1); 例例11.2 骨牌問(wèn)題骨牌問(wèn)題-順推法順推法問(wèn)題描述：?jiǎn)栴}描述： 設(shè)有一個(gè)共有設(shè)有一個(gè)共有n級(jí)的樓梯，某人每步可走級(jí)的樓梯，某人每步可走1級(jí)，也可走級(jí)，也可走2級(jí)，也可走級(jí)，也可走3級(jí)。級(jí)。問(wèn)：?jiǎn)枺呵髲牡讓娱_始走完全部樓梯的有多少種走法。求從底層開始走完全部樓梯的有多少種走法。例如，當(dāng)例如，當(dāng)n=3時(shí)，走法如下：時(shí)，走法如下： 1+1+1 1+2 2+1 3思考：上樓問(wèn)題思考：上樓問(wèn)題n=3，共有，共有4種走法種走法n的值的值 走法走法f(n) 1 1 2 2 3 4 4 7從遞推的思想出發(fā)從遞推的思想出發(fā)，可以設(shè)想，從第，可以設(shè)想，從第4 4項(xiàng)項(xiàng)開始，每開始，每1

14、1項(xiàng)等于前面項(xiàng)等于前面3 3項(xiàng)的和。項(xiàng)的和。上樓問(wèn)題上樓問(wèn)題-算法分析算法分析 f(n)=f(n-1)+f(n-2)+f(n-3)-遞推公式遞推公式 f(1)=1 , f(2)=2 , f(3)=4 -遞推邊界遞推邊界 #include /上樓問(wèn)題上樓問(wèn)題 void main( ) int x,n,i,a,b,c;scanf(%d,&n);a=1; b=2; c=4; if (n=1) x=1;else if (n=2) x=2; else if (n=3) x=4; for (i=4; i=n; i+) x=a+b+c; a=b; b=c; c=x; printf(%d,x); 例例11.3

15、 錯(cuò)排信件錯(cuò)排信件問(wèn)題描述：?jiǎn)栴}描述：某人寫了某人寫了n封信封信和和n個(gè)信封個(gè)信封，所所有的信都裝錯(cuò)了信封。有的信都裝錯(cuò)了信封。要求：若要求：若所有的信都裝錯(cuò)信封，共有多少所有的信都裝錯(cuò)信封，共有多少種不同情況？種不同情況？例例11.3 錯(cuò)排信件錯(cuò)排信件找規(guī)律：找規(guī)律：對(duì)對(duì)n封信封信以及以及n個(gè)信封個(gè)信封各自按照從各自按照從 1.n 進(jìn)行進(jìn)行編號(hào)；編號(hào)； f(n)-n個(gè)編號(hào)的信個(gè)編號(hào)的信放在放在n個(gè)編號(hào)的信封，個(gè)編號(hào)的信封，各各不對(duì)應(yīng)的方法數(shù)；不對(duì)應(yīng)的方法數(shù)；f(n-1)-n-1個(gè)編號(hào)的信放在個(gè)編號(hào)的信放在n-1個(gè)編號(hào)位置的個(gè)編號(hào)位置的信封，各不對(duì)應(yīng)的方法數(shù)。信封，各不對(duì)應(yīng)的方法數(shù)。例例11.

16、3 錯(cuò)排信件錯(cuò)排信件找規(guī)律：找規(guī)律： 第一步第一步: 把把第第n封信封信放在第放在第k個(gè)信封（個(gè)信封（kn），不對(duì)應(yīng)的共有），不對(duì)應(yīng)的共有n-1種方法；種方法； 第二步第二步: 放編號(hào)為放編號(hào)為 k 的信，有兩種情況：的信，有兩種情況： 1）放編號(hào)為放編號(hào)為 k 的信的信放到第放到第n個(gè)信封個(gè)信封，則對(duì)于剩下的，則對(duì)于剩下的n-2封信，封信，需要放到剩余的需要放到剩余的n-2個(gè)信封且各不對(duì)應(yīng)，就有個(gè)信封且各不對(duì)應(yīng)，就有f(n-2)種方法；種方法； 2）放編號(hào)為放編號(hào)為 k 的信的信不放到位置不放到位置n，對(duì)于這對(duì)于這n-1封信，放到剩余封信，放到剩余的的n-1個(gè)信封且各不對(duì)應(yīng)，有個(gè)信封且各不對(duì)

17、應(yīng)，有f(n-1)種方法；種方法； 結(jié)論：結(jié)論： f(n) = (n-1) * ( f (n-2) + f (n-1) ) 特例：特例：f（1）= 0， f（2）= 1 -邊界邊界例例11.3 錯(cuò)排信件錯(cuò)排信件 #include void main() int i,n, f20; f1=0;f2=1; scanf(%d,&n); for(i=3;i=n;i+) fi=(i-1)*(fi-2+fi-1); printf(%dn,fi); 例例11.4 馬踏過(guò)河卒馬踏過(guò)河卒-選講選講 棋盤上棋盤上A點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo)點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo)B點(diǎn)。點(diǎn)。 卒行走的規(guī)則：可以向下、或者向右

18、。卒行走的規(guī)則：可以向下、或者向右。 同時(shí)在棋盤上的任一點(diǎn)有一個(gè)對(duì)方的馬（如下圖中的同時(shí)在棋盤上的任一點(diǎn)有一個(gè)對(duì)方的馬（如下圖中的C點(diǎn)），該點(diǎn)），該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控制點(diǎn)（如下馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控制點(diǎn)（如下圖中的圖中的C點(diǎn)和點(diǎn)和P1，P2，P8）。）。 卒不能通過(guò)對(duì)方馬的控制點(diǎn)。棋盤用坐標(biāo)表示，卒不能通過(guò)對(duì)方馬的控制點(diǎn)。棋盤用坐標(biāo)表示，A點(diǎn)點(diǎn)(0,0)、B點(diǎn)點(diǎn)(n, m) (n,m為不超過(guò)為不超過(guò)20的整數(shù)的整數(shù))，同樣馬的位置坐標(biāo)是需要給出的，同樣馬的位置坐標(biāo)是需要給出的，CA且且CB。編程：編程：輸入輸入n，m，計(jì)算出卒，計(jì)算出卒從從A

19、點(diǎn)能夠到達(dá)點(diǎn)能夠到達(dá)B點(diǎn)的路徑的條數(shù)。點(diǎn)的路徑的條數(shù)。例例11.4 馬踏過(guò)河卒馬踏過(guò)河卒-選講選講 馬踏過(guò)河卒是一道很老的題目，一些程序設(shè)計(jì)比賽中馬踏過(guò)河卒是一道很老的題目，一些程序設(shè)計(jì)比賽中也經(jīng)常出現(xiàn)過(guò)這一問(wèn)題的變形。一看到這種類型的題也經(jīng)常出現(xiàn)過(guò)這一問(wèn)題的變形。一看到這種類型的題目容易讓人想到用搜索來(lái)解決，但盲目的搜索僅當(dāng)目容易讓人想到用搜索來(lái)解決，但盲目的搜索僅當(dāng)n,m=15就會(huì)超時(shí)?？梢栽囍眠f推來(lái)進(jìn)行求解。就會(huì)超時(shí)?？梢栽囍眠f推來(lái)進(jìn)行求解。 根據(jù)卒行走的規(guī)則，過(guò)河卒要到達(dá)棋盤上的一個(gè)點(diǎn)，根據(jù)卒行走的規(guī)則，過(guò)河卒要到達(dá)棋盤上的一個(gè)點(diǎn)，只能有兩種可能：只能有兩種可能：從左邊過(guò)來(lái)（左點(diǎn)）

20、或是從上面過(guò)從左邊過(guò)來(lái)（左點(diǎn)）或是從上面過(guò)來(lái)（上點(diǎn)），所以根據(jù)加法原理，過(guò)河卒到達(dá)某一點(diǎn)來(lái)（上點(diǎn)），所以根據(jù)加法原理，過(guò)河卒到達(dá)某一點(diǎn)的路徑數(shù)目，就等于其到達(dá)其相鄰的的路徑數(shù)目，就等于其到達(dá)其相鄰的上點(diǎn)和左點(diǎn)上點(diǎn)和左點(diǎn)的路的路徑數(shù)目之和，因此可用逐列（或逐行）遞推的方法求徑數(shù)目之和，因此可用逐列（或逐行）遞推的方法求出從起點(diǎn)到終點(diǎn)的路徑數(shù)目。障礙點(diǎn)（馬的控制點(diǎn)）出從起點(diǎn)到終點(diǎn)的路徑數(shù)目。障礙點(diǎn)（馬的控制點(diǎn)）也完全適用，只要將到達(dá)也完全適用，只要將到達(dá)該點(diǎn)的路徑數(shù)目設(shè)置為該點(diǎn)的路徑數(shù)目設(shè)置為0即可即可。 例例11.4 馬踏過(guò)河卒馬踏過(guò)河卒-選講選講 用二維數(shù)組元素用二維數(shù)組元素fijfij表示到

21、達(dá)點(diǎn)（表示到達(dá)點(diǎn)（i i，j j）的路徑數(shù)目；）的路徑數(shù)目； 用用gijgij表示點(diǎn)（表示點(diǎn)（i i，j j）是否是對(duì)方馬的控制點(diǎn)；）是否是對(duì)方馬的控制點(diǎn)； 若若gij=0gij=0表示不是對(duì)方馬的控制點(diǎn)，表示不是對(duì)方馬的控制點(diǎn)，gij=1gij=1表示是對(duì)表示是對(duì)方馬的控制點(diǎn)。方馬的控制點(diǎn)。則可以得到如下的遞推關(guān)系式：則可以得到如下的遞推關(guān)系式： fij = 0 fij = 0 當(dāng)當(dāng) gij=1gij=1 fi0 = fi-10 fi0 = fi-10 當(dāng)當(dāng) i i0, gij=00, gij=0 f0j = f0j-1 f0j = f0j-1 當(dāng)當(dāng) j j0, gij=00, gij=0

22、fij = fi-1j + fij-1 fij = fi-1j + fij-1 當(dāng)當(dāng) i i0, j0, j0, gij=00, gij=0 遞推邊界：遞推邊界：f00 = 1 #include / 馬踏過(guò)河卒馬踏過(guò)河卒 int main() int i,j,n,m,f2020,g2020,x,y; scanf(%d %d %d %d,&n,&m,&x,&y); for (i=1;i=n;i+)for (j=1;j=m;j+) fij=0; for (i=0;i=n;i+) for (j=0;j=m;j+) gij=0;gxy=1; gx-1y-2=1; gx+1y-2=1;gx-2y-1=1

23、; gx+2y-1=1; gx-2y+1=1;gx+2y+1=1; gx-1y+2=1; gx+1y+2=1;for (i=1;i=n;i+)if(gi0!=1) fi0=1;else for (;i=n;i+) fi0=0;for (j=1;j=m;j+)if(g0j!=1) f0j=1;else for(;j=m;j+) f0j=0;for (i=1;i=n;i+) for (j=1;j=m;j+)if (gij=0) fij=fi-1j+fij-1;printf(%dn,fnm);return 0;例例11.4 馬踏過(guò)河卒馬踏過(guò)河卒改進(jìn)改進(jìn)為了更簡(jiǎn)潔地表示馬的控制點(diǎn)，可以引入兩個(gè)一維數(shù)組

24、，分別用來(lái)為了更簡(jiǎn)潔地表示馬的控制點(diǎn)，可以引入兩個(gè)一維數(shù)組，分別用來(lái)統(tǒng)計(jì)從馬的初始位置可以橫向移動(dòng)的位移與縱向移動(dòng)的位移。統(tǒng)計(jì)從馬的初始位置可以橫向移動(dòng)的位移與縱向移動(dòng)的位移。程序的改進(jìn)如下：程序的改進(jìn)如下：#includeint main() int dx9=0,-2,-1,1,2,2,1,-1,-2; int dy9=0,1,2,2,1,-1,-2,-2,-1; int n,m,x,y,i,j; int f2020=0,g2020=0; scanf(%d%d%d%d,&n,&m,&x,&y); gxy= 1;例例11.4 馬踏過(guò)河卒馬踏過(guò)河卒 for(i=1;i=0)&(x+dxi=0)&

25、(y+dyi=m)gx+dxiy+dyi=1; for(i=1;i=n;i+) if (gi0!=1) fi0=1; else for(;i=n;i+)fi0=0; for(j=1;j=m;j+) if(g0j!=1) f0j=1; else for(;j=m;j+) f0j=0; for(i=1;i=n;i+) for(j=1;j=m;j+)if (gij=1) fij=0; else fij=fi-1j+fij-1; printf(%dn,fnm); return 0; 遞推應(yīng)用：王小二切餅，要求每遞推應(yīng)用：王小二切餅，要求每2條線都有交點(diǎn)。條線都有交點(diǎn)。 找規(guī)律：王小二切餅，要求每找規(guī)律

26、：王小二切餅，要求每2條線都有交點(diǎn)。條線都有交點(diǎn)。規(guī)律：規(guī)律：p(n)=p(n-1)+n #include / 用遞推求解用遞推求解-切餅問(wèn)題切餅問(wèn)題 int main() int n,i; int p100; p0=1;scanf(%d,&n);for (i=1;i=n;i+) pi=pi-1+i; printf(%dn,pi); return 0; 遞推思考遞推思考輸出輸出楊暉三角形的前楊暉三角形的前10行。行。楊暉三角形的前楊暉三角形的前5行如左下圖所示。行如左下圖所示。問(wèn)題分析：?jiǎn)栴}分析：觀察左上圖不太容易找到規(guī)律，但如果觀察左上圖不太容易找到規(guī)律，但如果將左上圖轉(zhuǎn)化為右上圖就不難發(fā)現(xiàn)

27、楊輝三角形其實(shí)將左上圖轉(zhuǎn)化為右上圖就不難發(fā)現(xiàn)楊輝三角形其實(shí)就是一個(gè)二維表（數(shù)組）的下三角部分。就是一個(gè)二維表（數(shù)組）的下三角部分。#include /打印楊輝三角形打印楊輝三角形void main() int i,j，a1010; for (i=0;i10;i+) ai0=1; for (i=0;i10;i+) for (j=i+1;j10;j+) aij=0; for (i=1;i10;i+) for (j=1;j=i;j+) aij=ai-1j-1+ai-1j; for (i=0;i10;i+) for (j=0;j=i;j+) printf(%4d,aij); printf(n); 遞推

28、小結(jié)遞推小結(jié)1）遞推是）遞推是從已知條件從已知條件開始；開始；2）遞推）遞推必須有明確必須有明確的通用公式；的通用公式；3）遞推）遞推必須是有限次必須是有限次運(yùn)算。運(yùn)算。11.2 遞歸遞歸遞歸的定義：遞歸的定義：在一個(gè)函數(shù)的定義中在一個(gè)函數(shù)的定義中又直接或間又直接或間接調(diào)用自身接調(diào)用自身的一種方法，它通常把一個(gè)大型的一種方法，它通常把一個(gè)大型復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解。規(guī)模較小的問(wèn)題來(lái)求解。11.2 遞歸遞歸遞歸思想：遞歸思想： 把規(guī)模大的、較難解決的問(wèn)題變成規(guī)模較小的、把規(guī)模大的、較難解決的問(wèn)題變成規(guī)模較小的、易解決的同一

29、問(wèn)題。規(guī)模較小的問(wèn)題又變成規(guī)模更小的問(wèn)易解決的同一問(wèn)題。規(guī)模較小的問(wèn)題又變成規(guī)模更小的問(wèn)題，并且小到一定程度可以直接得出它的解，從而得到原題，并且小到一定程度可以直接得出它的解，從而得到原來(lái)問(wèn)題的解。來(lái)問(wèn)題的解。 遞歸優(yōu)點(diǎn)：遞歸優(yōu)點(diǎn)：只需少量的程序就可描述出解題過(guò)程所需要的只需少量的程序就可描述出解題過(guò)程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。用遞歸算法多次重復(fù)計(jì)算，大大地減少了程序的代碼量。用遞歸算法編寫的程序結(jié)構(gòu)清晰，具有很好的可讀性。編寫的程序結(jié)構(gòu)清晰，具有很好的可讀性。 遞歸缺點(diǎn)：遞歸缺點(diǎn)：通過(guò)直接的遞歸過(guò)程和函數(shù)實(shí)現(xiàn)起來(lái)，有時(shí)效通過(guò)直接的遞歸過(guò)程和函數(shù)實(shí)現(xiàn)起來(lái)，有時(shí)效率很差（

30、用遞歸函數(shù)去求率很差（用遞歸函數(shù)去求1000!）。）。遞歸算法適用在三個(gè)場(chǎng)合遞歸算法適用在三個(gè)場(chǎng)合1) 數(shù)據(jù)數(shù)據(jù)的定義形式是遞歸的，如求的定義形式是遞歸的，如求n! ；2) 數(shù)據(jù)之間數(shù)據(jù)之間的邏輯關(guān)系（即數(shù)據(jù)結(jié)構(gòu)）是遞歸的，的邏輯關(guān)系（即數(shù)據(jù)結(jié)構(gòu)）是遞歸的，如樹、圖等的定義和操作；如樹、圖等的定義和操作；3) 某些問(wèn)題某些問(wèn)題雖然沒(méi)有明顯的遞歸關(guān)系或結(jié)構(gòu)，但雖然沒(méi)有明顯的遞歸關(guān)系或結(jié)構(gòu)，但問(wèn)題的解法是不斷重復(fù)執(zhí)行一種操作，只是問(wèn)問(wèn)題的解法是不斷重復(fù)執(zhí)行一種操作，只是問(wèn)題規(guī)模由大化小，直至某個(gè)原操作（基本操作）題規(guī)模由大化小，直至某個(gè)原操作（基本操作）就結(jié)束。例如：就結(jié)束。例如：漢諾塔問(wèn)題。漢諾

31、塔問(wèn)題。遞歸設(shè)計(jì)的要件遞歸設(shè)計(jì)的要件(1) 在函數(shù)中必須有直接或間接調(diào)用自身的語(yǔ)句；在函數(shù)中必須有直接或間接調(diào)用自身的語(yǔ)句；(2) 在使用遞歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)在使用遞歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口（或遞歸邊界）。束條件，稱為遞歸出口（或遞歸邊界）。編寫遞歸算法程序時(shí)，首先要對(duì)問(wèn)題的以下三個(gè)方面進(jìn)行分析：編寫遞歸算法程序時(shí)，首先要對(duì)問(wèn)題的以下三個(gè)方面進(jìn)行分析： u決定問(wèn)題規(guī)模的參數(shù)。決定問(wèn)題規(guī)模的參數(shù)。 需要用遞歸算法解決的問(wèn)題，其規(guī)模通常都是比較大的，在需要用遞歸算法解決的問(wèn)題，其規(guī)模通常都是比較大的，在問(wèn)題中決定規(guī)模大?。ɑ騿?wèn)題復(fù)雜程度）的量有哪些？問(wèn)題中

32、決定規(guī)模大?。ɑ騿?wèn)題復(fù)雜程度）的量有哪些？u問(wèn)題的邊界條件及邊界值。問(wèn)題的邊界條件及邊界值。 在什么情況下可以直接得出問(wèn)題的解？在什么情況下可以直接得出問(wèn)題的解？- -問(wèn)題的邊界條件及問(wèn)題的邊界條件及邊界值。邊界值。 u解決問(wèn)題的通式解決問(wèn)題的通式。 把規(guī)模大的、較難解決的問(wèn)題變成規(guī)模較小、易解決的同一把規(guī)模大的、較難解決的問(wèn)題變成規(guī)模較小、易解決的同一問(wèn)題，需要通過(guò)哪些步驟或等式來(lái)實(shí)現(xiàn)？問(wèn)題，需要通過(guò)哪些步驟或等式來(lái)實(shí)現(xiàn)？-解決遞歸問(wèn)題的難解決遞歸問(wèn)題的難點(diǎn)，把這些步驟或等式確定下來(lái)。點(diǎn)，把這些步驟或等式確定下來(lái)。 遞歸設(shè)計(jì)實(shí)例遞歸設(shè)計(jì)實(shí)例1 -哈諾（哈諾（HanoiHanoi）塔問(wèn)題：）塔

33、問(wèn)題：1)1)相傳在古代印度的相傳在古代印度的 Bramah Bramah 廟中，有位僧人整天把三根柱子廟中，有位僧人整天把三根柱子上的金盤倒來(lái)倒去，原來(lái)他是想把上的金盤倒來(lái)倒去，原來(lái)他是想把6464個(gè)一個(gè)比一個(gè)小的金盤個(gè)一個(gè)比一個(gè)小的金盤從一根柱子上移到另一根柱子上去。從一根柱子上移到另一根柱子上去。2)2)移動(dòng)規(guī)則：移動(dòng)規(guī)則：每次只允許移動(dòng)一只盤，大盤不得落在小盤上面。每次只允許移動(dòng)一只盤，大盤不得落在小盤上面。3)3)如以每秒移動(dòng)一只盤子如以每秒移動(dòng)一只盤子，按照上述規(guī)則，按照上述規(guī)則將將6464只盤子從一個(gè)柱只盤子從一個(gè)柱子移至另一個(gè)柱子上，所需時(shí)間約為子移至另一個(gè)柱子上，所需時(shí)間約為

34、58005800億年。億年。 先從最簡(jiǎn)單的情況開始分析，理出思路。先從最簡(jiǎn)單的情況開始分析，理出思路。1、在在 A 柱上只有一只盤子柱上只有一只盤子，假定盤號(hào)為，假定盤號(hào)為 1，這時(shí)，這時(shí)只需將該盤從只需將該盤從 A 搬至搬至 C，一次完成，記為，一次完成，記為: move 1# from A to C ABC12、在在 A 柱上柱上有有 2 只盤子，只盤子，1 為小盤，為小盤，2 為大盤。為大盤。第（第（1）步將步將1號(hào)盤從號(hào)盤從A移至移至B，這是為了讓，這是為了讓 2號(hào)盤能動(dòng)；號(hào)盤能動(dòng)； move 1# from A to B;第（第（2）步將步將 2 號(hào)盤從號(hào)盤從A 移至移至 C； mo

35、ve 2# from A to C;第（第（3）步再將步再將 1 號(hào)盤從號(hào)盤從 B 移至移至 C； move 1# form B to C;ABC213、在、在A柱上有柱上有3只盤子，從小到大分別為只盤子，從小到大分別為1號(hào)，號(hào)，2號(hào)，號(hào)，3號(hào)號(hào)第（第（1）步）步 ：將將1號(hào)盤和號(hào)盤和2號(hào)盤視為一個(gè)整體；先將二者號(hào)盤視為一個(gè)整體；先將二者作為整體從作為整體從A移至移至B，給，給3號(hào)盤創(chuàng)造能夠一次移至號(hào)盤創(chuàng)造能夠一次移至C的機(jī)的機(jī)會(huì)。會(huì)。這一步記為這一步記為 move( 2, A, C, B) 含義：含義：將上面的將上面的2只盤子作為整體從只盤子作為整體從A借助借助C移至移至B。第（第（2）步）

36、步 ：將將3號(hào)盤從號(hào)盤從A移至移至C，一次到位。記為，一次到位。記為 move 3# from A to C第（第（3）步）步 ：處于處于B上的作為一個(gè)整體的上的作為一個(gè)整體的2只盤子，再移只盤子，再移至至C。這一步記為。這一步記為 move( 2, B, A, C)含義：含義：將將2只盤子作為整體從只盤子作為整體從B借助借助A移至移至C。move (3, A, B, C)move (2, A, C, B)move (1, A, B, C)move (2, B, A, C)ABC213移動(dòng)移動(dòng)3 3個(gè)盤子的分解：個(gè)盤子的分解：move (3, A, B, C)move (2, A, C, B)

37、move (1, A, B, C)move (1, A, C, B)move (1, C, A, B)move (1, A, B, C)move (2, B, A, C)move (1, B, C, A)move (1, B, A, C)move (1, A, B, C)ABC2134、從題目的約束條件看，大盤上可以隨便摞小、從題目的約束條件看，大盤上可以隨便摞小盤，相反則不允許。在將盤，相反則不允許。在將1號(hào)和號(hào)和2號(hào)盤當(dāng)整體從號(hào)盤當(dāng)整體從A移至移至B的過(guò)程中的過(guò)程中 move(2, A, C, B) 實(shí)際上是分實(shí)際上是分解為以下三步解為以下三步第（第（1）.1步：步：move 1# for

38、m A to C;第（第（1）.2步：步：move 2# form A to B;第（第（1）.3步：步：move 1# form C to B;經(jīng)過(guò)以上步驟，將經(jīng)過(guò)以上步驟，將 1 號(hào)和號(hào)和 2 號(hào)盤作為整體號(hào)盤作為整體從從 A 移至移至 B，為，為 3 號(hào)盤從號(hào)盤從 A 移至移至 C 創(chuàng)造了條創(chuàng)造了條件。同樣，件。同樣，3號(hào)盤一旦到了號(hào)盤一旦到了 C，就要考慮如何，就要考慮如何實(shí)現(xiàn)將實(shí)現(xiàn)將 1 號(hào)和號(hào)和 2 號(hào)盤當(dāng)整體從號(hào)盤當(dāng)整體從 B 移至移至 C 的過(guò)的過(guò)程了。實(shí)際上程了。實(shí)際上 move( 2, B, A, C ) 也要分解為也要分解為三步：三步：第（第（3）.1步：步：move 1

39、# form B to A;第（第（3）.2步：步：move 2# form B to C;第（第（3）.3步：步：move 1# form A to C;5、move(2, A, C, B) 是將是將 2 只盤子從只盤子從 A 搬至搬至 B，但沒(méi)有但沒(méi)有 C 不行，因?yàn)榈冢ú恍校驗(yàn)榈冢?）.1步就要將步就要將 1# 盤盤從從 A 移到移到 C，給，給2 #盤創(chuàng)造條件從盤創(chuàng)造條件從 A 移至移至 B，然后再把然后再把 1# 盤從盤從 C 移至移至 B。 注意：在注意：在move(2, A, C, B)中，中， C 是一個(gè)橋梁用。是一個(gè)橋梁用。move(n, A, B, C) 分解為分解為3步

40、：步：(1) move(n-1, A, C, B) ：將：將 n-1 只盤子作為一個(gè)整體只盤子作為一個(gè)整體從從A經(jīng)經(jīng)C移到移到B；(2) 輸出輸出n：A to C：將將n號(hào)盤從號(hào)盤從A移到移到C，是直接可，是直接可解結(jié)點(diǎn)；解結(jié)點(diǎn)；(3) move(n-1, B, A, C)：將將n-1只盤子作為一個(gè)整體從只盤子作為一個(gè)整體從B經(jīng)經(jīng)A移到移到C。-遞歸遞歸實(shí)現(xiàn)實(shí)現(xiàn) move(n-1, A, C, B)要分為要分為 3 步：步：第第1步：步：將將 n-2 只盤子作為一個(gè)整體從只盤子作為一個(gè)整體從A經(jīng)經(jīng)B到到C - move(n-2, A, B, C)；第第2步：步：第第n-1號(hào)盤子從號(hào)盤子從A直接

41、移至直接移至B，即，即 n-1:A to B；第第3步：步：將將 n-2 只盤子作為一個(gè)整體從只盤子作為一個(gè)整體從C經(jīng)經(jīng)A移至移至B - move(n-2, C, A, B)；/m表示盤子數(shù)目表示盤子數(shù)目; a，b，c表示柱子標(biāo)號(hào)表示柱子標(biāo)號(hào) void move(int m, char a, char b, char c) if (m=1)/ 如果如果1個(gè)盤子，則為直接可解結(jié)點(diǎn)個(gè)盤子，則為直接可解結(jié)點(diǎn) step+;/ 步數(shù)加步數(shù)加1 printf(n%d move 1# from %c to %cn,step,a,c); else move(m-1,a,c,b);/ 遞歸調(diào)用遞歸調(diào)用move(

42、m-1) /直接可解結(jié)點(diǎn)直接可解結(jié)點(diǎn),輸出移盤信息輸出移盤信息 step+;/ 步數(shù)加步數(shù)加1 printf(n%d move %d# from %c to %cn,step,m,a,c ); move(m-1,b,a,c);/ 遞歸調(diào)用遞歸調(diào)用move(m-1) #include / 用遞歸求解用遞歸求解Hanoi問(wèn)題問(wèn)題 int step=0; / 整型全局變量，移動(dòng)步數(shù)整型全局變量，移動(dòng)步數(shù) int main() int n; printf(請(qǐng)輸入盤數(shù)請(qǐng)輸入盤數(shù) n=); scanf(%d,&n); printf(在在3根柱子上移根柱子上移 %d 只盤的步驟為只盤的步驟為:,n); mo

43、ve(n,A,B,C); return 0; 該題是該題是2000年全國(guó)青少年信息學(xué)奧林匹克的一道試題。敘述如下：年全國(guó)青少年信息學(xué)奧林匹克的一道試題。敘述如下： 1）一條小溪尺寸不大，一條小溪尺寸不大，青蛙可以從左岸跳到右岸青蛙可以從左岸跳到右岸，在左岸有一石，在左岸有一石柱柱L，面積只容得下一只青蛙落腳，同樣右岸也有一石柱，面積只容得下一只青蛙落腳，同樣右岸也有一石柱R，面，面積也只容得下一只青蛙落腳。積也只容得下一只青蛙落腳。2）有一隊(duì)青蛙從小到大編號(hào)：有一隊(duì)青蛙從小到大編號(hào)：1，2，n。3）初始時(shí)：）初始時(shí)：青蛙只能趴在左岸的石頭青蛙只能趴在左岸的石頭 L 上，按編號(hào)一個(gè)落一個(gè)，上，按

44、編號(hào)一個(gè)落一個(gè)，小的落在大的上面。不允許大的在小的上面。小的落在大的上面。不允許大的在小的上面。遞歸設(shè)計(jì)實(shí)例遞歸設(shè)計(jì)實(shí)例2該題是該題是2000年全國(guó)青少年信息學(xué)奧林匹克的一道試題。敘述如下：年全國(guó)青少年信息學(xué)奧林匹克的一道試題。敘述如下：4）在小溪中有在小溪中有S個(gè)石柱，有個(gè)石柱，有y片荷葉，規(guī)定溪中的片荷葉，規(guī)定溪中的石柱如有多只青石柱如有多只青蛙也是蛙也是大在下、小在上，而且大在下、小在上，而且必須編號(hào)相鄰必須編號(hào)相鄰；5）對(duì)于對(duì)于荷葉只允許一只青蛙落腳荷葉只允許一只青蛙落腳，不允許多只落在其上；，不允許多只落在其上；6）對(duì)于右岸的對(duì)于右岸的石柱石柱R，與左岸的石柱，與左岸的石柱L一樣允許

45、多個(gè)青蛙落腳一樣允許多個(gè)青蛙落腳，但，但須一個(gè)落一個(gè)，小的在上，大的在下，且編號(hào)相鄰；須一個(gè)落一個(gè)，小的在上，大的在下，且編號(hào)相鄰；7）當(dāng)青蛙從左岸的當(dāng)青蛙從左岸的L上跳走后就不允許再跳回來(lái)；同樣，從左岸上跳走后就不允許再跳回來(lái)；同樣，從左岸L上跳至右岸上跳至右岸R，或從溪中荷葉、溪中石柱跳至右岸，或從溪中荷葉、溪中石柱跳至右岸R上的青蛙也上的青蛙也不允許再離開。不允許再離開。問(wèn)：?jiǎn)枺涸谝阎杏性谝阎杏?s 根石柱根石柱和和 y 片片荷葉的情況下，最多能跳過(guò)多少荷葉的情況下，最多能跳過(guò)多少只青蛙？只青蛙？思路：思路：先從柱子和荷業(yè)較少的情況開始分析，先從柱子和荷業(yè)較少的情況開始分析，對(duì)多

46、個(gè)因素作分解，找出規(guī)律。對(duì)多個(gè)因素作分解，找出規(guī)律。1、 定義函數(shù)定義函數(shù) Jump ( s ,y ) 最多可跳過(guò)河的青蛙數(shù)最多可跳過(guò)河的青蛙數(shù) 其中：其中： s 河中柱子數(shù)河中柱子數(shù) y 荷葉數(shù)荷葉數(shù)2、河中無(wú)柱子：、河中無(wú)柱子：S=0，即，即Jump(0,y) y=1時(shí)，河中有一片荷葉，起始時(shí)時(shí)，河中有一片荷葉，起始時(shí)L上有兩只青蛙，上有兩只青蛙，1#在在2#上面。上面。 第一步：第一步：1# 跳到荷葉上；跳到荷葉上； 第二步：第二步：2# 從從L直接跳至直接跳至R上；上； 第三步：第三步：1# 再?gòu)暮扇~跳至再?gòu)暮扇~跳至R上。上。 結(jié)論：結(jié)論：Jump(0,1)=2； / 河中有河中有1片

47、片荷葉，能過(guò)荷葉，能過(guò)2只只青蛙。青蛙。左岸L右岸R荷葉當(dāng)當(dāng)y=2時(shí)河中有兩片荷葉時(shí)，起始時(shí)：時(shí)河中有兩片荷葉時(shí)，起始時(shí)：1#，2#，3# -共共3只青蛙落在只青蛙落在L上，上， 第一步：第一步：1# 從從L跳至葉跳至葉 1上，上， 第二步：第二步：2# 從從L跳至葉跳至葉 2上，上， 第三步：第三步：3# 從從L直接跳至直接跳至R上，上， 第四步：第四步：2# 從葉從葉2跳至跳至R上，上， 第五步：第五步：1# 從葉從葉1跳至跳至R上上 結(jié)論：結(jié)論： Jump(0,2)=3；/ 河中有河中有2片荷葉，能過(guò)片荷葉，能過(guò)3只青蛙。只青蛙。左岸左岸L右岸右岸R荷葉荷葉2荷葉荷葉12、河中無(wú)柱子：、

48、河中無(wú)柱子：S=0，即，即Jump(0,y)小結(jié)：小結(jié)： Jump ( 0 ,1 ) = 2 ； -能跳過(guò)能跳過(guò)2只青蛙只青蛙 Jump ( 0 , 2 ) = 3 ； -能跳過(guò)能跳過(guò)3只青蛙只青蛙思考：思考： Jump(0,3) = ? Jump(0,4) = ? Jump(0,y) = ?歸納法：歸納法：Jump(0,y)=y+1含義：含義：沒(méi)有石柱時(shí)，沒(méi)有石柱時(shí)，過(guò)河青蛙數(shù)過(guò)河青蛙數(shù)=荷葉數(shù)荷葉數(shù)+13、河中有石柱、河中有石柱Jump(S, y) = ？ 一個(gè)最簡(jiǎn)單情況：一個(gè)最簡(jiǎn)單情況：S=1、y=1時(shí)：時(shí)： 1# 青蛙從青蛙從 L Y； 2# 青蛙從青蛙從 L S； 1# 青蛙從青蛙從

49、 Y S； 3# 青蛙從青蛙從 L Y； 4# 青蛙從青蛙從 L R；左岸左岸L右岸右岸R荷葉荷葉Y石柱石柱S 3# 青蛙從青蛙從 Y R； 1# 青蛙從青蛙從 S Y； 2# 青蛙從青蛙從 S R； 1# 青蛙從青蛙從 Y R；結(jié)論：結(jié)論：Jump(1,1)=4 2*Jump(0,1)=2*2參照漢諾塔問(wèn)題將借助參照漢諾塔問(wèn)題將借助一個(gè)石柱一個(gè)石柱( s=1 )、一個(gè)荷葉、一個(gè)荷葉( y=1 )的青蛙的青蛙跳躍問(wèn)題分成五個(gè)步驟：跳躍問(wèn)題分成五個(gè)步驟：第一步：第一步：借助借助荷葉荷葉將將左左岸上面的若干青蛙（此時(shí)是岸上面的若干青蛙（此時(shí)是1#與與2#兩只）兩只）跳到跳到石柱石柱上暫存；上暫存；

50、第二步：第二步：左岸左岸下一下一只青蛙（此時(shí)是只青蛙（此時(shí)是3#）跳到）跳到荷葉荷葉上；上；第三步：第三步：左岸左岸再下一只青蛙再下一只青蛙（此時(shí)是（此時(shí)是4#）跳到）跳到右岸；右岸；第四步：荷葉暫存的青蛙（第四步：荷葉暫存的青蛙（ 3# ）跳到）跳到到右岸；到右岸；第五步：石柱上暫存青蛙（第五步：石柱上暫存青蛙（1#、2#）借助荷葉完成到跳到右岸。借助荷葉完成到跳到右岸。以上的以上的石柱石柱如果看成右岸如果看成右岸(步驟步驟1)或左岸（步驟或左岸（步驟2）的話，進(jìn)一）的話，進(jìn)一步的分析，還可以將上述步的分析，還可以將上述五個(gè)步驟五個(gè)步驟分成以下兩個(gè)階段：分成以下兩個(gè)階段： 第一、五兩步第一、

51、五兩步實(shí)際上完成的就是青蛙借助一個(gè)荷葉跳躍的實(shí)際上完成的就是青蛙借助一個(gè)荷葉跳躍的過(guò)程，并且這兩步的對(duì)象是同一批青蛙，青蛙個(gè)數(shù)是過(guò)程，并且這兩步的對(duì)象是同一批青蛙，青蛙個(gè)數(shù)是Jump(0,1)。 第二、三、四步第二、三、四步實(shí)際上完成的也是青蛙借助一個(gè)荷葉跳躍實(shí)際上完成的也是青蛙借助一個(gè)荷葉跳躍的過(guò)程，青蛙個(gè)數(shù)是的過(guò)程，青蛙個(gè)數(shù)是Jump(0,1)。所以：所以：Jump(1,1)的值是的值是Jump(0,1)+ Jump(0,1) 即：即：Jump(1,1)=2*Jump(0,1)；對(duì)于借助對(duì)于借助s個(gè)石柱、個(gè)石柱、y個(gè)荷葉的青蛙跳躍過(guò)程也可以類似的歸納出來(lái)，個(gè)荷葉的青蛙跳躍過(guò)程也可以類似的歸

52、納出來(lái)，這個(gè)實(shí)現(xiàn)步驟可以分成七個(gè)步驟：這個(gè)實(shí)現(xiàn)步驟可以分成七個(gè)步驟： 第一步：第一步：借助所有借助所有荷葉荷葉以及其余以及其余石柱石柱將左岸上面的若干青蛙跳到將左岸上面的若干青蛙跳到第一第一個(gè)石柱上個(gè)石柱上暫存；暫存； 第二步：第二步：左岸左岸余下的青蛙余下的青蛙借助其它可用的借助其它可用的石柱以及所有荷葉石柱以及所有荷葉跳到跳到其它石柱其它石柱上；上； 第三步：第三步：左岸左岸再余下的青蛙跳到所有荷葉再余下的青蛙跳到所有荷葉上；上； 第四步：第四步：左岸左岸再下一只青蛙完成到右岸的直接跳躍再下一只青蛙完成到右岸的直接跳躍-最大最大1只只 第五步：第五步：荷葉暫存的青蛙完成到右岸的跳躍；荷葉暫

53、存的青蛙完成到右岸的跳躍； 第六步：第六步：除了第一個(gè)外其余石柱上暫存青蛙完成到右岸的跳躍；除了第一個(gè)外其余石柱上暫存青蛙完成到右岸的跳躍； 第七步：第七步：第一個(gè)石柱上暫存的青蛙借助其余石柱以及所有荷葉完第一個(gè)石柱上暫存的青蛙借助其余石柱以及所有荷葉完成到右岸的跳躍；成到右岸的跳躍；如果以上的石柱在跳躍過(guò)程中可以看成右岸或左岸，這七個(gè)如果以上的石柱在跳躍過(guò)程中可以看成右岸或左岸，這七個(gè)步驟也可以簡(jiǎn)化成兩個(gè)階段：步驟也可以簡(jiǎn)化成兩個(gè)階段： 第一、七兩步實(shí)際上是青蛙借助第一、七兩步實(shí)際上是青蛙借助s-1個(gè)石柱以及個(gè)石柱以及y個(gè)荷葉個(gè)荷葉，完，完成從左岸到第一個(gè)石柱，再到右岸的跳躍的過(guò)程，而這兩成

54、從左岸到第一個(gè)石柱，再到右岸的跳躍的過(guò)程，而這兩步的對(duì)象是同一批青蛙，步的對(duì)象是同一批青蛙，青蛙個(gè)數(shù)是青蛙個(gè)數(shù)是Jump(s-1,y)。 第二步到第六步完成的是左岸的青蛙借助剩余的第二步到第六步完成的是左岸的青蛙借助剩余的n-1個(gè)石柱個(gè)石柱以及所有以及所有y個(gè)荷葉跳躍到右岸的過(guò)程，青蛙個(gè)數(shù)是個(gè)荷葉跳躍到右岸的過(guò)程，青蛙個(gè)數(shù)是Jump(s-1,y)。結(jié)論：結(jié)論：Jump(s, y)是是Jump(s-1,y)+ Jump(s-1,y)。 即：即：Jump(s,y)=2*Jump(s-1,y)；注意：注意：當(dāng)石柱數(shù)目為當(dāng)石柱數(shù)目為0是不需要遞歸的，此時(shí)跳躍的青蛙數(shù)目是不需要遞歸的，此時(shí)跳躍的青蛙數(shù)目

55、為為荷葉數(shù)目荷葉數(shù)目+1。即遞歸的結(jié)束條件為：即遞歸的結(jié)束條件為：Jump(0,y)=y+1;LRYS2876543S1214321例如：荷葉數(shù)是例如：荷葉數(shù)是1、石柱數(shù)是、石柱數(shù)是2的的Jump(2,1)=2* Jump(1,1)= 8 int Jump(int s,int y) /青蛙過(guò)河青蛙過(guò)河遞歸函數(shù)遞歸函數(shù) int k;if (s=0) / s=0表示無(wú)石柱表示無(wú)石柱 , 則為直接可解結(jié)點(diǎn)則為直接可解結(jié)點(diǎn) k=y+1;else / 如果如果 r 不為不為0 , 則要?jiǎng)t要 Jump(r-1,z) k=2*Jump(s-1,y);return(k); #include void main

56、( ) int s,y,sum; / s 為河中石柱數(shù)為河中石柱數(shù) , y為荷葉數(shù)為荷葉數(shù)printf(請(qǐng)輸入石柱數(shù)請(qǐng)輸入石柱數(shù)s= ); scanf(%d,&s);printf(請(qǐng)輸入荷葉數(shù)請(qǐng)輸入荷葉數(shù)y= );scanf(%d,&y);sum=Jump(s,y); printf(Jump(%d,%d)=%dn,s,y,sum); 漢諾塔游戲與青蛙跳河的不同漢諾塔游戲與青蛙跳河的不同1）初始位置、結(jié)束位置不同；初始位置、結(jié)束位置不同；2）在漢諾塔游戲中，所搬盤子總數(shù)在漢諾塔游戲中，所搬盤子總數(shù)n的值決定第的值決定第一個(gè)盤子是搬到一個(gè)盤子是搬到B、還是搬到、還是搬到C；3）在青蛙跳河中，青蛙總

57、數(shù)在青蛙跳河中，青蛙總數(shù)n的值不決定第一個(gè)的值不決定第一個(gè)青蛙搬到那個(gè)石柱上。青蛙搬到那個(gè)石柱上。 選擇排序、冒泡排序的排序思路比較簡(jiǎn)單，但是排序效率較選擇排序、冒泡排序的排序思路比較簡(jiǎn)單，但是排序效率較低，不能滿足需求（比如在低，不能滿足需求（比如在OJ或比賽題目中）。或比賽題目中）。效率更高的排序方法呢？效率更高的排序方法呢？ 快速排序快速排序是利用是利用分治遞歸分治遞歸技術(shù)實(shí)現(xiàn)的一種高效的方法。技術(shù)實(shí)現(xiàn)的一種高效的方法。 分治法分治法簡(jiǎn)而言之就是簡(jiǎn)而言之就是“分而治之分而治之”，即把一個(gè)復(fù)雜的問(wèn)題分，即把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題成兩個(gè)或更多的子問(wèn)題

58、，再把子問(wèn)題分成更小的子問(wèn)題直到最后分解成的子問(wèn)題可以直接求解，原問(wèn)題的直到最后分解成的子問(wèn)題可以直接求解，原問(wèn)題的解即子問(wèn)解即子問(wèn)題的解的合并。題的解的合并。遞歸設(shè)計(jì)實(shí)例遞歸設(shè)計(jì)實(shí)例3-快速排序快速排序 將要求解的較大規(guī)模的問(wèn)題分割成k個(gè)更小規(guī)模的子問(wèn)題。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 對(duì)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則對(duì)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模再劃分子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。足夠小，很容易求出其解為止。nT(n)=n/2T(n/4)T(n

59、/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。來(lái)問(wèn)題的解?？焖倥判虻乃枷肟焖倥判虻乃枷肟焖倥判蚴腔诜种芜f歸的思想來(lái)實(shí)現(xiàn)的：快速排序是基于分治遞歸的思想來(lái)實(shí)現(xiàn)的：1）設(shè)要排序的數(shù)組是設(shè)要排序的數(shù)組是a0an-1；2）任意選取一個(gè)數(shù)據(jù)（通常選用第一個(gè)數(shù)據(jù)）作為關(guān)任意選取一個(gè)數(shù)據(jù)（通常選用第一個(gè)數(shù)據(jù)

60、）作為關(guān)鍵數(shù)據(jù)；鍵數(shù)據(jù)；3）將所有比關(guān)鍵數(shù)據(jù)小的數(shù)都放到它前面（左），所將所有比關(guān)鍵數(shù)據(jù)小的數(shù)都放到它前面（左），所有比關(guān)鍵數(shù)據(jù)大的數(shù)都放到它后面（右）有比關(guān)鍵數(shù)據(jù)大的數(shù)都放到它后面（右）-這個(gè)過(guò)程稱為一趟快速排序。這個(gè)過(guò)程稱為一趟快速排序。4）對(duì)關(guān)鍵數(shù)據(jù)前、后的數(shù)據(jù)再分別進(jìn)行一趟快速排序，對(duì)關(guān)鍵數(shù)據(jù)前、后的數(shù)據(jù)再分別進(jìn)行一趟快速排序，直到直到參加排序參加排序的數(shù)字是一個(gè)為止。的數(shù)字是一個(gè)為止。一趟快速排序的算法步驟如下：一趟快速排序的算法步驟如下： 1）設(shè)置兩個(gè)變量設(shè)置兩個(gè)變量i、j，排序初：，排序初：i=0，j=n-1； 2）以以 a0 作為關(guān)鍵數(shù)據(jù)，即作為關(guān)鍵數(shù)據(jù)，即 key=a0； 3