第 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(m0) { 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