07 递归算法举例.ppt

第1页：第七讲递归算法举例封面

本页为第七讲 递归算法举例章节封面，本讲通过三个案例巩固递归编程思想：

• 青蛙过河
• 快速排序
• 分书问题
• 习题讨论

第2页：第七讲目录页

本页为第七讲目录，列出本讲内容：青蛙过河、快速排序、分书问题、习题讨论。

第3页：递归算法举例——青蛙过河

本节为递归算法举例——青蛙过河，以 2000 年全国青少年信息学奥林匹克试题为例讲解递归求解思路。

第4页：青蛙过河问题

讨论问题——青蛙过河。该题是 2000 年全国青少年信息学奥林匹克的一道试题，叙述如下：

一条小溪尺寸不大，青蛙可以从左岸跳到右岸。在左岸有一石柱 L，面积只容得下一只青蛙落脚，同样右岸也有一石柱 R，面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小，将青蛙从小到大用 1，2，…，n 编号。规定初始时这队青蛙只能趴在左岸的石头 L 上，当然是一个落一个，小的落在大的上面，不允许大的在小的上面。

在小溪中有 S 个石柱、有 y 片荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求一个落一个，大的在下、小的在上；对于荷叶只允许一只青蛙落脚，不允许多只在其上；对于右岸的石柱 R，与左岸的石柱 L 一样允许多个青蛙落脚，但须一个落一个，小的在上、大的在下。

当青蛙从左岸的 L 上跳走后就不允许再跳回来；同样，从左岸 L 上跳至右岸 R，或从溪中荷叶或溪中石柱跳至右岸 R 上的青蛙也不允许再离开。问：在已知溪中有 S 根石柱和 y 片荷叶的情况下，最多能跳过多少只青蛙？

第5页：青蛙过河的解题思路

这题看起来较难，但是如果我们认真分析，理出思路，就可化难为易。

思路：

1. 简化问题，探索规律：先从个别再到一般，要善于对多个因素作分解，孤立出一个一个因素来分析，化难为易
2. 定义函数 Jump(S,y)——最多可跳过河的青蛙数，其中 S 为河中柱子数、y 为荷叶数

第6页：河中无柱子且y=1

3. 先看简单情况，河中无柱子：S=0，Jump(0,y)

当 y=1 时 Jump(0,1)=2：河中有一片荷叶，可以过两只青蛙，起始时 L 上有两只青蛙，1# 在 2# 上面。

• 第一步：1# 跳到荷叶上
• 第二步：2# 从 L 直接跳至 R 上
• 第三步：1# 再从荷叶跳至 R 上

第7页：归纳出Jump(0,y)=y+1

当 y=2 时 Jump(0,2)=3：河中有两片荷叶时，可以过 3 只青蛙。起始时 1#、2#、3# 三只青蛙落在 L 上：

• 第一步：1# 从 L 跳至叶1上
• 第二步：2# 从 L 跳至叶2上
• 第三步：3# 从 L 直接跳至 R 上
• 第四步：2# 从叶2跳至 R 上
• 第五步：1# 从叶1跳至 R 上

采用归纳法：Jump(0,y)=y+1，意思是河中没有石柱的情况下，过河的青蛙数仅取决于荷叶数，数目是荷叶数+1。

第8页：S=1且y=1的跳法

再看 Jump(S, y)，先看一个最简单情况：S=1，y=1。从图上看出需要 9 步，跳过 4 只青蛙：

1. 1# 青蛙从 L → Y
2. 2# 青蛙从 L → S
3. 1# 青蛙从 Y → S
4. 3# 青蛙从 L → Y
5. 4# 青蛙从 L → R
6. 3# 青蛙从 Y → R
7. 1# 青蛙从 S → Y
8. 2# 青蛙从 S → R
9. 1# 青蛙从 Y → R

第9页：青蛙过河过程表

说明：源文件该页以粘连字符与图形方式给出（L1~L4、S1~S2、Y、R1~R4 各位置按时刻 0~9 排列），上表依据前后页所述的九步跳法还原，供对照原图核对。

第10页：一分为二的系统分解

为了将过河过程描述得更清楚，给出了表 1。表中 L1 L2 L3 L4 表示左岸石柱上落在一起的青蛙的高度位置，L1 在最上面、L4 在最下面的位置，引入这个信息就可比较容易地看出对青蛙占位的约束条件；同理 R1 R2 R3 R4 也是如此。对水中石柱 S 也分成两个高度位置 S1、S2；对荷叶 Y 无须分层，因为它只允许一只青蛙落在其上。

