什么是遞歸精品課件

1、什么是遞歸第1頁(yè)，共19頁(yè)，2022年，5月20日，12點(diǎn)55分，星期日引例1:需要多少粒麥子? 舍罕王打算獎(jiǎng)賞國(guó)際象棋的發(fā)明人宰相西薩班達(dá)依爾。國(guó)王問他想要什么，他對(duì)國(guó)王說(shuō)：“陛下，請(qǐng)您在這張棋盤的第1個(gè)小格里賞給我一粒麥子，在第2個(gè)小格里給2粒，第3個(gè)小格給4粒，以后每一小格都比前一小格加一倍。請(qǐng)您把這樣擺滿棋盤上所有64格的麥粒，都賞給您的仆人吧！”國(guó)王覺得這個(gè)要求太容易滿足了，就命令給他這些麥粒。當(dāng)人們把一袋一袋的麥子搬來(lái)開始計(jì)數(shù)時(shí)，國(guó)王才發(fā)現(xiàn)：就是把全印度甚至全世界的麥粒全拿來(lái)，也滿足不了那位宰相的要求。需要多少粒麥子? f(1)=1; f(n)=2*f(n-1); 這是一個(gè)遞歸問題

2、第2頁(yè)，共19頁(yè)，2022年，5月20日，12點(diǎn)55分，星期日遞歸與遞歸函數(shù) 引例1:漢諾塔問題: 漢諾塔（又稱河內(nèi)塔）問題是源于印度一個(gè)古老傳說(shuō)的益智玩具。大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤。演示 : n=1 n=2 n=3 n=8第3頁(yè)，共19頁(yè)，2022年，5月20日，12點(diǎn)55分，星期日這是一個(gè)遞歸的問題,需要用遞歸的方法來(lái)解決實(shí)現(xiàn)思想: 把上面n-1個(gè)圓盤由A借助C移動(dòng)到B 把第n個(gè)圓盤移動(dòng)到C

3、 把n-1個(gè)圓盤由B 借助A 移動(dòng)到Cn個(gè)圓盤的移動(dòng)問題轉(zhuǎn)換成為n-1個(gè)圓盤的移動(dòng)問題,又可以繼續(xù)轉(zhuǎn)化成為n-2,n-3,3,2,1個(gè)圓盤的移動(dòng)問題,使問題的規(guī)模不斷縮小第4頁(yè)，共19頁(yè)，2022年，5月20日，12點(diǎn)55分，星期日1什么是遞歸？用自身的結(jié)構(gòu)來(lái)描述自身就稱為遞歸。最典型的例子是對(duì)階乘運(yùn)算： 特點(diǎn)： 原始問題可轉(zhuǎn)化為解決方法相同的新問題； 新問題的規(guī)模比原始問題?。?新問題又可轉(zhuǎn)化為解決方法相同的規(guī)模更小的新問題，直至終結(jié)條件為止。第5頁(yè)，共19頁(yè)，2022年，5月20日，12點(diǎn)55分，星期日遞推回歸fac(2)=2*fac(1)fac(1)=1fac(4)=4*6fac(3)=

