计算机程序设计基础课程教学PPTF.ppt

《计算机程序设计基础课程教学PPTF.ppt》由会员分享，可在线阅读，更多相关《计算机程序设计基础课程教学PPTF.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础乔乔 林林计算机程序设计基础计算机程序设计基础Email:Email:Tel:62780973Tel:62780973清华大学计算机科学与技术系清华大学计算机科学与技术系2清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础第十二章 递归程序设计学习目标学习目标了解递归可以简化复杂问题的编程实现了解递归可以简化复杂问题的编程实现了解递归可以简化复杂问题的编程实现了解递归可以简化复杂问题的编程实现理解递归程序设计范型理解递归程序设计范型理解递归程序

2、设计范型理解递归程序设计范型理解函数递归调用的内部实现机制理解函数递归调用的内部实现机制理解函数递归调用的内部实现机制理解函数递归调用的内部实现机制熟悉典型递归程序的范例熟悉典型递归程序的范例熟悉典型递归程序的范例熟悉典型递归程序的范例能够编写简单的递归程序能够编写简单的递归程序能够编写简单的递归程序能够编写简单的递归程序3清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础12.1 递归问题的引入递归的目的递归的目的简化复杂问题的手段：将问题逐步化简，在化简简化复杂问题的手段：将问题逐步化简，在化简简化复杂问题的手段：将问题逐步化简，在化简简化

3、复杂问题的手段：将问题逐步化简，在化简过程中保持原问题的性质不变，直到问题最简，过程中保持原问题的性质不变，直到问题最简，过程中保持原问题的性质不变，直到问题最简，过程中保持原问题的性质不变，直到问题最简，可以轻易获得答案，然后将简化问题的答案组装可以轻易获得答案，然后将简化问题的答案组装可以轻易获得答案，然后将简化问题的答案组装可以轻易获得答案，然后将简化问题的答案组装成原始问题的解成原始问题的解成原始问题的解成原始问题的解递归示例递归示例n n!=1!=1 2 2 3 3 n n:n n!=(!=(n n-1)!1)!n n;0!=1;0!=1x xn n=x x x x x x x x:

4、x xn n=x xn n-1 1 x x;x x0 0=1=14清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础递归函数示例一阶乘的计算阶乘的计算long int long int CalFactorialCalFactorial(int(int n n)long int long int resultresult=1;=1;int int i i=0;=0;while(+while(+i i=n n)result result*=*=i i;return return resultresult;long int long int CalF

5、actorialCalFactorial(int(int n n)long int long int resultresult;if(if(n n=0|=0|n n=1)=1)resultresult=1;=1;else else resultresult=n n*CalFactorialCalFactorial(n n 1);1);return return resultresult;5清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础递归函数示例二幂的计算幂的计算long double long double CalPowerCalPowe

6、r(long double(long double x x,int,int n n)long double long double resultresult;if(if(n n=0)=0)resultresult=1;=1;else else resultresult=x x*CalPowerCalPower(x x,n n 1);1);return return resultresult;6清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础递归函数示例三求整数的各位数字之和求整数的各位数字之和int int SumDigitSumDigit(

7、int(int n n)if(if(n n 10)10)return return n n;else else return return n n%10+%10+SumDigitSumDigit(n n/10);/10);7清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础递归过程的跟踪阶乘的计算阶乘的计算#include#include long int long int CalFactorialCalFactorial(int(int n n)long int long int resultresult;if(if(n n=0|=0|n n

8、=1)=1)resultresult=1;=1;else else resultresult=n n*CalFactorialCalFactorial(n n 1);1);return return resultresult;void void mainmain()()int int numnum=3;long int =3;long int facfac;facfac=CalFactorialCalFactorial(numnum););printfprintf(“%(“%ldld”,”,facfac););8清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序

