第6单元函数PPT课件

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

2、数main（），称之（），称之为为“主函数主函数”，由函数，由函数 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）。）。【输出格式输出格式】一行一个整数，表示两个点之间的曼哈顿距离。一行一个整数，表示两个点之间的曼哈顿距离。【输入样例输入样例】10 5 6 20【输出样例输出样例】19高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p6-1-1#include#includeusing namespace std;int main() long lon

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

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

8、社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p6 -1-2#includeusing namespace std;/ 在此自定义一个函数在此自定义一个函数 check()，如果，如果 i 是回文数返回是回文数返回 true，否则返回否则返回 falseint main() int n,i,ans = 0; scanf( “ %d ” ,&n); for(i = 1; i = n; i+) if(check(i) ans+; printf( “ %dn ” ,ans); return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩

9、固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 2 课课 函数的定义和调用函数的定义和调用学习目标学习目标1. 学会函数的定义和调用。学会函数的定义和调用。2. 应用函数解决一些实际问题。应用函数解决一些实际问题。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）C+ 要求函数必须先定义、后使用。定义函数，就是要要求函数必须先定义、后使用。定义函数，就是要说明函数的返回值类型、函数名、函数参数，以及完成特说明函数的返回值类型、函数名、函数参数，以及完成特定功能的语句组合（函数体）。定功能的语句组合（函数体）。函数的定义和调用函数的定义和调用高等

10、教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）1. 函数的定义函数的定义定义函数的格式如下：定义函数的格式如下：返回值类型返回值类型 函数名（参数列表）函数名（参数列表） 函数体函数体其中，第一行称为函数头部。函数名是标识这个函数的其中，第一行称为函数头部。函数名是标识这个函数的合法标识符。返回值类型是指一个函数结束后返回给调用合法标识符。返回值类型是指一个函数结束后返回给调用者的一个者的一个“返回值返回值”的数据类型。的数据类型。有些函数的功能是执行有些函数的功能是执行一系列操作，而不返回任何值，这种情况下，返回值类型一系列操作，而不返回任何值，这种情况下，返回值类型是关

11、键字是关键字void。参数列表是当函数被调用时，调用者向函数。参数列表是当函数被调用时，调用者向函数传递的各种传递的各种“参数参数”，此处的参数称为形式参数，参数列，此处的参数称为形式参数，参数列表包括参数的数据类型和参数名，参数是可选的，没有参表包括参数的数据类型和参数名，参数是可选的，没有参数就是数就是“无参无参”函数，但是括号不能省略。函数，但是括号不能省略。 高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）1. 函数的定义函数的定义 大括号之间的部分称为大括号之间的部分称为“函数体函数体”，主要包括变量说，主要包括变量说明语句、表达式语句等。如果有返回值，则函数体

12、内至少明语句、表达式语句等。如果有返回值，则函数体内至少有一条语句有一条语句“return 表达式表达式”。在执行函数体的过程中，一。在执行函数体的过程中，一旦遇到旦遇到return语句，执行完就立刻退出函数，不再执行后续语句，执行完就立刻退出函数，不再执行后续的语句。无返回值函数不需要的语句。无返回值函数不需要return语句。语句。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）2. 函数的调用函数的调用在程序中以任何方式对函数的使用，都称为函数的调用。在程序中以任何方式对函数的使用，都称为函数的调用。函数调用是通过函数调用是通过“函数名函数名”进行的，进行的，一般格

13、式为：一般格式为：函数名（参数列表）函数名（参数列表）此处的参数列表称为此处的参数列表称为“实际参数实际参数”，是传递给调用函数，是传递给调用函数的，必须严格对应函数定义时函数头部的形式参数列表，的，必须严格对应函数定义时函数头部的形式参数列表，包括参数个数、参数顺序、数据类型。调用无参函数时参包括参数个数、参数顺序、数据类型。调用无参函数时参数列表可以没有，但括号不能省略。如果参数列表包含多数列表可以没有，但括号不能省略。如果参数列表包含多个参数，则各参数间用逗号隔开。个参数，则各参数间用逗号隔开。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）函数调用方式函数调用方式

14、以函数在程序中出现的位置和形式来看，函数调用方式以函数在程序中出现的位置和形式来看，函数调用方式分为三种。分为三种。（1）函数调用作为一条独立语句，完成一件事情（一）函数调用作为一条独立语句，完成一件事情（一系列操作），没有任何返回值。例如：系列操作），没有任何返回值。例如：print (n); doit(dep,total); input( );（2）函数调用的结果作为表达式的一部分。例如：）函数调用的结果作为表达式的一部分。例如：int t = compute(i,j) + i*j;（3）以实参形式出现在其他函数调用中。例如：）以实参形式出现在其他函数调用中。例如：number = min

15、(sum(-5,100),n); num = max(max(a,b), c);高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例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);/ 函数调用出现在

