第1讲-递推与迭代课件.ppt

1、1递推概述递推概述递推数列递推数列应用递推求解应用题应用递推求解应用题递推与递归比较递推与递归比较迭代及其应用迭代及其应用 2 2. 递推算法框架描述递推算法框架描述f(1i-1)=； /* 确定初始值确定初始值 */for(k=i;k=n;k+) f(k)=； /* 施递推施递推 */printf(f(n)； /* 输出输出n规模的解规模的解f(n) */3（2） 简单逆推算法简单逆推算法 逆推即从后往前推逆推即从后往前推,从已得的规模为从已得的规模为n，n-1，i+1的一系列解，推出问题规模为的一系列解，推出问题规模为 i的解，直至的解，直至得到规模为得到规模为1的解。的解。 简单逆推算法

2、框架描述：简单逆推算法框架描述：f(ni+1)=f(ni+1)= ； / /* * 确定初始值确定初始值 * */ /for(k=i;k=1;k-)for(k=i;k=1;k-) f(k)= f(k)= ；/ /* * 实施递推实施递推 * */ /printf(f(1)printf(f(1)； / /* * 输出解输出解f(1) f(1) * */ /4设递推的二维数组为设递推的二维数组为f(k,j)f(k,j)，1kn,1jm1kn,1jm。二维数组顺推算法框架描述：二维数组顺推算法框架描述：f(1,1m)=f(1,1m)= ； / /* * 赋初始值赋初始值 * */ /for(k=2;

3、k=n;k+)for(k=2;k=n;k+)for(j=1;j=m;j+)for(j=1;j=m;j+) f(k,j)= f(k,j)= ； / /* * 实施递推实施递推 * */ /printf(f(n,m)printf(f(n,m)； / /* * 输出解输出解f(n,m) f(n,m) * */ /5 当递推关系包含两个或两个以上关系式时，通常应用多关系当递推关系包含两个或两个以上关系式时，通常应用多关系分级递推算法求解。分级递推算法求解。（4 4） 多关系分级递推算法多关系分级递推算法f(1i-1)=f(1i-1)= ； / /* * 赋初始值赋初始值 * */ /for(k=i;k

4、=n;k+)for(k=i;k=n;k+) if( if()1) f(k)= f(k)=1； / /* * 据递推关系据递推关系1 1递推递推 * */ / if( if()2) f(k)= f(k)=2； / /* * 据递推关系据递推关系2 2递推递推 * */ / if( if()m) f(k)= f(k)=m； / /* * 据递推关系据递推关系m m递推递推 * */ /printf(f(n)printf(f(n)； / /* * 输出解输出解f(n) f(n) * */ /61.2 递推数列(1) (1) 递推算法设计递推算法设计设置设置k k循环（循环（k=1,2,k=1,2,，

5、n n，其中，其中n n为输入整数），在为输入整数），在k k循环外赋初值：循环外赋初值：a=2;b=3;s=0;a=2;b=3;s=0;在在k k循环中比较赋值：循环中比较赋值：当当ababab时，由赋值时，由赋值fk=bfk=b确定为序列的第确定为序列的第k k项；然后项；然后b=bb=b* *3 3，即，即b b按递按递推规律乘推规律乘3, 3, 为后一轮比较作准备。为后一轮比较作准备。1.2.1 幂序列幂序列7递推过程描述：递推过程描述：a=2;b=3; a=2;b=3; * * 为递推变量为递推变量a,ba,b赋初值赋初值 * */ /for(k=1;k=n;k+)for(k=1;k

6、=n;k+) if(ab) if(ab) fk=a;a=a fk=a;a=a* *2;/2;/* * 用用a a给给fkfk赋值赋值 * */ / else else fk=b;b=b fk=b;b=b* *3;/3;/* * 用用b b给给fkfk赋值赋值 * */ / 在这一算法中，变量在这一算法中，变量a,ba,b是变化的，分别代表是变化的，分别代表2 2的幂与的幂与3 3的幂。的幂。nn81.2.2 双关系递推数列(1) (1) 算法设计要点算法设计要点设设n n个数在数组个数在数组m m中，中，2x+12x+1与与 3x+13x+1均作为一个队列，从均作为一个队列，从两队列中选一排头

7、两队列中选一排头( (数值较小者数值较小者) )送入数组送入数组m m中。所谓中。所谓“排头排头”就是队列中尚未选入就是队列中尚未选入m m的最小的数（下标）。的最小的数（下标）。这里用这里用p2p2表示表示2x+12x+1这一列的排头的下标，用这一列的排头的下标，用p3p3表示表示3x+13x+1这一列的排头的下标。这一列的排头的下标。9if(2if(2* *m(p2)3m(p2)3m(p2)3* *m(p3)m(p3) m(i)=3 m(i)=3* *m(p3)+1;p3+;m(p3)+1;p3+;特别注意：两队列若出现相等时，给特别注意：两队列若出现相等时，给m m数组赋值数组赋值后，两

8、排头都要增后，两排头都要增1 1。if(2if(2* *m(p2)=3m(p2)=3* *m(p3)m(p3) m(i)=2 m(i)=2* *m(p2)+1;m(p2)+1; p2+; p3+; p2+; p3+; / /* * 为避免重复项，为避免重复项，P2P2，p3p3均须增均须增1 1 * */ / 101.3.1 1.3.1 猴子爬山问题猴子爬山问题【例例1.41.4】 一个顽猴在一座有一个顽猴在一座有3030级台阶的小山上级台阶的小山上爬山跳跃，猴子上山一步可跳爬山跳跃，猴子上山一步可跳1 1级，或跳级，或跳3 3级，试级，试求上山的求上山的3030级台阶有多少种不同的爬法。级台

9、阶有多少种不同的爬法。1. 1. 递推算法设计递推算法设计一般地有递推关系：一般地有递推关系： f(k)=f(k-1)+f(k-3) f(k)=f(k-1)+f(k-3) （k3k3）初始条件有初始条件有: : f(1)=1 f(1)=1； 即即1=11=1。 f(2)=1f(2)=1； 即即2=1+12=1+1。 f(3)=2f(3)=2； 即即3=1+1+13=1+1+1；3=33=3。1.3 应用递推求解应用题11 int k,n; long f1000;int k,n; long f1000; printf( printf(请输入台阶总数请输入台阶总数n:);n:); scanf(%d

10、,&n); scanf(%d,&n); f1=1;f2=1;f3=2; f1=1;f2=1;f3=2; / /* * 数组元素赋初值数组元素赋初值 * */ / for(k=4;k=n;k+) for(k=4;k=n;k+) fk=fk-1+fk-3; fk=fk-1+fk-3; / /* * 按递推关系实施递推按递推关系实施递推 * */ / printf(s=%ld,fn); printf(s=%ld,fn);2. 算法描述算法描述: 123. 3. 问题引申问题引申把问题引申为爬山把问题引申为爬山n n级，一步有级，一步有m m 种跨法，一步跨多少级均种跨法，一步跨多少级均从键盘输入。从

11、键盘输入。(1(1） 分级递推算法设计分级递推算法设计设爬山设爬山t t台阶级的不同爬法为台阶级的不同爬法为f(t),f(t),设从键盘输入一步跨多少设从键盘输入一步跨多少级的级的m m个整数分别为个整数分别为x(1), x(2), , x(m)x(1), x(2), , x(m) ( (约定约定x(1)x(2)x(m)n)x(1)x(2)x(m)n)。这里的整数这里的整数x(1), x(2), , x(m)x(1), x(2), , x(m)为键盘输入，事前并不知为键盘输入，事前并不知道，因此不能在设计时简单地确定道，因此不能在设计时简单地确定f(x(1),f(x(2),f(x(1),f(x

12、(2),。事实上，可以把初始条件放在分级递推中求取，应用多关系事实上，可以把初始条件放在分级递推中求取，应用多关系分级递推算法（分级递推算法（6 6）完成递推。）完成递推。13 (2) 探讨探讨f(t)的递推关系的递推关系当当tx(1)tx(1)时，时，f(t)=0f(t)=0；f(x(1)=1f(x(1)=1。（初始条件）。（初始条件）当当x(1)tx(2)x(1)tx(2)时，第时，第1 1级递推：级递推：f(t)=f(t-x(1)f(t)=f(t-x(1)；当当x(2)tx(3)x(2)tx(3)时，第时，第2 2级递推：级递推：f(t)=f(t-x(1)+f(t-f(t)=f(t-x(

13、1)+f(t-x(2)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)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)f(t)=f(t-x(1)+f(t-x(2)+f(t-x(m)14(3) (3) 注意注意当当t=x(2),t=x(2),或或t=x(3),t=x(3),或或t=x(m)t=x(m)时时, , 按上递推按上递推求求f(t)f(t)外外, ,还要加上还要加上1 1。道理很简单，因为此

14、时。道理很简单，因为此时t t本身即为一个一步到位的爬法。因而本身即为一个一步到位的爬法。因而 f(t)=f(t)+1f(t)=f(t)+1（t= x(2), x(3),x(m)t= x(2), x(3),x(m)）我们所求的目标为：我们所求的目标为： f(n)=f(n-x(1)+f(n-x(2)+f(n-x(m) f(n)=f(n-x(1)+f(n-x(2)+f(n-x(m) 在递推设计中我们可把台阶数在递推设计中我们可把台阶数n n记为数组元素记为数组元素x(m+1),x(m+1),这样处理是巧妙的这样处理是巧妙的,可以按相同的递推可以按相同的递推规律递推计算，简化算法设计。规律递推计算，

15、简化算法设计。 最后一项最后一项f(x(m+1)f(x(m+1)即为所求即为所求f(n)f(n)。 15for(i=1;i=x1-1;i+) fi=0; for(i=1;i=x1-1;i+) fi=0; xm+1=n;fx1=1;xm+1=n;fx1=1;for(k=1;k=m;k+)for(k=1;k=m;k+)for(t=xk+1;t=xk+1;t+)for(t=xk+1;t=xk+1;t+) ft=0; ft=0; for(j=1;j=k;j+) / for(j=1;j=k;j+) /* * 按公式分级按公式分级 * */ / ft=ft+ft-xj; ft=ft+ft-xj; if(t

16、=xk+1) / if(t=xk+1) /* * t=x(k+1) t=x(k+1)时增时增1 1 * */ / ft=ft+1; ft=ft+1; printf( %ld. n,fn-1);printf( %ld. n,fn-1);(4) 算法描述算法描述161.3.2 整数划分问题【例例1.51.5】 正整数正整数s s（简称为和数）的划分（简称为和数）的划分( (又称分划或拆又称分划或拆分分) )是把是把s s分成为若干个正整数（简称为零数或部分）之和分成为若干个正整数（简称为零数或部分）之和, , 划分式中允许零数重复划分式中允许零数重复, ,且不记零数的次序。且不记零数的次序。试求试

17、求s s共有多个不同的划分式？展示出共有多个不同的划分式？展示出s s的所有这些划分式。的所有这些划分式。1. 1. 探索划分的递推关系探索划分的递推关系为了建立递推关系，先对和数为了建立递推关系，先对和数k k较小时的划分式作观察：较小时的划分式作观察：17由以上各划分看到，除和数本身由以上各划分看到，除和数本身k=kk=k这一特殊划分这一特殊划分式外，其它每一个划分式至少为两项之和。约定式外，其它每一个划分式至少为两项之和。约定在所有划分式中零数作不减排列，探索和数在所有划分式中零数作不减排列，探索和数k k的划的划分式与和数分式与和数k-1k-1的划分式存在以下递推关系的划分式存在以下递

18、推关系: :(1) (1) 在所有和数在所有和数k-1k-1的划分式前加零数的划分式前加零数1 1都是和数都是和数k k的划分式。的划分式。(2) (2) 和数和数k-1k-1的划分式的前两个零数作比较的划分式的前两个零数作比较, ,如果如果第第1 1个零数个零数x1x1小于第小于第2 2个零数个零数x2x2，则把第，则把第1 1个零数加个零数加1 1后成为和数后成为和数k k的划分式。的划分式。18显然递推的初始条件为：显然递推的初始条件为： a(2,1,1)=1a(2,1,1)=1，a(2,1,2)=1; a(2,2,1)=2a(2,1,2)=1; a(2,2,1)=2。根据递推关系，实施

19、递推：根据递推关系，实施递推：(1) (1) 实施在实施在k-1k-1所有划分式前加所有划分式前加1 1操作操作 a(k,j,1)=1; a(k,j,1)=1; for(t=2;t=k;t+) for(t=2;t=k;t+) a(k,j,t)=a(k-1,j,t-1); a(k,j,t)=a(k-1,j,t-1); / /* * k-1 k-1的第的第t-1t-1项变为项变为k k的第的第t t项项 * */ / (2) (2) 若若k-1k-1划分式第划分式第1 1项小于第项小于第2 2项，第项，第1 1项加项加1 1，变为，变为k k的的第第i i个划分式个划分式 if(a(k-1,j,1

20、)a(k-1,j,2)if(a(k-1,j,1)a(k-1,j,2) a(k,i,1)=a(k-1,j,1)+1; a(k,i,1)=a(k-1,j,1)+1; for(t=2;t=k-1;t+) for(t=2;t=1;t-) for(t=i;t=1;t-) a(j,t+1)=a(j,t); a(j,t+1)=a(j,t);a(j,1)=1; a(j,1)=1; 20 211.4 递推与递归比较递归其实就是利用系统堆栈递归其实就是利用系统堆栈, ,实现函数自身调用实现函数自身调用, ,或者是相或者是相互调用的过程。在通往边界的过程中互调用的过程。在通往边界的过程中, ,都会把单步地址保都会把

21、单步地址保存下来，再按照先进后出进行运算。递归的数据传送也类存下来，再按照先进后出进行运算。递归的数据传送也类似。似。递归的运算方法递归的运算方法, ,决定了它的效率较低，因为数据要不断决定了它的效率较低，因为数据要不断的进栈出栈。在应用递归时，只要输入的的进栈出栈。在应用递归时，只要输入的n n值稍大，程序值稍大，程序求解就比较困难。因而从计算效率来说，递推往往要高于求解就比较困难。因而从计算效率来说，递推往往要高于递归。递归。递推免除了数据进出栈的过程，也就是说递推免除了数据进出栈的过程，也就是说, ,不需要函数不不需要函数不断的向边界值靠拢断的向边界值靠拢, ,而直接从边界出发，逐步推出

22、函数值而直接从边界出发，逐步推出函数值, , 直观明了。直观明了。在有些情况下，递归可以转化为效率较高的递推。但是递在有些情况下，递归可以转化为效率较高的递推。但是递归作为重要的基础算法归作为重要的基础算法, ,它的作用不可替代，在把握这两它的作用不可替代，在把握这两种算法的时候应该特别注意。种算法的时候应该特别注意。22【例例1.61.6】 求整数求整数s s的划分数的划分数解：设解：设n n的的“最大零数不超过最大零数不超过m”m”的划分式个数为的划分式个数为q(n,m)q(n,m)。 建立递推关系建立递推关系所有所有q(n,m)q(n,m)个划分式分为两类：零数中不包含个划分式分为两类：

23、零数中不包含m m的划分式的划分式有有q(n,m-1)q(n,m-1)个；零数中包含个；零数中包含m m 的划分式有的划分式有q(n-m,m)q(n-m,m)个。有个。有 q(n,m)=q(n,m-1)+q(n-m,m) (1mns)q(n,m)=q(n,m-1)+q(n-m,m) (1mns)其中其中 q(n-m,m)=q(n-m,n-m) q(n-m,m)=q(n-m,n-m) （若（若n-mmn-mm）注意到注意到n n等于等于n n本身也为一个划分式，则有本身也为一个划分式，则有 q(n,n)=1+q(n,n-1)q(n,n)=1+q(n,n-1) 确定初始条件确定初始条件 q(n,0

24、)=0q(n,0)=0 q(1,m)=1 (m=1,2, ,s, q(1,m)=1 (m=1,2, ,s,因整数因整数1 1只有一个划分只有一个划分) )23递推算法描述递推算法描述: :scanf(%d,&s); /scanf(%d,&s); /* * 输入划分的整数输入划分的整数 * */ /for(m=1;m=s;m+)for(m=1;m=s;m+)qm0=0;q1m=1; /qm0=0;q1m=1; /* * 确定初始条件确定初始条件 * */ /for(n=2;n=s;n+)for(n=2;n=s;n+) for(m=1;m=n-1;m+) for(m=1;m=n-1;m+) if(

25、n-mm) if(n-mm) qn-mm=qn-mn-m; / qn-mm=qn-mn-m; /* * 实施递推实施递推 * */ / qnm=qnm-1+qn-mm; qnm=qnm-1+qn-mm; qnn=qnn-1+1; / qnn=qnn-1+1; /* * 加上加上n=nn=n划分式划分式 * */ / printf(qss); /printf(qss); /* * 输出递推结果输出递推结果 * */ / Visual FoxPro24精品课件精品课件！Visual FoxPro25精品课件精品课件！26幂序列幂序列双关系递推数列双关系递推数列猴子爬山问题猴子爬山问题整数分划问题整数分划问题水手分椰子问题水手分椰子问题