第十七讲函数北京大学信息学院2函数的定义函数说明和函数体函数的调用(递归)参数传递:实参和形参返回值变量的作用域:全局变量和局部变量函数示例分治思想本讲内容3C语言与函数C语言是一种函数式语言,它的一个函数实际上就是一个功能模块——C程序的基本组成是函数。一个C程序是由一个固定名称为main的主函数和若干个其他函数(可没有)组成。一个C程序必须有一个、也只能有一个主函数。主函数在程序中的位置可以任意,但程序执行时总是从主函数开始,在主函数内结束。C语言程序是通过函数调用来完成复杂功能。4函数的定义函数的定义语句如下:返回值类型函数名([参数1类型参数名1,参数2类型参数名2,…]){语句1;//语句可能与参数有关语句2;//语句可能与参数有关……return返回值表达式;//该表达式的值的类型必需和返回值类型一致//如果返回值类型为void,则不需return语句,或者返回值表达式为空}参数:函数在完成其功能时需要由函数调用者传递给函数的数据。返回值:函数在完成其功能后得到的结果。5函数定义的例子下面是一个函数定义的例子:两个数相加intadd(intx,inty){intz;z=x+y;returnz;}voidadd2num(){intx,y,z;scanf(“%d%d”,&x,&y);z=x+y;printf(“%d”,z);return;//或者不要此语句}6函数的调用在C语言中,函数是语句的一种组织方式。把完成某一特定功能的语句按照一定的规则组合在一起,起一个名字,就构成了函数。在一段程序中,一个函数可以当作一条语句来运行,这称为函数的调用(函数调用语句)。一个函数在实际被调用时,它所包含的语句才会执行,并且,它的参数的具体取值也是在调用时给定的。在函数执行后,它的执行结果(如果有的话)可以通过返回值返回给调用它的程序。7函数的调用intadd(intx,inty){intz;z=x+y;returnz;}intminus(intx,inty){returnx-y;}8函数的调用voidmain(){intn1,n2;scanf(“%d%d”,&n1,&n2);n1=add(n1,n2);//函数调用语句n2=minus(n1,n2);//函数调用语句if(n10&&n20){printf(“%d\n”,add(n1,n2));//包含函数调用的语句}else{printf(“%d\n”,minus(n1,n2));//包含函数调用的语句}}9函数调用的过程intmax(intx,inty){if(x=y)returnx;elsereturny;}voidmain(){intx=0,y=0,z=0;x=20;y=45;z=max(x,y);……}10函数调用的过程11函数调用的过程12函数调用的过程13函数调用的过程14函数调用的过程15函数调用的过程16函数的调用一个函数在调用前必须是已经定义过的(“先定义,后使用”原则)。函数体函数说明17intmultiple(intx,inty);//函数说明declarationvoidmain(){inta=0,b=0,c;scanf(“%d%d”,&a,&b);c=multiple(a,b);//函数调用printf(“%d\n”,c);}//main()的返回值类型为void,因此没有return语句intmultiple(intx,inty)//函数体,在函数调用之后给出{intz;z=x*y;returnz;}函数说明和函数体18函数说明和函数体另一种形式:不需要函数说明intmultiple(intx,inty)//函数体,在函数调用之前给出{intz;z=x*y;returnz;}voidmain(){inta=0,b=0,c;scanf(“%d%d”,&a,&b);c=multiple(a,b);//函数调用printf(“%d\n”,c);}19函数的递归调用一个关于递归的故事一个没有去过北京的人问:天安门是什么样子?去过北京的人答道:天安门有个城楼,城楼上有个国徽,国徽里有个天安门,天安门有个城楼,城楼上有个国徽,国徽里有个天安门,……20函数的递归调用intfactorial(intn){if(n=0)return–1;if(n==1)return1;returnn*factorial(n-1);//递归调用}递归是常用的编程技术,其基本思想是“自己调用自己”。数学上最常见、最简单的递归问题就是自然数的阶乘。n=1n!=1;n1n!=n*(n-1)!;21适合用递归方法求解的问题满足两个条件出口条件:在某一条件下,递归不再继续递推公式–必需向出口条件推进:后续的情况可由前面的状态推出阶乘:n!=1,n=1;n!=n*(n-1)!,n1Fibonacci数列:F1=F2=1;Fn=Fn-1+Fn-2(n=3)解决问题的思想将问题逐步向更小规模的同类问题推进函数的递归调用22其他递归问题河内塔(HanoiTower)问题:这是一个流传很久的游戏。1.有三根杆子A,B,C。A杆上有n只碟子2.每次移动一块碟子,小的只能叠在大的上面3.把所有碟子从A杆经C杆全部移到B杆上.递归求解:1.若只有一只碟子,直接将它从A杆移到B杆;2.把n-1只碟子从A杆经B杆移动到C杆,将A杆上第n只碟子移到B杆;然后再将n-1只碟子从C杆经A杆移到B杆。函数的递归调用23其他递归问题8皇后问题:把8个皇后放在8x8的棋盘上,使得任何一个都不将其他7个的军。骑士巡游问题:给出一个nxn的棋盘,一位骑士按国际象棋的规则移动——放在第(0,0)格里,找出一种可以走遍整个棋盘的方案(如果存在的话)。即做n2-1次移动,使得棋盘上每个格子都恰好只被访问一次。函数的递归调用24函数参数:实参和形参在调用函数时,向函数传递的参数—实参:可以是数值。也可以是内存地址(指针)。函数内部进行运算的参数—形参实参形参:参数类型必须一一对应,采用值传递25指针形参voidswap(int*x,int*y){inttmp=0;tmp=*x;*x=*y;*y=tmp;}26指针实参voidmain(){inta=0,b=0;a=20;b=45;if(ab)swap(&a,&b);……}27程序运行过程28程序运行过程29程序运行过程30程序运行过程31程序运行过程32程序运行过程33程序运行过程34voidswap(intx,inty){inttmp=0;tmp=x;x=y;y=tmp;}voidmain(){inta=0,b=0;a=20;b=45;if(ab)swap(a,b);……}此时会有什么效果?35if(ab)swap(a,b);参数xy变量tmp代码段swaptmp=x;x=y;y=tmp;2045045202036再看scanf()和printf()函数scanf(char*control,……)每一个希望从键盘中输入的变量,都需要使用指针传递参数。printf(char*control,……)当输出变量是字符串时,也需要使用指针传递参数。39函数的返回值函数执行完以后可以向调用它的程序返回一个值,表明函数运行的状况。很多函数的功能就是对参数进行某种运算,之后通过函数返回值给出运算结果。函数的返回值可以有不同的类型,返回值类型在函数定义时说明。函数的返回值是通过return语句来实现的,一旦一个函数执行了return语句,则表明函数任务已经完成了,函数到此结束了。在main()函数中执行了return语句,表明什么?40函数的返回值intmin(intx,inty);//返回值类型为int,有两个整型参数,函数名为mindoublecalculate(inta,doubleb);//返回值类型为double,有一个整型参数,一个双精度浮点型参数//函数名为calculatecharjudge();//返回值类型为char,没有参数,函数名为judgevoidswap(int*x,int*y);//返回值类型为void,表示不返回任何值,有2个整型指针参数//函数名为swap41intadd(intx,inty){intz;z=x+y;returnz;}intminus(intx,inty){returnx-y;}函数的返回值voidswap(int*x,int*y){inttmp=0;tmp=*x;*x=*y;*y=tmp;}42问题:当需要从函数中返回多个数据时,该如何处理?函数的返回值使用指针形参!43变量的作用域:全局变量和局部变量在程序中,每一个变量都有一个可以起作用的范围,这个范围就是变量的作用域。根据变量作用域的不同,变量可分为全局变量和局部变量。44全局变量:在函数之外定义的变量#includestdio.hinttotal;//全局变量inttryit(inta){if(a100&&a200&&a%2==0)returna;total++;return0;}voidmain(){intn,j;total=0;for(j=0;j1000;j++){scanf(“%d”,&n);printf(“%d\n”,tryit(n));}printf(“%d\n”,total);}全局变量的作用域:从变量定义开始,到源程序结束。45局部变量:在代码段之内定义的变量#includestdio.hintcalculate(inta){intn=a;if(a100&&a=0)n=2*a;if(a=200)n=a*a;returnn;}voidmain(){intn,j,c;c=300;for(j=0;j1000;j++){intc;scanf(“%d”,&n);c=calculate(n);printf(“%d\n”,c);}}局部变量的作用域:从变量定义开始,到当前代码段结束。46变量的作用域参数pp的作用域:整个函数全局变量作用域:从变量定义处开始,一直到整个源文件结束。不同源文件之间:extern局部变量作用域:从变量定义处开始,到第离它最近的左大括号所匹配的右大括号为止。47全局变量和局部变量当需要静态分配较大的内存空间时,需要使用全局变量。#includestdio.hvoidmain(){inti,j,image[10000][10000];for(i=0;i10000;i++){for(j=0;j10000;j++){scanf(“%d”,&image[i][j]);}}}#includestdio.hintimage[10000][10000];voidmain(){inti,j;for(i=0;i10000;i++){for(j=0;j10000;j++){scanf(“%d”,&image[i][j]);}}}48函数示例:假币问题问题描述赛利有12枚银币。其中有11枚真币和1枚假币。假币看起来和真币没有区别,但是重量不同。赛利不知道假币比真币轻还是重。于是他向朋友借了一架天平。赛利希望称三次就能找出假币并且确定假币是轻是重。例如:如果赛利用天平称两枚硬币,发现天平平衡,说明两枚都是真的。如果赛利用一枚真币与另一枚银币比较,发现它比真币轻或重,说明它是假币。经过精心安排每次的称量,赛利保证在称三次后一定能够确定假币。任务编写一个程序,根据三次称量的结果,确定哪一个是假币,并指出其轻重。49输入输入有三行,每行表示一次称量的结果。赛利事先将银币标号为A-L。每次称量的结果用三个以空格隔开的字符串表示:天平左边放置的硬币天平右边放置的硬币平衡状态其中平衡状态用“up”,“down”或“even”表示,分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。函数示例:假币问题50输出输出哪一个标号的银币是假币,并说明它比真币轻还是重。函数示例:假币问题51输入样例ABCDEFGHevenABCIEFJKupABIJEFGHe