C语言程序设计-四川大学.ppt

六、函数 教学目标： 函数的概念、定义、调用和返回 带自定义函数的程序设计 递推算法 递归思想及算法实现 函数的参数传递方式 六、函数 6.1 函数概论 任务6.1 从键盘输入一个正整数a,编一个程序判断a是否为素数。 可以设计一个函数int checkPrime(int n)， 让该函数负责检查n是否为素数，如果是，返回1，否则返回0. 参考程序：程序6_1.cpp 6.1 函数概论 6.1.1 函数的说明 在全局上，自定义函数应该在主函数之前有一个说明，目的是告诉系统在程序中要用到一个自定义函数，被主函数直接或间接调用。 说明的时候就要写清楚这个函数的数据类型是什么，自变量有几个，都是什么数据类型。如任务6.1的函数 int ckeckPrim(int n); 说明自变量只有一个，是整型，函数的数值也是整型。函数的取值称为函数的返回值。这里用1表示真，0表示假。 6.1.3 函数的返回值 函数一般是由主函数调用（当然也可由别的函数或这个函数自已来调用），调用函数的目的是让它计算某一函数的值，这个值通过return语句返回给调用它的函数，格式为 return(表达式); 或 return 表达式; 如果不需返回数值，则用 return; 有调用就要有返回，函数中一定要有return出现，注意养成这个好习惯。 6.1.4 函数的调用 函数一经定义，以其名为标记的一片内存地址就被该函数所占有。在这片地址中存储着相关的一系列指令。因此在程序中出现该函数名，就意味着程序转到这一片内存地址，调用这个函数，执行了相关的一系列程序指令。 6.1.4 函数的调用 函数的调用方式 （1）对于有返回值的函数，可视其为表达式，可放在任何可放的地方。比如任务6.1中的checkPrime函数就放在if语句的表达式中。 （2）对于没有返回值的函数，一般在程序中作为独立一条语句出现，不以表达式形式出现。 如return(a); 任务6.1的调用过程 6.2 递推 递推是计算机数值计算中的一个重要算法。思路是通过数学推导，将复杂的运算化解为若干重复的简单运算，以充分发挥计算机长于重复计算的特点。 任务6.3 A,B,C,D,E合伙夜间捕鱼，凌晨时都疲惫不堪，各自在河边的树丛中找地方睡着了。日上三竿，A第一个醒来，他将鱼平分成5份，把多余的一条扔回湖中，拿自己的一份回家去了；B第二个醒来，也将鱼平分为5份，扔掉多余的一条，只拿走自己的一份；接着C,D,E依次醒来，也都按同样的办法分鱼。问5人至少合伙捕到多少条鱼？每个人醒来后看到的鱼数是多少条？ 任务6.3 解题思路 假定A,B,C,D,E的编号为1,2,3,4,5，整数数组fish[k]表示第k个人所看到的鱼数。 显然： fish[1]=5人合伙捕到的总鱼数 fisk[2]=(fish[1]-1)*4/5 fish[3]=(fish[2]-1)*4/5 fish[4]=(fish[3]-1)*4/5 fish[5]=(fish[4]-1)*4/5 即fish[i]=(fish[i-1]-1)*4/5,且fish[i-1]%5==1 或fish[i-1]=fish[i]*5/4+1,且fish[i]%4==0(i1) 任务6.3 解题思路(续) 按题意要求5人合伙捕鱼的最少鱼数，可以从小到大枚举。取fish[5]的值为6, 11, 16, 21，…依次计算fish[4], fish[3], fish[2], fish[1]的值，并比较其是否满足fish[i+1]%4==0(i=4,3,2,1)， 如果某次计算不能满足，则退出本次循环，继续从下一个fish[5]开始进行计算，如果所有的fish[i]均满足条件，则退出循环，得到结果。 程序：6_4.cpp 任务6.3 的程序框图(NS图) 6.2.1 递推数列的定义 一个数列从某一项起，它的任何一项都可以用它前面的若干项来确定，这样的数列称为递推数列，表示某项与其前面的若干项的关系就称为递推公式。 如1!,2!,3!,…,n!就是一个递推数列，其递推公式为:设fact(n)表示n! fact(n)=n*fact(n-1) （通项公式） fact(0)=1 （边界条件） 6.2.2 递推算法的程序实现 有了通项公式和边界条件后，采用循环结构，从边界条件出发，利用通项公式通过若干步递推过程就可以求出解来。 例：编写一个程序int fact(int n)，用于计算n!的值。 int fact(int n) { int i, prod=1; //通过边界条件赋初值 for(i=1;i=n;i++) prod = prod*i;//通项公式 return prod; } 6.3 递归及其实现 递归算法