清华大学C课件9

第六章函数、递推与递归清华大学,函数的概念、定义、调用和返回带自定义函数的程序设计递推算法递归思想及算法实现,内容要点,为什么需要函数？满足实际应用需求,6.1函数,函数是组成C/C+程序的基础C/C+库中已经为用户提供了许多标准库函数用户可以根据自己的需要选用合适的库函数如果没有所需函数，用户可自己定义和编写一些函数,函数概述,函数是模块化的基本单位主调函数与被调函数程序、源文件与函数关系程序中各模块关系,intmain()inta,b,sum;sum=Add(a,b);/函数调用,intAdd(intx,inty);/函数声明,intAdd(intx,inty)/函数定义/函数体取代函数声明尾部的分号,要使用C+函数，必须完成如下工作：提供函数定义提供函数声明（原型）调用函数,函数定义：有返回值的函数没有返回值的函数（void函数）,voidfunctionName(parameterList)/没有返回值return;/可选,typeNamefunctionName(parameterList)/有返回值returnvalue;,【任务6.1】素数判定,思路：设计一个函数intcheckprime(inta)，负责检查a是否为素数：如果是素数，该函数返回1；否则，该函数返回0。,#include#includeusingnamespacestd;intmain()inta=0;couta;if(checkprime(a)/函数调用couta是素数endl;elsecouta不是素数endl;return0;,intcheckprime(intn);/函数声明,intcheckprime(intn)/函数定义，n为形式参数intk=0;for(k=2;k=sqrt(n);k=k+1)if(n%k=0)/如果n能被k整除则返回0return0;return1;/n不能被k整除则返回1,函数原型intcheckprime(intn);,提高算法效率只要在1和n之间存在一个因子就可终止，并返回n不是素数若n可被2整除，不需检验其它数，程序终止并返回n不是素数；若否，则所有偶数都不是因子，程序只需检验奇数程序不必检验因子一直到n，只需到sqrt(n)即可,intcheckprime(intn)inti;if(n%2=0)return0;for(i=3;i=sqrt(n);i+=2)if(n%i=0)return0;return1;,问题1：本算法效率？每次迭代都需要计算平方根，很费时,问题2：本算法正确性？n=1n=2时结果错误,intcheckprime(intn)intlimit,i;limit=sqrt(n);if(n%2=0)return0;for(i=3;iy)return1;elsereturn-1;,编写函数Swap，互换两个整型数据x、y的值,voidSwap(intx,inty)intt;t=x;x=y;y=t;return;/没有返回值只需直接写return语句,函数定义示例：Swap函数,intIsDigit(charc)if(c=0,intIsDigit(charc)if(c=48,函数定义示例：IsDigit函数,charTransformIntoUpperCase(charc)if(c=a,函数定义示例：TransformIntoUpperCase函数,编写函数IsLeapYear，判断某个给定年份是否为闰年,intIsLeapYear(intyear)returnyear%4=0,函数定义示例：IsLeapYear函数,intmysqrt(intx)inti=1,sum=0,count=0;while(sumtimes;n_chars(ch,times);coutch;cout0)coutc;coutn;,doublecube(doublex);intmain()doublep,q;p=1.2;q=cube(p);coutp=pendl;cout实参p的地址是x;ciny;coutx“yendl;(1)Swap(x,y);coutx“ya;cinb;couta“bendl;Swap();couta“bendl;return0;,voidSwap()inttemp;couta“bendl;temp=a;a=b;b=temp;couta“bx;p=Max(x,p);q=Min(x,q);sum=sum+x;cout“选手得分”b)returna;elsereturnb;intMin(intc,intd)if(cai;coutYouhaveenteredthematrixa:n;print(a,n);return0;voidprint(intarray,intsize)/voidprint(int*array,intsize)for(intk=0;k=size-1;k+)coutsetw(10)arraykendl;,问题：一维数组作为参数,voidbubble(int,int);intmain()inta10;bubble(a,10);return0;,voidbubble(intarray,intsize)for(intj=1;jsize;j+)for(inti=0;isize-j;i+)if(arrayiaij;coutYouhaveenteredthematrixa:n;print(a,n);return0;voidprint(intarray4,intxsize)for(inti=0;i=xsize-1;i+)for(intj=0;j4;j+)coutsetw(10)arrayij;cout=1);for(i=1;i=5;i+)coutfishiendl;return0;,intmain()intn=100,i=0;intq101;q0=1;for(i=1;i=n;i=i+1)qi=qi-1+i;cout“切100刀后最多可得”qn块n;coutn的阶乘为fact(n)endl;return0;unsignedlongfact(unsignedintn)unsignedlongresult;if(n=1)result=1;elseresult=n*fact(n-1);returnresult;,【任务6.5】求n!,3,n,main,main函数栈框架,函数调用栈框架,fact,第一次以3为参数调用fact，进入函数时,3,n,result,fact,第二次以2为参数调用fact，进入函数时,fact,2,n,result,fact,第三次以1为参数调用fact，进入函数时,fact,fact,1,n,result,fact,第三次以1为参数调用fact，退出函数前,fact,fact,1,1,n,result,fact,第二次以2为参数调用fact，退出函数前,fact,2,2,n,result,fact,第一次以3为参数调用fact，退出函数前,3,6,n,result,3,n,main,递归调用结束后的main函数栈框架,递归与递推的比较（以求n!为例）,递推：从已知的初始条件出发，逐次去求所需要的阶乘值。fact(1)=1fact(2)=2*fact(1)=2fact(3)=3*fact(2)=6递归：出发点不在初始条件上，而在求解目标上。从所求的未知项出发，逐次调用自身，直到递归的边界（初始条件）。递归算法比较符合人的思维方式，逻辑性强，易于理解。,递归与递推的相似之处：都基于控制结构，均涉及循环递推：使用显式循环结构递归：使用选择结构，通过重复性的函数调用实现循环均涉及终止测试，都有可能发生无限循环递推：在循环条件不满足时终止递归：遇到初始条件时终止理论上，能用递归解决的问题也能用递推解决。,计算xn,longdoubleCalPower(longdoublex,intn)longdoubleresult;if(n=0)result=1;elseresult=x*CalPower(x,n1);returnresult;,算法举例(1),求两个正整数的最大公约数,算法举例(2),unsignedintgcd(unsignedintx,unsignedinty)unsignedintt;t=xy?x:y;while(x%t!=0|y%t!=0)t-;returnt;,穷举法,欧氏算法,步骤1：x整除以y，记余数为r步骤2：若r为0，则最大公约数即为y，算法结束步骤3：否则将y作为新x，将r作为新y，重复上述步骤unsignedintgcd(unsignedintx,unsignedinty)unsignedintr;while(1)r=x%y;if(r=0)returny;x=y;y=r;,求两个正整数的最大公约数,unsignedintgcd(unsignedintx,unsignedinty)while(y!=0)unsignedintr=x%y;x=y;y=r;returnx;,unsignedintgcd(unsignedintx,unsignedinty)if(x%y=0)returny;returngcd(y,x%y);,递归算法,求两个正整数的最大公约数,1,1,2,3,5,8,13,21,fibonacci(1)=1fibonacci(2)=1fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)求Fibonacci数的递归程序具有指数复杂性。,求Fibonacci数,算法举例(3),unsignedlongGetFibonacci(unsignedintn)if(n=2|n=1)return1;elsereturnGetFibonacci(n-1)+GetFibonacci(n-2);,unsignedlongGetFibonacci(unsignedintn)unsignedlongresult,i,f1,f2;if(n=2|n=1)return1;f2=1;f1=1;for(i=3;i=n;i+)result=f1+f2;f1=f2;f2=result;returnresult;非递归程序,几个问题的递归思想：,求数组an中各元素的和,求数组an中各元素的最大(最小)值,给数组an排序,求一个自然数的各位数字之和,下楼问题,跳马问题,八皇后问题,递归信任,理解递归问题的原则不分析复杂细节而仅考虑单一层次上的操作不必跟踪递归调用的堆栈框架基本递归假设只要递归调用时的参数比原始参数在某种程度上更简单，则递归调用就一定能获得正确答案递归心理学：这种简单递归调用一定正确工作的假设即为递归信任,递归实现是否检查了最简单情形在尝试将问题分解成子问题前，首先应检查问题是否已足够简单在大多数情况下，递归