16、表达式中函数调用出现在表达式中 cout x endl; return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例2、阅读程序，写出程序的运行结果，体会、阅读程序，写出程序的运行结果，体会“无返无返回值函数回值函数”的调用。的调用。/p6-2-2#include using namespace std;void maxnum(int x,int y) int w = x y ? x : y; cout w endl;int main() int a = 5,b = 22; maxnum(a,b);/ 函数调用作为一条独立语句函数调用作为一条独立语句 retu

17、rn 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例3、阅读程序，写出程序的运行结果，体会函数的、阅读程序，写出程序的运行结果，体会函数的“提前声明提前声明”。/p6-2-3#includeusing namespace std;int big(int x,int y);/ 函数的提前声明函数的提前声明int main() int x,y,z; cin x y z; cout big(big(x,y),z) y) return x; else return y;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例4、统计闰年、统计闰年【问题

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

19、4#include using namespace std;bool rn(int n) if(n % 4 = 0) & (n % 100 != 0) | (n % 400 = 0) return true; 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;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例5、数的分离、数的分离【问题描述问题描述】定义一函数定义一函数 digit (n

20、,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【输出样例输出样例】

21、8高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/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;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 3 课课 函数的参数函数的参数学习目标学习目标1. 理解形式参数与实际参数。理解形式参数与实际参数。2. 理解参

22、数传递的三种方式。理解参数传递的三种方式。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）函数的参数函数的参数参数是函数与函数之间实现通信的数据参数是函数与函数之间实现通信的数据“接口接口”。函数。函数调用的过程就是调用者带着实际参数（如果有）执行函数，调用的过程就是调用者带着实际参数（如果有）执行函数，将实际参数将实际参数“传递传递”给形式参数，执行完函数体后再将计给形式参数，执行完函数体后再将计算得到的返回值传递给调用者（如果有）。算得到的返回值传递给调用者（如果有）。 在未调用函数前，函数中的形式参数并不分配内存在未调用函数前，函数中的形式参数并不分配内存空间。只有

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

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

25、行，第 i 行有行有 i 个字母个字母 ch。【输入样例输入样例】3 a【输出样例输出样例】aaaaaa高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p6-3-1#includeusing 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;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）函数参数的传递方式函数参数的传递方式根据不同的

26、应用需求，函数参数的传递方式，或者说函根据不同的应用需求，函数参数的传递方式，或者说函数参数的调用方式分为三种：数参数的调用方式分为三种：（1） 传值（调用）传值（调用）：参见例参见例2；（2） 传址（调用）传址（调用）：参见例参见例3；（3） 引用（调用）引用（调用）：参见例参见例4、例、例5；高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例2、阅读程序，写出程序的运行结果，体会函数的传值、阅读程序，写出程序的运行结果，体会函数的传值(调用调用)。/p6-3-2#includeusing namespace std;void swap(int x,int y) in

27、t 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;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例3、阅读程序，写出程序的运行结果，体会函数的传址、阅读程序，写出程序的运行结果，体会函数的传址(调调用用)。/p6-3-3#includeusing namespace std;void swap(int *x,int *y)/ 形式参数的类型定义为指针形式参数的类型定义为指针

28、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 ;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例4、阅读程序，写出程序的运行结果，体会变量及其引用、阅读程序，写出程序的运行结果，体会变量及其引用的操作。的操作。/p6-3-4/#include using namespace std;int main

29、() int k = 32; int& k_adr = k; 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;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例5、阅读程序，写出程序的运行结果，体会函数的引用调用。、阅读

30、程序，写出程序的运行结果，体会函数的引用调用。/p6-3-5#includeusing 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;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 4 课课

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

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

33、出它们的作用域。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; 高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例2、找出程序中的错误。如果去掉错误，程序输出什么。、找出程序中的错误。如果去掉错误，程序输出什么。/p6-4-2#includeusing namespace std;int f() int b = 0,c = 1; b = b + 1; c = c + 1; return (b+c);int main() for(

34、int i = 1; i 4; i+) cout i “ .sum= ” f() endl; cout “ b= ” b “ c= ” c endl; return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+） C+允许在更多地方定义变量，例如允许在更多地方定义变量，例如for的第一个子句，的第一个子句，if、for或者或者while语句块的语句块的 内。这些变量只在当前语句块内内。这些变量只在当前语句块内有效。一个语句块内只能定义一个同名变量。不同的函数内有效。一个语句块内只能定义一个同名变量。不同的函数内部可以使用相同名称的变量，它们代表不同的对象，相互独部可