9、序设设计计基基础础递归过程的跟踪main()函数栈框架函数栈框架9清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础递归过程的跟踪第一次调用第一次调用 CalFactorial()函数栈框架函数栈框架long int long int CalFactorialCalFactorial(int(int n n)long int long int resultresult;if(if(n n=0|=0|n n=1)=1)resultresult=1;else =1;else resultresult=n n*CalFactorialCalFacto

10、rial(n n 1);1);return return resultresult;10清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础递归过程的跟踪第二次调用第二次调用 CalFactorial()函数栈框架函数栈框架long int long int CalFactorialCalFactorial(int(int n n)long int long int resultresult;if(if(n n=0|=0|n n=1)=1)resultresult=1;else =1;else resultresult=n n*CalFactor

11、ialCalFactorial(n n 1);1);return return resultresult;11清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础递归过程的跟踪第三次调用第三次调用 CalFactorial()执行后栈框架执行后栈框架long int long int CalFactorialCalFactorial(int(int n n)long int long int resultresult;if(if(n n=0|=0|n n=1)=1)resultresult=1;else =1;else resultresult=

12、n n*CalFactorialCalFactorial(n n 1);1);return return resultresult;12清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础递归过程的跟踪第二次调用第二次调用 CalFactorial()执行后栈框架执行后栈框架long int long int CalFactorialCalFactorial(int(int n n)long int long int resultresult;if(if(n n=0|=0|n n=1)=1)resultresult=1;else =1;else

13、resultresult=n n*CalFactorialCalFactorial(n n 1);1);return return resultresult;13清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础递归过程的跟踪第一次调用第一次调用 CalFactorial()执行后栈框架执行后栈框架long int long int CalFactorialCalFactorial(int(int n n)long int long int resultresult;if(if(n n=0|=0|n n=1)=1)resultresult=1;

14、else =1;else resultresult=n n*CalFactorialCalFactorial(n n 1);1);return return resultresult;14清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础递归过程的跟踪控制流返回控制流返回 main()函数时的栈框架函数时的栈框架15清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础递归信任与递归范型理解递归问题的原则理解递归问题的原则不分析复杂细节而仅考虑单一层次上的操作不分析复杂细节而仅考虑单一层次上的操作不

15、分析复杂细节而仅考虑单一层次上的操作不分析复杂细节而仅考虑单一层次上的操作不要跟踪递归调用的栈框架！不要跟踪递归调用的栈框架！不要跟踪递归调用的栈框架！不要跟踪递归调用的栈框架！基本递归假设基本递归假设只要递归调用时的参数比原始参数在某种程度上只要递归调用时的参数比原始参数在某种程度上只要递归调用时的参数比原始参数在某种程度上只要递归调用时的参数比原始参数在某种程度上更简单，则递归调用就一定能获得正确答案更简单，则递归调用就一定能获得正确答案更简单，则递归调用就一定能获得正确答案更简单，则递归调用就一定能获得正确答案递归心理学：这种简单递归调用一定正确工作的递归心理学：这种简单递归调用一定正确

16、工作的递归心理学：这种简单递归调用一定正确工作的递归心理学：这种简单递归调用一定正确工作的假设即为递归信任假设即为递归信任假设即为递归信任假设即为递归信任16清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础12.2 典型递归程序Hanoi 塔问题塔问题假设有三个分别命名为假设有三个分别命名为假设有三个分别命名为假设有三个分别命名为 X X、Y Y 和和和和 Z Z 的塔座，在塔的塔座，在塔的塔座，在塔的塔座，在塔座座座座 X X 上插有上插有上插有上插有 n n 个直径大小不同、依小到大分别编个直径大小不同、依小到大分别编个直径大小不同、依小

17、到大分别编个直径大小不同、依小到大分别编号为号为号为号为1 1，2 2，n n 的圆盘，如图所示。现要求将的圆盘，如图所示。现要求将的圆盘，如图所示。现要求将的圆盘，如图所示。现要求将X X 轴上的轴上的轴上的轴上的 n n 个圆盘移动到塔座个圆盘移动到塔座个圆盘移动到塔座个圆盘移动到塔座 Z Z 上并按相同顺序上并按相同顺序上并按相同顺序上并按相同顺序叠放，圆盘移动时必须遵循下述规则：叠放，圆盘移动时必须遵循下述规则：叠放，圆盘移动时必须遵循下述规则：叠放，圆盘移动时必须遵循下述规则：每次只能移动一个圆盘；每次只能移动一个圆盘；每次只能移动一个圆盘；每次只能移动一个圆盘；圆盘可以插在圆盘可以

