第1讲-递推与迭代课件

主要内容递推概述递推数列应用递推求解应用题递推与递归比较迭代及其应用

1VisualFoxPro

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)*/2VisualFoxPro（2）简单逆推算法

逆推即从后往前推,从已得的规模为n，n-1，…，i+1的一系列解，推出问题规模为i的解，直至得到规模为1的解。简单逆推算法框架描述：f(n—i+1)=<初始值>；/*确定初始值*/for(k=i;k>=1;k--)

f(k)=<递推关系式>；/*实施递推*/printf(f(1))；/*输出解f(1)*/3VisualFoxPro设递推的二维数组为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)*/（3）二维数组顺推算法4VisualFoxPro

当递推关系包含两个或两个以上关系式时，通常应用多关系分级递推算法求解。（4）多关系分级递推算法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)*/5VisualFoxPro1.2递推数列(1)递推算法设计设置k循环（k=1,2,…，n，其中n为输入整数），在k循环外赋初值：a=2;b=3;s=0;在k循环中比较赋值：当a<b时，由赋值f[k]=a确定为序列的第k项；然后a=a*2，即a按递推规律乘2,为后一轮比较作准备；当a>b时，由赋值f[k]=b确定为序列的第k项；然后b=b*3，即b按递推规律乘3,为后一轮比较作准备。1.2.1幂序列6VisualFoxPro递推过程描述：a=2;b=3;*为递推变量a,b赋初值*/for(k=1;k<=n;k++){if(a<b){f[k]=a;a=a*2;}/*用a给f[k]赋值*/else{f[k]=b;b=b*3;}/*用b给f[k]赋值*/}在这一算法中，变量a,b是变化的，分别代表2的幂与3的幂。7VisualFoxPro1.2.2双关系递推数列(1)算法设计要点设n个数在数组m中，2x+1与3x+1均作为一个队列，从两队列中选一排头(数值较小者)送入数组m中。所谓“排头”就是队列中尚未选入m的最小的数（下标）。这里用p2表示2x+1这一列的排头的下标，用p3表示3x+1这一列的排头的下标。8VisualFoxProif(2*m(p2)<3*m(p3)){m(i)=2*m(p2)+1;p2++;}if(2*m(p2)>3*m(p3)){m(i)=3*m(p3)+1;p3++;}特别注意：两队列若出现相等时，给m数组赋值后，两排头都要增1。if(2*m(p2)==3*m(p3)){m(i)=2*m(p2)+1;p2++;p3++;/*为避免重复项，P2，p3均须增1*/}

9VisualFoxPro1.3.1猴子爬山问题【例1.4】一个顽猴在一座有30级台阶的小山上爬山跳跃，猴子上山一步可跳1级，或跳3级，试求上山的30级台阶有多少种不同的爬法。1.递推算法设计一般地有递推关系：

f(k)=f(k-1)+f(k-3)（k>3）初始条件有:f(1)=1；即1=1。

f(2)=1；即2=1+1。

f(3)=2；即3=1+1+1；3=3。1.3应用递推求解应用题10VisualFoxPro

intk,n;longf[1000];printf("请输入台阶总数n:");scanf("%d",&n);f[1]=1;f[2]=1;f[3]=2;/*数组元素赋初值*/for(k=4;k<=n;k++)f[k]=f[k-1]+f[k-3];/*按递推关系实施递推*/printf("s=%ld",f[n]);2.算法描述:

11VisualFoxPro3.问题引申把问题引申为爬山n级，一步有m种跨法，一步跨多少级均从键盘输入。(1）分级递推算法设计设爬山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）完成递推。12VisualFoxPro

(2)探讨f(t)的递推关系当t<x(1)时，f(t)=0；f(x(1))=1。（初始条件）当x(1)<t≤x(2)时，第1级递推：f(t)=f(t-x(1))；当x(2)<t≤x(3)时，第2级递推：f(t)=f(t-x(1))+f(t-x(2))；……一般地，当x(k)<t≤x(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))13VisualFoxPro(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))在递推设计中我们可把台阶数n记为数组元素x(m+1),这样处理是巧妙的,可以按相同的递推规律递推计算，简化算法设计。最后一项f(x(m+1))即为所求f(n)。

