资源描述：
《计算机常用算法与程序设计教程 第4章 递推》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第4章递推1常用算法与程序设计主要内容4.1递推概述4.2递推数列4.3递推数阵4.4应用递推求解应用题4.5递推与递归比较2常用算法与程序设计4.1递推概述4.1.1递推算法递推是一种高效的数学模型，是组合数学中的一个重要解题方法。递推是利用问题本身所具有的一种递推关系求解问题的一种方法。递推算法的首要问题是得到相邻的数据项之间的关系，即递推关系。3常用算法与程序设计1.实施递推的步骤(1)确定递推变量(2)建立递推关系(3)确定初始（边界）条件(4)对递推过程进行控制4.1.2递推实施步骤与描述4常用算法与程序设计2.递推算法框架描述（
2、1）简单顺推算法顺推即从前往后推,从已求得的规模为1，2，…，i-1的一系列解，推出问题规模为i的解，直至得到规模为n的解。简单顺推算法框架描述：f(1—i-1)=<初始值>；/*确定初始值*/for(k=i;k<=n;k++)f(k)=<递推关系式>；/*施递推*/printf(f(n))；/*输出n规模的解f(n)*/5常用算法与程序设计（2）简单逆推算法逆推即从后往前推,从已得的规模为n，n-1，…，i+1的一系列解，推出问题规模为i的解，直至得到规模为1的解。简单逆推算法框架描述：f(n—i+1)=<初始值>；/*确定初始值*/fo
3、r(k=i;k>=1;k--)f(k)=<递推关系式>；/*实施递推*/printf(f(1))；/*输出解f(1)*/6常用算法与程序设计（3）计算处理顺推算法f(1)=a;f(2)=b;/*用a,b赋初值*/for(i=3;i<=n;i++)for(j=1;j<=i-1;j++){<对f(1—i-1)计算处理>f(i)=<递推关系式>;/*递推得f(i)*/}printf(f(n))；/*输出解f(n)*/7常用算法与程序设计（4）状态不确定的顺推算法f(1)=a;f(2)=b;k=2;/*用a,b赋初值*/for(i=2;i<=n;i
4、++)for(j=1;j<=i-1;j++){<对f(1—i-1)计算处理>k++;f(k)=<递推关系式>;/*递推得f(k)*/}printf(f(k))；/*输出解f(k)*/8常用算法与程序设计设递推的二维数组为f(k,j)，1≤k≤n,1≤j≤m。二维数组顺推算法框架描述：f(1,1—m)=<初始值>；/*赋初始值*/for(k=2;k<=n;k++)for(j=1;j<=m;j++)f(k,j)=<递推关系式>；/*实施递推*/printf(f(n,m))；/*输出解f(n,m)*/（5）二维数组顺推算法9常用算法与程序设计当递
5、推关系包含两个或两个以上关系式时，通常应用多关系分级递推算法求解。（6）多关系分级递推算法f(1—i-1)=<初始值>；/*赋初始值*/for(k=i;k<=n;k++)if(<条件1>)f(k)=<递推关系式1>；/*据递推关系1递推*/if(<条件2>)f(k)=<递推关系式2>；/*据递推关系2递推*/……if(<条件m>)f(k)=<递推关系式m>；/*据递推关系m递推*/printf(f(n))；/*输出解f(n)*/10常用算法与程序设计4.2递推数列11常用算法与程序设计递推算法设计:注意到F数列与L数列的递推关系相同，可一并
6、处理这两个数列。设置一维数组f(n),数列的递推关系为f(k)=f(k-1)+f(k-2)(k>2)注意到F与L两个数列初始值不同，在输入整数p选择数列(p=1时为F数列，p=2时为L数列)后，初始条件可统一为f(1)=1，f(2)=2*p-112常用算法与程序设计scanf("%d",&p);/*选定数列*/scanf("%d",&n);f[1]=1;f[2]=2*p-1;s=f[1]+f[2];/*赋初值*/for(k=3;k<=n;k++){f[k]=f[k-1]+f[k-2];/*实施递推*/s+=f[k];/*实施求和*/}pri
7、ntf("第%d项为:%ld,",n,f[n]);printf("前%d项之和为:%ld",n,s);13常用算法与程序设计4.2.2分数数列【例4.1】老师写出一个递推分数数列的前6项:1/2,3/5,4/7,6/10,8/13,9/15,...,引导学生注意观察数列的构成规律：第i项的分母d与分子c存在以下关系:d=c+i，而分子c为与前i-1项中的所有分子、分母均不相同的最小正整数。试求出该数列的第2008项,并求出前2008项中的最大项。1.算法设计注意到递推需用到前面的所有项,设置数组c(i)表第i项的分子,d(i)表第i项的
8、分母(均表现为整数)。初始条件：c(1)=1,d(1)=2；c(2)=3，d(2)=5。递推关系：d(i)=c(i)+i;c(i)为与前i-1项中的所有分子、分母均不相同的最小正
