第五講--遞推與遞歸

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

2、 = 1， 若：若： n2，則，則F(n)= F(n-1)+F(n-2)注意：注意： 1）每個數(shù)據(jù)項都和它前面的若干個數(shù)據(jù)項（或后面的若干每個數(shù)據(jù)項都和它前面的若干個數(shù)據(jù)項（或后面的若干個數(shù)據(jù)項）有一定的關(guān)聯(lián)個數(shù)據(jù)項）有一定的關(guān)聯(lián)-遞推關(guān)系式。遞推關(guān)系式。 2）從初始的一個或若干數(shù)據(jù)項出發(fā)，通過遞推關(guān)系式逐步從初始的一個或若干數(shù)據(jù)項出發(fā)，通過遞推關(guān)系式逐步推進(jìn)，從而得到最終結(jié)果。推進(jìn)，從而得到最終結(jié)果。11.1 遞遞 推推注意：注意：3）遞推必須有）遞推必須有 “邊界邊界”。4）解決遞推類型問題有三個重點(diǎn)：）解決遞推類型問題有三個重點(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)問題的方向，遞推分為：按照推導(dǎo)問題的方向，遞推分為：l 順推法：順推法：從初始數(shù)據(jù)開始推理。從初始數(shù)據(jù)開始推理。 例如：例如：n=0n=0時，時，n!=1n!=1； n1n1時，時，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天摘下若干個桃子，當(dāng)即吃了一半天摘下若干個桃子，當(dāng)即吃了

4、一半又一個。第又一個。第2天又把剩下的桃吃了一半又一個，以天又把剩下的桃吃了一半又一個，以后每天都吃前一天剩下的桃子的一半又一個，到第后每天都吃前一天剩下的桃子的一半又一個，到第10天猴子想吃時，只剩下一個桃子。天猴子想吃時，只剩下一個桃子。問：問：猴子第猴子第1天一共摘了多少桃子天一共摘了多少桃子? 分析：分析：已知條件：已知條件：第第 10 天剩下天剩下 1 個桃子；個桃子；隱含條件：隱含條件：每一次前一天的桃子個數(shù)等于后一天每一次前一天的桃子個數(shù)等于后一天桃子的個數(shù)加桃子的個數(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) 半夜里，一只猴子偷偷起來，把桃子均分成五堆后，發(fā)半夜里，一只猴子偷偷起來，把桃子均分成五堆后，發(fā)現(xiàn)還多一個，它吃掉這桃子，并拿走了其中一堆。現(xiàn)還多一個，它吃掉這桃子，并拿走了其中一堆。3)第二只猴子醒來，又把桃子均分成五堆后，還是多了一第二只猴子醒來，

6、又把桃子均分成五堆后，還是多了一個，它也吃掉這個桃子，并拿走了其中一堆。個，它也吃掉這個桃子，并拿走了其中一堆。第三只，第四只，第五只猴子都依次如此分食桃子。第三只，第四只，第五只猴子都依次如此分食桃子。問：問：五只猴子采得一堆桃子五只猴子采得一堆桃子數(shù)最少應(yīng)該有幾個呢？數(shù)最少應(yīng)該有幾個呢？逆推法逆推法算法分析：算法分析： 先要找第先要找第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通過遞推，求出通過遞推，求出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è)計實例遞推設(shè)計實例例例11.1：母牛的故事：母牛的故事 問題描述：問題描述：有一頭母牛，它每年年初生一頭小有一頭母牛，它每年年初生一頭小母牛。每頭小母牛從第四個年頭開始，母牛。每頭小母牛從第四個年頭開始，每年年每年年初也生一頭小母牛。初也生一頭小母牛。編程實現(xiàn)：編程實現(xiàn)：在第在第n年的時候，共有多少頭母牛？年的時候，共有多少頭母牛？例例11.1：母牛的故事：母牛的故事-順推法順推法 設(shè)數(shù)組設(shè)數(shù)組f(i)表示第表示第 i 年的母?？倲?shù)，則第年的母牛總數(shù)，則第 n 年的母?？倲?shù)為年的母?？倲?shù)為f

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

