清华大学C 课件9

第六章函数、递推与递归清华大学函数的概念、定义、调用和返回带自定义函数的程序设计递推算法递归思想及算法实现内容要点为什么需要函数？——满足实际应用需求6.1函数函数是组成C/C++程序的基础C/C++库中已经为用户提供了许多标准库函数用户可以根据自己的需要选用合适的库函数如果没有所需函数，用户可自己定义和编写一些函数函数概述•函数是模块化的基本单位•主调函数与被调函数•程序、源文件与函数关系•程序中各模块关系mainfun1fun2fun3fun4fun5file1.cppmain(){}fun1(){}fun2(){}file2.cppfun3(){}fun4(){}fun5(){}program……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。#includeiostream#includecmathusingnamespacestd;intmain(){inta=0;cout请输入一个整数：a=;cina;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;i=limit;i+=2){if(n%i==0)return0;}return1;}问题：本算法正确性？浮点数的存储有误差，程序的正确性依赖于机器的表示精度intcheckprime(intn){intlimit,i;limit=sqrt(n)+1;if(n%2==0)return0;for(i=3;i=limit;i+=2){if(n%i==0)return0;}return1;}if(n=1)return0;if(n==2)return1;改进后的正确函数：函数定义:intcheckprime(intn)checkprime为函数名int是函数返回值的数据类型n为函数的形式参数，形式参数也要定义其数据类型形式参数的特点：定义函数时放在函数名后的括号中函数未被调用时不占内存空间函数被调用时系统为其分配内存空间函数调用结束后释放内存空间作用域限定在函数内，属于局部变量函数声明（原型）：例：intcheckprime(intn);要放在主函数之前，告诉系统有自定义的函数可以被调用。函数原型确保：编译器正确处理函数返回值编译器检查使用的参数数目是否正确编译器检查使用的参数类型是否正确函数调用：一个函数在调用子函数时，要将实在参数赋给形式参数。实在参数是一个具有确定值的表达式。例如：if(checkprime(a))实在参数的个数及类型应与形式参数一致，赋值时前后对应关系不能改变。调用时1717实在参数a形式参数nintcheckprime(intn){…………}如何设计(定义)函数？函数名称参数返回值•求整数的绝对值intabs(intx){……return…;}•求两个正整数的最小公倍数intlcm(intx,inty){}•计算n!unsignedlongFactorial(intn){}•求Fibonacci数列的第n项unsignedlongFibonacci(intn){}•求一元二次方程的根?Compute(doublea,doubleb,doublec){?}•判断a是否为素数intcheckPrime(intn){}•计算整型数组元素的和intSum(?){}•将数组元素排序?Sort(?){?}•编写函数Add，求两个整数之和intAdd(intx,inty){intt;t=x+y;returnt;}函数定义示例：Add函数intAdd(intx,inty){returnx+y;}•编写函数Compare，比较两个整型数据x、y的大小。若x等于y返回0，若x大于y返回1，若x小于y返回-1intCompare(intx,inty){intt;if(x==y)t=0;elseif(xy)t=1;elset=-1;returnt;}函数定义示例：Compare函数;多条return语句intCompare(intx,inty){if(x==y)return0;elseif(xy)return1;elsereturn-1;}•编写函数Swap，互换两个整型数据x、y的值voidSwap(intx,inty){intt;t=x;x=y;y=t;return;//没有返回值只需直接写return语句}函数定义示例：Swap函数intIsDigit(charc){if(c='0'&&c='9')return1;elsereturn0;}intIsDigit(charc){if(c=48&&c=57)return1;elsereturn0;}函数定义示例：IsDigit函数charTransformIntoUpperCase(charc){if(c='a'&&c='z')//‘a’~’z’的ASCII值为61H~7AH//‘A’~’Z’的ASCII值为41H~5AHreturnc–'a'+'A';elsereturnc;}函数定义示例：TransformIntoUpperCase函数•编写函数IsLeapYear，判断某个给定年份是否为闰年intIsLeapYear(intyear){returnyear%4==0&&year%100!=0||year%400==0;}函数定义示例：IsLeapYear函数intmysqrt(intx){inti=1,sum=0,count=0;while(sum=x){sum+=i;count++;i+=2;}returncount-1;}求整数的平方根，取其整数部分思考：参数的有效性、合法性判断应•放在函数里?•放在主程序里?intmysqrt(intx){inti=0;while(i*i=x)i++;returni-1;}函数定义示例：我的平方根函数……intmain(){inttimes;charch;coutEnteracharater:;cinch;while(ch!='q'){coutEnteraninteger:;cintimes;n_chars(ch,times);coutThevalueoftimesistimesendl;coutEnteracharater:;cinch;}coutBye!!!\n;return0;}例：字符串输出voidn_chars(char,int);voidn_chars(charc,intn){while(n--0)coutc;cout\n;}……doublecube(doublex);intmain(){doublep,q;p=1.2;q=cube(p);coutp=pendl;cout实参p的地址是&pendl;coutq=qendl;return0;}doublecube(doublex){coutx=xendl;cout形参x的地址是&xendl;return(x*x*x);}例：……intmain(){intx,y;cinx;ciny;coutx““yendl;(1)Swap(x,y);coutx““yendl;(4)return0;}例：互换两个整数voidSwap(intx,inty){inttemp;coutx““yendl;(2)temp=x;x=y;y=temp;coutx““yendl;(3)return;}输入：1020输出：1020(1)1020(2)2010(3)1020(4)xymain()x1020ymain()main()x1020Swap()tempymain()x2010Swap()10tempyx1020ymain()函数调用栈框架:值传递与数据互换问题•值传递：值复制操作–将实际参数值复制给形式参数–此过程单向不可逆–复制完成后，形参与实参没有任何关联•如何解决数据值互换问题？–使用全局变量作为函数通信的手段–使用指针传递变量的地址缺点：将全局变量作为函数调用环境的一部分，没有在函数声明头部显式给出来，不易理解代码逻辑。……inta,b;/*全局变量，保证所有函数都可以访问到*/voidSwap();/*不再需要函数参数*/intmain(){cina;cinb;couta““bendl;Swap();couta““bendl;return0;}voidSwap(){inttemp;couta““bendl;temp=a;a=b;b=temp;couta““bendl;return;}输出：1020102020102010【任务6.2】给歌手打分•定义intMax(inta,intb)函数，返回a,b中的大者•定义intMin(inta,intb)函数，返回a,b中的小者•定义整型变量p，用以保存N个数中的最大值•定义整型变量q，用以保存N个数中的最小值•定义一个整型变量sum做累加用•最终得分：(sum-p-q)/(N-2)#includeiostream#includecmathusingnamespacestd;intMax(int,int);intMin(int,int);intmain(){intp=0;intq=100;intsum=0，x=0;inti=1;for(i=1;i=10;i=i+1){cout“请第”i“位裁判给分”endl;cinx;p=Max(x,p);q=Min(x,q);sum=sum+x;}cout“选手得分”(sum-p-q)/(10-2);return0;}intMax(inta,intb){if(ab)returna;elsereturnb;}intMin(i