學校課件遞歸算法_3

1、算法設(shè)計與分析什么是遞歸？什么是遞歸？ 當你往鏡子前面一站，鏡子里面就有當你往鏡子前面一站，鏡子里面就有一個你的像。但你試過兩面鏡子一起照嗎一個你的像。但你試過兩面鏡子一起照嗎? ?如果甲、乙兩面鏡子相互面對面放著，你如果甲、乙兩面鏡子相互面對面放著，你往中間一站，嘿，兩面鏡子里都有你的千往中間一站，嘿，兩面鏡子里都有你的千百個百個“化身化身”! !為什么會有這么奇妙的現(xiàn)為什么會有這么奇妙的現(xiàn)象呢象呢? ?原來，甲鏡子里有乙鏡子的像，乙原來，甲鏡子里有乙鏡子的像，乙鏡子里也有甲鏡子的像，而且這樣反反復(fù)鏡子里也有甲鏡子的像，而且這樣反反復(fù)復(fù)，就會產(chǎn)生一連串的復(fù)，就會產(chǎn)生一連串的“像中像像中像”。

2、這是。這是一種遞歸現(xiàn)象。一種遞歸現(xiàn)象。什么是遞歸？什么是遞歸？ 這種日常生活中的現(xiàn)象這種日常生活中的現(xiàn)象又被稱為德羅斯特效應(yīng)（英又被稱為德羅斯特效應(yīng)（英語：語：Droste effectDroste effect）是遞歸）是遞歸的一種視覺形式。的一種視覺形式。 圖中女性手持的物體中圖中女性手持的物體中有一幅她本人手持同一物體有一幅她本人手持同一物體的小圖片，進而小圖片中還的小圖片，進而小圖片中還有更小的一幅她手持同一物有更小的一幅她手持同一物體的圖片，依此類推。體的圖片，依此類推。什么是遞歸？什么是遞歸？ 在日常生活中，遞歸一在日常生活中，遞歸一詞較常用于描述以自相似方詞較常用于描述以自相似方

3、法重復(fù)事物的過程。法重復(fù)事物的過程。 在算法中，遞歸一詞用在算法中，遞歸一詞用于表示直接或間接的調(diào)用自于表示直接或間接的調(diào)用自身的算法。身的算法。 特別的，特別的，用函數(shù)自身給用函數(shù)自身給出定義的函數(shù)被稱之為遞歸出定義的函數(shù)被稱之為遞歸函數(shù)。函數(shù)。 什么是遞歸？什么是遞歸？ 其實，我們在生活中經(jīng)常運用遞歸的其實，我們在生活中經(jīng)常運用遞歸的方式來思考問題，如參考下面這個例子：方式來思考問題，如參考下面這個例子：例例1 1：第：第5 5個人的年齡比第個人的年齡比第4 4個人的年齡大個人的年齡大2 2歲，第歲，第4 4個人的年齡比第個人的年齡比第3 3個人的年齡大個人的年齡大2 2歲，第歲，第3 3

4、個人的年齡比第個人的年齡比第2 2個人的年齡大個人的年齡大2 2歲，第歲，第2 2個人的年齡比第個人的年齡比第1 1個人的年齡大個人的年齡大2 2歲，第歲，第1 1個的年齡個的年齡1010歲。第歲。第5 5個人的年該該個人的年該該是多少呢？是多少呢？ 著名的意大利數(shù)學家斐波那契著名的意大利數(shù)學家斐波那契(Fibonacci)(Fibonacci)在他的著作在他的著作算盤書算盤書中提出了中提出了一個一個“兔子問題兔子問題”：假定小兔子一個月就可：假定小兔子一個月就可以長成大兔子，而大兔子每個月都會生出一以長成大兔子，而大兔子每個月都會生出一對小兔子。如果年初養(yǎng)了一對小兔子，問到對小兔子。如果年初

5、養(yǎng)了一對小兔子，問到年底時將有多少對兔子年底時將有多少對兔子? (? (當然得假設(shè)兔子當然得假設(shè)兔子沒有死亡而且嚴格按照上述規(guī)律長大與繁殖沒有死亡而且嚴格按照上述規(guī)律長大與繁殖) ) 輸入計算兔子的月份數(shù)：輸入計算兔子的月份數(shù)：n n If n 3 Then c = 1 Else a = 1 If n 3 Then c = 1 Else a = 1；b = 1b = 1 i = 3 i = 3 c = a + b c = a + b a = b a = b b = c b = c i=i+1, i=i+1,如果如果inin則返回則返回 結(jié)束結(jié)束1月2月3月4月5月6月7月8月9月10月11月1

