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

《信息学奥赛课课通-第6单元电子课件.ppt》由会员分享，可在线阅读，更多相关《信息学奥赛课课通-第6单元电子课件.ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 高等教育出版社高等教育出版社 第第 6 单元单元 函数函数作者：林厚从作者：林厚从信息学奥赛课课通（信息学奥赛课课通（C+C+）高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 1 课课 模块化编程思想模块化编程思想学习目标学习目标1.体会模块化编程思想。体会模块化编程思想。2.了解函数的功能和调用。了解函数的功能和调用。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）一个一个C+程序无论大小，都由一个或者多个程序无论大小，都由一个或者多个“函数函数”组成，而且其中必须有且只有一个函数组成，而且其中必须有且只有一个函数main（），称（），称之

2、为之为“主函数主函数”，由函数，由函数main（）调用其他函数来完成（）调用其他函数来完成程序的特定功能。当然，其他函数之间也可以按照规则程序的特定功能。当然，其他函数之间也可以按照规则互相调用。互相调用。C+中的函数由一段相对独立的代码组成，这段代中的函数由一段相对独立的代码组成，这段代码能实现某一项具体、独立、完整的功能。码能实现某一项具体、独立、完整的功能。函数在程序设计中的作用主要有两个，一是函数在程序设计中的作用主要有两个，一是“代码重代码重用用”；二是；二是“问题分解问题分解”。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）代码重用是保证同一个函数可以被一个

3、或多个函数调用代码重用是保证同一个函数可以被一个或多个函数调用任意多次，从而减少重复代码的编写。问题分解可以保证一任意多次，从而减少重复代码的编写。问题分解可以保证一个大的程序（或者说软件），按照模块化编程思想，由大化个大的程序（或者说软件），按照模块化编程思想，由大化小，分解成若干个结构清晰、功能独立、调试方便的函数，小，分解成若干个结构清晰、功能独立、调试方便的函数，甚至给若干人合作完成，从而提高开发效率甚至给若干人合作完成，从而提高开发效率。C+提供了很多常用的系统函数，如输入单个字符的函数提供了很多常用的系统函数，如输入单个字符的函数getchar()等。但是有些函数，必须要加上相关头

4、文件才能使用，例如等。但是有些函数，必须要加上相关头文件才能使用，例如整数取绝对值的函数整数取绝对值的函数abs()、求算术平方根的函数、求算术平方根的函数sqrt()等，必等，必须要包含须要包含“cmath”。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例1、曼哈顿距离、曼哈顿距离【问题描述问题描述】平面直角坐标系中位于坐标（平面直角坐标系中位于坐标（x1，y1）的）的i点与位于坐标（点与位于坐标（x2，y2）的）的j点的曼哈顿距离为点的曼哈顿距离为d（i，j）=|x1-x2|+|y1-y2|。请编程输入两。请编程输入两个点的坐标，输出它们之间的曼哈顿距离。个点的

5、坐标，输出它们之间的曼哈顿距离。【输入格式输入格式】一行四个整数（一行四个整数（100以内），分别表示两个点的坐标（以内），分别表示两个点的坐标（x1，y1）和）和（x2，y2）。）。【输出格式输出格式】一行一个整数，表示两个点之间的曼哈顿距离。一行一个整数，表示两个点之间的曼哈顿距离。【输入样例输入样例】105620【输出样例输出样例】19高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p6-1-1#include#includeusingnamespacestd;intmain()longlongx1,y1,x2,y2,mht;cinx1y1x2y2;mht=abs

6、(x1-x2)+abs(y1-y2);coutmhtendl;return0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例2、回文数个数、回文数个数【问题描述问题描述】输入一个正整数输入一个正整数n，求，求1n之间之间“回文数回文数”的个数。回的个数。回文数是指一个数倒过来和原数一样，如文数是指一个数倒过来和原数一样，如12121、11、1221、1是回文数，而是回文数，而1231不是回文数。不是回文数。【输入格式输入格式】一行一个正整数一行一个正整数n，1n10000。【输出格式输出格式】一行一个正整数，表示一行一个正整数，表示1n之间回文数的个数。之间回文数的

