05 函数.ppt

第1页：第五讲函数封面

本页为第五讲 函数章节封面，本讲讲解自定义函数、形参与实参，并以递归与哈诺塔为例展开。

第2页：幂和问题的求解

编程求解 1^k+2^k+…+n^k，现假定 n=6、k=4。用函数来编写这个题的程序：

#include <stdio.h> #define n 6 #define k 4 void main() { printf("sum of %dth powers of integers from 1 to %d=",k,n ); printf("%d\n",SOP(n,k));}

第3页：被调函数SOP的实现

int SOP(m,l)int m,l; { int i,sum; sum=0; for (i=1; i<=m; i=i+1 ) { sum=sum+power( i ,l ); } return (sum); }

SOP 是被主程序调用的函数，其值为 1 到 m 的 l 次幂之和。

第4页：自定义函数的定义格式

自定义函数的一般形式为 <数据类型> <函数名> (<参数表>)，例：int power(p,n)。

• power 为函数名，要以英文字母开头
• int 是函数值的数据类型，这里是整型
• 括号中的 p、n 为形式参数，形式参数也要定义其数据类型

<数据类型> <函数名> (<参数表>) <参数说明;> { <说明语句> <执行语句> }

为突出重点，先学会基本内容，省略一些细节暂不讲述。

第5页：形式参数的说明

1. 形式参数是在定义函数时放在函数名后括号中的参数；未调用时不分配内存单元，发生函数调用时立刻分配，调用结束后释放，因此形参变量属于局部变量，作用域在其所在函数体内
2. 定义函数时必须指定形参变量的类型，有两种方法：int power(p,n) int p,n; {...} 与 int power(int p,int n) {...}，有些编译系统不认识第二种形式

第6页：实在参数的说明

4. 实在参数是一个具有确定值的表达式，函数调用时将实在参数赋给形式参数。如主函数调用 SOP(n,k)，n、k 为实在参数，n 的值为 6、k 的值为 4；被调函数中 int SOP(m,l) 的 m、l 为形式参数，调用时系统给 m、l 分配内存单元，之后 n 的值 6 赋给 m、k 的值 4 赋给 l

实在参数的个数及类型应与形式参数一致，赋值时前后对应关系不会改变。下面画出主函数与 SOP 函数调用与被调用时参数传递关系。

第7页：参数传递关系

