第
5
章递推法
5.算法设计思想
1
递推法是利用所求解问题本身具有的性质(递推关系)来求问题解的
有效方法。
n
之前的一步(1) n-n
具体做法是根据该问题
N
=n-或多步(1,2,
n-3,…) 的结果推导出
n
时的解:f(=F(n-1),n-2),…)(
n)f(f(称
为递推关系式); 而
N
0,…的初值f(f(…往往是直接给出或直
观得出的。
=1,0),1),
递推算法的关键问题是得到相邻的数据项之间的关系,即递推关系。
递推关系是一种高效的数学模型,是递推应用的核心。递推关系不仅在各
数学分支中发挥着重要的作用,而且由它体现出来的递推思想在各学科领
域中更是显示了独特的魅力。
在求解具体问题时,
N
=
n
的解到底与其前面的几步结果相关必须明
确。假设是两步,那么在计算的过程中只需记住这前两步的结果R1、R2,
下一步的结果
R
可以由这前两步的结果推导得到,即有R=F(R1,R2),
接下来进行递推:R1=R2,R2=R,向后传递,为求下一步的结果做好准
备。这也正是递推法名字的由来。若问题与前三步相关,则在计算的过程
中需要记住前三步的结果R1、R2、R3,下一步的结果
R
可由这前三步的结
果推导得到,即有R=F(R1,R2,R3), 接下来进行递推:R1=R2,R2=
R3,R3=R,向后传递。
递推法的一般步骤如下。
数组
(
。
1)确定递推变量。递推变量可以是简单变量,也可以是一维或多维
(2)建立递推关系。递推关系是递推的依据,是解决递推问题的关键。
(3)确定初始(边界)条件。根据问题最简单情形的数据确定递推变量
的初始(边界)值,这是递推的基础。
(4)控制递推过程。递推过程控制通常由循环结构实现,即递推在什
么时候进行,满足什么条件结束。
72 算法设计方法与优化（第2 版）
递推法可分为正推法和倒推法两种。其中,正推法是一种简单的递推方式,是从小规
模的问题推解出大规模问题的一种方法,也称为“正推”;倒推法则是对某些特殊问题所采
用的不同于通常习惯的一种方法,即从后向前进行推导,实现求解问题的方法。
5.2 典型例题
5.2.1 兔子繁殖问题
1.问题描述
一对兔子从出生后第三个月开始,每月生一对小兔子。小兔子长到第三个月又开始
生下一代小兔子。假若兔子只生不死,一月份抱来一对刚出生的小兔子,问一年中的每个
月各有多少对兔子。
2.问题分析
寻找问题的规律性,需要通过对现实问题的具体事例进行分析,从而抽象出其中的
规律。一
对兔子从出生后第三个月开始每月生一对小兔子,第三个月以后每月除上个月的
兔子外,还有新生的小兔子,在下面用加号后面的数字表示。则第三个月以后兔子的对数
就是前两个月兔子对数的和。过程如下:
1月2月3月4月5月6月…
1 1 1+1=2 2+1=3 3+2=5 5+3=8 …
3.算法说明
算法说明参见表5-1。
表 5-1
类 型名 称代表的含义
算法rabbit() 递推法求解兔子繁殖问题
变量a 当前月的前两个月的兔子对数
变量b 当前月的前一个月的兔子对数
变量c 当前月份的兔子对数
4.算法设计
#include "stdio.h"
void rabbit()
{
int i,c,a=1,b=1;
printf("%d,%d,",a,b);
for(i=1;i<=10;i++)
{
第5 章 递推法 73
c=a+b; /*斐波那契数列规律,第三项等于前两项之和*/
printf("%d,",c);
a=b; /*向后递推*/
b=c;
}
}v
oid main()
{
printf("一年中每个月兔子对数如下:\n");
rabbit();
}
5.运行结果
6.算法优化
1)优化说明
1 2 3 4 5 6 7 8 …
a b a=a+b b=b+a a=a+b b=b+a a=a+b b=b+a …
因此,可以归纳出用“a=a+b,b=b+a”做循环不变式,这样一来,循环其实是递推
了2步,循环次数自然减少。
2)算法说明
算法说明参见表5-1。
3)算法设计
#include "stdio.h"
void rabbit()
{
int i,a=1,b=1;
printf("%d,%d,",a,b);
for(i=1;i<=5;i++)
{
a=a+b;
b=b+a;
printf("%d,%d,",a,b);
}
}v
oid main()
{
rabbit();
}
74 算法设计方法与优化（第2 版）
5.2.2 最大公约数问题
1.问题描述
给出任意两个正整数,求它们的最大公约数。
2.问题分析
求两个数的最大公约数,最简单的方法就是用最大公约数的定义来求。
设m ,n 为两个正整数,d 取m 和n 中较小的一个,若d≠0,则判断d 是否同时整除
m ,n,如果是,则d 为最大公约数;否则,d=d-1重复上述过程,直到满足为止。因为最
后d=1时,一定会满足条件。
3.算法说明
算法说明参见表5-2。
表 5-2
类 型名 称代表的含义
算法f(intm,intn) 由定义求最大公约数
形参变量m,n 输入的两个数
变量d 保存最大公约数
4.算法设计
#include "stdio.h"
int f(int m,int n)
{
int d;
if(m<n)
d=m;
else
d=n;
while(d>0)
{
if(m%d==0 && n%d==0)
return(d);
d--;
}
}v
oid main()
{
int m,n;
printf("请输入两个正整数:");
scanf("%d%d",&m,&n);
printf("最大公约数为:%d\n",f(m,n));
}
第5 章 递推法 75
5.运行结果
6.算法优化
1)优化说明
下面应用递推法求解此问题。
在数学中,求最大公约数有一个很有名的方法叫辗转相除法,辗转相除法体现了递推
法的基本思想。
设m ,n 为两个正整数,且n 不为零,辗转相除法的过程如下。
(1)将问题转化为数学公式,即r=m %n,r 为m 除以n 的余数。
(2)若r=0,则n 即为所求的最大公约数,输出n。
(3)若r!=0,则令m =n,n=r,继续递归,再重复前面的(1)和(2)步骤。
其中第(3)步即为递推部分。
2)算法说明
算法说明参见表5-3。
表 5-3
类 型名 称代表的含义
算法f(intm,intn) 辗转相除法求最大公约数
形参变量m,n 输入的两个数
变量r 两个数相除的余数
3)算法设计
#include "stdio.h"
int f(int m,int n)
{
int r=n;
while(r!=0)
{
r=m%n; /*利用r=m%n,将余数赋给r*/
m=n;
n=r;
}
return m;
}v
oid main()
{
int m,n;
printf("Input two numbers:");
scanf("%d%d",&m,&n);
76 算法设计方法与优化（第2 版）
printf("%d\n",f(m,n));
}
5.2.3 猴子吃桃问题
1.问题描述
一只小猴子摘了若干个桃子,每天吃现有桃子的一半多一个,到第10天时只剩一个
桃子,求小猴子最初摘了多少个桃子?
2.问题分析
这道题可以用倒推法来解决。因为猴子每天吃的桃子数取决于前一天的桃子数,所
以可以用一个递推变量代替桃子数。设a 为递推变量,代表今天剩下的桃子数,那么就
可以推导出昨天剩下的桃子数,即a=(a+1)×2,这就是本题的递推关系式,找到这个关
系式,问题基本就解决了。
3.算法说明
算法说明参见表5-4。
表 5-4
类 型名 称代表的含义
算法tao() 递推法求解猴子吃桃问题
变量a 桃子数
变量i 天数
4.算法设计
#include "stdio.h"
void tao()
{
int i,a;
a=1;
for(i=9;i>=1;i--) /*利用倒推法求解*/
a=(a+1)*2;
printf("sum=%d\n",a);
}v
oid main()
{
tao();
}
5.运行结果
第5 章 递推法 77
6.算法优化
1)优化说明
这道题不但可以用倒推法解决,还可以用递归法求解。
由于猴子每天吃的桃子数取决于前一天的桃子数,因此可定义一个递归函数来求桃
子数,设tao(n)代表第n 天剩下的桃子数,则有递归关系式:
tao(n)=(tao(n +1)+1)×2 当n =1,2,3,…,9时
递归终止条件是:当n=10时,tao(n)=1。
2)算法说明
算法说明参见表5-5。
表 5-5
类 型名 称代表的含义
算法tao(intn) 求解猴子吃桃问题算法
形参变量n 天数
3)算法设计
#include "stdio.h"
int tao(int n)
{
if (n==10) return 1;
else
return (tao(n+1)+1)*2;
}v
oid main()
{
printf("sum=%d\n",tao(1));
}
5.2.4 杨辉三角形问题
1.问题描述
输出如图5-1所示的杨辉三角形(打印出10行)。
图 5-1
2.问题分析
由图5-1所示的杨辉三角形可以看出,中间的数据等于其
上一行左上、右上的数据和,第i 层有i 列需要求解i 个数据。
可以用二维数组array[][]存储杨辉三角形。
为了便于表示,可以将杨辉三角形变一下形状,即从第一
列开始放置,则可得到一个下三角矩阵,而且很有规律:第一
列都为1,主对角线都为1,从第三行起,中间(除第一个和对角
线之外)位置元素的值等于其上一行对应位置元素及其前一个元素之和,这就是从当前行
78 算法设计方法与优化（第2 版）
推导到下一行的递推关系式,由此便可求出杨辉三角形的任一行。
3.算法说明
算法说明参见表5-6。
表 5-6
类 型名 称代表的含义
算法yanghui() 递推法求解杨辉三角形问题
二维数组array 存储杨辉三角形
变量i 行
变量j 列
4.算法设计
#include "stdio.h"
void yanghui()
{
int array[10][10],i,j;
for(i=0;i<10;i++)
{
array[i][i]=array[i][0]=1;
for(j=1;j<=i;j++)
array[i+1][j]=array[i][j]+array[i][j-1];
}
for(i=0;i<10;i++)
{
for(j=0;j<=i;j++)
{
printf("%5d",array[i][j]);
printf(" ");
}
printf("\n");
}
}v
oid main()
{
yanghui();
}
5.运行结果
第5 章 递推法 79
6.算法优化
1)优化说明
前面以二维数组为存储,使用递推法求解杨辉三角形问题,那么,是否可以用一维数
组为存储来解决本问题呢? 回答当然是肯定的。
使用一维数组时注意以下两个问题:一是不能保存完整的杨辉三角形,只能求出一
行输出一行;二是在利用递推法从上一行推导下一行时,如果按照通常从前向后推导的
话,则原有已知数据将被覆盖,怎么办? 只好倒过来从后向前逐项计算,这也是一种倒
推法。下
面举例说明。设有一维数组a[],现已存储第三行数据,则有a[1]=1,a[2]=2,
a[3]=1,那么,下一行的求值顺序是:先求a[4],已知所有数组元素初值均为0,因此,
a[4]=a[3]+a[4]=1+0=1;再求a[3]=a[2]+a[3]=2+1=3;以此类推。
2)算法说明
算法说明参见表5-7。
表 5-7
类 型名 称代表的含义
算法yanghui() 递推法求解杨辉三角形问题
一维数组a 存储杨辉三角形
变量i 杨辉三角形的行数
变量j 数组下标
3)算法设计
#include "stdio.h"
void yanghui()
{
int n,i,j,a[20];
printf(" 1\n");
a[1]=a[2]=1;
printf(" %-4d %-4d\n",a[1],a[2]);
for(i=3;i<=10;i++)
{
a[1]=a[i]=1;
for(j=i-1;j>1;j--)
a[j]=a[j]+a[j-1];
for(j=1;j<=i;j++)
printf(" %-4d ",a[j]);
printf("\n");
}
}v
oid main()
{
yanghui();
}
80 算法设计方法与优化（第2 版）
5.2.5 伯努利装错信封问题
1.问题描述
某人写了n 封信,这n 封信对应有n 个信封。求把所有的信都装错了信封的情况共
有多少种?
这是组合数学中有名的错位问题。著名数学家伯努利(Bernoulli)曾最先考虑此题。
后来,欧拉对此题产生了兴趣,称此题是“组合理论的一个妙题”,独立地解出了此题。
2.问题分析
为叙述方便,把某一元素在自己相应位置(如“2”在第2个位置)称为在自然位;某一
元素不在自己相应位置称为错位。
事实上,所有全排列分为以下三类。
(1)所有元素都在自然位,实际上只有一个排列。当n=5时,即12345。
(2)所有元素都错位。当n=5时,如24513。
(3)部分元素在自然位,部分元素错位。当n=5时,如21354。
装错信封问题求解实际上是求n 个元素全排列中的“每一元素都错位”的子集。
当n=2时显然只有一个解:21(“2”不在第2个位置且“1”不在第1个位置)。
当n=3时,有231,312两个解。
通常,可在实现排列过程中加上“限制取位”的条件。
设置一维数组a[]。a[i]在1~n 中取值,出现数字相同a[j]=a[i]或元素在自然
位j=a[j]时返回(j=1,2,…,n-1)。
当i<n 时,还未取n 个数,i 增1后a[i]=1继续;
当i=n 且最后一个元素不在自然位a[n]!=n 时,输出一个错位排列,并设置变量s
统计错位排列的个数。
当a[i]<n 时,a[i]增1继续。
当a[i]=n 时,回溯或调整,直到i=1且a[1]=n 时结束。
3.算法说明
算法说明参见表5-8。
表 5-8
类 型名 称代表的含义
算法bernoulli(intn) 回溯法求解伯努利装错信封问题
形参变量n 信封个数
一维数组a 标记信和信封是否错位
变量s 统计全错位总和
4.算法设计
#include "stdio.h"
int bernoulli(int n)