14VisualFoxProfor(i=1;i<=x[1]-1;i++)f[i]=0;x[m+1]=n;f[x[1]]=1;for(k=1;k<=m;k++)for(t=x[k]+1;t<=x[k+1];t++){f[t]=0;for(j=1;j<=k;j++)/*按公式分级*/f[t]=f[t]+f[t-x[j]];if(t==x[k+1])/*t=x(k+1)时增1*/f[t]=f[t]+1;}printf("%ld.\n",f[n]-1);(4)算法描述15VisualFoxPro1.3.2整数划分问题【例1.5】正整数s（简称为和数）的划分(又称分划或拆分)是把s分成为若干个正整数（简称为零数或部分）之和,划分式中允许零数重复,且不记零数的次序。试求s共有多个不同的划分式？展示出s的所有这些划分式。1.探索划分的递推关系为了建立递推关系，先对和数k较小时的划分式作观察：k=2：1+1；2k=3：1+1+1；1+2；3k=4：1+1+1+1；1+1+2；1+3；2+2；4k=5：1+1+1+1+1；1+1+1+2；1+1+3；1+2+2；1+4；2+3；516VisualFoxPro由以上各划分看到，除和数本身k=k这一特殊划分式外，其它每一个划分式至少为两项之和。约定在所有划分式中零数作不减排列，探索和数k的划分式与和数k-1的划分式存在以下递推关系:(1)在所有和数k-1的划分式前加零数1都是和数k的划分式。(2)和数k-1的划分式的前两个零数作比较,如果第1个零数x1小于第2个零数x2，则把第1个零数加1后成为和数k的划分式。17VisualFoxPro显然递推的初始条件为：

a(2,1,1)=1，a(2,1,2)=1;a(2,2,1)=2。根据递推关系，实施递推：(1)实施在k-1所有划分式前加1操作

a(k,j,1)=1;for(t=2;t<=k;t++)a(k,j,t)=a(k-1,j,t-1); /*k-1的第t-1项变为k的第t项*/(2)若k-1划分式第1项小于第2项，第1项加1，变为k的第i个划分式

if(a(k-1,j,1)<a(k-1,j,2){a(k,i,1)=a(k-1,j,1)+1;for(t=2;t<=k-1;t++)a(k,i,t)=a(k-1,j,t);}2.算法描述18VisualFoxPro3.整数划分递推设计的优化考察以上应用三维数组a(k,j,i)完成递推过程，当由k-1的划分式推出k的划分式时，k-1以前的数组单元已完全闲置。为此可考虑把三维数组a(k,j,i)改进为二维数组a(j,i)。二维数组a(j,i)表示和数是k-1的已有划分式，根据递推关系推出k的划分式：(1）把a(j,i）依次存储到a(j,i+1),加上第一项a(j,1)=1；这样完成在k-1的所有划分式前加1的操作，转化为k的划分式。for(t=i;t>=1;t--)a(j,t+1)=a(j,t);a(j,1)=1;19VisualFoxPro(2)对已转化的u个划分式逐个检验，若其第2个数小于第3个数（相当于k-1时的第1个数小于第2个数），则把第2个数加1，去除第一个数后，作为k时增加的一个划分式，为第t(t从u开始，每增加一个划分式，t增1)划分式。for(t=u,j=1;j<=u;j++)if(a(j,2)<a(j,3))/*若k-1式第1项小于第2项*/{t++;a(t,1)=a(j,2)+1;/*第1项加1作为k的第t个划分式的第1项*/i=3;while(a(j,i)>0){a(t,i-1)=a(j,i);i++;}}

20VisualFoxPro1.4递推与递归比较递归其实就是利用系统堆栈,实现函数自身调用,或者是相互调用的过程。在通往边界的过程中,都会把单步地址保存下来，再按照先进后出进行运算。递归的数据传送也类似。递归的运算方法,决定了它的效率较低，因为数据要不断的进栈出栈。在应用递归时，只要输入的n值稍大，程序求解就比较困难。因而从计算效率来说，递推往往要高于递归。递推免除了数据进出栈的过程，也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发，逐步推出函数值,直观明了。在有些情况下，递归可以转化为效率较高的递推。但是递归作为重要的基础算法,它的作用不可替代，在把握这两种算法的时候应该特别注意。21VisualFoxPro【例1.6】求整数s的划分数解：设n的“最大零数不超过m”的划分式个数为q(n,m)。①建立递推关系所有q(n,m)个划分式分为两类：零数中不包含m的划分式有q(n,m-1)个；零数中包含m的划分式有q(n-m,m)个。有

q(n,m)=q(n,m-1)+q(n-m,m)(1≤m<n≤s)其中q(n-m,m)=q(n-m,n-m)