18、插在圆盘可以插在圆盘可以插在 X X、Y Y 与与与与 Z Z 中的任意塔座上中的任意塔座上中的任意塔座上中的任意塔座上 任何时刻都不能将较大的圆盘压在较小的圆盘上任何时刻都不能将较大的圆盘压在较小的圆盘上任何时刻都不能将较大的圆盘压在较小的圆盘上任何时刻都不能将较大的圆盘压在较小的圆盘上如何实现移动圆盘的操作呢？如何实现移动圆盘的操作呢？如何实现移动圆盘的操作呢？如何实现移动圆盘的操作呢？17清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础Hanoi 塔问题18清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程

19、序序设设计计基基础础Hanoi 塔问题递归算法的伪代码递归算法的伪代码void void MoveHanoiTowerMoveHanoiTower(int(int numnum,char,char sourcesource,char,char temptemp,char,char dest dest)if(if(n n=1)=1)将一个圆盘从将一个圆盘从将一个圆盘从将一个圆盘从 sourcesource 移动到移动到移动到移动到 destdest else else 将将将将 n n 1 1 个圆盘从个圆盘从个圆盘从个圆盘从 sourcesource 移动到移动到移动到移动到 temptemp

20、 将圆盘将圆盘将圆盘将圆盘 n n 从从从从 sourcesource 移动到移动到移动到移动到 destdest 将将将将 n n 1 1 个圆盘从个圆盘从个圆盘从个圆盘从 temptemp 移动到移动到移动到移动到 destdest 19清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础Hanoi 塔问题递归算法递归算法void void movemove(char(char sourcesource,char,char destdest)printfprintf(“%(“%c c-%c c”,”,sourcesource,dest des

21、t););void void MoveHanoiTowerMoveHanoiTower(int(int numnum,char,char sourcesource,char,char temptemp,char,char dest dest)if(if(numnum=1)=1)movemove(sourcesource,destdest););else else MoveHanoiTowerMoveHanoiTower(num num 1,1,sourcesource,destdest,temp temp););movemove(sourcesource,dest dest););MoveHa

22、noiTowerMoveHanoiTower(num num 1,1,temptemp,sourcesource,dest dest););20清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础分形问题打印一棵对称的分形树打印一棵对称的分形树分形：部分与整体相似的图形分形：部分与整体相似的图形分形：部分与整体相似的图形分形：部分与整体相似的图形递归：可分解为画树干及其两个树枝的递归过程递归：可分解为画树干及其两个树枝的递归过程递归：可分解为画树干及其两个树枝的递归过程递归：可分解为画树干及其两个树枝的递归过程21清华大学计算机科学与技术系清华大

23、学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础分形问题算法分析算法分析层数：在递归过程中层数不断减少，当层数为层数：在递归过程中层数不断减少，当层数为层数：在递归过程中层数不断减少，当层数为层数：在递归过程中层数不断减少，当层数为 0 0时达到最简时达到最简时达到最简时达到最简长度值及长度变化比例系数：使得长度值根据所长度值及长度变化比例系数：使得长度值根据所长度值及长度变化比例系数：使得长度值根据所长度值及长度变化比例系数：使得长度值根据所处的不同层数而不同处的不同层数而不同处的不同层数而不同处的不同层数而不同角度值及左右分枝对树干的夹角：角度值是树干角度值及左右分枝对

24、树干的夹角：角度值是树干角度值及左右分枝对树干的夹角：角度值是树干角度值及左右分枝对树干的夹角：角度值是树干与水平轴之间的夹角与水平轴之间的夹角与水平轴之间的夹角与水平轴之间的夹角树干顶点坐标值树干顶点坐标值树干顶点坐标值树干顶点坐标值22清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础分形问题伪代码伪代码if(if(层数为层数为层数为层数为 0)0)画树干画树干画树干画树干 elseelse 画树干画树干画树干画树干 计算本树干顶点坐标计算本树干顶点坐标计算本树干顶点坐标计算本树干顶点坐标 在本树干的顶部画左分枝在本树干的顶部画左分枝在本树