主函数执行 printf("%d\n",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），即累加 6 次。

第8页：嵌套调用power函数

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。

第9页：函数调用与返回关系

本页以图示方式展示主函数、SOP 函数与 power 函数之间的调用与返回关系，源文件未给出更多文字说明。

第10页：递归算法导入

递归算法在可计算性理论中占有重要地位，是算法设计的有力工具，对拓展编程思路非常有用。递归算法并不涉及高深数学知识，只是初学者建立递归概念不十分容易。先从最简单的例子导入——用递归算法求 n!

定义：函数 fact(n) = n! fact(n-1) = (n-1)! 则有 fact(n) = n * fact(n-1) 已知 fact(1) = 1

第11页：或结点

为表述直观清晰，定义两个结点：或结点与与结点。A 为“或结点”，A 依不同条件会有两种不同的取值 B 或 C。

第12页：多取值或结点

如果有多于 2 种取值，可用下图表示：条件为 Z1, Z2, …, Zn，取值为 B 或 C, … 或 G。

第13页：与结点

2. 与结点：与结点要涂黑，相关联的 B 与 C 之间要用弧线连起来。A 为与结点，A 的最终取值为 C 结点的值，但为求得 C 的值，得先求出 B 结点的值，C 是 B 的函数。

第14页：求n!的与或图

仍以求 n! 为例画出与或图：A 为或结点；B 为直接可解结点，值为 1；C 为与结点，当 n>1 时 A 的取值即 C 的值，而 C 的值即 E 的值；为求 E 的值需要先求出 D 的值，D 值 fact(n-1) 乘以 n 即为 E 的值。

第15页：多关联点与结点

与结点可能有多个相关联的点：A 结点的值最终为 D 的值，但为求 D 需先求 B 和 C。从图上看先求左边的点才能求最右边的点的值，约定最右边 D 点的值就是 A 结点的值。

第16页：3!的与或结点图

下面以 3! 为例画与或结点图，目的是体会递归的含义：

C = 1 D = 2*C = 2 B = D = 2 E = 3*B = 3*2 = 6 A = E = 6

第17页：调用与返回的递归示意图

本页画出了调用和返回的递归示意图，展示 fact 函数层层调用自身、到达边界后再逐层返回的过程。

第18页：递归过程的形象解释

从图可以想象：欲求 fact(3)，先要求 fact(2)；要求 fact(2) 先求 fact(1)。就像剥一颗圆白菜，从外向里一层层剥下来，到了菜心遇到 1 的阶乘其值为 1，到达了递归的边界。然后再用 fact(n)=n*fact(n-1) 这个普遍公式，从里向外倒推回去得到 fact(n) 的值。为把问题说得再透彻一点，另画了流程图。

第19页：递归流程图

本页以流程图形式展示求阶乘时的递归调用与返回流程，源文件未给出更多文字说明。

第20页：递归过程改画图

为了形象地描述递归过程，将上图改画成下图。

第21页：递归与递推的比较

在这个图中“内层”与“外层”有着相同的结构，它们“你中有我，我中有你”，呈现相互依存的关系。为讲清递归概念，将递归与递推做一比较，仍以求阶乘为例。递推是从已知的初始条件出发，逐次去求所需要的阶乘值：

初始条件 fact(1) = 1 fact(2) = 2*fact(1) = 2 fact(3) = 3*fact(2) = 6

第22页：递归算法的优越性

递推相当于从菜心“推到”外层。而递归算法的出发点不放在初始条件上，而放在求解的目标上，从所求的未知项出发逐次调用本身的求解过程，直到递归的边界（即初始条件）。

就本例而言递归似乎多余，但许多实际问题不可能或不容易找到显而易见的递推关系，这时递归算法就表现出明显优越性：它比较符合人的思维方式，逻辑性强，可将问题描述得简单扼要，可读性好、易于理解。下面举一个尽人皆知的例子——哈诺（Hanoi）塔问题。

第23页：哈诺塔故事

故事：相传在古代印度的 Bramah 庙中，有位僧人整天把三根柱子上的金盘倒来倒去，想把 64 个一个比一个小的金盘从一根柱子移到另一根柱子上。移动过程恪守规则：每次只允许移动一只盘，且大盘不得落在小盘上面。

有人觉得这很简单，真的动手移盘就会发现：如以每秒移动一只盘子计算，将 64 只盘子按上述规则移完，所需时间约为 5800 亿年。

第24页：一只盘子的移法

怎样编写这种程序？思路上先从最简单的情况分析起，搬一搬看，慢慢理出思路。

1. 在 A 柱上只有一只盘子，假定盘号为 1，这时只需将该盘从 A 搬至 C，一次完成，记为 move 1 from A to C

第25页：两只盘子的移法

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 from B to C;

第26页：三只盘子的移法

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)

所谓“借助”是什么意思，等这件事做完了不言自明。

第27页：三盘移动过程

本页以图示方式展示 A 柱上有 3 只盘子时的整体转移过程，源文件未给出更多文字说明。

第28页：整体移动的分解

4. 从约束条件看，大盘上可以随便摞小盘，相反则不允许。在把 1 号和 2 号盘当整体从 A 移至 B 的过程中，move(2, A, C, B) 实际分解为三步：

第(1).1步：move 1 from A to C; 第(1).2步：move 2 from A to B; 第(1).3步：move 1 from C to B;

同样，3 号盘一旦到了 C，move(2, B, A, C) 也分解为三步：

第(3).1步：move 1 from B to A; 第(3).2步：move 2 from B to C; 第(3).3步：move 1 from A to C;

第29页：搬移函数的定义

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) 步，可把搬移过程用与或结点图表示。

第30页：哈诺塔的三步分解

这里用与或结点的含义是分解为 (1)(2)(3) 步，这 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

第31页：递归定义的展开

这里显然是一种递归定义。当解 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 只盘子为例画出递归的与或图。

第32页：倒置的递归树

这个图很象一颗倒置着的树：结点 move(3, A, B, C) 是树根，与结点是树的分枝，叶子都是直接可解结点。

第33页：哈诺塔递归树

本页以图形方式给出哈诺塔递归分解树，源文件未给出更多文字说明。

第34页：哈诺塔递归结构

本页继续以图形方式展示哈诺塔递归结构与盘号移动顺序，源文件未给出更多文字说明。

第35页：哈诺塔参考程序

#include <stdio.h> int step=1;void move(int , char ,char,char);void main() { int n; printf("请输入盘数n=" ); scanf("%d",&n); printf("在3根柱子上移%d只盘的步骤为:\n",n); move(n,'a','b','c'); } void move(int m, char p, char q, char r) { if (m==1) { printf("[%d] move 1# from %c to %c\n", step, p, r); step=step+1; } else { move(m-1,p,r,q); printf("[%d] move %d# from %c to %c\n", step, m, p, r); step=step+1; move(m-1,q,p,r); } }

第36页：哈诺塔小结

本页以图示方式收束哈诺塔问题与递归实现的内容，源文件未给出更多文字说明。