第3讲递推

1第3讲递推递推是一种应用非常广泛的常用算法之一，与下一章的递归有着密切的联系。本章探讨递推在求解数列、数阵以及计数等应用案例方面的应用。3.1递推概述在纷繁变幻的世界，所有事物都随时间的流逝发生着微妙的变化。许多现象的变化是有规律可循的，这种规律往往呈现出前因后果的关系。某种现象的变化结果与紧靠它前面变化的一个或一些结果紧密关联。递推的思想正体现了这一变化规律。3.1.1递推算法所谓递推，是在命题归纳时，可以由n−k,…,n−1的情形推得n的情形。一个线性递推可以形式地写成11()nnknkacacafn其中f(n)=0时递推是齐次的，否则是非齐次的。递推的一般解法要用到n次方程的求根。递推关系是一种高效的数学模型，是组合数学中的一个重要解题方法，在组合计数中有着广泛的应用。在概率方面利用递推可以解决一类基本事件个数较大的概率问题。在对多项式的求解过程中，很多情况可以使用递推算法来实现。在行列式方面，某些n阶行列式只用初等变换难以解决，但如果采用递推求解则显得较为容易。递推关系不仅在各数学分支中发挥着重要的作用，由它所体现出来的递推思想在各学科领域中更是显示出其独特的魅力。递推是利用问题本身所具有的一种递推关系求解问题的一种方法。设要求问题规模为n的解，当n=1时，解或为已知，或能非常方便地得到解。能采用递推法构造算法的递推性质，能从已求得的规模为1,2,…,i−1的一系列解，构造出问题规模为i的解。这样，程序可从i=0或i=1出发，重复地由已知至i−1规模的解，通过递推，获得规模为i的解，直至得到规模为n的解。递推算法的基本思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法充分利用了计算机的运算速度快和不知疲倦的特点，从头开始一步步地推出问题最终的结果。使用递推算法编程，既可使程序简练，又可节省计算时间。对于一个序列来说，如果已知它的通项公式，那么要求出数列中某项之值或求数列的前2n项之和是简单的。但是，在许多情况下，要得到数列的通项公式是困难的，甚至无法得到。然而，一个有规律的数列的相邻位置上的数据项之间通常存在着一定的关系，可以借助已知的项，利用特定的关系逐项推算出它的后继项的值，直到找到所需的那一项为止。递推算法避开了求通项公项的麻烦，把一个复杂的问题的求解，分解成连续的若干步简单运算。递推算法的首要问题是得到相邻的数据项之间的关系，即递推关系。它针对这样一类问题：问题的解决可以分为若干步骤，每个步骤都产生一个子解（部分结果），每个子解都是由前面若干子解生成。不同的子解，其所相关的问题规模也随子解不同而递增。我们把这种由前面的子解得出后面的子解的规则称为递推关系。我们在设计求解问题前，要通过细心的观察，丰富的联想，不断尝试推理，尽可能归纳总结其内在规律，然后再把这种规律性的东西抽象成递推数学模型。3.1.2递推实施步骤与描述利用递推求解实际问题，需要掌握递推的具体描述及其实施步骤。1．实施递推的步骤（1）确定递推变量应用递推算法解决问题，要根据问题的具体实际设置递推变量。递推变量可以是简单变量，也可以是一维或多维数组。（2）建立递推关系递推关系是指如何从变量的前一些值推出其下一个值或从变量的后一些值推出其上一个值的公式（或关系）。递推关系是递推的依据，是解决递推问题的关键。有些问题，其递推关系是明确的，大多数实际问题并没有现成的明确的递推关系，需根据问题的具体实际，细心的观察，丰富的联想，不断尝试推理，才能确定问题的递推关系。（3）确定初始（边界）条件对所确定的递推变量，要根据问题最简单情形的数据确定递推变量的初始（边界）值，这是递推的基础。（4）对递推过程进行控制递推过程不能无休止地重复执行下去。递推过程在什么时候结束，满足什么条件结束，这是编写递推算法必须考虑的问题。递推过程的控制通常可分为两种情形：一种是所需的递推次数是确定的值，可以计算出来；另一种是所需的递推次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对递推过程的控制；对于后一种情况，需要进一步分析出用来结束递推过程的条件。2．递推算法框架描述递推通常由循环来实现，一般在循环外确定初始（边界）条件，在设置的循环中实施递推。下面归纳常用的递推模式并作简要的框架描述。首先，从递推流向可分为顺推与逆推。（1）简单顺推算法顺推即从前往后推，从已求得的规模为1,2,…,i−1的一系列解，推出问题规模为i的3解，直至得到规模为n的解。简单顺推算法框架描述：f(1−i−1)=初始值；//确定初始值for(k=i;k=n;k++)f(k)=递推关系式；//根据递推关系实施递推printf(f(n))；//输出n规模的解f(n)（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)简单递推问题设置一维数组实现，较复杂的递推问题需设置二维或二维以上数组。例如当规模为i的解为规模为1,2,…,i−1的解通过计算处理决定时，可设置二重循环处理这一较为复杂的递推。（3）二维数组顺推算法设递推的二维数组为f(k,j)，1≤k≤n,1≤j≤m，由初始条件分别求得f(1,1),f(1,2),…,f(1,m)，需求f(n,m)，则据给定的递推关系由初始条件依次顺推得f(2,1),f(2,2),…,f(2,m)；f(3,1),f(3,2),…,f(3,m)；…，直至得到所要求的解f(n,m)。二维数组顺推算法框架描述：f(1,1−m)=初始值；//赋初始值for(k=2;k=n;k++)for(j=1;j=m;j++)f(k,j)=递推关系式；//根据递推关系实施递推printf(f(n,m))；//输出n规模的解f(n,m)二维或二维以上数组递推常用于动态规划设计的最优值求解过程。当递推关系包含两个或两个以上关系式时，通常应用多关系分级递推算法求解。（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实施递推4}printf(f(n))；//输出n规模的解f(n)关于递推的时间复杂度，如果在一重循环中可完成递推，通常其相应的时间复杂度为O(n)。在实际应用中，由于递推关系的不同，往往需要二重或更复杂的循环结构才能完成递推，其相应的时间复杂度为O(n2)或更高。3.2幂序列本节探讨双幂序列与双幂积序列这两个典型的递推序列问题的求解。3.2.1双幂序列设x,y为正整数，试计算集合}0,0|3,2{yxMyx的元素由小到大排列的双幂序列第n项与前n项之和。（1）递推算法设计集合由2的幂与3的幂组成，实际上给出的是两个递推关系。显然，第1项也是最小项为1（当x=y=0时）。从第2项开始，为了实现从小到大排列，设置a,b两个变量，a为2的幂，b为3的幂，显然a≠b。设置k循环（k=2,3,…,n，其中n为键盘输入整数），在k循环外赋初值：a=2;b=3;s=1;在k循环中通过比较赋值：当ab时，由赋值f[k]=a确定为序列的第k项；然后a=a*2，即a按递推规律乘2，为后一轮比较作准备；当ab时，由赋值f[k]=b确定为序列的第k项；然后b=b*3，即b按递推规律乘3，为后一轮比较作准备。递推过程描述：a=2;b=3;//为递推变量a,b赋初值for(k=2;k=n;k++){if(ab){f[k]=a;a=a*2;}//用a给f[k]赋值else{f[k]=b;b=b*3;}//用b给f[k]赋值}在这一算法中，变量a,b是变化的，分别代表2的幂与3的幂。上述递推算法的时间复杂度与空间复杂度均为O(n)。（2）双幂序列程序实现5//双幂序列求解#includestdio.hvoidmain(){intk,m,t,p2,p3;doublea,b,s,f[100];printf(求数列的第m项与前m项和,请输入m:);scanf(%d,&m);f[1]=1;p2=0;p3=0;a=2;b=3;s=1;for(k=2;k=m;k++){if(ab){f[k]=a;a=a*2;//用2的幂给f[k]赋值t=2;p2++;//t=2表示2的幂，p2为指数}else{f[k]=b;b=b*3;//用3的幂给f[k]赋值t=3;p3++;//t=3表示3的幂，p3为指数}s+=f[k];}printf(数列的第%d项为:%.0f,m,f[m]);if(t==2)//对输出项进行标注printf((2^%d)\n,p2);elseprintf((3^%d)\n,p3);printf(数列的前%d项之和为：%.0f\n,m,s);}运行程序，求数列的第n项与前n项和,请输入n:50数列的第50项为:1162261467(3^19)数列的前50项之和为：38908758463.2.2幂积序列1.案例提出设x,y为非负整数，试计算集合}0,0|32{yxMyx的元素小于指定整数n的个数，并求这些元素从小到大排序的第m项。以下给出案例求解的三种设计,并比较其时间复杂度。62.穷举求解(1）设计要点集合元素由2的幂与3的幂及其乘积组成，设元素从小到大排序的第k项为f(k)。显然，f(1)=1,f(2)=2。设置a从3开始递增至n循环，对每一个a(赋值给j),逐次试用2试商，然后逐次试用3试商。试商后若j1，说明原a有2，3以外的因数，不属于该序列。若j=1，说明原a只有2，3的因数，为序列第k项赋值。由于实施从小到大穷举赋值，所得项无疑是从小到大的序列。当达到指定的n，退出循环，输出指定项f(m)。(2)穷举程序实现//幂序列2^x*3^y穷举求解#includestdio.hvoidmain(){intk,m;longa,j,n,f[1000];printf(计算小于n的项数，请指定n:);scanf(%ld,&n);printf(输出序列的第m项，请指定m:);scanf(%d,&m);f[1]=1;f[2]=2;k=2;for(a=3;a=n;a++){j=a;while(j%2==0)j=j/2;//反复用2试商while(j%3==0)j=j/3;//反复用3试商if(j==1){k++;f[k]=a;}}printf(幂序列中小于%ld的项数为：%d\n,n,k);if(m=k)printf(从小到大排序的第%d项为：%ld\n,m,f[m]);elseprintf(所输入的m大于序列的项数！\n);}（3）程序运行示例计算小于n的项数，请指定n:10000000输出序列的第m项，请指定m:100幂序列中小于10000000的项数为：190从小到大排序的第100项为：9331273.递推排序求解（1）递推算法设计1）确定递推关系为探索x+y=i时各项与x+y=i−1时各项之间的递推规律，剖析x+y的前若干项情形：x+y=0时，元素为1（初始条件）；x+y=1时，元素为2*1=2,3*1=3，共2项；x+y=2时，序列有2*2=4,2*3=6,3*3=9，共3项；x+y=3时，序列有2*2*2=8,2*2*3=12,2*3*3=18,3*3*3=27，共4项；……可归纳出以下递推关系：x+y=i时，序列共i+1项，其中前i项是x+y=i−1时的所有i项分别乘2所得；最后一项为x+y=i−1时的最后一项乘3所得（即t=3^i）。注意，对x+y=i−1的所有i项分别乘2，设为f[h]*2，必须检测是否小于n而大于0。同样，对t也必须检测是否小于n而大于0。只有小于n且大于0时