10、生育，所以今年可以生育的母牛的數(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 骨牌問題骨牌問題-順推法順推法例例11.2 骨牌問題骨牌問題-順推法順推法例例11.2 骨牌問題骨牌問題-順推法順推法 例例11.2 骨牌問題骨牌問題-順推法順推法因此，因此，n塊骨牌的鋪法塊骨牌的鋪法是是首塊骨牌橫鋪方式的首塊骨牌橫鋪方式的鋪法與豎鋪方式的鋪法之和。鋪法與豎鋪方式的鋪法之和。 即：即： f(n)=f(n-1)+f(n-2)邊界：邊

12、界： f(1)=1 ，f(2)=2例例11.2 骨牌問題骨牌問題-順推法順推法遞推公式遞推公式 #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 骨牌問題骨牌問題#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 骨牌問題骨牌問題-順推法順推法問題描述：問題描述： 設(shè)有一個共有設(shè)有一個共有n級的樓梯，某人每步可走級的樓梯，某人每步可走1級，也可走級，也可走2級，也可走級，也可走3級。級。問：問：求從底層開始走完全部樓梯的有多少種走法。求從底層開始走完全部樓梯的有多少種走法。例如，當(dāng)例如，當(dāng)n=3時，走法如下：時，走法如下： 1+1+1 1+2 2+1 3思考：上樓問題思考：上樓問題n=3，共有，共有4種走法種走法n的值的值 走法走法f(n) 1 1 2 2 3 4 4 7從遞推的思想出發(fā)從遞推的思想出發(fā)，可以設(shè)想，從第，可以設(shè)想，從第4 4項項開始，每開始，每1

14、1項等于前面項等于前面3 3項的和。項的和。上樓問題上樓問題-算法分析算法分析 f(n)=f(n-1)+f(n-2)+f(n-3)-遞推公式遞推公式 f(1)=1 , f(2)=2 , f(3)=4 -遞推邊界遞推邊界 #include /上樓問題上樓問題 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、 錯排信件錯排信件問題描述：問題描述：某人寫了某人寫了n封信封信和和n個信封個信封，所所有的信都裝錯了信封。有的信都裝錯了信封。要求：若要求：若所有的信都裝錯信封，共有多少所有的信都裝錯信封，共有多少種不同情況？種不同情況？例例11.3 錯排信件錯排信件找規(guī)律：找規(guī)律：對對n封信封信以及以及n個信封個信封各自按照從各自按照從 1.n 進(jìn)行進(jìn)行編號；編號； f(n)-n個編號的信個編號的信放在放在n個編號的信封，個編號的信封，各各不對應(yīng)的方法數(shù)；不對應(yīng)的方法數(shù)；f(n-1)-n-1個編號的信放在個編號的信放在n-1個編號位置的個編號位置的信封，各不對應(yīng)的方法數(shù)。信封，各不對應(yīng)的方法數(shù)。例例11.

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

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 錯排信件錯排信件 #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 馬踏過河卒馬踏過河卒-選講選講 棋盤上棋盤上A點(diǎn)有一個過河卒，需要走到目標(biāo)點(diǎn)有一個過河卒，需要走到目標(biāo)B點(diǎn)。點(diǎn)。 卒行走的規(guī)則：可以向下、或者向右

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

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

20、或是從上面過從左邊過來（左點(diǎn)）或是從上面過來（上點(diǎn)），所以根據(jù)加法原理，過河卒到達(dá)某一點(diǎn)來（上點(diǎn)），所以根據(jù)加法原理，過河卒到達(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 馬踏過河卒馬踏過河卒-選講選講 用二維數(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）是否是對方馬的控制點(diǎn)；）是否是對方馬的控制點(diǎn)； 若若gij=0gij=0表示不是對方馬的控制點(diǎn)，表示不是對方馬的控制點(diǎn)，gij=1gij=1表示是對表示是對方馬的控制點(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 / 馬踏過河卒馬踏過河卒 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 馬踏過河卒馬踏過河卒改進(jìn)改進(jìn)為了更簡潔地表示馬的控制點(diǎn)，可以引入兩個一維數(shù)組

24、，分別用來為了更簡潔地表示馬的控制點(diǎn)，可以引入兩個一維數(shù)組，分別用來統(tǒng)計從馬的初始位置可以橫向移動的位移與縱向移動的位移。統(tǒ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 馬踏過河卒馬踏過河卒 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 / 用遞推求解用遞推求解-切餅問題切餅問題 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行如左下圖所示。行如左下圖所示。問題分析：問題分析：觀察左上圖不太容易找到規(guī)律，但如果觀察左上圖不太容易找到規(guī)律，但如果將左上圖轉(zhuǎn)化為右上圖就不難發(fā)現(xiàn)

27、楊輝三角形其實將左上圖轉(zhuǎn)化為右上圖就不難發(fā)現(xiàn)楊輝三角形其實就是一個二維表（數(shù)組）的下三角部分。就是一個二維表（數(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 遞歸遞歸遞歸的定義：遞歸的定義：在一個函數(shù)的定義中在一個函數(shù)的定義中又直接或間又直接或間接調(diào)用自身接調(diào)用自身的一種方法，它通常把一個大型的一種方法，它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解。規(guī)模較小的問題來求解。11.2 遞歸遞歸遞歸思想：遞歸思想： 把規(guī)模大的、較難解決的問題變成規(guī)模較小的、把規(guī)模大的、較難解決的問題變成規(guī)模較小的、易解決的同一

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

30、用遞歸函數(shù)去求率很差（用遞歸函數(shù)去求1000!）。）。遞歸算法適用在三個場合遞歸算法適用在三個場合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) 某些問題某些問題雖然沒有明顯的遞歸關(guān)系或結(jié)構(gòu)，但雖然沒有明顯的遞歸關(guān)系或結(jié)構(gòu)，但問題的解法是不斷重復(fù)執(zhí)行一種操作，只是問問題的解法是不斷重復(fù)執(zhí)行一種操作，只是問題規(guī)模由大化小，直至某個原操作（基本操作）題規(guī)模由大化小，直至某個原操作（基本操作）就結(jié)束。例如：就結(jié)束。例如：漢諾塔問題。漢諾

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

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

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

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

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

36、步 ：將將3號盤從號盤從A移至移至C，一次到位。記為，一次到位。記為 move 3# from A to C第（第（3）步）步 ：處于處于B上的作為一個整體的上的作為一個整體的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移動移動3 3個盤子的分解：個盤子的分解：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號和號和2號盤當(dāng)整體從號盤當(dāng)整體從A移至移至B的過程中的過程中 move(2, A, C, B) 實際上是分實際上是分解為以下三步解為以下三步第（第（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)過以上步驟，將經(jīng)過以上步驟，將 1 號和號和 2 號盤作為整體號盤作為整體從從 A 移至移至 B，為，為 3 號盤從號盤從 A 移至移至 C 創(chuàng)造了條創(chuàng)造了條件。同樣，件。同樣，3號盤一旦到了號盤一旦到了 C，就要考慮如何，就要考慮如何實現(xiàn)將實現(xiàn)將 1 號和號和 2 號盤當(dāng)整體從號盤當(dāng)整體從 B 移至移至 C 的過的過程了。實際上程了。實際上 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，但沒有但沒有 C 不行，因為第（不行，因為第（1）.1步就要將步就要將 1# 盤盤從從 A 移到移到 C，給，給2 #盤創(chuàng)造條件從盤創(chuàng)造條件從 A 移至移至 B，然后再把然后再把 1# 盤從盤從 C 移至移至 B。 注意：在注意：在move(2, A, C, B)中，中， C 是一個橋梁用。是一個橋梁用。move(n, A, B, C) 分解為分解為3步

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

41、移至直接移至B，即，即 n-1:A to B；第第3步：步：將將 n-2 只盤子作為一個整體從只盤子作為一個整體從C經(jīng)經(jīng)A移至移至B - move(n-2, C, A, B)；/m表示盤子數(shù)目表示盤子數(shù)目; a，b，c表示柱子標(biāo)號表示柱子標(biāo)號 void move(int m, char a, char b, char c) if (m=1)/ 如果如果1個盤子，則為直接可解結(jié)點(diǎn)個盤子，則為直接可解結(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問題問題 int step=0; / 整型全局變量，移動步數(shù)整型全局變量，移動步數(shù) int main() int n; printf(請輸入盤數(shù)請輸入盤數(shù) n=); scanf(%d,&n); printf(在在3根柱子上移根柱子上移 %d 只盤的步驟為只盤的步驟為:,n); mo

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

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

45、多個青蛙落腳一樣允許多個青蛙落腳，但，但須一個落一個，小的在上，大的在下，且編號相鄰；須一個落一個，小的在上，大的在下，且編號相鄰；7）當(dāng)青蛙從左岸的當(dāng)青蛙從左岸的L上跳走后就不允許再跳回來；同樣，從左岸上跳走后就不允許再跳回來；同樣，從左岸L上跳至右岸上跳至右岸R，或從溪中荷葉、溪中石柱跳至右岸，或從溪中荷葉、溪中石柱跳至右岸R上的青蛙也上的青蛙也不允許再離開。不允許再離開。問：問：在已知溪中有在已知溪中有 s 根石柱根石柱和和 y 片片荷葉的情況下，最多能跳過多少荷葉的情況下，最多能跳過多少只青蛙？只青蛙？思路：思路：先從柱子和荷業(yè)較少的情況開始分析，先從柱子和荷業(yè)較少的情況開始分析，對多

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

47、片荷葉，能過荷葉，能過2只只青蛙。青蛙。左岸L右岸R荷葉當(dāng)當(dāng)y=2時河中有兩片荷葉時，起始時：時河中有兩片荷葉時，起始時：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片荷葉，能過片荷葉，能過3只青蛙。只青蛙。左岸左岸L右岸右岸R荷葉荷葉2荷葉荷葉12、河中無柱子：、

48、河中無柱子：S=0，即，即Jump(0,y)小結(jié)：小結(jié)： Jump ( 0 ,1 ) = 2 ； -能跳過能跳過2只青蛙只青蛙 Jump ( 0 , 2 ) = 3 ； -能跳過能跳過3只青蛙只青蛙思考：思考： Jump(0,3) = ? Jump(0,4) = ? Jump(0,y) = ?歸納法：歸納法：Jump(0,y)=y+1含義：含義：沒有石柱時，沒有石柱時，過河青蛙數(shù)過河青蛙數(shù)=荷葉數(shù)荷葉數(shù)+13、河中有石柱、河中有石柱Jump(S, y) = ？ 一個最簡單情況：一個最簡單情況：S=1、y=1時：時： 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參照漢諾塔問題將借助參照漢諾塔問題將借助一個石柱一個石柱( s=1 )、一個荷葉、一個荷葉( y=1 )的青蛙的青蛙跳躍問題分成五個步驟：跳躍問題分成五個步驟：第一步：第一步：借助借助荷葉荷葉將將左左岸上面的若干青蛙（此時是岸上面的若干青蛙（此時是1#與與2#兩只）兩只）跳到跳到石柱石柱上暫存；上暫存；

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

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

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

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

54、從左岸到第一個石柱，再到右岸的跳躍的過程，而這兩步的對象是同一批青蛙，步的對象是同一批青蛙，青蛙個數(shù)是青蛙個數(shù)是Jump(s-1,y)。 第二步到第六步完成的是左岸的青蛙借助剩余的第二步到第六步完成的是左岸的青蛙借助剩余的n-1個石柱個石柱以及所有以及所有y個荷葉跳躍到右岸的過程，青蛙個數(shù)是個荷葉跳躍到右岸的過程，青蛙個數(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ù)目

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) /青蛙過河青蛙過河遞歸函數(shù)遞歸函數(shù) int k;if (s=0) / s=0表示無石柱表示無石柱 , 則為直接可解結(jié)點(diǎn)則為直接可解結(jié)點(diǎn) k=y+1;else / 如果如果 r 不為不為0 , 則要則要 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(請輸入石柱數(shù)請輸入石柱數(shù)s= ); scanf(%d,&s);printf(請輸入荷葉數(shù)請輸入荷葉數(shù)y= );scanf(%d,&y);sum=Jump(s,y); printf(Jump(%d,%d)=%dn,s,y,sum); 漢諾塔游戲與青蛙跳河的不同漢諾塔游戲與青蛙跳河的不同1）初始位置、結(jié)束位置不同；初始位置、結(jié)束位置不同；2）在漢諾塔游戲中，所搬盤子總數(shù)在漢諾塔游戲中，所搬盤子總數(shù)n的值決定第的值決定第一個盤子是搬到一個盤子是搬到B、還是搬到、還是搬到C；3）在青蛙跳河中，青蛙總

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

58、，再把子問題分成更小的子問題直到最后分解成的子問題可以直接求解，原問題的直到最后分解成的子問題可以直接求解，原問題的解即子問解即子問題的解的合并。題的解的合并。遞歸設(shè)計實例遞歸設(shè)計實例3-快速排序快速排序 將要求解的較大規(guī)模的問題分割成k個更小規(guī)模的子問題。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 對子問題分別求解。如果子問題的規(guī)模仍然不夠小，則對子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模再劃分子問題，如此遞歸的進(jì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ī)模的問題的解合并為一個更將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原大規(guī)模的問題的解，自底向上逐步求出原來問題的解。來問題的解?？焖倥判虻乃枷肟焖倥判虻乃枷肟焖倥判蚴腔诜种芜f歸的思想來實現(xiàn)的：快速排序是基于分治遞歸的思想來實現(xiàn)的：1）設(shè)要排序的數(shù)組是設(shè)要排序的數(shù)組是a0an-1；2）任意選取一個數(shù)據(jù)（通常選用第一個數(shù)據(jù)）作為關(guān)任意選取一個數(shù)據(jù)（通常選用第一個數(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ù)都放到它后面（右）-這個過程稱為一趟快速排序。這個過程稱為一趟快速排序。4）對關(guān)鍵數(shù)據(jù)前、后的數(shù)據(jù)再分別進(jìn)行一趟快速排序，對關(guān)鍵數(shù)據(jù)前、后的數(shù)據(jù)再分別進(jìn)行一趟快速排序，直到直到參加排序參加排序的數(shù)字是一個為止。的數(shù)字是一個為止。一趟快速排序的算法步驟如下：一趟快速排序的算法步驟如下： 1）設(shè)置兩個變量設(shè)置兩個變量i、j，排序初：，排序初：i=0，j=n-1； 2）以以 a0 作為關(guān)鍵數(shù)據(jù)，即作為關(guān)鍵數(shù)據(jù)，即 key=a0； 3