7、个数。【输入样例输入样例】12【输出样例输出样例】10高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【问题分析问题分析】定义一个计数器变量并初始化为定义一个计数器变量并初始化为0，然后穷举，然后穷举1n中的中的每一个整数每一个整数i，判断是否是回文数，是则计数器加一。如何，判断是否是回文数，是则计数器加一。如何判断判断i是回文数呢？是回文数呢？C+系统函数里没有，只能自己编写系统函数里没有，只能自己编写一个。一个。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p6-1-2#includeusingnamespacestd;/在此自定义一个函数在

8、此自定义一个函数check()，如果，如果i是回文数返回是回文数返回true，否则返回否则返回falseintmain()intn,i,ans=0;scanf(“%d”,&n);for(i=1;i=n;i+)if(check(i)ans+;printf(“%dn”,ans);return0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 2 课课 函数的定义和调用函数的定义和调用学习目标学习目标1.学会函数的定义和调用。学会函数的定义和调用。2.应用函数解决一些实际问题。应用函数解

9、决一些实际问题。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）C+要求函数必须先定义、后使用。定义函数，就是要要求函数必须先定义、后使用。定义函数，就是要说明函数的返回值类型、函数名、函数参数，以及完成特定说明函数的返回值类型、函数名、函数参数，以及完成特定功能的语句组合（函数体）。功能的语句组合（函数体）。函数的定义和调用函数的定义和调用高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）1.函数的定义函数的定义定义函数的格式如下：定义函数的格式如下：返回值类型返回值类型函数名（参数列表）函数名（参数列表）函数体函数体其中，第一行称为函数头部。函数名

10、是标识这个函数的其中，第一行称为函数头部。函数名是标识这个函数的合法标识符。返回值类型是指一个函数结束后返回给调用者合法标识符。返回值类型是指一个函数结束后返回给调用者的一个的一个“返回值返回值”的数据类型。的数据类型。有些函数的功能是执行一系有些函数的功能是执行一系列操作，而不返回任何值，这种情况下，返回值类型是关键列操作，而不返回任何值，这种情况下，返回值类型是关键字字void。参数列表是当函数被调用时，调用者向函数传递的。参数列表是当函数被调用时，调用者向函数传递的各种各种“参数参数”，此处的参数称为形式参数，参数列表包括参，此处的参数称为形式参数，参数列表包括参数的数据类型和参数名，参

11、数是可选的，没有参数就是数的数据类型和参数名，参数是可选的，没有参数就是“无无参参”函数，但是括号不能省略。函数，但是括号不能省略。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）1.函数的定义函数的定义大括号之间的部分称为大括号之间的部分称为“函数体函数体”，主要包括变量说明，主要包括变量说明语句、表达式语句等。如果有返回值，则函数体内至少有一语句、表达式语句等。如果有返回值，则函数体内至少有一条语句条语句“return表达式表达式”。在执行函数体的过程中，一旦遇到。在执行函数体的过程中，一旦遇到return语句，执行完就立刻退出函数，不再执行后续的语句。语句，执行完就

12、立刻退出函数，不再执行后续的语句。无返回值函数不需要无返回值函数不需要return语句。语句。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）2.函数的调用函数的调用在程序中以任何方式对函数的使用，都称为函数的调用。在程序中以任何方式对函数的使用，都称为函数的调用。函数调用是通过函数调用是通过“函数名函数名”进行的，进行的，一般格式为：一般格式为：函数名（参数列表）函数名（参数列表）此处的参数列表称为此处的参数列表称为“实际参数实际参数”，是传递给调用函数，是传递给调用函数的，必须严格对应函数定义时函数头部的形式参数列表，包的，必须严格对应函数定义时函数头部的形式参数列表

13、，包括参数个数、参数顺序、数据类型。调用无参函数时参数列括参数个数、参数顺序、数据类型。调用无参函数时参数列表可以没有，但括号不能省略。如果参数列表包含多个参数，表可以没有，但括号不能省略。如果参数列表包含多个参数，则各参数间用逗号隔开。则各参数间用逗号隔开。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）函数调用方式函数调用方式以函数在程序中出现的位置和形式来看，函数调用方式以函数在程序中出现的位置和形式来看，函数调用方式分为三种。分为三种。（1）函数调用作为一条独立语句，完成一件事情（一）函数调用作为一条独立语句，完成一件事情（一系列操作），没有任何返回值。例如：系列

14、操作），没有任何返回值。例如：print(n);doit(dep,total);input();（2）函数调用的结果作为表达式的一部分。例如：）函数调用的结果作为表达式的一部分。例如：intt=compute(i,j)+i*j;（3）以实参形式出现在其他函数调用中。例如：）以实参形式出现在其他函数调用中。例如：number=min(sum(-5,100),n);num=max(max(a,b),c);高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例1、阅读程序，写出程序的运行结果，体会、阅读程序，写出程序的运行结果，体会“代码代码重用重用”和和“有返回值函数有返回值函

15、数”的调用。的调用。/p6-2-1#includeusingnamespacestd;intfac(intn)intz=1;for(inti=1;i=n;i+)z=z*i;returnz;intmain()intx=fac(5)+fac(4);/函数调用出现在表达式中函数调用出现在表达式中coutxendl;return0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例2、阅读程序，写出程序的运行结果，体会、阅读程序，写出程序的运行结果，体会“无返无返回值函数回值函数”的调用。的调用。/p6-2-2#includeusingnamespacestd;voidmaxn

16、um(intx,inty)intw=xy?x:y;coutwendl;intmain()inta=5,b=22;maxnum(a,b);/函数调用作为一条独立语句函数调用作为一条独立语句return0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例3、阅读程序，写出程序的运行结果，体会函数的、阅读程序，写出程序的运行结果，体会函数的“提前声明提前声明”。/p6-2-3#includeusingnamespacestd;intbig(intx,inty);/函数的提前声明函数的提前声明intmain()intx,y,z;cinxyz;coutbig(big(x,y),

17、z)y)returnx;elsereturny;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例4、统计闰年、统计闰年【问题描述问题描述】输入两个年份输入两个年份x和和y，统计并输出公元，统计并输出公元x年到公元年到公元y年之年之间的所有闰年数（包括间的所有闰年数（包括x年和年和y年），年），1xy3000。【输入格式输入格式】一行两个正整数表示一行两个正整数表示x和和y，之间用一个空格隔开。，之间用一个空格隔开。【输出格式输出格式】一行一个正整数，表示公元一行一个正整数，表示公元x年到公元年到公元y年之间的所有闰年之间的所有闰年数。年数。【输入样例输入样例】2000