• t=0 为初始时刻，青蛙从小到大落在石柱 L 上
• t=1 为第一步：1# 从 L 跳至荷叶 Y 上，L 上只剩 2# 3# 4#
• t=2 为第二步：2# 从 L 跳至石柱 S 上，处在 S2 位置上，L 上只剩 3# 和 4#
• t=3 为第三步：1# 从 Y 跳至 S，将 Y 清空。这时 S 上有 1#、2#，L 上有 3#、4#，好象是原来在 L 上的 4 只青蛙分成了上下两部分，上面的 2 只通过荷叶 y 转移到了 S 上

这一过程是一分为二的过程：将 L 上的一队青蛙分解为两个队，每队各二只，且将上面的二只转移到了 S 上。这时可以考虑形成两个系统：一个是 L、Y、R 系统，一个是 S、Y、R 系统，前者二只青蛙号大、后者二只青蛙号小，先跳号大的、再跳号小的。从第五步到第九步可以看出的确是这么做的。

第11页：两个子系统求和

对于 LYR 系统，相当于 Jump(0,1)；对于 SYR 系统，相当于 Jump(0,1)。两个系统之和为 2*Jump(0,1)，因此有：

Jump(1,1) = 2*Jump(0,1) = 2*2 = 4

现在再看 S=2、y=1 的 Jump(2,1)：将河中的两个石柱称作 S1 和 S2，荷叶叫 y，考虑先将 L 上的青蛙的一半借助于 S2 和 y 转移到 S1 上，当然是一半小号的青蛙在 S1 上、大的留在 L 上。

第12页：递归公式Jump(S,y)

这样 L S1 S2 y R 系统分解为：

（L S2 y R系统）+（S1 S2 y R系统） = 2 *（L S2 y R系统） = 2 * Jump(1,1)

用归纳法得：Jump(S, y)=2*Jump(S-1, y)

第13页：青蛙过河的与或结点图

将上述分析出来的规律写成递归形式的与或结点图如下。

第14页：计算举例Jump(3,4)

举例：S=3，y=4，算 Jump(3,4)。由 Jump(0,y)=y+1 与 Jump(S,y)=2*Jump(S-1,y) 可得 Jump(3,4)=2*Jump(2,4)=4*Jump(1,4)=8*Jump(0,4)=8*5=40，即最多可跳过 40 只青蛙。

说明：源文件该页仅给出“举例：S=3，y=4，算 Jump(3,4)”的标题性内容，上式为依据前面递推关系补算的示例结果，供对照原图核对。

第15页：青蛙过河参考程序

#include <stdio.h> int Jump(int, int);void main() { int s,y,sum; printf("请输入石柱数s=" ); scanf("%d",&s); printf("请输入荷叶数y=" ); scanf("%d",&y); sum=Jump(s,y); printf("Jump(%d,%d)=%d\n",s,y,sum); } int Jump(int r,int z){ int k; if (r==0) { k=z+1; } else { k=2*Jump(r-1,z); } return(k);}

第16页：递归算法举例——快速排序

本节为递归算法举例——快速排序，讲解用递归思想实现快速排序的思路与程序。

第17页：快速排序的思路

快速排序的思路：

1. 将待排序的数据放入数组 a 中，下标从 l 到 r
2. 取 a[l] 放变量 k 中，通过由右、左两边对 k 的大小的比较，为 k 选择应该排定的位置。这时要将比 k 大的数放右边、比 k 小的数放左边。当 k 到达最终位置后，由 k 划分了左右两个集合，然后再用同样的思路处理左集合与右集合
3. 令 sort(l,r) 为将数组元素从下标为 l 到下标为 r 的 r-l+1 个元素从小到大排序

第18页：快速排序的与或图

我们画出与或图来阐述快速排序的思路。

第19页：分区处理与结点分解

分区处理：

1. 让 k=a[l]
2. 将 k 放在 a[m]
3. 使 a[l], a[l+1], …, a[m-1] <= a[m]
4. 使 a[m] < a[m+1], a[m+2], …, a[r]

A 结点表示将数组 a[l], a[l+1], …, a[r] 中的元素按由小到大用快速排序的思路排序；B 结点表示如果 l>=r，则什么也不做，这是直接可解结点；C 结点是在 l<r 情况下 A 结点的解。C 是一个与结点，要对 C 求解需分解为三步，依次为：

第20页：D结点的分区处理

1. 先解 D 结点，D 结点是一个直接可解结点，功能是进行所谓的分区处理，规定这一步要做的事情是：

• 将 a[l] 中的元素放到它应该在的位置上，比如 m 位置，这时 a[m] ← a[l]
• 让下标从 l 到 m-1 的数组元素小于等于 a[m]
• 让下标从 m+1 到 r 的数组元素大于 a[m]

