《计算机常用算法与程序设计教程第4章递推》由会员分享，可在线阅读，更多相关《计算机常用算法与程序设计教程第4章递推（40页珍藏版）》请在金锄头文库上搜索。
1、常用算法与程序设计,1,第 4 章,递 推,常用算法与程序设计,2,主要内容,4.1 递推概述 4.2 递推数列 4.3 递推数阵 4.4 应用递推求解应用题 4.5 递推与递归比较,常用算法与程序设计,3,4.1 递推概述,4.1.1 递推算法 递推是一种高效的数学模型，是组合数学中的一个重要解题方法。 递推是利用问题本身所具有的一种递推关系求解问题的一种方法。 递推算法的首要问题是得到相邻的数据项之间的关系，即递推关系。,常用算法与程序设计,4,1. 实施递推的步骤(1) 确定递推变量(2) 建立递推关系(3) 确定初始（边界）条件(4) 对递推过程进行控制,4.1.2 递推实施步骤与描述
2、,常用算法与程序设计,5,2. 递推算法框架描述,（1） 简单顺推算法顺推即从前往后推,从已求得的规模为1，2， ，i-1的一系列解，推出问题规模为 i的解，直至得到规模为n的解。简单顺推算法框架描述： f(1i-1)=； /* 确定初始值 */ for(k=i;k； /* 施递推 */ printf(f(n)； /* 输出n规模的解f(n) */,常用算法与程序设计,6,（2） 简单逆推算法逆推即从后往前推,从已得的规模为n，n-1， ，i+1的一系列解，推出问题规模为 i的解，直至得到规模为1的解。简单逆推算法框架描述： f(ni+1)=； /* 确定初始值 */ for(k=i;k=1;
3、k-)f(k)=；/* 实施递推 */ printf(f(1)； /* 输出解f(1) */,常用算法与程序设计,7,（3） 计算处理顺推算法 f(1)=a;f(2)=b; /* 用a,b赋初值 */ for(i=3;i f(i)=; /* 递推得f(i) */ printf(f(n)； /* 输出解f(n) */,常用算法与程序设计,8,（4） 状态不确定的顺推算法f(1)=a;f(2)=b;k=2; /* 用a,b赋初值 */ for(i=2;i k+; f(k)=; /* 递推得f(k) */ printf(f(k)； /* 输出解f(k) */,常用算法与程序设计,9,设递推的二维数组
4、为f(k,j)，1kn,1jm。 二维数组顺推算法框架描述： f(1,1m)=； /* 赋初始值 */ for(k=2;k； /* 实施递推 */ printf(f(n,m)； /* 输出解f(n,m) */,（5） 二维数组顺推算法,常用算法与程序设计,10,当递推关系包含两个或两个以上关系式时，通常应用多关系分级递推算法求解。 （6） 多关系分级递推算法f(1i-1)=； /* 赋初始值 */ for(k=i;k)f(k)=； /* 据递推关系1递推 */ if()f(k)=； /* 据递推关系2递推 */if()f(k)=； /* 据递推关系m递推 */ printf(f(n)； /*
5、输出解f(n) */,常用算法与程序设计,11,4.2 递推数列,常用算法与程序设计,12,递推算法设计:注意到F数列与L数列的递推关系相同，可一并处理这两个数列。设置一维数组f(n),数列的递推关系为f(k)=f(k-1)+f(k-2) (k2) 注意到F与L两个数列初始值不同，在输入整数p选择数列(p=1时为F数列，p=2时为L数列)后，初始条件可统一为f(1)=1，f(2)=2*p-1,常用算法与程序设计,13,scanf(“%d“,常用算法与程序设计,14,4.2.2 分数数列,【例4.1】 老师写出一个递推分数数列的前6项: 1/2, 3/5, 4/7, 6/10, 8/13, 9/
6、15, .,引导学生注意观察数列的构成规律：第i项的分母d与分子c存在以下关系:d=c+i，而分子c为与前i-1项中的所有分子、分母均不相同的最小正整数。 试求出该数列的第2008项,并求出前2008项中的最大项。 1. 算法设计注意到递推需用到前面的所有项,设置数组c(i)表第i项的分子,d(i)表第i项的分母(均表现为整数)。 初始条件：c(1)=1,d(1)=2；c(2)=3，d(2)=5。 递推关系：d(i)=c(i)+i; c(i)为与前i-1项中的所有分子、分母均不相同的最小正整数。,常用算法与程序设计,15,递推过程描述： c(1)=1;d(1)=2; c(2)=3;d(2)=5
7、; /* 数组元素赋初值 */ for(i=3;i=n;i+) for(k=c(i-1)+1;kd(i-1);k+)t=0; /* k穷举探求第i项分子c */for(j=1;j=i-1;j+)if(k=d(j) /* 若k与d(j)相同则返回 */t=1;break;if(t=0) c(i)=k;d(i)=k+i; /* 给c(i),d(i)赋值 */break;,常用算法与程序设计,16,(1) 递推算法设计 设置k循环（k=1,2,，n，其中n为输入整数），在k循环外赋初值：a=2;b=3;s=0;在k循环中比较赋值： 当ab时，由赋值fk=b确定为序列的第k项；然后b=b*3，即b按递
8、推规律乘3, 为后一轮比较作准备。,4.2.3 幂序列,常用算法与程序设计,17,递推过程描述：a=2;b=3; * 为递推变量a,b赋初值 */ for(k=1;k=n;k+)if(a3） 初始条件有: f(1)=1； 即1=1。f(2)=1； 即2=1+1。f(3)=2； 即3=1+1+1；3=3。,4.4 应用递推求解应用题,常用算法与程序设计,24,int k,n; long f1000;printf(“请输入台阶总数n:“);scanf(“%d“,2. 算法描述:,常用算法与程序设计,25,3. 问题引申 把问题引申为爬山n级，一步有m 种跨法，一步跨多少级均从键盘输入。(1） 分级
9、递推算法设计 设爬山t台阶级的不同爬法为f(t),设从键盘输入一步跨多少级的m个整数分别为x(1), x(2), , x(m)(约定x(1)x(2)x(m)n)。 这里的整数x(1), x(2), , x(m)为键盘输入，事前并不知道，因此不能在设计时简单地确定f(x(1),f(x(2),。 事实上，可以把初始条件放在分级递推中求取，应用多关系分级递推算法（6）完成递推。,常用算法与程序设计,26,(2) 探讨f(t)的递推关系当tx(1)时，f(t)=0；f(x(1)=1。（初始条件） 当x(1)tx(2)时，第1级递推：f(t)=f(t-x(1)； 当x(2)tx(3)时，第2级递推：f(
10、t)=f(t-x(1)+f(t-x(2)； 一般地，当x(k)tx(k+1),k=1,2,m-1,有第k级递推：f(t)=f(t-x(1)+f(t-x(2)+f(t-x(k) 当x(m)t时，第m级递推：f(t)=f(t-x(1)+f(t-x(2)+f(t-x(m),常用算法与程序设计,27,(3) 注意 当t=x(2),或t=x(3),或t=x(m)时, 按上递推求f(t)外,还要加上1。道理很简单，因为此时t本身即为一个一步到位的爬法。因而f(t)=f(t)+1（t= x(2), x(3),x(m)） 我们所求的目标为：f(n)=f(n-x(1)+f(n-x(2)+f(n-x(m) 在递推
11、设计中我们可把台阶数n记为数组元素x(m+1),这样处理是巧妙的,可以按相同的递推规律递推计算，简化算法设计。最后一项f(x(m+1)即为所求f(n)。,常用算法与程序设计,28,for(i=1;i=x1-1;i+) fi=0; xm+1=n;fx1=1; for(k=1;k=m;k+) for(t=xk+1;t=xk+1;t+) ft=0;for(j=1;j=k;j+) /* 按公式分级 */ft=ft+ft-xj;if(t=xk+1) /* t=x(k+1)时增1 */ft=ft+1; printf( “%ld. n“,fn-1);,(4) 算法描述,常用算法与程序设计,29,4.4.2
12、整币兑零问题,【例4.7】 把一张n分整币兑换成m种零币x(1), x(2), x(m)（单位分），求不同的兑换种数。1. 算法设计 因为零币的种数较多时,应用穷举显然不能胜任,考虑应用递推求解。 应用递推求解的关键在于寻求递推关系。 整币为n个单位,m种指定零币从键盘输入分别为x(1), x(2), x(m)(约定x(1)x(2)x(m)n)个单位。,常用算法与程序设计,30,记a(j,i)为整币是i,最大零币是x(j)的化零种数。当兑去一个x(j)后,整体数变为p=i-x(j),最大零币可为x(1),x(2),x(j)(因可重复),于是得到以下递推关系:a(j,i)=a(1,p)+a(2,p)+a(j,p) (其中p=i-x(j) 可据整币i能否被x(1)整除确定初始条件:a(1,i)=1 (当i能被x(1)整除时)a(1,i)=0 (当i不能被x(1)整除时) 按以上递推分别计算得a(1,n),a(2,n),.,a(m,n),求和即得所求的整币兑零种数为: n(x(1),x(2),.,x(m)=a(1,n)+a(2,n)+.+a(m,n),