25、干的顶部画左分枝在本树干的顶部画左分枝 在本树干的顶部画右分枝在本树干的顶部画右分枝在本树干的顶部画右分枝在本树干的顶部画右分枝 23清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础分形问题算法初步实现算法初步实现void void DrawFractalDrawFractal(double(double lengthlength,double,double scalescale,double,double alphaalpha,double,double deltadelta,double,double cxcx,double,double

26、 cycy,int,int order order)if(if(orderorder=0)=0)画树干，当前点画树干，当前点画树干，当前点画树干，当前点(cxcx,cycy)，长度为长度为长度为长度为lengthlength，水平夹角水平夹角水平夹角水平夹角 alphaalpha elseelse 画树干，当前点画树干，当前点画树干，当前点画树干，当前点(cxcx,cycy)，长度长度长度长度 lengthlength，水平夹角水平夹角水平夹角水平夹角alphaalpha 计算新的线段顶点坐标计算新的线段顶点坐标计算新的线段顶点坐标计算新的线段顶点坐标(cxcx,cycy)画右分枝，新顶点画右

27、分枝，新顶点画右分枝，新顶点画右分枝，新顶点(cxcx,cycy)，长度，长度，长度，长度 length length*scalescale，水平夹角水平夹角水平夹角水平夹角 alpha alpha deltadelta 画左分枝，新顶点画左分枝，新顶点画左分枝，新顶点画左分枝，新顶点(cxcx,cycy)，长度，长度，长度，长度 length length*scalescale，水平夹角水平夹角水平夹角水平夹角 alpha alpha+deltadelta 24清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础分形问题算法实现算法实现void

28、 void DrawLineDrawLine(double(double lengthlength,double,double alphaalpha,double,double cxcx,double,double cycy)double double thetatheta;theta theta=alpha alpha/180.0*/180.0*PIPI;movetomoveto(cxcx,cycy););linerellinerel(length length*coscos(thetatheta),),length length*sinsin(thetatheta););void void

29、 DrawFractalDrawFractal(double(double lengthlength,double,double scalescale,double,double alphaalpha,double double deltadelta,double,double cxcx,double,double cycy,int,int order order)if(if(order order=0)=0)DrawLineDrawLine(lengthlength,alphaalpha,cxcx,cy cy););else else DrawLineDrawLine(lengthlengt

30、h,alphaalpha,cxcx,cy cy););cxcx=cxcx+lengthlength*scalescale*coscos(alphaalpha/180.0*/180.0*PIPI););cy cy=cycy length length*scale scale*sinsin(alphaalpha/180.0*/180.0*PIPI););DrawFractalDrawFractal(lengthlength*scalescale,scalescale,alphaalpha deltadelta,deltadelta,cxcx,cycy,orderorder1);1);DrawFra

31、ctalDrawFractal(lengthlength*scalescale,scalescale,alphaalpha+deltadelta,deltadelta,cxcx,cycy,orderorder1);1);25清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础其他递归问题一Pascal 三角形三角形int int PascalTrianglePascalTriangle(int(int n n,int,int k k)if(if(k k=0|=0|k k=n n)return 1;return 1;else else return

32、 return PascalTrianglePascalTriangle(n n1,1,k k1)+1)+PascalTrianglePascalTriangle(n n1,1,k k););26清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础其他递归问题二折半查找折半查找int int BinarySearchBinarySearch(int(int a a,int,int keykey,int,int lowlow,int,int high high)int int mid mid=(=(low low+high high)/2;)/2;

33、if(if(low low high high)return 1;)return 1;if(if(key key=a a midmid)return )return midmid;else else if(if(key key 2 2递归算法的效率远远低于迭代算法递归算法的效率远远低于迭代算法32清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础12.3 递归与迭代递归算法实现递归算法实现long int long int FabonacciFabonacci(int(int n n)if(if(n n=1|=1|n n=2)=2)return

34、 1;return 1;else else return return FabonacciFabonacci(n n 1)+1)+FabonacciFabonacci(n n 2);2);33清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础12.3 递归与迭代迭代算法实现迭代算法实现long int long int FabonacciFabonacci(int(int n n)int int i i,f f,f1f1=1,=1,f2f2=1;=1;if(if(n n=1|=1|n n=2)=2)return 1;return 1;else else for(for(i i=3;=3;i i=n n;i i+)+)f f=f1f1+f2f2;f2f2=f1f1;f1f1=f f;return return f f;34清华大学计算机科学与技术系清华大学计算机科学与技术系http:/计计算算机机程程序序设设计计基基础础作 业第第360360页：第三题（编程题）页：第三题（编程题）第第第第 7 7 7 7 小题小题小题小题