《第1讲 递推与迭代优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第1讲 递推与迭代优秀PPT.ppt（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第1讲 递推与迭代Visual FoxPro1现在学习的是第1页，共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计2递推概述递推概述递推数列递推数列应用递推求解应用题应用递推求解应用题递推与递归比较递推与递归比较迭代及其应用迭代及其应用 现在学习的是第2页，共27页常用算法与程序设计常用算法与程序设计31.1 递推概述递推概述1.1.1 递推算法递推算法1.1.递推是一种高效的数学模型，是组合数学中的一个重要递推是一种高效的数学模型，是组合数学中的一个重要递推是一种高效的数学模型，是组合数学中的一个重要递推是一种高效的数学模型，是组合数学中的一个重要解题方法解题
2、方法解题方法解题方法。2.2.递推是利用问题本身所具有的一种递推关系求解问递推是利用问题本身所具有的一种递推关系求解问题的一种方法。题的一种方法。3.3.递推算法的首要问题是得到相邻的数据项之间的关递推算法的首要问题是得到相邻的数据项之间的关系，即递推关系。系，即递推关系。现在学习的是第3页，共27页常用算法与程序设计常用算法与程序设计41.实施递推的步骤实施递推的步骤(1)确定递推变量确定递推变量(2)建立递推关系建立递推关系(3)确定初始（边界）条件确定初始（边界）条件(4)对递推过程进行控制对递推过程进行控制1.1.2 递推实施步骤与描述递推实施步骤与描述现在学习的是第4页，共27页常用
3、算法与程序设计常用算法与程序设计5 2.递推算法框架描述递推算法框架描述（1）简单顺推算法 顺推即从前往后推顺推即从前往后推顺推即从前往后推顺推即从前往后推,从已求得的规模为从已求得的规模为从已求得的规模为从已求得的规模为1 1，2 2，i-1的一系列解，推出问题规模为的一系列解，推出问题规模为 i的解，直至得的解，直至得到规模为到规模为n的解。的解。简单顺推算法框架描述：简单顺推算法框架描述：f(1i-1)=；/*确定初始值确定初始值*/for(k=i;k=n;k+)f(k)=；/*施递推施递推*/printf(f(n)；/*输出输出n规模的解规模的解f(n)*/现在学习的是第5页，共27页
4、常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计6（2）简单逆推算法简单逆推算法 逆推即从后往前推逆推即从后往前推,从已得的规模为从已得的规模为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)*
5、/f(1)*/现在学习的是第6页，共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计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
6、(n,m)*/（3 3）二维数组顺推算法二维数组顺推算法现在学习的是第7页，共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计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)
7、=2；/*/*据递推关系据递推关系2 2递推递推*/*/if(if()m)f(k)=f(k)=m；/*/*据递推关系据递推关系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循环中比较赋值：循环中比较赋值：当当abab
8、ab时，由赋值时，由赋值fk=bfk=b确定为序列的第确定为序列的第k k项；然后项；然后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 f
9、k=b;b=b*3;/*fk=b;b=b*3;/*用用b 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中。所谓中。所谓“排头排头”就就是队列中尚未选入是队列中尚未选
10、入m m的最小的数（下标）。这里用的最小的数（下标）。这里用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(p2
11、)=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级台阶有级台阶有多少种不同的爬法。多少种不同的爬法。
12、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(printf(请输入台阶总
13、数请输入台阶总数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.问题引申问题引申把问题引申为爬山把问题引申为爬山n n级，一步有级，一步有m m
14、 种跨法，一步跨多少级均从键盘输种跨法，一步跨多少级均从键盘输入。入。(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),
15、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(1)f(t)=f(t-x(1)；当当x(2)tx(3)x(2)tx(3)时，第时
16、，第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页常用算法与程序设计常用算法与程序设计17(3)(3)注意注意当当t=x(2),t=x(2),或或t=x(3),
17、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(n-x(m)在递推设计中我们可把台阶数在递推设计中我们可把台阶数n n记为数组元素记为数组元素x(m+1),x
18、(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+)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
19、(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页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计191.3.2 整数划分问题【例【例1.51.5】正整数正整数s s（简称为和数）的划分（简称为和数）的划分(又称分划或拆分又称分
20、划或拆分)是把是把s s分成为若干个正整数（简称为零数或部分）之和分成为若干个正整数（简称为零数或部分）之和,划分式中允许划分式中允许零数重复零数重复,且不记零数的次序。且不记零数的次序。试求试求s s共有多个不同的划分式？展示出共有多个不同的划分式？展示出s s的所有这些划分式。的所有这些划分式。1.1.探索划分的递推关系探索划分的递推关系为了建立递推关系，先对和数为了建立递推关系，先对和数k k较小时的划分式作观察：较小时的划分式作观察：k=2k=2k=2k=2：1+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+2
21、1+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+41+4；2+32+32+32+3；5 5 5 5现在学习的是第19页，共27页常用算法与程序设计常用算法与程序设计常用算法
22、与程序设计常用算法与程序设计20由以上各划分看到，除和数本身由以上各划分看到，除和数本身k=kk=k这一特殊划分式这一特殊划分式外，其它每一个划分式至少为两项之和。约定在所有外，其它每一个划分式至少为两项之和。约定在所有划分式中零数作不减排列，探索和数划分式中零数作不减排列，探索和数k k的划分式与和的划分式与和数数k-1k-1的划分式存在以下递推关系的划分式存在以下递推关系:(1)(1)在所有和数在所有和数k-1k-1的划分式前加零数的划分式前加零数1 1都是和数都是和数k k的划的划分式。分式。(2)(2)和数和数k-1k-1的划分式的前两个零数作比较的划分式的前两个零数作比较,如果第如果
23、第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。根据递推关系，实施递推：根据递推关系，实施递推：(1)(1)实施在实施在k-1k-1所有划分式前加所有划分式前加1 1操作操作 a(k,j,1)=1;a(k,j,1)=1;for(t=2;t=k;t+
24、)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)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
25、-)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个数小于第个数小于第个数小于第个数小于第3 3 3 3个数个数个数个数（相当于（相当于（相当于（相当于k-1k-1k-1k-1时的第时的第时的第时的第1 1 1 1个数小于第个数小于第个数小于第个数小于第2
26、2 2 2个数），则把第个数），则把第个数），则把第个数），则把第2 2 2 2个数加个数加个数加个数加1 1 1 1，去除，去除，去除，去除第一个数后，作为第一个数后，作为第一个数后，作为第一个数后，作为k k k k时增加的一个划分式，为第时增加的一个划分式，为第时增加的一个划分式，为第时增加的一个划分式，为第t(tt(tt(tt(t从从从从u u u u开始，每增开始，每增开始，每增开始，每增加一个划分式，加一个划分式，加一个划分式，加一个划分式，t t t t增增增增1)1)1)1)划分式。划分式。划分式。划分式。for(t=u,j=1;j=u;j+)for(t=u,j=1;j=u;j
27、+)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)=a(j,i);i+;现在学习的是第23页，共27页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计241.4 递推与递归比较递归其实就是利用系统堆栈递归其实
28、就是利用系统堆栈,实现函数自身调用实现函数自身调用,或者是相互调或者是相互调用的过程。在通往边界的过程中用的过程。在通往边界的过程中,都会把单步地址保存下来，都会把单步地址保存下来，再按照先进后出进行运算。递归的数据传送也类似。再按照先进后出进行运算。递归的数据传送也类似。递归的运算方法递归的运算方法,决定了它的效率较低，因为数据要不断的进栈出栈。决定了它的效率较低，因为数据要不断的进栈出栈。在应用递归时，只要输入的在应用递归时，只要输入的n n值稍大，程序求解就比较困难。因而从值稍大，程序求解就比较困难。因而从计算效率来说，递推往往要高于递归。计算效率来说，递推往往要高于递归。递推免除了数据
29、进出栈的过程，也就是说递推免除了数据进出栈的过程，也就是说,不需要函数不断不需要函数不断的向边界值靠拢的向边界值靠拢,而直接从边界出发，逐步推出函数值而直接从边界出发，逐步推出函数值,直直观明了。观明了。在有些情况下，递归可以转化为效率较高的递推。但是递归作在有些情况下，递归可以转化为效率较高的递推。但是递归作为重要的基础算法为重要的基础算法,它的作用不可替代，在把握这两种算法的它的作用不可替代，在把握这两种算法的时候应该特别注意。时候应该特别注意。现在学习的是第24页，共27页常用算法与程序设计常用算法与程序设计25【例【例1.61.6】求整数求整数s s的划分数的划分数解：设解：设n n的
30、的“最大零数不超过最大零数不超过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-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
31、）注意到注意到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页常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计26递推算法描述递推算法描述:scanf(%d,&s);/*scanf(%d,&s);/*输入划分的整数输入划分的整数*/*/for(m=1;m=s;m+)for(m=
32、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.上机上机:幂序列幂序列双关系递推数列双关系递推数列猴子爬山问题猴子爬山问题整数分划问题整数分划问题水手分椰子问题水手分椰子问题 2.上机通过各习题。上机通过各习题。作业：作业：2.3.4.现在学习的是第27页，共27页