6、2月小兔111235813213455大兔1123581321345589合計1123581321345589144這個表格雖然解決了斐波那契的兔子問題這個表格雖然解決了斐波那契的兔子問題( (年年底時兔子的總數(shù)是底時兔子的總數(shù)是144144對對) )，但仔細觀察一下，但仔細觀察一下這個表格，你會發(fā)現(xiàn)兔子的數(shù)目增長得越來這個表格，你會發(fā)現(xiàn)兔子的數(shù)目增長得越來越快，如果時間再長，只用列表的方法就會越快，如果時間再長，只用列表的方法就會有困難。有困難。( (例如，你愿意用列表的方法求出例如，你愿意用列表的方法求出5 5年后兔子的數(shù)目嗎？年后兔子的數(shù)目嗎？) )我們需要研究表中的規(guī)我們需要研究表中的

7、規(guī)律，找出一般的方法，去解決這個問題。律，找出一般的方法，去解決這個問題。 仔細研究上頁的表，你有些什么發(fā)現(xiàn)？仔細研究上頁的表，你有些什么發(fā)現(xiàn)？每一個月份的大兔數(shù)、小兔數(shù)與上一個月的每一個月份的大兔數(shù)、小兔數(shù)與上一個月的數(shù)字有什么聯(lián)系，能肯定這個規(guī)律嗎？恭喜數(shù)字有什么聯(lián)系，能肯定這個規(guī)律嗎？恭喜你，你快成功了？你，你快成功了？ “ “兔子問題兔子問題”很容易列出一條遞推式而很容易列出一條遞推式而得到解決。假設(shè)第得到解決。假設(shè)第N N個月的兔子數(shù)目是個月的兔子數(shù)目是F(N)F(N)，我們有：我們有： 這是因為每月的大兔子數(shù)目一定等于上這是因為每月的大兔子數(shù)目一定等于上月的兔子總數(shù)，而每個月的小兔

8、子數(shù)目一月的兔子總數(shù)，而每個月的小兔子數(shù)目一定等于上月的大兔子數(shù)目定等于上月的大兔子數(shù)目( (即前一個月的兔即前一個月的兔子的數(shù)目子的數(shù)目) )。第n個Fibonacci數(shù)可遞歸地計算如下：int fibonacci(int n) if (n =1); fish5=fish5+5; / .1 for ( i=4; i=1; i- ) / .2 fishi+1%4 != 0 true false break; /退出 for 循環(huán) fishi = fishi+1*5/4+1; 該圖可分為三部分該圖可分為三部分(1) 是說明部分：包含定義數(shù)組是說明部分：包含定義數(shù)組 fish6，并初始化為，并初始

9、化為 1 和定義循和定義循環(huán)控制變量環(huán)控制變量 i，并初始化為，并初始化為 0。(2) 是是 do.while 直到型循環(huán)，其循環(huán)體又含兩塊：直到型循環(huán)，其循環(huán)體又含兩塊：(2).1 是枚舉過程中的是枚舉過程中的 fish5 的初值設(shè)置，一開始的初值設(shè)置，一開始 fish5=1+5; 以后每次增以后每次增 5。(2).2 是一個是一個 for 循環(huán)，循環(huán)，i的初值為的初值為 4，終值為，終值為 1，步長為，步長為 -1，該，該循環(huán)的循環(huán)體是一個分支語句，如果循環(huán)的循環(huán)體是一個分支語句，如果 fishi+1不能被不能被 4 整除，整除，則跳出則跳出 for 循環(huán)（使用循環(huán)（使用 break 語句

10、語句;）否則，從）否則，從 fishi+1 算出算出fishi。當由當由 break 語句讓程序退出循環(huán)時，意味著某語句讓程序退出循環(huán)時，意味著某人看到的魚數(shù)不是整數(shù)，當然不是所求，必須令人看到的魚數(shù)不是整數(shù)，當然不是所求，必須令fish 5 加加 5 后再試，即重新進入直到型循環(huán)后再試，即重新進入直到型循環(huán) do while 的循環(huán)體。的循環(huán)體。當著正常退出當著正常退出 for 循環(huán)時，一定是控制變量循環(huán)時，一定是控制變量 i 從初值從初值 4，一步一步執(zhí)行到終值，一步一步執(zhí)行到終值 1，每一步的魚數(shù)均，每一步的魚數(shù)均為整數(shù)，最后為整數(shù)，最后 i = 0，表示計算完畢，且也達到了退，表示計算