18、2004【输出样例输出样例】2高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p6-2-4#includeusingnamespacestd;boolrn(intn)if(n%4=0)&(n%100!=0)|(n%400=0)returntrue;elsereturnfalse;intmain()intx,y,t=0;cinxy;for(inti=x;i=y;i+)if(rn(i)t+;couttendl;return0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例5、数的分离、数的分离【问题描述问题描述】定义一函数定义一函数digit(n

19、,k)分离出整数分离出整数n从右边数第从右边数第k个数字。个数字。如如digit(2076,1)等于等于6，而，而digit(2076,5)等于等于0。main函数输函数输入入n和和k，调用，调用digit(n,k)输出答案，输出答案，n在在longlong范围内。范围内。【输入格式输入格式】一行两个整数分别表示一行两个整数分别表示n和和k，之间用一个空格隔开。，之间用一个空格隔开。【输出格式输出格式】一行一个整数，表示整数一行一个整数，表示整数n从右边数第从右边数第k个数字。个数字。【输入样例输入样例】318593【输出样例输出样例】8高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛

20、课课通（C+）/p6-2-5#includeusingnamespacestd;intdigit(longlongn,intk)inttmp;for(inti=1;ink;coutdigit(n,k)endl;return0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 3 课课 函数的参数函数的参数学习目标学习目标1.理解形式参数与实际参数。理解形式参数与实际参数。2.理解参数传递的三种方式。理解参数传递的三种方式。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通

