1
?青蛙过河
?快速排序
?分书问题
?习题讨论
第七讲 递归算法举例
n
mC
2
?
1
11
1,
,1
2
5;
1
2
3
n
m
n n n
m m m
n m n
m m n
C m n
C C C
C
C
?
??
?
?
??
?
习题：
已知 表示从 个元素中取 个的组合数，又知
、试画出符合上述关系的与或结合图；
、指出哪个是直接可解结点；
、画出 求解结点图；
4,写出递归程序求解组合问题。
3
递 归 算 法 举 例
——青蛙过河
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
3,先看简单情况，河中无柱子,S=0,
Jump(0,y)
当 y=1时,Jump(0,1)=2；
说明：河中有一片荷叶，可以过两只青蛙，起始时 L上有两
只青蛙,1#在 2#上面。
第一步,1# 跳到荷叶上；
第二步,2# 从 L直接跳至 R上；
第三步,1# 再从荷叶跳至 R上。
如下图,
2#
1#
2
1
3
L
左岸
R
右岸
7
当 y=2时,
Jump(0,2)=3；
说明：河中有两片荷叶时，可以过 3只青蛙。起始时,
1#,2#,3# 3只青蛙落在 L上,
第一步,1# 从 L跳至叶 1上,
第二步,2# 从 L跳至叶 2上,
第三步,3# 从 L直接跳至 R上,
第四步,2# 从叶 2跳至 R上,
第五步,1# 从叶 1跳至 R上,
叶1
3
1
5
L
R
叶2
2
4
采用归纳法,Jump(0,y)=y+1；
意思是：在河中没有石柱的情
况下，过河的青蛙数仅取决于荷
叶数，数目是荷叶数 +1。
8
再看 Jump(S,y)
先看一个最简单情况,S=1,y=1。
从图上看出需要 9步，跳过 4只青蛙。
1# 青蛙从 L － > Y；
2# 青蛙从 L － > S；
1# 青蛙从 Y － > S；
3# 青蛙从 L － > Y；
4# 青蛙从 L － > R；
3# 青蛙从 Y － > R；
1# 青蛙从 S － > Y；
2# 青蛙从 S － > R；
1# 青蛙从 Y － > R；
S
Y
5
4
6
L
R
1
2
3 7
8
91#
2#
4#
3#
3#
1#
2#
1#1#
9
t
L S Y R
L4 L3 L2 L1 S2 S1 R4 R3 R2 R1
0
1
2
3
4
5
6
7
8
9
4
4
4
4
4
3
3
3
3
2
2
1
2
2
2
2
2
1
1
1
1
1
3
1
1
4
4
4
4
4
3
3
3
3
2
2
1
表一
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上。
y
L R
S1 S2
12
这样 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
5,将上述分析出来的规律写成递归形式的与或结点图为,
Jum p(S,y)
y+1
S!=0S==0
Jum p(S-1,y) 2*Jump( S-1,y)
14
举例,S=3,y=4，算 Jump(3,4)
A=Jump(2,4)
2*B
2*10=20
Jump(3,4)
2*A
2*20=40
2*C
2*5=10
C=Jump(0,4)
S== 0
4+1 5
B=Jump(1,4)
3( 3,4 ) 2 ( 1 ) 2 (4 1 ) 4 0SJ u m p y? ? ? ? ?
15
#include <stdio.h> //预编译命令
int Jump(int,int); //声明有被调用函数
void main() //主函数
{ //主程序开始
int s,y,sum; //整型变量,s为河中石柱数,y为荷叶数
printf("请输入石柱数 s=" ); //提示信息
scanf("%d",&s); //输入正整数 s
printf("请输入荷叶数 y=" ); //提示信息
scanf("%d",&y); //输入正整数 y
sum=Jump(s,y); //Jump(s,y)为被调用函数
printf(“Jump(%d,%d)=%d \n",s,y,sum); //输出结果
} //主程序结束
//以下函数是被主程序调用的函数
int Jump(int r,int z) //整型自定义函数,r,z为形参
{ //自定义函数体开始
int k; //整型变量
if (r==0) //如果 r为 0,则为直接可解结点,
{
k=z+1; //直接可解结点,k值为 z+1
}
else //如果不为 1,则要调用 Jump(r-1,z)
{
k=2*Jump(r-1,z); //计算 Jump(r-1,z)再乘以 2赋给 k
}
return(k); //将 k的值返回给 Jump(s,y)
} //自定义函数体结束
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
我们画出与或图来阐述快速排序的思路,
l>=r
A so r t(l,r )
数据在a [ l ],.,,,a [ r ] 中
B
什么也不做
C
l< r
D
分区处理
F
so r t(m + 1,r )
E
so r t(l,m -1 )
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
1、先解 D结点,D结点是一个直接可解结点，功能是
进行所谓的分区处理，规定这一步要做的事情是
? （ 1）将 a[l]中的元素放到它应该在的位置上，比
如 m位置。这时 a[m]?a[l]；
? （ 2）让下标从 l到 m-1的数组元素小于等于 a[m]；
? （ 3）让下标从 m+1到 r的数组元素大于 a[m]；
比如 a数组中 a[l]=5，经分组处理后,5送至 a[4]。 5
到位后，其左边 a[0]～ a[3]的值都小于 5；其右边
a[5]a[6]大于 5。
（见下图）
21
5 2 6 1 7 3 4 a
0 1 2 3 4 5 6
l r
4 2 3 1 5 7 6 a
0 1 2 3 4 5 6
m
下标,
下标,
l m-1 r m+1
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
ll <r r
l = l l; r =r r ; k =ar r a y [l ];
T F
do
w hi l e( (l <r)& & (a rra y [r] >= k )) (1)
r = r - 1;
l<r (2) T F
a r r a y [l ]=a r r a y [r];
l=l+1
w h i le (( l<r )&&( a r r a y [ l ]<=k )) (3 )
l = l + 1;
l<r ; (4) T F
a r r a y [r]=ar r a y [ l] ;
w h i le ( l !=r );
a r r a y [l ]=k ;
f or (i =ll ; i<=r r ; i=i+1 )
输出 a r r a y [i ];
换行 ;
so r t( a r r a y,ll,l - 1 );
so r t( a r r a y,l+1,r r ) ;
24
下面举例说明排序过程
图 1 a数组中有 7个元素待排序
1 让 k=a[l]=a[0]=5
5 2 6 1 7 3 4
0 1 2 3 4 5 6
l r
图 1
5 k
25
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
4 2 6 1 7 3 4
0 1 2 3 4 5 6
l r
图 2
5 k
26
? 执行（ 3）图 2中的 a[1]<k，满足当循环条件,l=l+1=2，
l增 1后的情况如 图 3。图 3的情况不再满足当循环条件。
4 2 6 1 7 3 4
0 1 2 3 4 5 6
l r
图 3
5 k
27
? 执行（ 4） a[r]=a[l]，即 a[6]=a[2]=6，见 图 4。这时
l!=r还得执行直到型循环的循环体。
4 2 6 1 7 3 6
0 1 2 3 4 5 6
l r
图 4
5 k
28
? 执行（ 1） a[r]=a[6]=6,6>k满足当循环的条件,
r=r-1=6-1=5
见 图 5，之后退出当循环，因为 a[r]=3<k
4 2 6 1 7 3 6
0 1 2 3 4 5 6
l r
图 5
5 k
29
? 执行（ 2） a[l]=a[r]，并让 l=l+1=3，见 图 6
4 2 3 1 7 3 6
0 1 2 3 4 5 6
l r
图 6
5 k
30
? 执行（ 3）由于 a[3]=1<k，满足当循环条件，让
l=l+1=4。 a[4]=7>k，退出循环。见 图 7
4 2 3 1 7 3 6
0 1 2 3 4 5 6
l r
图 7
5 k
31
? 执行（ 4） a[r]=a[l],a[5]=7。见 图 8
这时仍然 l<r，应继续执行直到型循环的循环体。
4 2 3 1 7 7 6
0 1 2 3 4 5 6
l r
图 8
5 k
32
? 执行（ 1）,a[r]=7>k，让 r=r-1=4。见 图 9
4 2 3 1 7 7 6
0 1 2 3 4 5 6
l r
图 9
5 k
33
? 之后,l=r，退出直到型循环，做 a[l]=k,l=4，
a[4]=5，这是 5的最终位置,5将整个数据分成左右两
个集合，见 图 10。
4 2 3 1 5 7 6
0 1 2 3 4 5 6
l r
图 10
左 右
5 k
34
用上述思路去排左边的部分
从 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
1 2 3 1
0 1 2 3
l r
图 12
4 2 3 1
0 1 2 3
l r
图 11
4 k
35
? 执行（ 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，左边也排好了。
1 2 3 4
0 1 2 3
图 14
1 2 3 1
0 1 2 3
l r
图 13
l r
4 k 4 k
36
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
图 16
7 6
5 6
l r
图 15
6 6
5 6
l r
7 k
37
这时 l=r，不再执行（ 3）（ 4），退出直到型循环后，
做 a[l]=k，见图 17。
图 17
6 7
5 6
l r
7 k
38
在有了递归调用函数之后，主程序很容易写，主程序中应
包含
1,定义整型变量：数组 a[10],i；
2,用循环结构输入待排序的数，将其放入 a数组；
3,调用 sort函数，使用三个实际参数
a——将数组 a当实参；
0——数组下标下界；
9——数组下标上界；
4,输出排序结果
下面给出参考程序（分两页）
39
#include <stdio.h> //预编译命令
void sort(int array[ ],int ll,int rr) //被调用函数，数组 array,ll,rr为形参
{ //函数体开始
int l,r,i,k; //定义变量
if(ll<rr) //如果 ll<rr,则做下列 7件事,
{ //7件事开始
l=ll;r=rr;k=array[l]; //第 1件事
do { //第 2件事 (开始 )
while((l<r)&&(array[r]>=k))r=r-1; //2.1,右边的元素 >=k,让 r往中间移
if(l<r) //2.2,右边的元素 <k,让
{
array[l]=array[r]; //array[r]送给 array[l],
l=l+1; //同时让 l往中间移
}
while((l<r)&&(array[l]<=k))l=l+1; //2.3,左边的元素 <=k,让 l往中间移
if (l<r) array[r]=array[l]; //2.4,左边的元素 >k,让 array[l]
//送给 array[r]
} //
while(l!=r); //第 2件事 (结束 )
array[l]=k; //第 3件事,k已排到位
for(i=ll;i<=rr;i=i+1) //第 4件事，输出
{ printf("a[%d]=%d;",i,array[i]);} //
printf("\n"); //第 5件事，换行
sort(array,ll,l-1); //第 6件事，排左边部分
sort(array,l+1,rr); //第 7件事，排右边部分
} //7件事结束
} //函数体结束
40
void main() //主函数开始
{
int a[10],i; //整型变量
printf("请输入 10个整数 \n" ); //提示信息
for (i=0;i<10;i=i+1) //输入 10个整数
scanf("%d",&a[i]); //
sort(a,0,9); //调用 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五个人，每个人阅读兴趣用
一个二维数组加以描述,
? 10[ ] [ ] ijijl i k e i j ? 喜欢书不喜欢书
43
希望你写一个程序，输出所有分书方案，让人人皆
大欢喜。假定 5个人对 5本书的阅读兴趣如下表,
0 1 2 3 4
A
B
C
D
E
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
人
书
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};
解题思路,
45
3、画出思路图
定义 try(i)——试着给第 i人分书 (i=0,1,…,4)
try(i )
Lp Lp Lp Lp Lp
j = 0 1 2 3 4
46
条件C=(like[i][j]>0)&&(book[j]==0)
Lp
什么也不做
sh3
c==1
c!= 1
n=n+ 1;
输出方案n;
take[i ]=- 1;
book[j]= 0;
take[i ]=j ;
book[j]= 1;
sh1
i==4 i!=4
try(i+1);
sh2
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[i]=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个方案之后，去寻找下一个分书方案所必需的。
（ 6）在有了上述的与或图之后，我们很容易写出一个程
序框图。先看被调用函数 try(i)的框图。
49
void tr y (i nt i)
for ( j =0 ; j <= 4; j =j+ 1)
(l ik e[i][ j]> 0)&& (b o ok [j]= =0 )
T F
T F
ta k e[i]= j; { 将书 j 给 i} s h1
boo k [j]= 1; {j 书已分 }
i = =4 s h 2
n=n+ 1;
输出方案 n;
t ry( i+ 1);
{ 试分下一 人 }
tak e[i]= - 1; {i 将书退回 } s h3
boo k [j]= 0; { 书 j 待选 }
什么也
不做
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
void try(int i) //被调用函数，数组 array,ll,rr为形参
{ //函数体开始
int j,k; //定义变量
for(j=0;j<=4;j=j+1) //循环,j代表书号
{ //循环体开始
if((like[i][j]>0)&&(book[j]==0)) //如果满足分书条件作下列事
{
take[i]=j; //把 j号书给 i
book[j]=1; //记录 j书已分
if(i==4) //如果 i==4,输出分书方案
{
n=n+1; //让方案数加 1
printf("第 %d个方案 \n",n); //输出分书方案号
for(k=0;k<=4;k=k+1)
{
printf("%d号书分给 %c;\n",take[k],k+65);
//输出分书方案
}
printf("\n"); //换行
}
else //如果 i!=4,继续给下一人分书
{
try(i+1); //递归调用 try(i+1)
}
take[i]=-1; //让 i把书退还
book[j]=0; //记录 j书待分
}//
}//
}
52
void main() //主函数
{ //主函数开始
n=0; //分书方案号预置 0
try(0); //调用 try函数,实参为 1
} //主函数结束
53
结 束
?青蛙过河
?快速排序
?分书问题
?习题讨论
第七讲 递归算法举例
n
mC
2
?
1
11
1,
,1
2
5;
1
2
3
n
m
n n n
m m m
n m n
m m n
C m n
C C C
C
C
?
??
?
?
??
?
习题：
已知 表示从 个元素中取 个的组合数，又知
、试画出符合上述关系的与或结合图；
、指出哪个是直接可解结点；
、画出 求解结点图；
4,写出递归程序求解组合问题。
3
递 归 算 法 举 例
——青蛙过河
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
3,先看简单情况，河中无柱子,S=0,
Jump(0,y)
当 y=1时,Jump(0,1)=2；
说明：河中有一片荷叶，可以过两只青蛙，起始时 L上有两
只青蛙,1#在 2#上面。
第一步,1# 跳到荷叶上；
第二步,2# 从 L直接跳至 R上；
第三步,1# 再从荷叶跳至 R上。
如下图,
2#
1#
2
1
3
L
左岸
R
右岸
7
当 y=2时,
Jump(0,2)=3；
说明：河中有两片荷叶时，可以过 3只青蛙。起始时,
1#,2#,3# 3只青蛙落在 L上,
第一步,1# 从 L跳至叶 1上,
第二步,2# 从 L跳至叶 2上,
第三步,3# 从 L直接跳至 R上,
第四步,2# 从叶 2跳至 R上,
第五步,1# 从叶 1跳至 R上,
叶1
3
1
5
L
R
叶2
2
4
采用归纳法,Jump(0,y)=y+1；
意思是：在河中没有石柱的情
况下，过河的青蛙数仅取决于荷
叶数，数目是荷叶数 +1。
8
再看 Jump(S,y)
先看一个最简单情况,S=1,y=1。
从图上看出需要 9步，跳过 4只青蛙。
1# 青蛙从 L － > Y；
2# 青蛙从 L － > S；
1# 青蛙从 Y － > S；
3# 青蛙从 L － > Y；
4# 青蛙从 L － > R；
3# 青蛙从 Y － > R；
1# 青蛙从 S － > Y；
2# 青蛙从 S － > R；
1# 青蛙从 Y － > R；
S
Y
5
4
6
L
R
1
2
3 7
8
91#
2#
4#
3#
3#
1#
2#
1#1#
9
t
L S Y R
L4 L3 L2 L1 S2 S1 R4 R3 R2 R1
0
1
2
3
4
5
6
7
8
9
4
4
4
4
4
3
3
3
3
2
2
1
2
2
2
2
2
1
1
1
1
1
3
1
1
4
4
4
4
4
3
3
3
3
2
2
1
表一
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上。
y
L R
S1 S2
12
这样 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
5,将上述分析出来的规律写成递归形式的与或结点图为,
Jum p(S,y)
y+1
S!=0S==0
Jum p(S-1,y) 2*Jump( S-1,y)
14
举例,S=3,y=4，算 Jump(3,4)
A=Jump(2,4)
2*B
2*10=20
Jump(3,4)
2*A
2*20=40
2*C
2*5=10
C=Jump(0,4)
S== 0
4+1 5
B=Jump(1,4)
3( 3,4 ) 2 ( 1 ) 2 (4 1 ) 4 0SJ u m p y? ? ? ? ?
15
#include <stdio.h> //预编译命令
int Jump(int,int); //声明有被调用函数
void main() //主函数
{ //主程序开始
int s,y,sum; //整型变量,s为河中石柱数,y为荷叶数
printf("请输入石柱数 s=" ); //提示信息
scanf("%d",&s); //输入正整数 s
printf("请输入荷叶数 y=" ); //提示信息
scanf("%d",&y); //输入正整数 y
sum=Jump(s,y); //Jump(s,y)为被调用函数
printf(“Jump(%d,%d)=%d \n",s,y,sum); //输出结果
} //主程序结束
//以下函数是被主程序调用的函数
int Jump(int r,int z) //整型自定义函数,r,z为形参
{ //自定义函数体开始
int k; //整型变量
if (r==0) //如果 r为 0,则为直接可解结点,
{
k=z+1; //直接可解结点,k值为 z+1
}
else //如果不为 1,则要调用 Jump(r-1,z)
{
k=2*Jump(r-1,z); //计算 Jump(r-1,z)再乘以 2赋给 k
}
return(k); //将 k的值返回给 Jump(s,y)
} //自定义函数体结束
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
我们画出与或图来阐述快速排序的思路,
l>=r
A so r t(l,r )
数据在a [ l ],.,,,a [ r ] 中
B
什么也不做
C
l< r
D
分区处理
F
so r t(m + 1,r )
E
so r t(l,m -1 )
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
1、先解 D结点,D结点是一个直接可解结点，功能是
进行所谓的分区处理，规定这一步要做的事情是
? （ 1）将 a[l]中的元素放到它应该在的位置上，比
如 m位置。这时 a[m]?a[l]；
? （ 2）让下标从 l到 m-1的数组元素小于等于 a[m]；
? （ 3）让下标从 m+1到 r的数组元素大于 a[m]；
比如 a数组中 a[l]=5，经分组处理后,5送至 a[4]。 5
到位后，其左边 a[0]～ a[3]的值都小于 5；其右边
a[5]a[6]大于 5。
（见下图）
21
5 2 6 1 7 3 4 a
0 1 2 3 4 5 6
l r
4 2 3 1 5 7 6 a
0 1 2 3 4 5 6
m
下标,
下标,
l m-1 r m+1
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
ll <r r
l = l l; r =r r ; k =ar r a y [l ];
T F
do
w hi l e( (l <r)& & (a rra y [r] >= k )) (1)
r = r - 1;
l<r (2) T F
a r r a y [l ]=a r r a y [r];
l=l+1
w h i le (( l<r )&&( a r r a y [ l ]<=k )) (3 )
l = l + 1;
l<r ; (4) T F
a r r a y [r]=ar r a y [ l] ;
w h i le ( l !=r );
a r r a y [l ]=k ;
f or (i =ll ; i<=r r ; i=i+1 )
输出 a r r a y [i ];
换行 ;
so r t( a r r a y,ll,l - 1 );
so r t( a r r a y,l+1,r r ) ;
24
下面举例说明排序过程
图 1 a数组中有 7个元素待排序
1 让 k=a[l]=a[0]=5
5 2 6 1 7 3 4
0 1 2 3 4 5 6
l r
图 1
5 k
25
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
4 2 6 1 7 3 4
0 1 2 3 4 5 6
l r
图 2
5 k
26
? 执行（ 3）图 2中的 a[1]<k，满足当循环条件,l=l+1=2，
l增 1后的情况如 图 3。图 3的情况不再满足当循环条件。
4 2 6 1 7 3 4
0 1 2 3 4 5 6
l r
图 3
5 k
27
? 执行（ 4） a[r]=a[l]，即 a[6]=a[2]=6，见 图 4。这时
l!=r还得执行直到型循环的循环体。
4 2 6 1 7 3 6
0 1 2 3 4 5 6
l r
图 4
5 k
28
? 执行（ 1） a[r]=a[6]=6,6>k满足当循环的条件,
r=r-1=6-1=5
见 图 5，之后退出当循环，因为 a[r]=3<k
4 2 6 1 7 3 6
0 1 2 3 4 5 6
l r
图 5
5 k
29
? 执行（ 2） a[l]=a[r]，并让 l=l+1=3，见 图 6
4 2 3 1 7 3 6
0 1 2 3 4 5 6
l r
图 6
5 k
30
? 执行（ 3）由于 a[3]=1<k，满足当循环条件，让
l=l+1=4。 a[4]=7>k，退出循环。见 图 7
4 2 3 1 7 3 6
0 1 2 3 4 5 6
l r
图 7
5 k
31
? 执行（ 4） a[r]=a[l],a[5]=7。见 图 8
这时仍然 l<r，应继续执行直到型循环的循环体。
4 2 3 1 7 7 6
0 1 2 3 4 5 6
l r
图 8
5 k
32
? 执行（ 1）,a[r]=7>k，让 r=r-1=4。见 图 9
4 2 3 1 7 7 6
0 1 2 3 4 5 6
l r
图 9
5 k
33
? 之后,l=r，退出直到型循环，做 a[l]=k,l=4，
a[4]=5，这是 5的最终位置,5将整个数据分成左右两
个集合，见 图 10。
4 2 3 1 5 7 6
0 1 2 3 4 5 6
l r
图 10
左 右
5 k
34
用上述思路去排左边的部分
从 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
1 2 3 1
0 1 2 3
l r
图 12
4 2 3 1
0 1 2 3
l r
图 11
4 k
35
? 执行（ 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，左边也排好了。
1 2 3 4
0 1 2 3
图 14
1 2 3 1
0 1 2 3
l r
图 13
l r
4 k 4 k
36
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
图 16
7 6
5 6
l r
图 15
6 6
5 6
l r
7 k
37
这时 l=r，不再执行（ 3）（ 4），退出直到型循环后，
做 a[l]=k，见图 17。
图 17
6 7
5 6
l r
7 k
38
在有了递归调用函数之后，主程序很容易写，主程序中应
包含
1,定义整型变量：数组 a[10],i；
2,用循环结构输入待排序的数，将其放入 a数组；
3,调用 sort函数，使用三个实际参数
a——将数组 a当实参；
0——数组下标下界；
9——数组下标上界；
4,输出排序结果
下面给出参考程序（分两页）
39
#include <stdio.h> //预编译命令
void sort(int array[ ],int ll,int rr) //被调用函数，数组 array,ll,rr为形参
{ //函数体开始
int l,r,i,k; //定义变量
if(ll<rr) //如果 ll<rr,则做下列 7件事,
{ //7件事开始
l=ll;r=rr;k=array[l]; //第 1件事
do { //第 2件事 (开始 )
while((l<r)&&(array[r]>=k))r=r-1; //2.1,右边的元素 >=k,让 r往中间移
if(l<r) //2.2,右边的元素 <k,让
{
array[l]=array[r]; //array[r]送给 array[l],
l=l+1; //同时让 l往中间移
}
while((l<r)&&(array[l]<=k))l=l+1; //2.3,左边的元素 <=k,让 l往中间移
if (l<r) array[r]=array[l]; //2.4,左边的元素 >k,让 array[l]
//送给 array[r]
} //
while(l!=r); //第 2件事 (结束 )
array[l]=k; //第 3件事,k已排到位
for(i=ll;i<=rr;i=i+1) //第 4件事，输出
{ printf("a[%d]=%d;",i,array[i]);} //
printf("\n"); //第 5件事，换行
sort(array,ll,l-1); //第 6件事，排左边部分
sort(array,l+1,rr); //第 7件事，排右边部分
} //7件事结束
} //函数体结束
40
void main() //主函数开始
{
int a[10],i; //整型变量
printf("请输入 10个整数 \n" ); //提示信息
for (i=0;i<10;i=i+1) //输入 10个整数
scanf("%d",&a[i]); //
sort(a,0,9); //调用 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五个人，每个人阅读兴趣用
一个二维数组加以描述,
? 10[ ] [ ] ijijl i k e i j ? 喜欢书不喜欢书
43
希望你写一个程序，输出所有分书方案，让人人皆
大欢喜。假定 5个人对 5本书的阅读兴趣如下表,
0 1 2 3 4
A
B
C
D
E
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
人
书
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};
解题思路,
45
3、画出思路图
定义 try(i)——试着给第 i人分书 (i=0,1,…,4)
try(i )
Lp Lp Lp Lp Lp
j = 0 1 2 3 4
46
条件C=(like[i][j]>0)&&(book[j]==0)
Lp
什么也不做
sh3
c==1
c!= 1
n=n+ 1;
输出方案n;
take[i ]=- 1;
book[j]= 0;
take[i ]=j ;
book[j]= 1;
sh1
i==4 i!=4
try(i+1);
sh2
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[i]=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个方案之后，去寻找下一个分书方案所必需的。
（ 6）在有了上述的与或图之后，我们很容易写出一个程
序框图。先看被调用函数 try(i)的框图。
49
void tr y (i nt i)
for ( j =0 ; j <= 4; j =j+ 1)
(l ik e[i][ j]> 0)&& (b o ok [j]= =0 )
T F
T F
ta k e[i]= j; { 将书 j 给 i} s h1
boo k [j]= 1; {j 书已分 }
i = =4 s h 2
n=n+ 1;
输出方案 n;
t ry( i+ 1);
{ 试分下一 人 }
tak e[i]= - 1; {i 将书退回 } s h3
boo k [j]= 0; { 书 j 待选 }
什么也
不做
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
void try(int i) //被调用函数，数组 array,ll,rr为形参
{ //函数体开始
int j,k; //定义变量
for(j=0;j<=4;j=j+1) //循环,j代表书号
{ //循环体开始
if((like[i][j]>0)&&(book[j]==0)) //如果满足分书条件作下列事
{
take[i]=j; //把 j号书给 i
book[j]=1; //记录 j书已分
if(i==4) //如果 i==4,输出分书方案
{
n=n+1; //让方案数加 1
printf("第 %d个方案 \n",n); //输出分书方案号
for(k=0;k<=4;k=k+1)
{
printf("%d号书分给 %c;\n",take[k],k+65);
//输出分书方案
}
printf("\n"); //换行
}
else //如果 i!=4,继续给下一人分书
{
try(i+1); //递归调用 try(i+1)
}
take[i]=-1; //让 i把书退还
book[j]=0; //记录 j书待分
}//
}//
}
52
void main() //主函数
{ //主函数开始
n=0; //分书方案号预置 0
try(0); //调用 try函数,实参为 1
} //主函数结束
53
结 束