比如 a 数组中 a[l]=5，经分组处理后 5 送至 a[4]。5 到位后，其左边 a[0]～a[3] 的值都小于 5，其右边 a[5]、a[6] 大于 5。

第21页：分区处理示意图

本页以图形方式展示分区处理前后数组元素的变化：分区前数组 a 的下标 0~6 依次为 5、4、3、7、1、6、2，分区后为 4、3、1、2、5、7、6，5 落在下标 m=4 处，其左侧元素均不大于 5、右侧元素均大于 5。

说明：源文件该页为图示，数组数值与下标对应关系依据前后页程序与排序过程还原，建议对照原图核对。

第22页：左右集合的递归处理

2. 再解 E 结点，这时要处理的是 a[0]～a[3]
3. 再解 F 结点，处理 a[5]、a[6]

下面按照这种思路构思一个快速排序的程序框图：

void sort(int array[ ], int ll, int rr) int l,r,i,k;

第23页：快速排序程序框图

本页以图形方式给出快速排序的程序框图，源文件未给出更多文字说明。

第24页：排序过程示例图1

下面举例说明排序过程。

图1：a 数组中有 7 个元素待排序，让 k=a[l]=a[0]=5，下标 l=0、r=6。

第25页：排序过程图2

2 进入直到型循环：

• 执行（1）a[r]=a[6]=4 不满足当循环条件，r 不动
• 执行（2）l<r，做两件事：a[l]=a[r]，即 a[0]=a[6]=4；l=l+1=0+1=1，见图2

第26页：排序过程图3

• 执行（3）图2中的 a[1]<k，满足当循环条件，l=l+1=2，l 增 1 后的情况如图3。图3 的情况不再满足当循环条件

第27页：排序过程图4

• 执行（4）a[r]=a[l]，即 a[6]=a[2]=6，见图4。这时 l!=r 还得执行直到型循环的循环体

第28页：排序过程图5

• 执行（1）a[r]=a[6]=6，6>k 满足当循环的条件，r=r-1=6-1=5 见图5，之后退出当循环，因为 a[r]=3<k

第29页：排序过程图6

• 执行（2）a[l]=a[r]，并让 l=l+1=3，见图6

第30页：排序过程图7

• 执行（3）由于 a[3]=1<k，满足当循环条件，让 l=l+1=4；a[4]=7>k，退出循环。见图7

第31页：排序过程图8

• 执行（4）a[r]=a[l]，a[5]=7。见图8，这时仍然 l<r，应继续执行直到型循环的循环体

第32页：排序过程图9

• 执行（1）a[r]=7>k，让 r=r-1=4。见图9

第33页：排序过程图10

• 之后 l=r，退出直到型循环，做 a[l]=k，l=4、a[4]=5，这是 5 的最终位置，5 将整个数据分成左右两个集合，见图10

第34页：排左半部分图11与12

4、用上述思路去排左边的部分，从 l=0 到 r=3，见图11。让 k=a[l]=a[0]=4，然后进到直到型循环：

• 执行（1）a[r]=1<k，不满足当循环的条件，r 不动
• 执行（2）a[l]=a[r]，l=l+1=1，见图12

第35页：排左半部分图13与14

• 执行（3）a[l]<k，l=l+1=2；a[2]<k，l=l+1=3，这时 l=r，不会执行（4），同时退出直到型循环，见图13。然后做 a[l]=k，即 a[3]=4，见图14，左边也排好了

第36页：排右半部分图15与16

4、用上述思路去排右边的部分，见图15，让 k=a[l]=a[5]=7，进入直到型循环：

• 执行（1）a[r]=6<k，r 不动
• 执行（2）a[l]=a[r]=6，l=l+1=5+1=6，见图16

第37页：排右半部分图17

这时 l=r，不再执行（3）（4），退出直到型循环后，做 a[l]=k，见图17。

第38页：主程序的写法

在有了递归调用函数之后，主程序很容易写，主程序中应包含：

1. 定义整型变量：数组 a[10]、i
2. 用循环结构输入待排序的数，将其放入 a 数组
3. 调用 sort 函数，使用三个实际参数：a（将数组 a 当实参）、0（数组下标下界）、9（数组下标上界）
4. 输出排序结果

下面给出参考程序（分两页）。

第39页：快速排序sort函数

#include <stdio.h> void sort(int array[ ],int ll,int rr){ int l,r,i,k; if(ll<rr) { l=ll; r=rr; k=array[l]; do { while((l<r)&&(array[r]>=k)) r=r-1; if(l<r) { array[l]=array[r]; l=l+1; } while((l<r)&&(array[l]<=k)) l=l+1; if (l<r) array[r]=array[l]; } while(l!=r); array[l]=k; for(i=ll;i<=rr;i=i+1) { printf("a[%d]=%d;",i,array[i]); } printf("\n"); sort(array,ll,l-1); sort(array,l+1,rr); } }

