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

《第1讲 递推与迭代优秀课件.ppt》由会员分享，可在线阅读，更多相关《第1讲 递推与迭代优秀课件.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1讲 递推与迭代Visual FoxPro1第1页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计2递推概述递推概述递推数列递推数列应用递推求解应用题应用递推求解应用题递推与递归比较递推与递归比较迭代及其应用迭代及其应用 第2页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计31.1 递推概述递推概述1.1.1 递推算法递推算法1.1.递推是一种高效的数学模型，是组合数学中的一递推是一种高效的数学模型，是组合数学中的一递推是一种高效的数学模型，是组合数学中的一递推是一种高效的数学模型，是组合数学中的一个重要解题方

2、法个重要解题方法个重要解题方法个重要解题方法。2.2.递推是利用问题本身所具有的一种递推关系求解递推是利用问题本身所具有的一种递推关系求解递推是利用问题本身所具有的一种递推关系求解递推是利用问题本身所具有的一种递推关系求解问题的一种方法。问题的一种方法。问题的一种方法。问题的一种方法。3.3.递推算法的首要问题是得到相邻的数据项之间的递推算法的首要问题是得到相邻的数据项之间的递推算法的首要问题是得到相邻的数据项之间的递推算法的首要问题是得到相邻的数据项之间的关系，即递推关系。关系，即递推关系。关系，即递推关系。关系，即递推关系。第3页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法

3、与程序设计常用算法与程序设计41.实施递推的步骤实施递推的步骤(1)(1)确定递推变量确定递推变量确定递推变量确定递推变量(2)建立递推关系建立递推关系(3)确定初始（边界）条件确定初始（边界）条件(4)(4)对递推过程进行控制对递推过程进行控制对递推过程进行控制对递推过程进行控制1.1.2 递推实施步骤与描述第4页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计5 2.递推算法框架描述递推算法框架描述（1 1）简单顺推算法简单顺推算法 顺推即从前往后推顺推即从前往后推顺推即从前往后推顺推即从前往后推,从已求得的规模为从已求得的规模为从已求得的规模为从已

4、求得的规模为1 1，2 2，i-1i-1的一系列解，推出问题规模为的一系列解，推出问题规模为的一系列解，推出问题规模为的一系列解，推出问题规模为 i i的解，直至得的解，直至得的解，直至得的解，直至得到规模为到规模为到规模为到规模为n n的解。的解。的解。的解。简单顺推算法框架描述：简单顺推算法框架描述：f(1i-1)=；/*确定初始值确定初始值*/for(k=i;k=n;k+)f(k)=；/*施递推施递推*/printf(f(n)；/*输出输出n规模的解规模的解f(n)*/第5页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计6（2）简单逆推算法简单逆

5、推算法 逆推即从后往前推逆推即从后往前推,从已得的规模为从已得的规模为n，n-1，i+1的一系列解，推出问题规模为的一系列解，推出问题规模为 i的解，直至的解，直至得到规模为得到规模为1的解。的解。简单逆推算法框架描述：简单逆推算法框架描述：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)*/第6页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法

6、与程序设计7设递推的二维数组为设递推的二维数组为f(k,j)f(k,j)，1kn,1jm1kn,1jm。二维数组顺推算法框架描述：二维数组顺推算法框架描述：f(1,1m)=f(1,1m)=；/*/*赋初始值赋初始值*/*/for(k=2;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)*/（3 3）二维数组顺推算法二维数组顺推算法第7页，本讲稿共27页常用算法与程序设计常用算法