21、（C+）函数的参数函数的参数参数是函数与函数之间实现通信的数据参数是函数与函数之间实现通信的数据“接口接口”。函数。函数调用的过程就是调用者带着实际参数（如果有）执行函数，调用的过程就是调用者带着实际参数（如果有）执行函数，将实际参数将实际参数“传递传递”给形式参数，执行完函数体后再将计算给形式参数，执行完函数体后再将计算得到的返回值传递给调用者（如果有）。得到的返回值传递给调用者（如果有）。在未调用函数前，函数中的形式参数并不分配内存在未调用函数前，函数中的形式参数并不分配内存空间。只有在被调用执行时，才被分配临时存储空间。函数空间。只有在被调用执行时，才被分配临时存储空间。函数调用结束后，

22、形式参数的内存空间将被操作系统立刻收回。调用结束后，形式参数的内存空间将被操作系统立刻收回。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）函数的参数函数的参数实际参数可以是任何符合形式参数类型的常量、变量、实际参数可以是任何符合形式参数类型的常量、变量、表达式。函数参数传递的过程就是实际参数和形式参数相结表达式。函数参数传递的过程就是实际参数和形式参数相结合的过程，必须遵守三个一致。合的过程，必须遵守三个一致。（1）个数一致。个数一致。（2）顺序一致。顺序一致。（3）类型一致。类型一致。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例1、打印字

23、符三角形、打印字符三角形【问题描述问题描述】编写一个函数编写一个函数print(n,ch)，表示打印一行，表示打印一行n个英文字母个英文字母ch，并换，并换行。然后，在函数行。然后，在函数main()中输入中输入n和和ch，调用函数，调用函数print()打印一个字打印一个字符三角形。符三角形。【输入格式输入格式】一行一个整数一行一个整数n和一个英文字母和一个英文字母ch，之间用一个空格隔开，之间用一个空格隔开，1n20。【输出格式输出格式】n行，第行，第i行有行有i个字母个字母ch。【输入样例输入样例】3a【输出样例输出样例】aaaaaa高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥

24、赛课课通（C+）/p6-3-1#includeusingnamespacestd;voidprint(inti,charch)for(intj=1;j=i;j+)coutch;coutnch;for(inti=1;i=n;i+)print(i,ch);return0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）函数参数的传递方式函数参数的传递方式根据不同的应用需求，函数参数的传递方式，或者说函根据不同的应用需求，函数参数的传递方式，或者说函数参数的调用方式分为三种：数参数的调用方式分为三种：（1）传值（调用）传值（调用）：参见例参见例2；（2）传址（调用）传址（调用）

25、：参见例参见例3；（3）引用（调用）引用（调用）：参见例参见例4、例、例5；高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例2、阅读程序，写出程序的运行结果，体会函数的传值、阅读程序，写出程序的运行结果，体会函数的传值(调用调用)。/p6-3-2#includeusingnamespacestd;voidswap(intx,inty)inttemp;temp=x;x=y;y=temp;coutx“yendl;intmain()inta=10,b=50;swap(a,b);couta“bendl;return0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课

26、课通（C+）例例3、阅读程序，写出程序的运行结果，体会函数的传址、阅读程序，写出程序的运行结果，体会函数的传址(调用调用)。/p6-3-3#includeusingnamespacestd;voidswap(int*x,int*y)/形式参数的类型定义为指针形式参数的类型定义为指针inttemp;temp=*x;*x=*y;*y=temp;cout*x“*yendl;intmain()inta=10,b=50;swap(&a,&b);/实际参数必须是地址实际参数必须是地址couta“bendl;return0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例4、阅读程

27、序，写出程序的运行结果，体会变量及其引用的、阅读程序，写出程序的运行结果，体会变量及其引用的操作。操作。/p6-3-4/#includeusingnamespacestd;intmain()intk=32;int&k_adr=k;cout“k=”k“k_adr=”k_adrendl;k+;cout“k=”k“k_adr=”k_adrendl;k_adr=-5;cout“k=”k“k_adr=”k_adrendl;inti=100;k_adr+=i;cout“k=”k“k_adr=”k_adrendl;return0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例5、

