信息学奥赛课课通-第6单元-电子课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,高等教育出版社,信息学奥赛课课通（,C+,）,第,6,单元 函数,作者：林厚从,信息学奥赛课课通（,C+,）,1,第,1,课 模块化编程思想,学习目标,1.,体会模块化编程思想。,2.,了解函数的功能和调用。,2,一个,C+,程序无论大小，都由一个或者多个“函数”组成，而且其中必须有且只有一个函数,main,（），称之为“主函数”，由函数,main,（）调用其他函数来完成程序的特定功能。当然，其他函数之间也可以按照规则互相调用。,C+,中的函数由一段相对独立的代码组成，这段代码能实现某一项具体、独立、完整的功能。,函数在程序设计中的作用主要有两个，一是“代码重用”；二是“问题分解”。,3,代码重用是保证同一个函数可以被一个或多个函数调用任意多次，从而减少重复代码的编写。问题分解可以保证一个大的程序（或者说软件），按照模块化编程思想，由大化小，分解成若干个结构清晰、功能独立、调试方便的函数，甚至给若干人合作完成，从而提高开发效率,。,C+,提供了很多常用的系统函数，如输入单个字符的函数,getchar(),等。但是有些函数，必须要加上相关头文件才能使用，例如整数取绝对值的函数,abs(),、求算术平方根的函数,sqrt(),等，必须要包含“,cmath,”。,4,例,1,、曼哈顿距离,【,问题描述,】,平面直角坐标系中位于坐标（,x1,，,y1,）的,i,点与位于坐标（,x2,，,y2,）的,j,点的曼哈顿距离为,d,（,i,，,j,）,=|x1-x2|+|y1-y2|,。请编程输入两个点的坐标，输出它们之间的曼哈顿距离。,【,输入格式,】,一行四个整数（,100,以内），分别表示两个点的坐标（,x1,，,y1,）和（,x2,，,y2,）。,【,输出格式,】,一行一个整数，表示两个点之间的曼哈顿距离。,【,输入样例,】,10 5 6 20,【,输出样例,】,19,5,/p6-1-1,#include,#include,using namespace std;,int main(),long long x1,y1,x2,y2,mht;,cin x1 y1 x2 y2;,mht=abs(x1-x2)+abs(y1-y2);,cout mht endl;,return 0;,6,例,2,、,回文数个数,【,问题描述,】,输入一个正整数,n,，求,1n,之间“回文数”的个数。回文数是指一个数倒过来和原数一样，如,12121,、,11,、,1221,、,1,是回文数，而,1231,不是回文数。,【,输入格式,】,一行一个正整数,n,，,1n10000,。,【,输出格式,】,一行一个正整数，表示,1n,之间回文数的个数。,【,输入样例,】,12,【,输出样例,】,10,7,【,问题分析,】,定义一个计数器变量并初始化为,0,，然后穷举,1n,中的每一个整数,i,，判断是否是回文数，是则计数器加一。如何判断,i,是回文数呢？,C+,系统函数里没有，只能自己编写一个。,8,/p6-1-2,#include,using namespace std;,/,在此自定义一个函数,check(),，如果,i,是回文数返回,true,，否则返回,false,int main(),int n,i,ans=0;,scanf(“%d”,for(i=1;i=n;i+),if(check(i)ans+;,printf(“%dn”,ans);,return 0;,9,实践巩固,10,第,2,课 函数的定义和调用,学习目标,1.,学会函数的定义和调用。,2.,应用函数解决一些实际问题。,11,C+,要求函数必须先定义、后使用。定义函数，就是要说明函数的返回值类型、函数名、函数参数，以及完成特定功能的语句组合（函数体）。,函数的定义和调用,12,1.,函数的定义,定义函数的格式如下：,返回值类型 函数名（参数列表）,函数体,其中，第一行称为函数头部。函数名是标识这个函数的合法标识符。返回值类型是指一个函数结束后返回给调用者的一个“返回值”的数据类型。,有些函数的功能是执行一系列操作，而不返回任何值，这种情况下，返回值类型是关键字,void,。参数列表是当函数被调用时，调用者向函数传递的各种“参数”，此处的参数称为形式参数，参数列表包括参数的数据类型和参数名，参数是可选的，没有参数就是“无参”函数，但是括号不能省略。,13,1.,函数的定义,大括号之间的部分称为“函数体”，主要包括变量说明语句、表达式语句等。如果有返回值，则函数体内至少有一条语句,“return,表达式,”,。在执行函数体的过程中，一旦遇到,return,语句，执行完就立刻退出函数，不再执行后续的语句。无返回值函数不需要,return,语句。,14,2.,函数的调用,在程序中以任何方式对函数的使用，都称为函数的调用。函数调用是通过“函数名”进行的，,一般格式为：,函数名（参数列表）,此处的参数列表称为“实际参数”，是传递给调用函数的，必须严格对应函数定义时函数头部的形式参数列表，包括参数个数、参数顺序、数据类型。调用无参函数时参数列表可以没有，但括号不能省略。如果参数列表包含多个参数，则各参数间用逗号隔开。,15,函数调用方式,以函数在程序中出现的位置和形式来看，函数调用方式分为三种。,（,1,）函数调用作为一条独立语句，完成一件事情（一系列操作），没有任何返回值。例如：,print(n);doit(dep,total);,input();,（,2,）函数调用的结果作为表达式的一部分。例如：,int t=compute(i,j),+i*j;,（,3,）以实参形式出现在其他函数调用中。例如：,number=min(sum(-5,100),n);num=max(max(a,b),c);,16,例,1,、阅读程序，写出程序的运行结果，体会“代码重用”和“有返回值函数”的调用。,/p6-2-1,#include,using namespace std;,int fac(int n),int z=1;,for(int i=1;i=n;i+)z=z*i;,return z;,int main(),int x=fac(5)+fac(4);/,函数调用出现在表达式中,cout x y?x:y;,cout w x y z;,cout big(big(x,y),z)y)return x;,else return y;,19,例,4,、统计闰年,【,问题描述,】,输入两个年份,x,和,y,，统计并输出公元,x,年到公元,y,年之间的所有闰年数（包括,x,年和,y,年），,1xy3000,。,【,输入格式,】,一行两个正整数表示,x,和,y,，之间用一个空格隔开。,【,输出格式,】,一行一个正整数，表示公元,x,年到公元,y,年之间的所有闰年数。,【,输入样例,】,2000 2004,【,输出样例,】,2,20,/p6-2-4,#include,using namespace std;,bool rn(int n),if(n%4=0),else return false;,int main(),int x,y,t=0;,cin x y;,for(int i=x;i=y;i+),if(rn(i)t+;,cout t endl;,return 0;,21,例,5,、数的分离,【,问题描述,】,定义一函数,digit(n,k),分离出整数,n,从右边数第,k,个数字。如,digit(2076,1),等于,6,，而,digit(2076,5),等于,0,。,main,函数输入,n,和,k,，调用,digit(n,k),输出答案，,n,在,long long,范围内。,【,输入格式,】,一行两个整数分别表示,n,和,k,，之间用一个空格隔开。,【,输出格式,】,一行一个整数，表示整数,n,从右边数第,k,个数字。,【,输入样例,】,31859 3,【,输出样例,】,8,22,/p6-2-5,#include,using namespace std;,int digit(long long n,int k),int tmp;,for(int i=1;i n k;,cout digit(n,k)endl;,return 0;,23,实践巩固,24,第,3,课 函数的参数,学习目标,1.,理解形式参数与实际参数。,2.,理解参数传递的三种方式。,25,函数的参数,参数是函数与函数之间实现通信的数据“接口”。函数调用的过程就是调用者带着实际参数（如果有）执行函数，将实际参数“传递”给形式参数，执行完函数体后再将计算得到的返回值传递给调用者（如果有）。,在未调用函数前，函数中的形式参数并不分配内存空间。只有在被调用执行时，才被分配临时存储空间。函数调用结束后，形式参数的内存空间将被操作系统立刻收回。,26,函数的参数,实际参数可以是任何符合形式参数类型的常量、变量、表达式。函数参数传递的过程就是实际参数和形式参数相结合的过程，必须遵守三个一致。,（,1,）个数一致。,（,2,）顺序一致。,（,3,）类型一致。,27,例,1,、打印字符,三角形,【,问题描述,】,编写一个函数,print(n,ch),，表示打印一行,n,个英文字母,ch,，并换行。然后，在函数,main(),中输入,n,和,ch,，调用函数,print(),打印一个字符三角形。,【,输入格式,】,一行一个整数,n,和一个英文字母,ch,，之间用一个空格隔开，,1n20,。,【,输出格式,】,n,行，第,i,行有,i,个字母,ch,。,【,输入样例,】,3 a,【,输出样例,】,a,aa,aaa,28,/p6-3-1,#include,using namespace std;,void print(,int i,char ch),for(int j=1;j=i;j+)cout ch;,cout n ch;,for(int i=1;i=n;i+)print(,i,ch,);,return 0;,29,函数参数的传递方式,根据不同的应用需求，函数参数的传递方式，或者说函数参数的调用方式分为三种：,（,1,）传值（调用）,：,参见例,2,；,（,2,）传址（调用）,：,参见例,3,；,（,3,）引用（调用）,：,参见例,4,、例,5,；,30,例,2,、阅读程序，写出程序的运行结果，体会函数的传值,(,调用,),。,/p6-3-2,#include,using namespace std;,void swap(,int x,int y,),int temp;,temp=x;,x=y;,y=temp;,cout x “y endl;,int main(),int a=10,b=50;,swap(a,b);,cout a “b endl;,return 0;,31,例,3,、阅读程序，写出程序的运行结果，体会函数的传址,(,调用,),。,/p6-3-3,#include,using namespace std;,void swap(,int*x,int*y,)/,形式参数的类型定义为指针,int temp;,temp=*x;,*x=*y;,*y=temp;,cout *x “*y endl;,int main(),int a=10,b=50;,swap(,&a,&b,);/,实际参数必须是地址,cout a “b endl;,return 0;,32,例,4,、阅读程序，写出程序的运行结果，体会变量及其引用的操作。,/p6-3-4,/#include,using namespace std;,int main(),int k=32;,int,cout “k=”k “k_adr=”k_adr endl;,k+;,cout “k=”k “k_adr=”k_adr endl;,k_adr=-5;,cout “k=”k “k_adr=”k_adr endl;,int i=100;,k_adr+=i;,cout “k=”k “k_adr=”k_adr endl;,return 0;,33,例,5,、阅读程序，写出程序的运行结果，体会函数的引用调用。,/p6-3-5,#include,using namespace std;,void swap(,int&a,int&b,),int temp;,temp=a;,a=b;,b=temp;,cout a “b endl;,int main(),int a=10,b=50;,swap(,a,b,);,cout a “b endl;,return 0;,34,实践巩固,35,第,4,课 变量的作用域,学习目标,1.,理解变量的作用域。,2.,熟练规范使用局部变量和全局变量。,36,变量的作用域,变量按其在程序中的作用范围，分为全局变量和局部变量。,全局变量是指定义在任何函数之外的变量，也就是不被任何“函数体”所包含，可以被源文件中其他函数所共用，用静态数据区存储，作用域（有效范围）是从定义变量的位置开始到源文件（整个程序）结束。,局部变量是指在一个函数（包括,main,函数）内部定义的变量，它只在本函数内部有效，其他函数不能使用这些变量，用动态数据区存储，函数的参数也是局部变量。,37,例,1,、以下程序中，哪些是全局变量，哪些是局部变量，并指出它们的作用域。,int x,y;,float a,b;,float find(int c,d),float e,f;,int i,j;,int z;,void doit(),int main(),int g,h;,38,例,2,、找出程序中的错误。如果去掉错误，程序输出什么。,/p6-4-2,#include,using namespace std;,int f(),int b=0,c=1;,b=b+1;,c=c+1;,return(b+c);,int main(),for(int i=1;i 4;i+),cout i “.sum=”f()endl;,cout “b=”b “c=”c x;,for(int i=1;i x y;,cout x+y endl;,cout x endl;,cout :x endl;,cout i “y endl;,return 0;,41,例,4,、阅读程序，写出程序的运行结果。,/p6-4-4,#include,using namespace std;,int x=10,y=15;,void change(int a,int b,int x),int temp;,x+;y+;,temp=a;a=b;b=temp;,int main(),int a=3,b=5;,cout x “”y “”a “”b endl;,change(a,b,x);,cout x “”y “”a “”b 0),p(n-1);,for(int i=0;i n;i+)cout n;,cout n;,cout jc(n)m n;,cout gcd(m,n)1),if(n%p=0),if(first),cout p;,first=false;,else cout “n;,zyz(n,2);,cout endl;,return 0;,57,例,5,、抽奖,问题描述,参见教材,213,页。,【,问题分析,】,我们已经学习过用循环语句实现“二分查找”，很明显，也可以采用“递归”思想实现二分查找。,58,/p6-5-5,#include,using namespace std;,int win,g101;,int binsearch(int left,int right),if(left=right),int mid=(left+right)/2;,if(gmid=win)return mid;/,找到,if(win gmid)return binsearch(mid+1,right);/,在右半部分,else return 0;/,没找到,int main(),int n,i,f,left,right,mid;,scanf(%d,for(i=1;i win;,f=binsearch(1,n);,cout f endl;,return 0;,59,实践巩固,60,第,6,课 函数应用举例,学习目标,1.,熟练应用函数和结构化编程思想解决一些实际问题。,2.,学会函数的单步跟踪，并进一步理解递归函数的执行过程。,61,例,1,、孪生素数,【,问题描述,】,在素数的大家庭中，大小之差为,2,的两个素数称之为一对“孪生素数”，如,3,和,5,、,17,和,19,等。请你编程统计出不大于自然数,n,的素数中，孪生素数的对数。,【,输入格式,】,一行一个正整数,n,，,1n2 31,。,【,输出格式,】,若干行，每行两个整数，之间用一个空格隔开，从小到大输出每一对孪生素数。,【,输入样例,】,100,【,输出样例,】,3 5,5 7,11 13,17 19,29 31,41 43,59 61,71 73,62,【,问题分析,】,首先，大于,2,的两个连续自然数不可能都是素数，大于,2,的偶数也一定不是素数。所以，从,3,开始穷举一个自然数,s,，检查,s,和,s+2,是不是都为素数，是则输出这对孪生素数。然后，,s=s+2,，继续寻找下一对孪生素数。,63,/p6-6-1,#include,using namespace std;,bool prime(int n),for(int i=2;i*i n;,while(i=n-2),if(prime(i),i+=2;,return 0;,上机实践，学会单步跟踪函数。,64,例,2,、幂次方表示法,问题描述,参见教材,218,页。,【,问题分析,】,将,n,拆分为若干,2,的幂次的和，再将各个幂次（指数）拆分成若干,2,的幂次的和,明显具有递归思想。所以，定义数组元素,p0,表示,2,的,0,次方，,p1,表示,2,的,1,次方，,p2,表示,2,的,2,次方，,从最接近,n,值的,2,的幂次方开始分解，如果,n,大于或等于当前,2i,，则,n,减去,2i,，将,i,分解，,直到,n,为,0,。,具体程序参考教材,218-219,页。,65,例,3,、汉诺塔问题,问题描述,参见教材,219-220,页。,【,问题分析,】,具体分析及程序参考教材,220-222,页。,66,实践巩固,67,