7、与程序设计常用算法与程序设计常用算法与程序设计8 当递推关系包含两个或两个以上关系式时，通常应用多关系分级当递推关系包含两个或两个以上关系式时，通常应用多关系分级递推算法求解。递推算法求解。（4 4）多关系分级递推算法多关系分级递推算法f(1i-1)=f(1i-1)=；/*/*赋初始值赋初始值*/*/for(k=i;k=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；/*/*据递

8、推关系据递推关系m m递推递推*/*/printf(f(n)printf(f(n)；/*/*输出解输出解f(n)*/f(n)*/第8页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计91.2 递推数列(1)(1)递推算法设计递推算法设计设置设置k k循环（循环（k=1,2,k=1,2,，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项；然

9、后项；然后b=b*3b=b*3，即，即b b按递推规律乘按递推规律乘3,3,为后一轮比较作准备。为后一轮比较作准备。1.2.1 幂序列第9页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计10递推过程描述：递推过程描述：a=2;b=3;*a=2;b=3;*为递推变量为递推变量a,ba,b赋初值赋初值*/*/for(k=1;k=n;k+)for(k=1;k=n;k+)if(ab)if(ab)fk=a;a=a*2;/*fk=a;a=a*2;/*用用a a给给fkfk赋值赋值*/*/else else fk=b;b=b*3;/*fk=b;b=b*3;/*用用b

10、 b给给fkfk赋值赋值*/*/在这一算法中，变量在这一算法中，变量a,ba,b是变化的，分别代表是变化的，分别代表2 2的幂与的幂与3 3的幂。的幂。第10页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计111.2.2 双关系递推数列(1)(1)算法设计要点算法设计要点设设n n个数在数组个数在数组m m中，中，2x+12x+1与与 3x+1 3x+1均作为一个队列，从两均作为一个队列，从两队列中选一排头队列中选一排头(数值较小者数值较小者)送入数组送入数组m m中。所谓中。所谓“排头排头”就是队列中尚未选入就是队列中尚未选入m m的最小的数（下标）

11、。这里用的最小的数（下标）。这里用p2p2表示表示2x+12x+1这一列的排头的下标，用这一列的排头的下标，用p3p3表示表示3x+13x+1这一列的这一列的排头的下标。排头的下标。第11页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计12if(2*m(p2)3*m(p3)if(2*m(p2)3*m(p3)if(2*m(p2)3*m(p3)m(i)=3*m(p3)+1;p3+;m(i)=3*m(p3)+1;p3+;特别注意：两队列若出现相等时，给特别注意：两队列若出现相等时，给m m数组赋值后，两排数组赋值后，两排头都要增头都要增1 1。if(2*m(

12、p2)=3*m(p3)if(2*m(p2)=3*m(p3)m(i)=2*m(p2)+1;m(i)=2*m(p2)+1;p2+;p3+;p2+;p3+;/*/*为避免重复项，为避免重复项，P2P2，p3p3均须增均须增1*/1*/第12页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计131.3.1 1.3.1 猴子爬山问题猴子爬山问题【例【例1.41.4】一个顽猴在一座有一个顽猴在一座有3030级台阶的小山上爬山级台阶的小山上爬山跳跃，猴子上山一步可跳跳跃，猴子上山一步可跳1 1级，或跳级，或跳3 3级，试求上山的级，试求上山的3030级台阶有多少种不同

13、的爬法。级台阶有多少种不同的爬法。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)=1 f(2)=1；即即2=1+12=1+1。f(3)=2 f(3)=2；即即3=1+1+13=1+1+1；3=33=3。1.3 应用递推求解应用题第13页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计14 int k,n;long f1000;int k,n;long f1000;printf

14、(printf(请输入台阶总数请输入台阶总数n:);n:);scanf(%d,&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.算法描述:第14页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计153.3.问题引申问题引申把问题引申为爬

15、山把问题引申为爬山n n级，一步有级，一步有m m 种跨法，一步跨多少级均从键种跨法，一步跨多少级均从键盘输入。盘输入。(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)为键盘输入，事前并不知道，因此不为键盘输入，事前并不知道，因此不能在设计时简单地确

16、定能在设计时简单地确定f(x(1),f(x(2),f(x(1),f(x(2),。事实上，可以把初始条件放在分级递推中求取，应用多关系分级递推算事实上，可以把初始条件放在分级递推中求取，应用多关系分级递推算法（法（6 6）完成递推。）完成递推。第15页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计16 (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(

17、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-x(2)f(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)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)第16页，本讲稿共27页常用算法与程序设计常用算法与程序设计

18、常用算法与程序设计常用算法与程序设计17(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。道理很简单，因为此时。道理很简单，因为此时t t本身即为一个一步到位的爬法。因而本身即为一个一步到位的爬法。因而 f(t)=f(t)+1 f(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(

19、n-x(m)在递推设计中我们可把台阶数在递推设计中我们可把台阶数n n记为数组元素记为数组元素x(m+1),x(m+1),这样处理是巧妙的这样处理是巧妙的,可以按相同的递推可以按相同的递推规律递推计算，简化算法设计。规律递推计算，简化算法设计。最后一项最后一项f(x(m+1)f(x(m+1)即为所求即为所求f(n)f(n)。第17页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计18for(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+)

20、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=xk+1)/*t=x(k+1)if(t=xk+1)/*t=x(k+1)时增时增1*/1*/ft=ft+1;ft=ft+1;printf(%ld.n,fn-1);printf(%ld.n,fn-1);(4)算法描述第18页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计19

21、1.3.2 整数划分问题【例【例1.51.5】正整数正整数s s（简称为和数）的划分（简称为和数）的划分(又称分划或拆分又称分划或拆分)是是把把s s分成为若干个正整数（简称为零数或部分）之和分成为若干个正整数（简称为零数或部分）之和,划分式中划分式中允许零数重复允许零数重复,且不记零数的次序。且不记零数的次序。试求试求s s共有多个不同的划分式？展示出共有多个不同的划分式？展示出s s的所有这些划分式。的所有这些划分式。1.1.探索划分的递推关系探索划分的递推关系为了建立递推关系，先对和数为了建立递推关系，先对和数k k较小时的划分式作观察：较小时的划分式作观察：k=2k=2k=2k=2：1

22、+11+11+11+1；2 2 2 2 k=3k=3k=3k=3：1+1+11+1+11+1+11+1+1；1+21+21+21+2；3 3 3 3 k=4k=4k=4k=4：1+1+1+11+1+1+11+1+1+11+1+1+1；1+1+21+1+21+1+21+1+2；1+31+31+31+3；2+22+22+22+2；4 4 4 4 k=5k=5k=5k=5：1+1+1+1+11+1+1+1+11+1+1+1+11+1+1+1+1；1+1+1+21+1+1+21+1+1+21+1+1+2；1+1+31+1+31+1+31+1+3；1+2+21+2+21+2+21+2+2；1+41+41

23、+41+4；2+32+32+32+3；5 5 5 5第19页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计20由以上各划分看到，除和数本身由以上各划分看到，除和数本身k=kk=k这一特殊划分式外，这一特殊划分式外，其它每一个划分式至少为两项之和。约定在所有划分式其它每一个划分式至少为两项之和。约定在所有划分式中零数作不减排列，探索和数中零数作不减排列，探索和数k k的划分式与和数的划分式与和数k-1k-1的划的划分式存在以下递推关系分式存在以下递推关系:(1)(1)在所有和数在所有和数k-1k-1的划分式前加零数的划分式前加零数1 1都是和数都是和数k

24、 k的的划分式。划分式。(2)(2)和数和数k-1k-1的划分式的前两个零数作比较的划分式的前两个零数作比较,如果第如果第1 1个个零数零数x1x1小于第小于第2 2个零数个零数x2x2，则把第，则把第1 1个零数加个零数加1 1后成为和后成为和数数k k的划分式。的划分式。第20页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计21显然递推的初始条件为：显然递推的初始条件为：a(2,1,1)=1 a(2,1,1)=1，a(2,1,2)=1;a(2,2,1)=2a(2,1,2)=1;a(2,2,1)=2。根据递推关系，实施递推：根据递推关系，实施递推：(

25、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)a(k-1,j,2)if(a(k-1,j,1)a(k-1,j,2

26、)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;第22页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计23(2)(2)(2)(2)对已转化的对已转化的对已转化的对已转化的u u u u个划分式逐个检验，若其第个划分式逐个检验，若其第个划分式逐个检验，若其第个划分式逐个检验，若其第2 2 2 2个数小于个数小于个数小于个数

27、小于第第第第3 3 3 3个数（相当于个数（相当于个数（相当于个数（相当于k-1k-1k-1k-1时的第时的第时的第时的第1 1 1 1个数小于第个数小于第个数小于第个数小于第2 2 2 2个数），则把个数），则把个数），则把个数），则把第第第第2 2 2 2个数加个数加个数加个数加1 1 1 1，去除第一个数后，作为，去除第一个数后，作为，去除第一个数后，作为，去除第一个数后，作为k k k k时增加的一个划时增加的一个划时增加的一个划时增加的一个划分式，为第分式，为第分式，为第分式，为第t(tt(tt(tt(t从从从从u u u u开始，每增加一个划分式，开始，每增加一个划分式，开始，每增

28、加一个划分式，开始，每增加一个划分式，t t t t增增增增1)1)1)1)划划划划分式。分式。分式。分式。for(t=u,j=1;j=u;j+)for(t=u,j=1;j=u;j+)for(t=u,j=1;j=u;j+)for(t=u,j=1;j=u;j+)if(a(j,2)a(j,3)/*if(a(j,2)a(j,3)/*if(a(j,2)a(j,3)/*if(a(j,2)0)while(a(j,i)0)while(a(j,i)0)while(a(j,i)0)a(t,i-1)=a(j,i);i+;a(t,i-1)=a(j,i);i+;a(t,i-1)=a(j,i);i+;a(t,i-1)=

29、a(j,i);i+;第23页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计241.4 递推与递归比较递归其实就是利用系统堆栈递归其实就是利用系统堆栈,实现函数自身调用实现函数自身调用,或者是相互或者是相互调用的过程。在通往边界的过程中调用的过程。在通往边界的过程中,都会把单步地址保存下都会把单步地址保存下来，再按照先进后出进行运算。递归的数据传送也类似。来，再按照先进后出进行运算。递归的数据传送也类似。递归的运算方法递归的运算方法,决定了它的效率较低，因为数据要不断的进栈决定了它的效率较低，因为数据要不断的进栈出栈。在应用递归时，只要输入的出栈。在应用

30、递归时，只要输入的n n值稍大，程序求解就比较困值稍大，程序求解就比较困难。因而从计算效率来说，递推往往要高于递归。难。因而从计算效率来说，递推往往要高于递归。递推免除了数据进出栈的过程，也就是说递推免除了数据进出栈的过程，也就是说,不需要函数不断的向不需要函数不断的向边界值靠拢边界值靠拢,而直接从边界出发，逐步推出函数值而直接从边界出发，逐步推出函数值,直观明了。直观明了。在有些情况下，递归可以转化为效率较高的递推。但是递归作为重要在有些情况下，递归可以转化为效率较高的递推。但是递归作为重要的基础算法的基础算法,它的作用不可替代，在把握这两种算法的时候应该特别它的作用不可替代，在把握这两种算

31、法的时候应该特别注意。注意。第24页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计25【例【例1.61.6】求整数求整数s s的划分数的划分数解：设解：设n n的的“最大零数不超过最大零数不超过m”m”的划分式个数为的划分式个数为q(n,m)q(n,m)。建立递推关系建立递推关系所有所有q(n,m)q(n,m)个划分式分为两类：零数中不包含个划分式分为两类：零数中不包含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-

32、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)=0 q(n,0)=0 q(1,m)=1 (m=1,2,s,q(1,m)=1 (m=1,2,s,因整数因整数1 1只有一个划分只有一个划分)第25页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算

33、法与程序设计常用算法与程序设计26递推算法描述递推算法描述: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(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);/*输出递推结果输出递推结果*/*/第26页，本讲稿共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计271.1.上机上机上机上机:幂序列幂序列双关系递推数列双关系递推数列猴子爬山问题猴子爬山问题整数分划问题整数分划问题水手分椰子问题水手分椰子问题 2.上机通过各习题。上机通过各习题。作业：作业：作业：作业：2.3.4.2.3.4.第27页，本讲稿共27页