28、阅读程序，写出程序的运行结果，体会函数的引用调用。、阅读程序，写出程序的运行结果，体会函数的引用调用。/p6-3-5#includeusingnamespacestd;voidswap(int&a,int&b)inttemp;temp=a;a=b;b=temp;couta“bendl;intmain()inta=10,b=50;swap(a,b);couta“bendl;return0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 4 课课 变量的作用域变量的作用域学习目标学习目

29、标1.理解变量的作用域。理解变量的作用域。2.熟练规范使用局部变量和全局变量。熟练规范使用局部变量和全局变量。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）变量的作用域变量的作用域变量按其在程序中的作用范围，分为全局变量和局部变变量按其在程序中的作用范围，分为全局变量和局部变量。量。全局变量是指定义在任何函数之外的变量，也就是不被全局变量是指定义在任何函数之外的变量，也就是不被任何任何“函数体函数体”所包含，可以被源文件中其他函数所共所包含，可以被源文件中其他函数所共用，用静态数据区存储，作用域（有效范围）是从定义变量用，用静态数据区存储，作用域（有效范围）是从定义变量

30、的位置开始到源文件（整个程序）结束。的位置开始到源文件（整个程序）结束。局部变量是指在一个函数（包括局部变量是指在一个函数（包括main函数）内部定义函数）内部定义的变量，它只在本函数内部有效，其他函数不能使用这些变的变量，它只在本函数内部有效，其他函数不能使用这些变量，用动态数据区存储，函数的参数也是局部变量。量，用动态数据区存储，函数的参数也是局部变量。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例1、以下程序中，哪些是全局变量，哪些是局部变量，并指、以下程序中，哪些是全局变量，哪些是局部变量，并指出它们的作用域。出它们的作用域。intx,y;floata,b;

31、floatfind(intc,d)floate,f;inti,j;intz;voiddoit()intmain()intg,h;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例2、找出程序中的错误。如果去掉错误，程序输出什么。、找出程序中的错误。如果去掉错误，程序输出什么。/p6-4-2#includeusingnamespacestd;intf()intb=0,c=1;b=b+1;c=c+1;return(b+c);intmain()for(inti=1;i4;i+)couti“.sum=”f()endl;cout“b=”b“c=”cendl;return0;高等教

32、育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）C+允许在更多地方定义变量，例如允许在更多地方定义变量，例如for的第一个子句，的第一个子句，if、for或者或者while语句块的语句块的内。这些变量只在当前语句块内有内。这些变量只在当前语句块内有效。一个语句块内只能定义一个同名变量。不同的函数内部效。一个语句块内只能定义一个同名变量。不同的函数内部可以使用相同名称的变量，它们代表不同的对象，相互独立，可以使用相同名称的变量，它们代表不同的对象，相互独立，互不干扰。访问同名变量时、只能访问到当前有效、且最近互不干扰。访问同名变量时、只能访问到当前有效、且最近定义的该变量。特别地

33、，在变量前加定义的该变量。特别地，在变量前加“:”可以指定访问全可以指定访问全局变量。在写复杂代码时，可以利用这些特性，调整临时变局变量。在写复杂代码时，可以利用这些特性，调整临时变量的定义位置和作用域，以规避变量重名带来的编译错误。量的定义位置和作用域，以规避变量重名带来的编译错误。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例3、找出程序中的错误。如果去掉错误，程序输出什么。、找出程序中的错误。如果去掉错误，程序输出什么。/p6-4-3#includeusingnamespacestd;intx=233;intmain()intx;cinx;for(inti=1

34、;ixy;coutx+yendl;coutxendl;cout:xendl;couti“yendl;return0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例4、阅读程序，写出程序的运行结果。、阅读程序，写出程序的运行结果。/p6-4-4#includeusingnamespacestd;intx=10,y=15;voidchange(inta,intb,intx)inttemp;x+;y+;temp=a;a=b;b=temp;intmain()inta=3,b=5;coutx“”y“”a“”bendl;change(a,b,x);coutx“”y“”a“”be

