清华大学C--课件9doc资料.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章函数、递推与递归,清华大学,函数的概念、定义、调用和返回,带自定义函数的程序设计,递推算法,递归思想及算法实现,内 容 要 点,为什么需要函数？,满足实际应用需求,6.1,函数,函数是组成,C/C+,程序的基础,C/C+,库中已经为用户提供了许多标准库函数,用户可以根据自己的需要选用合适的库函数,如果没有所需函数，用户可自己定义和编写一些函数,函数概述,函数是模块化的基本单位,主调函数与被调函数,程序、源文件与函数关系,程序中各模块关系,file1.cpp,main,(),fun1,(),fun2,(),file2.cpp,fun3,(),fun4,(),fun5,(),program,int,main,(),int,a,b,sum,;,sum,=,Add,(,a,b,);,/,函数调用,int,Add,(int,x,int,y,),;,/,函数声明,int,Add,(int,x,int,y,),/,函数定义,/,函数体取代函数声明尾部的,分号,要使用,C+,函数，必须,完成如下工作：,提供函数定义,提供函数声明（原型）,调用函数,函数定义：,有返回值的函数,没有返回值的函数（,void,函数）,void functionName(parameterList),/,没有返回值,return/,可选,typeName functionName(parameterList),/,有返回值,return value;,【,任务,6.1】,素数判定,思路：,设计一个函数,int check,prime(int a),，,负责检查,a,是否为素数：,如果是素数，该函数返回,1,；,否则，该函数返回,0,。,#include,#include,using namespace std;,int,main,(),int a=0;,cout a;,if(,check,prime(a),),/函数,调用,cout a 是素数 endl;,else,cout a 不是素数 endl;,return 0;,int,check,prime(,int,n,);,/函数声明,int check,prime(int,n),/函数,定义，,n,为形式参数,int k=0;,for(k=2;k=sqrt(,n,);k=k+1),if(,n,%k=0,),/如果,n,能被k整除则返回0,return 0;,return 1;/,n,不能被k整除则返回1,有何问题？,函数原型,int check,prime(int,n,);,提高算法效率,只要在,1,和,n,之间存在一个因子就可终止，并返回,n,不是素数,若,n,可被,2,整除，不需检验其它数，程序终止并返回,n,不是素数；若否，则所有偶数都不是因子程序只需检验奇数,程序不必检验因子一直到,n,，只需到,sqrt,(,n,),即可,int,check,prime,(int,n,),int,i,;,if(,n,%2,=0),return 0;,for(,i,=3;,i,=,sqrt,(,n,);,i,+=2),if(,n,%,i,=0),return 0;,return 1;,问题,1,：本算法效率？,每次迭代都需要计算平方根，很费时,问题,2,：本算法正确性？,n,=1,n,=2,时结果错误,int,check,prime,(int,n,),int,limit,i,;,limit,=,sqrt,(,n,);,if(,n,%2,=0),return 0;,for(,i,=3;,i,=,limit,;,i,+=2),if(,n,%,i,=0),return 0;,return 1;,问题：本算法正确性？,浮点数的存储有误差，程序的正确性依赖于机器的表示精度,int,check,prime,(int,n,),int,limit,i,;,limit,=,sqrt,(,n,)+1;,if(,n,%2,=0),return 0;,for(,i,=3;,i,=,limit,;,i,+=2),if(,n,%,i,=0),return 0;,return 1;,if(,n y),t=1;,else,t=-1;,return t;,函数定义示例Compare,函数,;,多条,return,语句,int Compare(int x,int y),if(x=y),return 0;,else if(x y),return,1;,else,return-1;,编写函数,Swap,，互换两个整型数据,x,、,y,的值,void,Swap,(int x,int y),int t;,t=x;,x=y;,y=t;,return;,/,没有返回值只需直接写,return,语句,函数定义示例：,Swap,函数,int IsDigit(char c),if(c=0&c=48&c,=a&c=z),/az,的,ASCII,值为,61H7AH,/AZ,的ASCII,值为,41H5AH,return c a+A;,else,return c;,函数定义示例：,TransformIntoUpperCase,函数,编写函数,IsLeapYear,，判断某个给定年份是否为闰年,int IsLeapYear,(int year),return,year%4=0,函数定义示例：,IsLeapYear,函数,int,mysqrt,(int,x,),int i=1,sum=0,count=0;,while(sum=x),sum+=i;,count+;,i+=2;,return,count-1,;,求整数的平方根，取其整数部分,思考：,参数的有效性、合法性判断,应,放在函数里,?,放在主程序里,?,int mysqrt(int x),int i=0;,while(i*ich;,while(ch!=q),couttimes;,n_chars(ch,times);,coutThe value of times is timesch;,cout0),coutc;,coutn;,double cube(double x);,int main(),double p,q;,p=1.2;,q=,cube(p),;,coutp=pendl;,cout,实参,p,的地址是,&p,endl;,coutq=qendl;,return 0;,double cube(double x),coutx=xendl;,cout,形参,x,的地址是,&x,x;,ciny;,cout,x“yendl;(1),Swap,(,x,y,);,cout,x“yendl;(4),return 0;,例：互换两个整数,void,Swap,(int,x,int,y,),int,temp,;,cout,x“yendl;(2),temp,=,x,;,x,=,y,;,y,=,temp,;,cout,x“y,a;,cinb;,cout,a,“,b,endl;,Swap,();,cout,a,“,b,endl;,return 0;,void,Swap,(),int,temp,;,cout,a,b,endl;,temp,=,a,;,a,=,b,;,b,=,temp,;,cout,a,“,b,endl;,return;,输出：,10 20,10 20,20 10,20 10,【,任务,6.2】,给歌手打分,定义,int Max(int a,int b),函数，返回,a,b,中的大者,定义,int Min(int a,int b),函数，返回,a,b,中的小者,定义整型变量,p,，用以保存,N,个数中的最大值,定义整型变量,q,，用以保存,N,个数中的最小值,定义一个整型变量,sum,做累加用,最终得分：,(sum-p-q)/(N-2),#include,#include,using namespace std;,int Max(int,int);,int Min(int,int);,int main(),int p=0;int q=100;,int sum=0,，,x=0;int i=1;,for(i=1;i=10;i=i+1),cout“,请第”,i,“,位裁判给分”,x;,p=,Max(x,p),;,q=,Min(x,q),;,sum=sum+x;,cout“,选手得分”,b),return a,;,else,return b;,int Min(int c,int d),if (c d),return c,;,else,return d;,#include,#include,using namespace std;,void print(int,int);,/void print(int*,int);,int main(),const int n=5;int an;,coutai;,coutYou have entered the matrix a:n;,print(a,n);,return 0;,void print(int array,int size),/void print(int*array,int size),for(int k=0;k=size-1;k+),cout,setw(10),arraykendl;,问题：一维数组作为参数,void bubble(int,int);,int main(),int a10;,bubble(a,10);,return 0;,void bubble(int array,int size),for(,int j,=1;jsize;j+),for(,int i,=0;isize-j;i+),if(arrayiarrayi+1),int p,=arrayi;,arrayi=arrayi+1;,arrayi+1=p;,冒泡排序：,#include,#include,using namespace std;,void print(int4,int);,int main(),const int n=5;int an4;,coutEnter matrix a:n;,for(int i=0;iaij;,coutYou have entered the matrix a:n;,print(a,n);,return 0;,void print(int array4,int xsize),for(int i=0;i=xsize-1;i+),for(int j=0;j4;j+),coutsetw(10)arrayij;,cout=1;i-),if(fishi+1%4!=0),break;,/,跳出,for,循环,else,fishi=fishi+1*5/4+1;,/,计算第,i,人看到的鱼数,while(i=1);,for(i=1;i=5;i+)cout fishi endl;,return 0;,int main(),int n=100,i=0;int q101;,q0=1;,for(i=1;i=n;i=i+1),qi=qi-1+i;,cout“,切,100,刀后最多可得”,qn,块,endl;,return 0;,【,任务,6.4】,王小二切饼,1 2 4 7 11,切,0,刀 切,1,刀 切,2,刀 切,3,刀 切,4,刀,递推公式：,q(0)=1,q(n)=q(n-1)+n,5051,递归算法,在可计算性理论中占有重要地位，它是算法,设计的有力工具，对于拓展编程思路非常有用。,6.3,递归及其实现,递归的目的,简化复杂问题的手段：,将问题逐步化简（递简），在化简过程中,保持原问题的性质不变,，直到问题最简，可以轻易地获得答案；然后将简化问题的答案组装成原始问题的解（回归）,递归示例,n,!=1,2 3 ,n,:,n,!=(,n,-,1)!,n,;1!=1,x,n,=,x,x,x,x,:,x,n,=,x,n,-,1,x,;,x,0,=1,或结点,和,与结点：,A,B,C,条件,Z,条件,!Z,A,B,G,Z,1,Z,2,Z,n,C,条件为,Z,1,Z,2,Z,n,A,取值为,B,或,C,或,G,或结点,A,为,与结点,，,A,的最终取值为,C,结点的值，为了求得,C,的值，,先求出,B,结点的值，,C,是,B,的,函数。,A,B,C,A,B,D,C,与结点,A,结点的值最终为,D,的值，,为了求,D,需要先求,B,和,C,。,先求左边的点才能求最右边,的点。,例如：求,n!,的,与或图,直接可解结点,C=1,D=2*C=2,B=D=2,E=3*B=3*2=6,A=E=6,例如：求,3!,的,与或图,求,3!,的递归调用与返回,求,3!,的程序框图,1,求,3!,的程序框图,2,unsigned long fact(unsigned int);,int main(),int n=0;,coutn;,coutn,的阶乘为,fact(n),endl;,return 0;unsigned long,fact,(unsigned int,n,),unsigned long result;,if(n=1)result=1;,elseresult,=,n*,fact(,n,-1),;,return result;,【,任务,6.5】,求,n!,3,n,main,main,函数栈框架,函数调用栈框架,main,fact,第一次以,3,为参数调用,fact,，进入函数时,3,n,result,main,fact,第二次以,2,为参数调用,fact,，进入函数时,fact,2,n,result,main,fact,第三次以,1,为参数调用,fact,，进入函数时,fact,fact,1,n,result,main,fact,第三次以,1,为参数调用,fact,，退出函数前,fact,fact,1,1,n,result,main,fact,第二次以,2,为参数调用,fact,，退出函数前,fact,2,2,n,result,main,fact,第一次以,3,为参数调用,fact,，退出函数前,3,6,n,result,3,n,main,递归调用结束后的,main,函数栈框架,递归,与,递推的,比较（以求,n!,为例）,递推：,从已知的初始条件出发，逐次去求所需要的,阶乘值。,fact(1)=1,fact(2)=2*fact(1)=2,fact(3)=3*fact(2)=6 ,递归：,出发点不在初始条件上，而在,求解目标,上。,从所求的未知项出发，,逐次调用自身,，直到,递归的边界（初始条件）。,递归算法比较符合人的思维方式，逻辑性强，,易于理解。,递归,与,递推的相似之处：,都基于控制结构，均涉及循环,递推：使用显式循环结构,递归：使用选择结构，通过重复性的函数调用实现循环,均涉及终止测试，都有可能发生无限循环,递推：在循环条件不满足时终止,递归：遇到初始条件时终止,理论上，能用递归解决的问题也能用递推解决。,计算,x,n,long double,CalPower(long double x,int n),long double result;,if(n=0),result=1;,else,result=x*,CalPower(x,n 1),;,return result;,算法举例,(1),求两个正整数的最大公约数,算法举例,(2),unsigned int,gcd,(unsigned int x,unsigned int y),unsigned int t;,t=x y?x:y;,while(x%t!=0|y%t!=0),t-;,return t;,穷举法,欧氏算法,步骤,1,：,x,整除以,y,，,记余数为,r,步骤,2,：若,r,为,0,，则最大公约数即为,y,，,算法结束,步骤,3,：否则将,y,作为新,x,，,将,r,作为新y,，,重复上述步骤,unsigned int,gcd,(unsigned int x,unsigned int y),unsigned int r;,while(1),r,=,x%y;,if(r=0),return y;,x=y;,y=r;,求两个正整数的最大公约数,unsigned int,gcd,(unsigned int x,unsigned int y),while(y!=0),unsigned,int r=x%y;x=y;y=r;,return x;,unsigned int,gcd,(unsigned int x,unsigned int y),if(x%y=0),return y;,return,gcd(y,x%y),;,递归算法,求两个正整数的最大公约数,1,1,2,3,5,8,13,21,fibonacci(1)=1,fibonacci(2)=1,fibonacci(n)=fibonacci(n-1)+fibonacci(n-2),求,Fibonacci,数的递归程序具有指数复杂性。,求,Fibonacci,数,算法举例,(3),unsigned long,GetFibonacci,(unsigned int,n,),if(n=2|n=1)return 1;,elsereturn,GetFibonacci,(,n,-1)+,GetFibonacci(n-2),unsigned long,GetFibonacci,(unsigned int,n,),unsigned long result,i,f1,f2;,if(n=2|n=1)return 1;,f2=1;f1=1;,for(i=3;i=n;i+),result,=,f1+f2;f1=f2;f2=result;,return result;,非递归程序,几个问题的递归思想,：,求数组,an,中各元素的和,求数组,an,中各元素的最大,(,最小,),值,给数组,an,排序,求一个自然数的各位数字之和,下楼问题,跳马问题,八皇后问题,递归信任,理解递归问题的原则,不分析复杂细节而仅考虑单一层次上的操作,不必跟踪递归调用的堆栈框架,基本递归假设,只要,递归调用时的参数比原始参数在某种程度上更简单,，则递归调用就一定能获得正确答案,递归心理学：这种简单递归调用一定正确工作的假设即为,递归信任,递归实现是否检查了最简单情形,在尝试将问题分解成子问题前，首先应检查问题是否已足够简单,在大多数情况下，递归函数以,if,开头,如果程序不是这样，仔细检查源程序,是否解决了最简单情形,大量递归错误是由没有正确解决最简单情形导致的,最简单情形不能调用递归,递归分解是否使问题更简单,只有分解出的子问题更简单，递归才能正确工作，否则将形成无限递归，算法无法终止,问题简化过程是否能够确实回归最简单情形，还是遗漏了某些情况,子问题是否与原始问题完全一致,如果递归过程改变了问题实质，则整个过程肯定会得到错误结果,子问题的解是否正确组装为原始问题的解,将子问题的解正确组装以形成原始问题的解也是必不可少的步骤,