4、3*2fac(2)=2*1fac(3)=3*fac(2)fac(4)=4*fac(3)【例5.15】編fac(n)=n! 的遞歸函數(shù)long fac(int n) if(n=1) return(1); return (n*fac(n-1);遞推過(guò)程每調(diào)用自身，當(dāng)前參數(shù)壓棧，直到達(dá)到遞歸結(jié)束條件?；貧w過(guò)程不斷從棧中彈出當(dāng)前的參數(shù)，直到?？?。思考：若fac函數(shù)中沒有語(yǔ)句 if(n=1) return(1);程序運(yùn)行結(jié)果將如何？第6頁(yè)，共19頁(yè)，2022年，5月20日，12點(diǎn)55分，星期日【例5.16】用遞歸函數(shù)實(shí)現(xiàn)將一個(gè)十進(jìn)制整數(shù)轉(zhuǎn)換成二至十六任意進(jìn)制的字符 void convert(int m,

5、int r) char b17=0123456789ABCDEF;if(m!=0) convert(m/r,r);coutbm%r; 任何有意義的遞歸必須具有： 遞歸結(jié)束條件及結(jié)束時(shí)的值（出口）； 能用遞歸形式表示，并且遞歸向終止條件發(fā)展。優(yōu)缺點(diǎn)：遞歸算法設(shè)計(jì)簡(jiǎn)單，程序代碼簡(jiǎn)潔易讀，但它消耗的機(jī)時(shí)和占據(jù)的內(nèi)存空間比非遞歸大。程序執(zhí)行過(guò)程與參數(shù)傳遞過(guò)程?第7頁(yè)，共19頁(yè)，2022年，5月20日，12點(diǎn)55分，星期日課堂練習(xí)1：分析程序的運(yùn)行結(jié)果：Void f(int n,int r) if (n!=0) f=f(n/r,r); coutn%r; Void main()f(100,8);F(100

6、,8) 4F(12,8) 4F(1,8) 1F(0,8)第8頁(yè)，共19頁(yè)，2022年，5月20日，12點(diǎn)55分，星期日2遞歸算法一般用于解決哪些問題？一般用于解決三類問題： (1)數(shù)據(jù)的定義是按遞歸定義的。Fibonacci Sequence f(n)=f(n-1)+f(n-2)出口：f(1)=1,f(0)=1階乘：n!=n*(n-1)! 出口： 1!=1猴子吃桃這一類問題也可用靜態(tài)變量或循環(huán)來(lái)實(shí)現(xiàn)第9頁(yè)，共19頁(yè)，2022年，5月20日，12點(diǎn)55分，星期日遞歸：#include iostream.h#include iomanip.hlong f(int n)if (n=1) return

7、 1;else if (n=2) return 1;elsereturn f(n-1)+f(n-2);void main()int n;cout輸入n,求數(shù)列的第n個(gè)數(shù)n;cout數(shù)列的第n個(gè)數(shù)： f(n) endl;靜態(tài)變量：long f1(int n)long x;static int x1=1,x2=1;if (n=1 ) return x1;else if (n=2) return x2;else x=x1+x2; x1=x2; x2=x; return x;出口遞歸調(diào)用使用靜態(tài)變量，取上一次的計(jì)算結(jié)果void main()int n,i;cout輸入n,求數(shù)列的第n個(gè)數(shù)n;cout數(shù)

8、列的第n個(gè)數(shù)：endl;coutf(n)endl;for (i=1;i=n;i+) cout f1(i)endl;第10頁(yè)，共19頁(yè)，2022年，5月20日，12點(diǎn)55分，星期日猴子吃桃 小猴在一天摘了若干桃，當(dāng)天吃掉一半多一個(gè)，第二天接著吃掉剩下的一半多一個(gè)，以后每天都吃掉尚存桃子的一半多一個(gè)，第7天早上只剩1個(gè)，問小猴摘了多少個(gè)桃？第11頁(yè)，共19頁(yè)，2022年，5月20日，12點(diǎn)55分，星期日int f(int n)if (n=7) return 1;else return (f(n+1)+1)*2;void main()couthigh 輾轉(zhuǎn)相除法求m,n最大公約數(shù) 出口: r=0 數(shù)

9、制轉(zhuǎn)換(m轉(zhuǎn)換成r進(jìn)制） 出口：m=0遞歸圖形打印第13頁(yè)，共19頁(yè)，2022年，5月20日，12點(diǎn)55分，星期日漢諾塔#include iostream.h#include iomanip.hvoid hanoi(int n,char one,char two,char three)void move(char getone,char putone);if(n=1)move(one,three);elsehanoi(n-1,one,three,two);move(one,three);hanoi(n-1,two,one,three);void move(char getone,char pu

10、tone)coutgetoneputoneendl;void main()int m;coutInput the number of disk:m;coutthe steps of movingmdisks :1)u1=(x1+x2)/2;u2=(x2+x3)/2;v1=(y1+y2)/2;triangle(u1,x2,u2,v1,y2,k-1);triangle(x1,u1,x2,y1,v1,k-1);triangle(x2,u2,x3,y1,v1,k-1);elseline(x1,y1,x3,y1);line(x1,y1,x2,y2);line(x2,y2,x3,y1);void main()int n;cinn;initgraph(600,600);triangle(30,320,570,30,570,n);getch();closegraph();第16頁(yè)，共19頁(yè)，2022年，5月20日，12點(diǎn)55分，星期日課堂練習(xí)2：最大公約數(shù)#include iostream.hint gcd(int m,int n)if (m%n=0)return n;else returngcd(n,m%n);void main()