35、ndl;return0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 5 课课 函数的递归调用函数的递归调用学习目标学习目标1.理解函数的递归调用。理解函数的递归调用。2.应用递归法解决一些实际问题。应用递归法解决一些实际问题。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）函数的递归调用函数的递归调用函数调用自己，这种调用称为函数调用自己，这种调用称为“递归递归”调用，这样的函调用，这样的函数称为数称为“递归函数递归函数”。高等教育出版社高等教育出版社信息

36、学奥赛课课通（信息学奥赛课课通（C+）例例1、阅读程序，写出程序的运行结果。利用单步跟、阅读程序，写出程序的运行结果。利用单步跟踪，体会函数递归调用执行的过程。踪，体会函数递归调用执行的过程。/p6-5-1#includeusingnamespacestd;voidp(intn)if(n0)p(n-1);for(inti=0;in;i+)coutn;coutendl;intmain()p(5);return0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）递归的调用递归的调用一个问题要想用递归的方法（函数）来解决，必须要符一个问题要想用递归的方法（函数）来解决，必须要符

37、合两个条件。合两个条件。（1）可以把这个问题转化成一个新问题，而新问题的可以把这个问题转化成一个新问题，而新问题的解法和原问题的解法完全相同，只是问题规模变小了；解法和原问题的解法完全相同，只是问题规模变小了；（2）必须要有一个明确的递归结束条件（递归边界）。必须要有一个明确的递归结束条件（递归边界）。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例2、求阶乘、求阶乘【问题描述问题描述】编程求编程求n阶乘的值，阶乘的值，n!=123(n-1)n。【输入格式输入格式】一行一个正整数一行一个正整数n，1n20。【输出格式输出格式】一行一个正整数，表示一行一个正整数，表示n

38、!的值。的值。【输入样例输入样例】5【输出样例输出样例】120高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【问题分析问题分析】求求n!的值带有明显的递归思想。要想求出的值带有明显的递归思想。要想求出n!，就要先，就要先求（求（n-1）!，因为（，因为（n-1）!乘以乘以n就是就是n!；而要求（；而要求（n-1）!又要先求出（又要先求出（n-2）!，因为（，因为（n-2）！乘以（）！乘以（n-1）就是（）就是（n-1）!；要求要求2!又要先求出又要先求出1!，因为，因为2乘以乘以1！就是！就是2!；而；而1！是已知的，就是！是已知的，就是1。所以，阶乘问题的递归公式为：

39、。所以，阶乘问题的递归公式为：高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p6-5-2#includeusingnamespacestd;longlongjc(intn)if(n=1)return1;/递归边界递归边界returnjc(n-1)*n;/递归公式递归公式intmain()intn;cinn;coutjc(n)endl;return0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）求求5！的递归调用过程如下！的递归调用过程如下:高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例3、求最大公约数、求最大公约数

40、【问题描述问题描述】输入两个正整数输入两个正整数m和和n，求它们的最大公约数。，求它们的最大公约数。【输入格式输入格式】一行两个正整数一行两个正整数m和和n，用一个空格隔开，用一个空格隔开，2m，n10000。【输出格式输出格式】一行一个正整数，表示一行一个正整数，表示m和和n的最大公约数。的最大公约数。【输入样例输入样例】2436【输出样例输出样例】12高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【问题分析问题分析】用欧几里得用欧几里得“辗转相除法辗转相除法”演示求最大公约数的过程，演示求最大公约数的过程，发现（发现（m，n）的最大公约数与（）的最大公约数与（n，m

41、%n）的最大公约数）的最大公约数是一样的，但是数据规模变小了。所以，最大公约数问题的是一样的，但是数据规模变小了。所以，最大公约数问题的递归公式为：递归公式为：高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p6-5-3#includeusingnamespacestd;intgcd(intm,intn)if(n=0)returnm;elsereturngcd(n,m%n);intmain()intm,n;cinmn;coutgcd(m,n)endl;return0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例4、分解质因子、分解质因子【问