第40页：快速排序主函数

void main() { int a[10],i; printf("请输入10个整数\n" ); for (i=0;i<10;i=i+1) scanf("%d",&a[i]); sort(a,0,9); printf("排序结果为:"); for (i=0;i<10;i=i+1) printf("%d;",a[i]); printf("\n"); }

第41页：递归算法举例——分书问题

本节为递归算法举例——分书问题。

• 教学目标：巩固用递归思想编写程序
• 教学内容：分书问题

第42页：分书问题题目

题目：有编号分别为 1，2，3，4，5 的五本书，准备分给 A、B、C、D、E 五个人，每个人阅读兴趣用一个二维数组加以描述。

希望你写一个程序，输出所有分书方案，让人人皆大欢喜。

第43页：五人对五本书的兴趣表

第44页：解题思路——定义数组

解题思路：

1. 定义一个整型的二维数组，将表中的阅读喜好用初始化方法赋给这个二维数组：

int like[5][5]={ {0,0,1,1,0}, {1,1,0,0,1}, {0,1,1,0,1}, {0,0,0,1,0}, {0,1,0,0,1} };

2. 定义一个整型一维数组 book[5] 用来记录书是否已被选用。用下标作为五本书的标号，被选过元素值为 1，未被选过元素值为 0，初始化皆置 0：

int book[5]={0,0,0,0,0};

说明：源文件此处写作「book[i]=1」，与程序及题意不符，按标准写法应为 book[j]=1（以书号 j 为下标记录该书已被选用）。

第45页：定义try(i)的思路图

3. 画出思路图：定义 try(i)——试着给第 i 人分书（i=0,1,…,4）

第46页：分书问题的与或图

本页以图形方式给出分书问题的与或图，源文件未给出更多文字说明。

第47页：与或图的说明

说明：

1. 试着给第 i 个人分书，先试分 0 号书，再分 1 号书、分 2 号书……因此有一个与结点，让 j=0,1,2,3,4，j 表示书
2. LP 为循环结构的循环体
3. 条件 C 是由两部分“与”起来的：“第 i 个人喜欢 j 书，且 j 书尚未被分走”，满足这个条件是 i 人能够得到 j 书的条件
4. 如果不满足 C 条件，则什么也不做，这是直接可解结点

第48页：回溯的三件事

5. 满足 C 条件，做三件事：

• sh1 第一件事：将 j 书分给 i，用一个数组 take[i]=j 记住书 j 给了 i 人，同时记录 j 书已被选用，book[j]=1
• sh2 第二件事：查看 i 是否为 4，如果不为 4，表示尚未将所有 5 个人所要的书分完，这时应递归再试下一人，即 try(i+1)。如果 i==4，则应先使方案数 n=n+1，然后输出第 n 个方案下的每个人所得之书
• sh3 第三件事：回溯。让第 i 人退回 j 书，恢复 j 书尚未被选的标志，即 take[i]=-1 和 book[j]=0。这是在已输出第 n 个方案之后，去寻找下一个分书方案所必需的

在有了上述的与或图之后，我们很容易写出一个程序框图。先看被调用函数 try(i) 的框图。

说明：源文件此处「同时记录 j 书已被选用」处写作 book[i]=1，与程序不符，按标准写法应为 book[j]=1。

第49页：try(i)程序框图

本页以图形方式给出被调用函数 try(i) 的程序框图，源文件未给出更多文字说明。

第50页：主程序与全局变量

#include <stdio.h> int take[5],n; int like[5][5] = { {0,0,1,1,0}, {1,1,0,0,1}, {0,1,1,0,1}, {0,0,0,1,0}, {0,1,0,0,1} }; int book[5]={0,0,0,0,0};

下面讨论主程序应该做的事情：

1. 将分书方案号预置 0
2. 从第 0 号人（A）开始试分书，调用 try(0)

参考程序如下所示（分三页）：

第51页：分书问题try函数

void try(int i){ int j,k; for(j=0;j<=4;j=j+1) { if((like[i][j]>0)&&(book[j]==0)) { take[i]=j; book[j]=1; if(i==4) { n=n+1; printf("第%d个方案\n",n); for(k=0;k<=4;k=k+1) { printf("%d号书分给%c;\n",take[k],k+65); } printf("\n"); } else { try(i+1); } take[i]=-1; book[j]=0; } } }

第52页：分书问题主函数

void main() { n=0; try(0);}

第53页：第七讲结束页

本页为第七讲 递归算法举例的结束页，本讲内容至此结束。