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

第 6 单元 函数,作者：林厚从,信息学奥赛课课通（C+）,第 1 课 模块化编程思想,学习目标1.体会模块化编程思想。2.了解函数的功能和调用。,一个 C+程序无论大小，都由一个或者多个“函数”组成，而且其中必须有且只有一个函数main（），称之为“主函数”，由函数 main（）调用其他函数来完成程序的特定功能。当然，其他函数之间也可以按照规则互相调用。C+中的函数由一段相对独立的代码组成，这段代码能实现某一项具体、独立、完整的功能。函数在程序设计中的作用主要有两个，一是“代码重用”；二是“问题分解”。,代码重用是保证同一个函数可以被一个或多个函数调用任意多次，从而减少重复代码的编写。问题分解可以保证一个大的程序（或者说软件），按照模块化编程思想，由大化小，分解成若干个结构清晰、功能独立、调试方便的函数，甚至给若干人合作完成，从而提高开发效率。,C+提供了很多常用的系统函数，如输入单个字符的函数getchar()等。但是有些函数，必须要加上相关头文件才能使用，例如整数取绝对值的函数abs()、求算术平方根的函数sqrt()等，必须要包含“cmath”。,例1、曼哈顿距离,【问题描述】平面直角坐标系中位于坐标（x1，y1）的 i 点与位于坐标（x2，y2）的 j 点的曼哈顿距离为 d（i，j）=|x1-x2|+|y1-y2|。请编程输入两个点的坐标，输出它们之间的曼哈顿距离。【输入格式】一行四个整数（100 以内），分别表示两个点的坐标（x1，y1）和（x2，y2）。【输出格式】一行一个整数，表示两个点之间的曼哈顿距离。【输入样例】10 5 6 20【输出样例】19,/p6-1-1#include#includeusing 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;,例2、回文数个数,【问题描述】输入一个正整数 n，求 1n 之间“回文数”的个数。回文数是指一个数倒过来和原数一样，如 12121、11、1221、1 是回文数，而 1231 不是回文数。【输入格式】一行一个正整数 n，1n10000。【输出格式】一行一个正整数，表示 1n 之间回文数的个数。【输入样例】12【输出样例】10,【问题分析】定义一个计数器变量并初始化为 0，然后穷举 1n 中的每一个整数 i，判断是否是回文数，是则计数器加一。如何判断 i 是回文数呢？C+系统函数里没有，只能自己编写一个。,/p6-1-2#includeusing namespace std;/在此自定义一个函数 check()，如果 i 是回文数返回 true，否则返回 falseint main()int n,i,ans=0;scanf(“%d”,实践巩固,第 2 课 函数的定义和调用,学习目标1.学会函数的定义和调用。2.应用函数解决一些实际问题。,C+要求函数必须先定义、后使用。定义函数，就是要说明函数的返回值类型、函数名、函数参数，以及完成特定功能的语句组合（函数体）。,函数的定义和调用,1.函数的定义,定义函数的格式如下：返回值类型 函数名（参数列表）函数体其中，第一行称为函数头部。函数名是标识这个函数的合法标识符。返回值类型是指一个函数结束后返回给调用者的一个“返回值”的数据类型。有些函数的功能是执行一系列操作，而不返回任何值，这种情况下，返回值类型是关键字void。参数列表是当函数被调用时，调用者向函数传递的各种“参数”，此处的参数称为形式参数，参数列表包括参数的数据类型和参数名，参数是可选的，没有参数就是“无参”函数，但是括号不能省略。,1.函数的定义,大括号之间的部分称为“函数体”，主要包括变量说明语句、表达式语句等。如果有返回值，则函数体内至少有一条语句“return 表达式”。在执行函数体的过程中，一旦遇到return语句，执行完就立刻退出函数，不再执行后续的语句。无返回值函数不需要return语句。,2.函数的调用,在程序中以任何方式对函数的使用，都称为函数的调用。函数调用是通过“函数名”进行的，一般格式为：函数名（参数列表）此处的参数列表称为“实际参数”，是传递给调用函数的，必须严格对应函数定义时函数头部的形式参数列表，包括参数个数、参数顺序、数据类型。调用无参函数时参数列表可以没有，但括号不能省略。如果参数列表包含多个参数，则各参数间用逗号隔开。,函数调用方式,以函数在程序中出现的位置和形式来看，函数调用方式分为三种。（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);,例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 endl;return 0;,例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);/函数调用作为一条独立语句 return 0;,例3、阅读程序，写出程序的运行结果，体会函数的“提前声明”。,/p6-2-3#includeusing namespace std;int big(int x,int y);/函数的提前声明int main()int x,y,z;cin x y z;cout y)return x;else return y;,例4、统计闰年,【问题描述】输入两个年份 x 和 y，统计并输出公元 x 年到公元 y 年之间的所有闰年数（包括 x 年和 y 年），1xy3000。【输入格式】一行两个正整数表示 x 和 y，之间用一个空格隔开。【输出格式】一行一个正整数，表示公元 x 年到公元 y 年之间的所有闰年数。【输入样例】2000 2004【输出样例】2,/p6-2-4#include using namespace std;bool rn(int n)if(n%4=0),例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,/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;,实践巩固,第 3 课 函数的参数,学习目标1.理解形式参数与实际参数。2.理解参数传递的三种方式。,函数的参数,参数是函数与函数之间实现通信的数据“接口”。函数调用的过程就是调用者带着实际参数（如果有）执行函数，将实际参数“传递”给形式参数，执行完函数体后再将计算得到的返回值传递给调用者（如果有）。在未调用函数前，函数中的形式参数并不分配内存空间。只有在被调用执行时，才被分配临时存储空间。函数调用结束后，形式参数的内存空间将被操作系统立刻收回。,函数的参数,实际参数可以是任何符合形式参数类型的常量、变量、表达式。函数参数传递的过程就是实际参数和形式参数相结合的过程，必须遵守三个一致。（1）个数一致。（2）顺序一致。（3）类型一致。,例1、打印字符三角形,【问题描述】编写一个函数 print(n,ch)，表示打印一行 n 个英文字母 ch，并换行。然后，在函数 main()中输入 n 和 ch，调用函数 print()打印一个字符三角形。【输入格式】一行一个整数 n 和一个英文字母 ch，之间用一个空格隔开，1n20。【输出格式】n 行，第 i 行有 i 个字母 ch。【输入样例】3 a【输出样例】aaaaaa,/p6-3-1#includeusing namespace std;void print(int i,char ch)for(int j=1;j n ch;for(int i=1;i=n;i+)print(i,ch);return 0;,函数参数的传递方式,根据不同的应用需求，函数参数的传递方式，或者说函数参数的调用方式分为三种：（1）传值（调用）：参见例2；（2）传址（调用）：参见例3；（3）引用（调用）：参见例4、例5；,例2、阅读程序，写出程序的运行结果，体会函数的传值(调用)。,/p6-3-2#includeusing 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;,例3、阅读程序，写出程序的运行结果，体会函数的传址(调用)。,/p6-3-3#includeusing 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(,例4、阅读程序，写出程序的运行结果，体会变量及其引用的操作。,/p6-3-4/#include using namespace std;int main()int k=32;int,例5、阅读程序，写出程序的运行结果，体会函数的引用调用。,/p6-3-5#includeusing namespace std;void swap(int,实践巩固,第 4 课 变量的作用域,学习目标1.理解变量的作用域。2.熟练规范使用局部变量和全局变量。,变量的作用域,变量按其在程序中的作用范围，分为全局变量和局部变量。全局变量是指定义在任何函数之外的变量，也就是不被任何“函数体”所包含，可以被源文件中其他函数所共用，用静态数据区存储，作用域（有效范围）是从定义变量的位置开始到源文件（整个程序）结束。局部变量是指在一个函数（包括 main 函数）内部定义的变量，它只在本函数内部有效，其他函数不能使用这些变量，用动态数据区存储，函数的参数也是局部变量。,例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;,例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(int i=1;i 4;i+)cout i“.sum=”f()endl;cout“b=”b“c=”c endl;return 0;,C+允许在更多地方定义变量，例如for的第一个子句，if、for或者while语句块的 内。这些变量只在当前语句块内有效。一个语句块内只能定义一个同名变量。不同的函数内部可以使用相同名称的变量，它们代表不同的对象，相互独立，互不干扰。访问同名变量时、只能访问到当前有效、且最近定义的该变量。特别地，在变量前加“:”可以指定访问全局变量。在写复杂代码时，可以利用这些特性，调整临时变量的定义位置和作用域，以规避变量重名带来的编译错误。,例3、找出程序中的错误。如果去掉错误，程序输出什么。,/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;,例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 endl;return 0;,实践巩固,第 5 课 函数的递归调用,学习目标1.理解函数的递归调用。2.应用递归法解决一些实际问题。,函数的递归调用,函数调用自己，这种调用称为“递归”调用，这样的函数称为“递归函数”。,例1、阅读程序，写出程序的运行结果。利用单步跟踪，体会函数递归调用执行的过程。,/p6-5-1#includeusing 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;,递归的调用,一个问题要想用递归的方法（函数）来解决，必须要符合两个条件。（1）可以把这个问题转化成一个新问题，而新问题的解法和原问题的解法完全相同，只是问题规模变小了；（2）必须要有一个明确的递归结束条件（递归边界）。,例2、求阶乘,【问题描述】编程求 n 阶乘的值，n!=123(n-1)n。【输入格式】一行一个正整数 n，1n20。【输出格式】一行一个正整数，表示 n!的值。【输入样例】5【输出样例】120,【问题分析】求 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。所以，阶乘问题的递归公式为：,/p6-5-2#includeusing 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;,求 5！的递归调用过程如下:,例3、求最大公约数,【问题描述】输入两个正整数 m 和 n，求它们的最大公约数。【输入格式】一行两个正整数 m 和 n，用一个空格隔开，2m，n10000。【输出格式】一行一个正整数，表示 m 和 n 的最大公约数。【输入样例】24 36【输出样例】12,【问题分析】用欧几里得“辗转相除法”演示求最大公约数的过程，发现（m，n）的最大公约数与（n，m%n）的最大公约数是一样的，但是数据规模变小了。所以，最大公约数问题的递归公式为：,/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;,例4、分解质因子,【问题描述】输入一个正整数 n，用递归方法从小到大输出它的所有质因子（因子是质数）。【输入格式】一行一个正整数 n，2n10000。【输出格式】一行若干个正整数，两数之间用一个空格隔开，从小到大输出。【输入样例】18【输出样例】2 3 3,【问题分析】显然，如果 n 等于 1，就没法再分解了。如果 n 大于 1，从整数 p（p 从 2 开始）开始试除，如果能被 p 整除，就得到一个质因子 p。问题就转化成对于整数 n/p，从 p 开始继续分解质因子。如果不能被 p 整除，问题就转化为对于整数 n，从 p+1 开始分解质因子。所以，递归公式为：,/p6-5-4#includeusing namespace std;bool first=true;void zyz(int n,int p)if(n 1)if(n%p=0)if(first)cout p;first=false;else cout“p;zyz(n/p,p);else zyz(n,p+1);,int main()int n;cin n;zyz(n,2);cout endl;return 0;,例5、抽奖,问题描述参见教材213页。,【问题分析】我们已经学习过用循环语句实现“二分查找”，很明显，也可以采用“递归”思想实现二分查找。,/p6-5-5#includeusing namespace std;int win,g101;int binsearch(int left,int right)if(left gmid)return binsearch(mid+1,right);/在右半部分else return 0;/没找到int main()int n,i,f,left,right,mid;scanf(%d,实践巩固,第 6 课 函数应用举例,学习目标1.熟练应用函数和结构化编程思想解决一些实际问题。2.学会函数的单步跟踪，并进一步理解递归函数的执行过程。,例1、孪生素数,【问题描述】在素数的大家庭中，大小之差为2的两个素数称之为一对“孪生素数”，如3和5、17 和 19 等。请你编程统计出不大于自然数 n 的素数中，孪生素数的对数。【输入格式】一行一个正整数 n，1n2 31。【输出格式】若干行，每行两个整数，之间用一个空格隔开，从小到大输出每一对孪生素数。【输入样例】100,【输出样例】3 55 711 1317 1929 3141 4359 6171 73,【问题分析】首先，大于 2 的两个连续自然数不可能都是素数，大于 2 的偶数也一定不是素数。所以，从3 开始穷举一个自然数 s，检查 s 和 s+2 是不是都为素数，是则输出这对孪生素数。然后，s=s+2，继续寻找下一对孪生素数。,/p6-6-1#includeusing namespace std;bool prime(int n)for(int i=2;i*i n;while(i=n-2)if(prime(i),上机实践，学会单步跟踪函数。,例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页。,例3、汉诺塔问题,问题描述参见教材219-220页。,【问题分析】具体分析及程序参考教材220-222页。,实践巩固,