42、题描述问题描述】输入一个正整数输入一个正整数n，用递归方法从小到大输出它的所有，用递归方法从小到大输出它的所有质因子（因子是质数）。质因子（因子是质数）。【输入格式输入格式】一行一个正整数一行一个正整数n，2n10000。【输出格式输出格式】一行若干个正整数，两数之间用一个空格隔开，从小到一行若干个正整数，两数之间用一个空格隔开，从小到大输出。大输出。【输入样例输入样例】18【输出样例输出样例】233高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【问题分析问题分析】显然，如果显然，如果n等于等于1，就没法再分解了。如果，就没法再分解了。如果n大于大于1，从整数从整数p（

43、p从从2开始）开始试除，如果能被开始）开始试除，如果能被p整除，就得到整除，就得到一个质因子一个质因子p。问题就转化成对于整数。问题就转化成对于整数n/p，从，从p开始继续分开始继续分解质因子。解质因子。如果不能被如果不能被p整除，问题就转化为对于整数整除，问题就转化为对于整数n，从，从p+1开开始分解质因子。所以，递归公式为：始分解质因子。所以，递归公式为：高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p6-5-4#includeusingnamespacestd;boolfirst=true;voidzyz(intn,intp)if(n1)if(n%p=0)if(

44、first)coutp;first=false;elsecout“n;zyz(n,2);coutendl;return0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例5、抽奖、抽奖问题描述问题描述参见教材参见教材213页。页。【问题分析问题分析】我们已经学习过用循环语句实现我们已经学习过用循环语句实现“二分查找二分查找”，很明显，很明显，也可以采用也可以采用“递归递归”思想实现二分查找。思想实现二分查找。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p6-5-5#includeusingnamespacestd;intwin,g101;i

45、ntbinsearch(intleft,intright)if(left=right)intmid=(left+right)/2;if(gmid=win)returnmid;/找到找到if(wingmid)returnbinsearch(mid+1,right);/在右半部分在右半部分elsereturn0;/没找到没找到intmain()intn,i,f,left,right,mid;scanf(%d,&n);for(i=1;iwin;f=binsearch(1,n);coutfendl;return0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩固高

46、等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 6 课课 函数应用举例函数应用举例学习目标学习目标1.熟练应用函数和结构化编程思想解决一些实际问题。熟练应用函数和结构化编程思想解决一些实际问题。2.学会函数的单步跟踪，并进一步理解递归函数的执行学会函数的单步跟踪，并进一步理解递归函数的执行过程。过程。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例1、孪生素数、孪生素数【问题描述问题描述】在素数的大家庭中，大小之差为在素数的大家庭中，大小之差为2的两个素数的两个素数称之为一对称之为一对“孪生素数孪生素数”，如，如3和和5、17和和19等。请你

47、编程统计出不大于自然数等。请你编程统计出不大于自然数n的素数的素数中，孪生素数的对数。中，孪生素数的对数。【输入格式输入格式】一行一个正整数一行一个正整数n，1n231。【输出格式输出格式】若干行，每行两个整数，之间用一个空格隔若干行，每行两个整数，之间用一个空格隔开，从小到大输出每一对孪生素数。开，从小到大输出每一对孪生素数。【输入样例输入样例】100【输出样例输出样例】3557111317192931414359617173高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【问题分析问题分析】首先，大于首先，大于2的两个连续自然数不可能都是素数，大于的两个连续自然数不可

48、能都是素数，大于2的偶数也一定不是素数。所以，从的偶数也一定不是素数。所以，从3开始穷举一个自然数开始穷举一个自然数s，检查检查s和和s+2是不是都为素数，是则输出这对孪生素数。然是不是都为素数，是则输出这对孪生素数。然后，后，s=s+2，继续寻找下一对孪生素数。，继续寻找下一对孪生素数。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p6-6-1#includeusingnamespacestd;boolprime(intn)for(inti=2;i*in;while(i=n-2)if(prime(i)&prime(i+2)couti“i+2endl;i+=2;ret

49、urn0;上机实践，学会单步跟上机实践，学会单步跟踪函数。踪函数。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例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页。页。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例3、汉诺塔问题、汉诺塔问题问题描述问题描述参见教材参见教材219-220页。页。【问题分析问题分析】具体分析及程序参考教材具体分析及程序参考教材220-222页。页。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩固