计算机语言与程序设计函数.ppt

计算机程序设计基础 第五讲 函数 1 三、数组 问题：编程求解问题：编程求解 现假定 n=6，k=4 我们用函数来编写这个题的程序，参考程序如下： #include / /预编译命令预编译命令 #define n 6 /#define n 6 /定义定义n n为为6 6 #define k 4 /#define k 4 /定义定义k k为为4 4 void main() /void main() /主函数主函数 / /主程序开始主程序开始 printf(“sumprintf(“sum of % of %dthdth powers of integers from 1 to %d=“, powers of integers from 1 to %d=“,k,nk,n ); ); / /提示信息提示信息 printf(“%dn“,SOP(n,kprintf(“%dn“,SOP(n,k); /); /输出结果输出结果, ,其中其中 / /SOP(n,kSOP(n,k) )为被调用函数为被调用函数 / /主程序结束主程序结束 2 / /以下函数是被主程序调用的函数以下函数是被主程序调用的函数 intint SOP(m,lSOP(m,l) /) /整型自定义函数整型自定义函数, ,m,lm,l 为形参为形参 intint m,lm,l; /; /形参形参m,lm,l 为整型变量为整型变量 / /自定义函数体开始自定义函数体开始 intint i,sumi,sum; /; /整型变量整型变量i,sumi,sum sum=0; /sum=0; /初始化累加器初始化累加器 for (i=1; i () 例: int power(p,n) power为函数名，要以英文字母开头。 int是函数值的数据类型，这里是int（整型）。 (p,n)括号中的p,n为函数的形式参数，形式参数也要定义其数据 类型。 函数定义的一般格式： () 为了突出重点，先学会基本东西，省略掉一些事情先不讲。 4 1、形式参数是在定义函数时放在函数名后括号中的参数。在未进 行函数调用时，并不对形式参数分配内存单元。在发生函数调 用时，立刻给形式参数分配内存单元。调用结束后，释放掉行 参所占的内存单元。 2、因此，形参变量属于局部变量，其作用域在它所在的函数体内 。 3、在定义函数的时候，必须指定形参变量的类型，如何指定？有 二种方法： 形式参数与实在参数 (1) int power(p,n) int p,n; (2) int power(int p,int n) 有些编译系统不认识第（2）种形式 5 4、实在参数是一个具有确定值的表达式。函数在调用时，将实在 参数赋给形式参数。 比如，主函数调用SOP(n,k)，这时，n,k为实在参数，n的 值为6，k的值为4。在被调用函数定义中，int SOP(m,l)中的m,l 为形式参数，在SOP被调用时，系统给m,l这两个形式参数分配 了内存单元。之后，n的值6赋给m，k的值4赋给l。 实在参数的个数及类型应与形式参数一致。赋值时前后对应关系 不会改变。下面画出主函数与SOP函数，调用与被调用时参数 传递关系： 6 主函数执行下述语句时， printf(“%dn”,SOP(n,k); 传值给被调用函数 int SOP(m,l) n的值6传给m, k的值4传给l。 6和4为实在参数，m和l为形式参数。 被调用函数在其形式参数被赋值之后，开始执行函数体，先是让 累加器初始化为0（sum=0），接着进入以i为控制变量的计算循 环，i从1变到m（m=6），即累加m次（即6次）。循环体为 sum=sum+power(i,l)。当6次循环执行完后，实现的是 注意这里 是由另一个自定义函数power(i,l)实现的。 7 power(i,l)处在SOP(m,l)函数中，表示SOP函数去调用 power 函数。其中i,l为实在参数，而int power(p,q)中 的p,q为形式参数。 比如，执行SOP(6,4)时，l=4,m=6, 当i=1时， sum=sum+power(1,4) 这里1，4为实在参数，调用power(p,q)，两个形式参数 p,q分别被赋以1，4。 8 9 递归算法在可计算性理论中占有重要地位，它是算法 设计的有力工具，对于拓展编程思路非常有用。就递 归算法而言并不涉及高深数学知识，只不过初学者要 建立起递归概念不十分容易。 我们先从一个最简单的例子导入。 递归及其实现递归及其实现 用递归算法求n! 定义：函数 fact(n) = n! fact(n-1) = (n-1)! 则有 fact(n) = n fact(n-1) 已知 fact(1) = 1 10 为了表述得直观清晰，我们定义两个结点：或结点与 与结点。 图示的直观性与思维助力。 1、或结点 A为“或结点”，A依不同条件会有两种不同的取值B或C 。结点用 表示。 11 如果有多于2种取值，可用下图： 条件为Z1, Z2, ,Zn，取值为B或C,或G 12 2、与结点 与结点要涂黑，相关联 的B与C之间要用弧线 连起来。 A为与结点，A的最终取值为C结点的值，但为了 求得C的值，得先求出B结点的值，C是B的函数 。 13 仍以求n!为例画出如下与或图 A为或结点；B为直接可解结点，值为1； C为与结点，当n1时，A的取值即C的值，而C的值即 E的值，为了求得E的值，需要先求出D的值。D值 fact(n-1)乘以n即为E的值。 14 与结点可能有多个相关联的点，这时可描述为下图 A结点的值最终为D的值，但为了求D需先求B和C。从 图上看先求左边的点才能求最右边的点的值，我们约 定最右边D点的值就是A结点的值。 15 下面我们以3！为例来画与或结点图，目的是体会递归 的含义。 C = 1 D = 2*C = 2 B = D = 2 E = 3*B = 3*2 = 6 A = E = 6 16 下面画出了调用和返回的递归示意图 17 从图可以想象： 欲求fact(3)，先要求fact(2)；要求fact(2)先求fact(1) 。就象剥一颗圆白菜，从外向里，一层层剥下来，到 了菜心，遇到1的阶乘，其值为1，到达了递归的边界 。然后再用fact(n)=n*fact(n-1)这个普遍公式，从里 向外倒推回去得到fact(n)的值。 为了把这个问题说得再透彻一点。我们画了如下的流 程图： 18 19 为了形象地描述递归过程，将上图改画成下图 20 在这个图中“内层”与“外层”有着相同的结构。它们之 间“你中有我，我中有你”，呈现相互依存的关系。 为了进一步讲清递归的概念，将递归与递推做一比较 。仍以求阶乘为例。 递推是从已知的初始条件出发，逐次去求所需要的阶 乘值。 如求3！ 初始条件 fact(1) = 1 fact(2) = 2*fact(1) = 2 fact(3) = 3*fact(2) = 6 21 这相当于从菜心“推到”外层。而递归算法的出发点不 放在初始条件上，而放在求解的目标上，从所求的未 知项出发逐次调用本身的求解过程，直到递归的边界 （即初始条件）。就本例而言，读者会认为递归算法 可能是多余的，费力而不讨好。但许多实际问题不可 能或不容易找到显而易见的递推关系，这时递归算法 就表现出了明显的优越性。下面我们将会看到，递归 算法比较符合人的思维方式，逻辑性强，可将问题描 述得简单扼要，具有良好的可读性，易于理解，许多 看来相当复杂，或难以下手的问题，如果能够使用递 归算法就会使问题变得易于处理。下面举一个尽人皆 知的例子哈诺（Hanoi）塔问题。 22 故事：相传在古代印度的Bramah庙中，有位僧人整天 把三根柱子上的金盘倒来倒去，原来他是想把64个一 个比一个小的金盘从一根柱子上移到另一根柱子上去 。移动过程中恪守下述规则：每次只允许移动一只盘 ，且大盘不得落在小盘上面。有人会觉得这很简单， 真的动手移盘就会发现，如以每秒移动一只盘子的话 ，按照上述规则将64只盘子从一个柱子移至另一个柱 子上，所需时间约为5800亿年。 23 怎样编写这种程序？思路上还是先从最简单的情况分 析起，搬一搬看，慢慢理出思路。 1、在A柱上只有一只盘子，假定盘号为1，这时只 需将该盘从A搬至C，一次完成，记为move 1 from A to C 24 2、在A柱上有二只盘子，1为小盘，2为大盘。 第（1）步将1号盘从A移至B，这是为了让2号盘能移动； 第（2）步将2号盘从A移至C； 第（3）步再将1号盘从B移至C； 这三步记为： move 1 from A to B; move 2 from A to C; move 3 form B to C; 25 3、在A柱上有3只盘子，从小到大分别为1号，2号，3号 第（1）步将1号盘和2号盘视为一个整体；先将二者作为 整体从A移至B，给3号盘创造能够一次移至C的机会。这 一步记为 move( 2, A, C, B) 意思是将上面的2只盘子作为整体从A借助C移至B。 第（2）步将3号盘从A移至C，一次到位。记为 move 3 from A to C 第（3）步处于B上的作为一个整体的2只盘子，再移至C。 这一步记为 move( 2, B, A, C) 意思是将2只盘子作为整体从B借助A移至C。 所谓借助是什么意思，等这件事做完了不言自明。 26 27 4、从题目的约束条件看，大盘上可以随便摞小盘，相 反则不允许。在将1号和2号盘当整体从A移至B的过 程中move(2, A, C, B)实际上是分解为以下三步 第（1）.1步：move 1 form A to C; 第（1）.2步：move 2 form A to B; 第（1）.3步：move 1 form C to B; 经过以上步骤，将1号和2号盘作为整体从A移至B，为3 号盘从A移至C创造了条件。同样，3号盘一旦到了C ，就要考虑如何实现将1号和2号盘当整体从B移至C 的过程了。实际上move(2, B, A, C)也要分解为三步 ： 第（3）.1步：move 1 form B to A; 第（3）.2步：move 2 form B to C; 第（3）.3步：move 1 form A to C; 28 5、看move(2, A, C, B)是说要将2只盼自从A搬至B，但 没有C是不行的，因为第（1）.1步就要将1盘从A移 到C，给2盘创造条件从A移至B，然后再把1盘从C移 至B。看到这里就能明白借助C的含义了。因此，在 构思搬移过程的参量时，要把3个柱子都用上。 6、定义搬移函数move(n, A, B, C)，物理意义是将n只 盘子从A经B搬到C 考虑到前面已经 研究过的 (1)(2)(3)步，可 以将搬移过程 用如下的与或 结点图表示。 29 这里用与或结点的含义是分解为(1)(2)(3)步。这3步是 相关的，相互依存的，而且是有序的，从左至右执行 。 move(n, A, B, C) 分解为3步 (1)move(n-1, A, C, B)理解为将上面的n-1只盘子作为一 个整体从A经C移至B； (2)输出n：A to C，理解将n号盘从A移至C，是直接可 解结点； (3)Move(n-1, B, A, C)理解为将上面的n-1只盘子作为一 个整体从B经A移至C。 30 这里显然是一种递归定义，当着解move(n-1, A, C, B)时 又可想到，将其分解为3步： 第1步：将上面的n-2只盘子作为一个整体从A经B到C ，move(n-2, A, B, C)； 第2步：第n-1号盘子从A直接移至B，即n-1:A to B； 第3步：再将上面的n-2只盘子作为一个整体从C经A移 至B，move(n-2, C, A, B)； 下面，我们还是以3只盘子为例画出递归的与或图。 31 这个图很象一颗倒置着的树，结点move(3, A, B, C)是 树根，与结点是树的分枝，叶子都是直接可解结点。 32 33 34 #include /预编译命令 int step=1 ; /整型全局变量,预置1,步数 void move(int , char ,char,char); /声明要用到的被调用函数 void main() /主函数 /主程序开始 int n; /整型变量,n为盘数, printf(“请输入盘数n=“ ); /提示信息 scanf(“%d“, /输入正整数n printf(“在3根柱子上移%d只盘的步骤为:n“,n); /输出提示信息 move(n,a,b,c);/调用函数 move(n,a,b,c) /主程序结束 /以下函数是被主程序调用的函数 void move(int m, char p, char q, char r) /自定义函数,m,p,q,r为形参，m 为整型变量 / p,q,r 为字符型变量 /自定义函数体开始 if (m=1) /如果m为1