35、以使用相同名称的变量，它们代表不同的对象，相互独立，互不干扰。访问同名变量时、只能访问到当前有效、且立，互不干扰。访问同名变量时、只能访问到当前有效、且最近定义的该变量。特别地，在变量前加最近定义的该变量。特别地，在变量前加“:”可以指定访问可以指定访问全局变量。在写复杂代码时，可以利用这些特性，调整临时全局变量。在写复杂代码时，可以利用这些特性，调整临时变量的定义位置和作用域，以规避变量重名带来的编译错误变量的定义位置和作用域，以规避变量重名带来的编译错误。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例3、找出程序中的错误。如果去掉错误，程序输出什么。、找出程序中

36、的错误。如果去掉错误，程序输出什么。/p6-4-3#includeusing namespace std;int x = 233;int main() int x; cin x; for(int i = 1; i x y; cout x + y endl; cout x endl; cout :x endl; cout i “ “ y endl; return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例4、阅读程序，写出程序的运行结果。、阅读程序，写出程序的运行结果。/p6-4-4#include using namespace std;int x = 10

37、, 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 endl; return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 5 课课 函数的递归调用函数的递归调用学习

38、目标学习目标1. 理解函数的递归调用。理解函数的递归调用。2. 应用递归法解决一些实际问题。应用递归法解决一些实际问题。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）函数的递归调用函数的递归调用函数调用自己，这种调用称为函数调用自己，这种调用称为“递归递归”调用，这样的函调用，这样的函数称为数称为“递归函数递归函数”。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例1、阅读程序，写出程序的运行结果。利用单步跟、阅读程序，写出程序的运行结果。利用单步跟踪，体会函数递归调用执行的过程。踪，体会函数递归调用执行的过程。/p6-5-1#includeu

39、sing namespace std;void p(int n) if(n 0) p(n-1); for(int i = 0; i n; i+) cout n; cout endl; int main() p(5); return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）递归的调用递归的调用一个问题要想用递归的方法（函数）来解决，必须要符一个问题要想用递归的方法（函数）来解决，必须要符合两个条件。合两个条件。（1） 可以把这个问题转化成一个新问题，而新问题的可以把这个问题转化成一个新问题，而新问题的解法和原问题的解法完全相同，只是问题规模变小了；解法和原问题的

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

41、! 的值带有明显的递归思想。要想求出的值带有明显的递归思想。要想求出 n!，就要先求，就要先求（n-1）!，因为（，因为（n-1）! 乘以乘以 n 就是就是 n!；而要求（；而要求（n-1）! 又又要先求出（要先求出（n-2）!，因为（，因为（n-2）！乘以（）！乘以（n-1）就是（）就是（n-1）!；要求要求 2! 又要先求出又要先求出 1!，因为，因为 2 乘以乘以 1 ！就是！就是 2!；而而 1 ！是已知的，就是！是已知的，就是 1。所以，阶乘问题的递归公式为：。所以，阶乘问题的递归公式为：高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p6-5-2#inclu

42、deusing namespace std;long long jc(int n) if(n = 1) return 1; / 递归边界递归边界 return jc(n-1) * n; / 递归公式递归公式int main() int n; cin n; cout jc(n) endl; return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）求求 5 ！的递归调用过程如下！的递归调用过程如下:高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例3、求最大公约数、求最大公约数【问题描述问题描述】输入两个正整数输入两个正整数 m 和和 n，求

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

44、的，但是数据规模变小了。所以，最大公约数问题的一样的，但是数据规模变小了。所以，最大公约数问题的递归公式为：递归公式为：高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p6-5-3#includeusing namespace std;int gcd(int m,int n) if(n = 0) return m; else return gcd(n,m % n);int main() int m,n; cin m n; cout gcd(m,n) endl; return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例4、分解质因子、分

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

46、 大于大于 1，从整，从整数数 p（p 从从 2 开始）开始试除，如果能被开始）开始试除，如果能被 p 整除，就得到一个整除，就得到一个质因子质因子 p。问题就转化成对于整数。问题就转化成对于整数 n/p，从，从 p 开始继续分解质开始继续分解质因子。因子。如果不能被如果不能被 p 整除，问题就转化为对于整数整除，问题就转化为对于整数 n，从，从 p+1 开始分开始分解质因子。所以，递归公式为：解质因子。所以，递归公式为：高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p6-5-4#includeusing namespace std;bool first = true

47、;void zyz(int n,int p) if(n 1) if(n % p = 0) if(first) cout p; first = false; else cout “ “ n; zyz(n,2); cout endl; return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例5、抽奖、抽奖问题描述问题描述参见教材参见教材213页。页。【问题分析问题分析】我们已经学习过用循环语句实现我们已经学习过用循环语句实现“二分查找二分查找”，很明显，很明显，也可以采用也可以采用“递归递归”思想实现二分查找。思想实现二分查找。高等教育出版社高等教育出版社信息学

48、奥赛课课通（信息学奥赛课课通（C+）/p6-5-5#includeusing 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,&n);for(i = 1; i win; f = binsearch(1,n); c