11、完畢，且也達到了退出直到型循環(huán)的條件。出直到型循環(huán)的條件。(3) 輸出計算結(jié)果輸出計算結(jié)果（五人合伙捕魚）（五人合伙捕魚） 遞推算法的實現(xiàn)遞推算法的實現(xiàn) /*#include / 預(yù)編譯命令預(yù)編譯命令using namespace std;void main() /主函數(shù)主函數(shù) int fish6=1,1,1,1,1,1; / 整型數(shù)組，記錄每人醒來后看到的魚數(shù)整型數(shù)組，記錄每人醒來后看到的魚數(shù) int i=0; do fish5=fish5+5; / 讓讓E看到的魚數(shù)增看到的魚數(shù)增5。 for (i=4; i=1; i-) if ( fishi+1%4 !=0 )break; / 跳出跳出f

12、or循環(huán)循環(huán)elsefishi=fishi+1*5/4+1;/ 計算第計算第i人看到的魚數(shù)人看到的魚數(shù) while( i=1 ); / 當當 i=1 繼續(xù)做繼續(xù)做do循環(huán)循環(huán)for (i=1; i=5; i+) / 輸出計算結(jié)果輸出計算結(jié)果cout fishi endl;system(pause);31212496199615961276輸出結(jié)果為：輸出結(jié)果為：遞遞 歸歸 經(jīng)經(jīng) 典典 題題 目目故事：故事：相傳在古代印度的相傳在古代印度的 Bramah 廟中，有位僧人整天把三根柱子廟中，有位僧人整天把三根柱子上的金盤倒來倒去，原來他是想把上的金盤倒來倒去，原來他是想把64個一個比一個小的金盤個

13、一個比一個小的金盤從一根柱子上移到另一根柱子上去。移動過程中恪守下述規(guī)從一根柱子上移到另一根柱子上去。移動過程中恪守下述規(guī)則：每次只允許移動一只盤，且大盤不得落在小盤上面。有則：每次只允許移動一只盤，且大盤不得落在小盤上面。有人會覺得這很簡單，真的動手移盤就會發(fā)現(xiàn)，如以每秒移動人會覺得這很簡單，真的動手移盤就會發(fā)現(xiàn)，如以每秒移動一只盤子的話，按照上述規(guī)則將一只盤子的話，按照上述規(guī)則將64只盤子從一個柱子移至另只盤子從一個柱子移至另一個柱子上，所需時間約為一個柱子上，所需時間約為5800億年。億年。 怎樣編寫這種程序？思路上還是先從最簡單的情況分析起，搬怎樣編寫這種程序？思路上還是先從最簡單的情

14、況分析起，搬一搬看，慢慢理出思路。一搬看，慢慢理出思路。1、在、在A柱上只有一只盤子，假定盤號為柱上只有一只盤子，假定盤號為 1，這時只需將該，這時只需將該盤從盤從 A 搬至搬至 C，一次完成，記為，一次完成，記為move 1 from A to C (演示演示)ABC12、在、在 A 柱上有二只盤子，柱上有二只盤子，1 為小盤，為小盤，2 為大盤。為大盤。第（第（1）步將）步將1號盤從號盤從A移至移至B，這是為了讓，這是為了讓 2號盤能移動；號盤能移動；第（第（2）步將）步將 2 號盤從號盤從A 移至移至 C；第（第（3）步再將）步再將 1 號盤從號盤從 B 移至移至 C；這三步記為（這三步

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

16、將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個盤子的

17、分解個盤子的分解move (3, A, B, C)move (2, A, C, B)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號盤當整體從號盤當整體從A移至移至B的過的過程中程中 move(2, A, C, B) 實際上

18、是分解為以下三步實際上是分解為以下三步第（第（1）.1步：步：move 1 form 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 號盤當整體從號盤當整體從 B 移至移至 C 的過的過程了。實際上程了。實際上 move( 2, B, A,

19、 C ) 也要分解為也要分解為三步：三步：第（第（3）.1步：步：move 1 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?？础？吹竭@里就能明白借助到這里就能明白借助 C

20、 的含義了。因此，在的含義了。因此，在構(gòu)思搬移過程的參量時，要把構(gòu)思搬移過程的參量時，要把 3 個柱子都用上。個柱子都用上。6、定義搬移函數(shù)、定義搬移函數(shù) move(n, A, B, C)，物理意義是，物理意義是將將 n 只盤子從只盤子從 A 經(jīng)經(jīng) B 搬到搬到 Cmove(n, A, B, C) 分解為分解為3步步(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é)點；解結(jié)點；(3)Move(n-1, B, A,

21、C)理解為將上面的理解為將上面的n-1只盤子作為一只盤子作為一個整體從個整體從B經(jīng)經(jīng)A移至移至C。這里顯然是一種遞歸定義，當著解這里顯然是一種遞歸定義，當著解 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直接移至直接移至B，即，即n-1:A to B；第第3步：再將上面的步：再將上面的n-2只盤子作為一個整體從只盤子作為一個整體從C經(jīng)經(jīng)A移至移至B，move(n-2, C,

22、A, B)；#include using namespace std;/把n號圓盤從x移到y(tǒng)，并打印出。void Move(int n, char x, char y)cout 把 n 號圓盤從 x 移動到 y endl;/把前n個通過b從a移到cvoid Hanoi(int n, char a, char b, char c) if(n = 1)Move(1, a, c);elseHanoi(n-1, a, c, b);Move(n, a, c);Hanoi(n-1, b, a, c);int main()int n;cout n;Hanoi(n, a, b, c);cout Ok! end

23、l;system(pause);作業(yè)：作業(yè)：1 1、運動會開了、運動會開了N N天，一共發(fā)出金牌天，一共發(fā)出金牌M M枚。第一天發(fā)金枚。第一天發(fā)金牌牌1 1枚加剩下的七分之一枚，第二天發(fā)金牌枚加剩下的七分之一枚，第二天發(fā)金牌2 2枚加剩下枚加剩下的七分之一枚，第的七分之一枚，第3 3天發(fā)金牌天發(fā)金牌3 3枚加剩下的七分之一枚，枚加剩下的七分之一枚，以后每天都照此辦理。到了第以后每天都照此辦理。到了第N N天剛好還有金牌天剛好還有金牌N N枚，枚，到此金牌全部發(fā)完。編程求到此金牌全部發(fā)完。編程求N N和和M M。1717枚，枚，6 6天天作業(yè)：作業(yè)：2 2、國王分財產(chǎn)。某國王臨終前給兒子們分財產(chǎn)

24、。他把、國王分財產(chǎn)。某國王臨終前給兒子們分財產(chǎn)。他把財產(chǎn)分為若干份，然后給第一個兒子一份，再加上剩財產(chǎn)分為若干份，然后給第一個兒子一份，再加上剩余財產(chǎn)的余財產(chǎn)的1/101/10；給第二個兒子兩份，再加上剩余財產(chǎn)；給第二個兒子兩份，再加上剩余財產(chǎn)的的1/101/10；給第；給第i i個兒子個兒子i i份，再加上剩余財產(chǎn)的份，再加上剩余財產(chǎn)的1/101/10。每個兒子都竊竊自喜。以為得到了父王的偏愛，。每個兒子都竊竊自喜。以為得到了父王的偏愛，孰不知國王是孰不知國王是“一碗水端平一碗水端平”的。請用程序回答，老的。請用程序回答，老國王共有幾個兒子？財產(chǎn)共分成了多少份？國王共有幾個兒子？財產(chǎn)共分成了

25、多少份？作業(yè)：作業(yè)：3 3、出售金魚。、出售金魚。第一次賣出全部金魚的一半加二分之一條金魚；第一次賣出全部金魚的一半加二分之一條金魚；第二次賣出乘余金魚的三分之一加三分之一條金魚；第二次賣出乘余金魚的三分之一加三分之一條金魚；第三次賣出剩余金魚的四分之一加四分之一條金魚；第三次賣出剩余金魚的四分之一加四分之一條金魚；第四次賣出剩余金魚的五分之一加五分之一條金魚；第四次賣出剩余金魚的五分之一加五分之一條金魚；現(xiàn)在還剩下現(xiàn)在還剩下1111條金魚，在出售金魚時不能把金魚切開條金魚，在出售金魚時不能把金魚切開或者有任何破損的。問這魚缸里原有多少條金魚？或者有任何破損的。問這魚缸里原有多少條金魚？2222作業(yè)：作業(yè)：4 4、某路公共汽車，總共有八站，從一號站發(fā)軒時車上、某路公共汽車，總共有八站，從一號站發(fā)軒時車上已有已有n n位乘客，到了第二站先下一半乘客，再上來了六位乘客，到了第二站先下一半乘客，再上來了六位乘客；到了第三站也先下一半乘客，再上來了五位位乘客；到了第三站也先下一半乘客，再上來了五位乘客，以后每到一站都先下車上已有的一半乘客