第3讲递推专题讲座 acm

1、第3讲 递推递推是一种应用非常广泛的常用算法之一，与下一章的递归有着密切的联系。本章探讨递推在求解数列、数阵以及计数等应用案例方面的应用。3.1 递推概述在纷繁变幻的世界，所有事物都随时间的流逝发生着微妙的变化。许多现象的变化是有规律可循的，这种规律往往呈现出前因后果的关系。某种现象的变化结果与紧靠它前面变化的一个或一些结果紧密关联。递推的思想正体现了这一变化规律。3.1.1 递推算法所谓递推，是在命题归纳时，可以由nk,n1的情形推得n的情形。一个线性递推可以形式地写成其中f(n)=0时递推是齐次的，否则是非齐次的。递推的一般解法要用到n次方程的求根。递推关系是一种高效的数学模型，是组合数学

2、中的一个重要解题方法，在组合计数中有着广泛的应用。在概率方面利用递推可以解决一类基本事件个数较大的概率问题。在对多项式的求解过程中，很多情况可以使用递推算法来实现。 在行列式方面，某些n阶行列式只用初等变换难以解决，但如果采用递推求解则显得较为容易。递推关系不仅在各数学分支中发挥着重要的作用，由它所体现出来的递推思想在各学科领域中更是显示出其独特的魅力。递推是利用问题本身所具有的一种递推关系求解问题的一种方法。设要求问题规模为n的解，当n=1时，解或为已知，或能非常方便地得到解。能采用递推法构造算法的递推性质，能从已求得的规模为1,2,i1的一系列解，构造出问题规模为i的解。这样，程序可从i=

3、0或i=1出发，重复地由已知至i1规模的解，通过递推，获得规模为i的解，直至得到规模为n的解。递推算法的基本思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法充分利用了计算机的运算速度快和不知疲倦的特点，从头开始一步步地推出问题最终的结果。使用递推算法编程，既可使程序简练，又可节省计算时间。对于一个序列来说，如果已知它的通项公式，那么要求出数列中某项之值或求数列的前n项之和是简单的。但是，在许多情况下，要得到数列的通项公式是困难的，甚至无法得到。然而，一个有规律的数列的相邻位置上的数据项之间通常存在着一定的关系，可以借助已知的项，利用特定的关系逐项推算出它的后继项的值，直到找到所

4、需的那一项为止。递推算法避开了求通项公项的麻烦，把一个复杂的问题的求解，分解成连续的若干步简单运算。递推算法的首要问题是得到相邻的数据项之间的关系，即递推关系。它针对这样一类问题：问题的解决可以分为若干步骤，每个步骤都产生一个子解（部分结果），每个子解都是由前面若干子解生成。不同的子解，其所相关的问题规模也随子解不同而递增。我们把这种由前面的子解得出后面的子解的规则称为递推关系。我们在设计求解问题前，要通过细心的观察，丰富的联想，不断尝试推理，尽可能归纳总结其内在规律，然后再把这种规律性的东西抽象成递推数学模型。3.1.2 递推实施步骤与描述利用递推求解实际问题，需要掌握递推的具体描述及其实施

5、步骤。1实施递推的步骤（1）确定递推变量应用递推算法解决问题，要根据问题的具体实际设置递推变量。递推变量可以是简单变量，也可以是一维或多维数组。 （2）建立递推关系递推关系是指如何从变量的前一些值推出其下一个值或从变量的后一些值推出其上一个值的公式（或关系）。递推关系是递推的依据，是解决递推问题的关键。有些问题，其递推关系是明确的，大多数实际问题并没有现成的明确的递推关系，需根据问题的具体实际，细心的观察，丰富的联想，不断尝试推理，才能确定问题的递推关系。（3）确定初始（边界）条件对所确定的递推变量，要根据问题最简单情形的数据确定递推变量的初始（边界）值，这是递推的基础。（4）对递推过程进行控

6、制递推过程不能无休止地重复执行下去。递推过程在什么时候结束，满足什么条件结束，这是编写递推算法必须考虑的问题。递推过程的控制通常可分为两种情形：一种是所需的递推次数是确定的值，可以计算出来；另一种是所需的递推次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对递推过程的控制；对于后一种情况，需要进一步分析出用来结束递推过程的条件。2递推算法框架描述递推通常由循环来实现，一般在循环外确定初始（边界）条件，在设置的循环中实施递推。下面归纳常用的递推模式并作简要的框架描述。首先，从递推流向可分为顺推与逆推。（1）简单顺推算法顺推即从前往后推，从已求得的规模为1,2,i1的一系列解，推出问

7、题规模为i的解，直至得到规模为n的解。简单顺推算法框架描述：f(1i1)=； / 确定初始值 for(k=i;k=n;k+) f(k)=； / 根据递推关系实施递推 printf(f(n)； / 输出n规模的解f(n) （2）简单逆推算法逆推即从后往前推，从已求得的规模为n,n1,i+1的一系列解，推出问题规模为i的解，直至得到规模为1的解。简单逆推算法框架描述：f(ni+1)=； / 确定初始值 for(k=i;k=1;k) f(k)=； / 根据递推关系实施递推 printf(f(1)； / 输出解f(1) 简单递推问题设置一维数组实现，较复杂的递推问题需设置二维或二维以上数组。例如当规模

8、为i的解为规模为1,2,i1的解通过计算处理决定时，可设置二重循环处理这一较为复杂的递推。（3）二维数组顺推算法设递推的二维数组为f(k,j)，1kn,1jm，由初始条件分别求得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,1m)=； / 赋初始值 for(k=2;k=n;k+)for(j=1;j=m;j+) f(k,j)=； / 根据递推关系实施递推 printf(f(n,m)； / 输

9、出n规模的解f(n,m) 二维或二维以上数组递推常用于动态规划设计的最优值求解过程。当递推关系包含两个或两个以上关系式时，通常应用多关系分级递推算法求解。（4）多关系分级递推算法f(1i1)=； / 赋初始值 for(k=i;k=n;k+) if() f(k)=； / 根据递推关系1实施递推 if() f(k)=； / 根据递推关系2实施递推 if() f(k)=； / 根据递推关系m实施递推 printf(f(n)； / 输出n规模的解f(n) 关于递推的时间复杂度，如果在一重循环中可完成递推，通常其相应的时间复杂度为O(n)。在实际应用中，由于递推关系的不同，往往需要二重或更复杂的循环结构

10、才能完成递推，其相应的时间复杂度为O(n2)或更高。3.2 递推数列3.2.1 摆动数列1. 安全提出已知递推数列：a(1)=1,a(2i)=a(i)+1,a(2i+1)=a(i)+a(i+1)，（i为正整数），试求该数列的第n项与前n项中哪些项最大?最大值为多少?。2. 算法设计该数列分项序号为奇或偶两种情况作不同递推,所得数列呈大小有规律的摆动.设置a数组,赋初值a(1)=1.根据递推式,在循环中分项序号i(2n)为奇或偶作不同递推:mod(i,2)=0(即i为偶数),a(i)=a(i/2)+1.mod(i,2)=1(即i为奇数),a(i)=a(i+1)/2)+a(i-1)/2)每得一项a

11、(i),与最大值max作比较,如果a(i)max,则max=a(i).最后,在所有项中搜索最大项(因最大项可能多于一项),并打印最大值max.3. 程序设计/* 摆动数列 */#include void main() int i,n,max,a10000; printf( 请确定项数n: ); scanf(%d,&n); a1=1;max=0; for(i=2;imax) max=ai; printf( a(%d)=%d n,n,an);printf( 摆动数列前%d项中最大项有：,n);for(i=2;ic(i-1)，同时可证当i2时，第i个分数的分子c(i)总小于第i-1个分数的分母d(i

12、-1)。置k在区间(c(i-1),d(i-1)取值，k分别与d(1),d(2),.d(i-1)比较，若有相同，则k增1后再比较；若没有相同的，则产生第i项，作赋值: c(i)=k，d(i)=k+i。为了准确求出数列前n项中的最大项，设最大项为第x项(x赋初值1)，每产生第i项，如果有 c(i)/d(i)c(x)/d(x) c(i)*d(x)c(x)*d(i)即第i项要比原最大的第x项大，则作赋值x=i，把产生的第i项确定为最大项。产生第n项后，前n项中的最大项也比较出来了。在程序设计中比较最大项，用后一个整数不等式是适宜的，准确的。3. 程序设计 /* 分数递推数列*/ #include vo

13、id main() int n,i,k,t,j,kmax; long c3001,d3001; printf(请输入整数n(1-3000):); /* 键盘输入确定整数n */ scanf(%d,&n); c1=1; d1=2; c2=3;d2=5; kmax=1; /* 数组与最大项序号赋初值 */ for(i=3;i=n;i+) for(k=ci-1+1;kdi-1;k+) t=0; /* k穷举探求第i项分子c */ for(j=1;jckmax*di) kmax=i; /* 比较得最大项的序号kmax */ printf(数列第%d项为: %ld/%ld。n,n,cn,dn); pri

14、ntf(数列前%d项中最大项为,n); for(i=1;i=n;i+) /* 检查有多个最大项时输出 */ if(ci*dkmax=ckmax*di) printf(第%d项: %ld/%ld。n,i,ci,di); 4. 程序运行示例请输入整数n(1-3000):2011数列第2011项为: 3253/5264。数列前2011项中最大项为第1597项: 2584/4181。3.3 幂序列本节探讨双幂序列与双幂积序列这两个典型的递推序列问题的求解。3.3.1 双幂序列1. 案例提出设x,y为正整数，试计算集合的元素由小到大排列的双幂序列第n项与前n项之和。2. 递推算法设计集合由2的幂与3的幂

15、组成，实际上给出的是两个递推关系。显然，第1项也是最小项为1（当x=y=0时）。从第2项开始，为了实现从小到大排列，设置a,b两个变量，a为2的幂，b为3的幂，显然ab。设置k循环（k=2,3,n，其中n为键盘输入整数），在k循环外赋初值：a=2;b=3;s=1;在k循环中通过比较赋值：当ab时，由赋值fk=b确定为序列的第k项；然后b=b*3，即b按递推规律乘3，为后一轮比较作准备。递推过程描述：a=2;b=3; / 为递推变量a,b赋初值 for(k=2;k=n;k+) if(ab) fk=a;a=a*2; / 用a给fk赋值 else fk=b;b=b*3; / 用b给fk赋值 在这一算

16、法中，变量a,b是变化的，分别代表2的幂与3的幂。上述递推算法的时间复杂度与空间复杂度均为O(n)。3. 双幂序列程序实现/ 双幂序列求解 #include void main()int k,m,t,p2,p3; double a,b,s,f100; printf( 求数列的第m项与前m项和,请输入m: ); scanf(%d,&m); f1=1;p2=0;p3=0; a=2;b=3;s=1; for(k=2;k=m;k+) if(a1，说明原a有2，3以外的因数，不属于该序列。若j=1，说明原a只有2，3的因数，为序列第k项赋值。由于实施从小到大穷举赋值，所得项无疑是从小到大的序列。当达到指

17、定的n，退出循环，输出指定项f(m)。(2) 穷举程序实现/ 幂序列2x*3y穷举求解 #include void main()int k,m; long a,j,n,f1000; printf( 计算小于n的项数，请指定n: ); scanf(%ld,&n); printf( 输出序列的第m项，请指定m: ); scanf(%d,&m);f1=1;f2=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+;fk=a; printf( 幂序列中小于%ld的项

18、数为：%dn,n,k); if(m=k) printf( 从小到大排序的第%d项为：%ldn,m,fm); elseprintf( 所输入的m大于序列的项数！n);（3） 程序运行示例计算小于n的项数，请指定n: 输出序列的第m项，请指定m: 100幂序列中小于的项数为：190从小到大排序的第100项为：933123. 递推排序求解（1）递推算法设计1） 确定递推关系为探索x+y=i时各项与x+y=i1时各项之间的递推规律，剖析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，共

19、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=i1时的所有i项分别乘2所得；最后一项为x+y=i1时的最后一项乘3所得（即t=3i）。注意，对x+y=i1的所有i项分别乘2，设为fh*2，必须检测是否小于n而大于0。同样，对t也必须检测是否小于n而大于0。只有小于n且大于0时才能赋值。这里要指出，最后若干行可能不是完整的，即可能只有前若干项能递推出新项。为此设置变量u: 当一行有递推项时u=1；否则u=0。只有当u=0时停止，否则会影响序列的项数。2） 以n=100

20、0为例说明递推的实施： f( 1)=1i= 1 f( 2)=2 f( 3)=3 i= 2 f( 4)=4 f( 5)=6 f( 6)=9 i= 3 f( 7)=8 f( 8)=12 f( 9)=18 f(10)=27 i= 4 f(11)=16 f(12)=24 f(13)=36 f(14)=54 f(15)=81 i= 5 f(16)=32 f(17)=48 f(18)=72 f(19)=108 f(20)=162 f(21)=243 i= 6 f(22)=64 f(23)=96 f(24)=144 f(25)=216 f(26)=324 f(27)=486 f(28)=729 i= 7 f

21、(29)=128 f(30)=192 f(31)=288 f(32)=432 f(33)=648 f(34)=972 i= 8 f(35)=256 f(36)=384 f(37)=576 f(38)=864 i= 9 f(39)=512 f(40)=768每一列的下一个数是上一个数的2倍。而每一行的最后一数为3的幂。当所有递推项完成后，对所有k项应用逐项比较进行从小到大排序。排序后输出指定的第m项。3） 递推描述 for(j=0;j=i-1;j+) h=ci-1+j; if(fh*20) k+;fk=fh*2; / 用fh*2给fk赋值 if(j=0) ci=k; else break; t=

22、t*3;if(t0) k+;fk=t; / 用t给fk赋值 （2）递推排序程序实现/ 递推排序求解 #include void main()int i,j,h,k,m,u,c100; double d,n,t,f1000; printf( 计算小于n的项数，请指定n: ); scanf(%lf,&n); printf( 输出序列的第m项，请指定m: ); scanf(%d,&m); k=1;t=1.0; i=1;c0=1; f1=1.0; while(1) u=0; for(j=0;j=i-1;j+) h=ci-1+j; if(fh*20) / 第i行各项为前一行各项乘2 k+;fk=fh*2

23、;u=1; if(j=0) ci=k; / 该行的第1项的项数值赋给c(i) else break; t=t*3; / 最后一项为3的幂 if(t0) k+;fk=t; / 用t给fk赋值 if(u=0) break; i+; for(i=1;ik;i+) / 逐项比较排序 for(j=i+1;jfj) d=fi;fi=fj;fj=d; printf( 幂序列中小于%f的项数为：%dn,n,k); if(m=k) printf( 从小到大排序的第%d项为：%.0fn,m,fm); elseprintf( 所输入的m大于序列的项数！n);（3）程序运行示例 计算小于n的项数，请指定n: 输出序列

24、的第m项，请指定m: 300 幂序列中小于的项数为：306 从小到大排序的第300项为：4. 递推结合比较赋值求解（1） 设计要点从u=1, f(u)=1开始, 在已求得f(u)的基础上,可递推地求出f(u+1)：求出各大于f(u)的最小数, 取其中最小者即为f(u+1)。递推结合比较赋值设置永真外循环，实施乘2的内循环。首先，从p=0开始，若qp=fu，则递推得一个3的幂即qp=3p，并赋给最小值标志量h。然后转入内循环i(0p-1)中，若qi=fu，则qi乘2,即qi=2*qi。然后qi与h比较，即2j*3i（in，表明递推结合比较赋值完成，退出外循环，输出序列的项数u与序列中指定的项fm

25、后结束。（2） 递推结合比较赋值程序设计 / 求3i * 2jn的项数及从小到大第m项 #include void main() int i,m,u,p;double n,h,f1000,q100;printf( 计算小于n的项数，请指定n: );scanf(%lf,&n);printf( 输出序列的第m项，请指定m: );scanf(%d,&m);u=1; fu=1.0; p=0; qp=1.0;while(1) if(qp=fu) p+; qp=3*qp-1; h=qp; / 递推3的幂，qp=3p for(i=0;ip;i+) if(qi=fu) qi*=2; / 幂积qi=2j*3i,

26、j=1,2,3, if(qin) break; u+;fu=h; printf( 幂序列中小于%.0f的项数为：%dn,n,u); if(m=u) printf( 从小到大排序的第%d项为：%.0fn,m,fm); else printf( 所输入的m大于序列的项数！n);（3） 程序运行示例计算小于n的项数，请指定n: 000 输出序列的第m项，请指定m: 600 幂序列中小于000的项数为：624 从小到大排序的第600项为：365. 三个算法时间复杂度比较以上求幂积序列的三个程序，当n很大时，递推求解的速度明显快于穷举。（1） 穷举复杂度分析穷举算法简单明了，对整数a操作，每一个a进行除

27、2、除3操作，平均估算为10次，整个n个数的操作为10n次，算法复杂度为O(n)。（2） 递推排序算法复杂度分析递推排序算法对序列项数进行操作，当n充分大时，项数。其中逐项比较排序的时间复杂度是O(n2)即O(k2)，因而递推排序算法的时间复杂度为O。（3） 递推结合比较赋值算法复杂度分析 外循环次数为序列项数u，当n充分大时，项数。内循环i(0p-1)，p为幂指数: ，即。注意到p是从0增长的，每一项按平均即p/2估算，因而得递推结合比较赋值算法复杂度为O()。当n充分大时，有。可见以上三种算法中，递推结合比较赋值算法时间最省，而穷举所需时间较长。3.4 数阵探索3.4.1 杨辉三角1. 案

28、例提出杨辉三角，历史悠久，是我国古代数学家杨辉揭示二项展开式各项系数的数字三角形。我国北宋数学家贾宪约1050年首先使用“贾宪三角”进行高次开方运算，南宋数学家杨辉在详解九章算法记载并保存了“贾宪三角”，故称杨辉三角。元朝数学家朱世杰在四元玉鉴扩充了“贾宪三角”成“古法七乘方图”。在欧洲直到1623年以后，法国数学家帕斯卡才发现了“帕斯卡三角”。 杨辉三角构建规律主要包括横行各数之间的大小关系以及不同横行数字之间的联系，奥妙无穷：每一行的首尾两数均为1；第k行共k个数，除首尾两数外，其余各数均为上一行的肩上两数的和。如图3-1为5行杨辉三角。 图3-1 5行杨辉三角形设计程序，打印杨辉三角形的

29、前n行(n从键盘输入)。2. 应用数组递推设计（1）设计要点考察杨辉三角形的构成规律，三角形的第i行有i个数，其中第1个数与第i个数都是1，其余各项为它的两肩上数之和(即上一行中相应项及其前一项之和)。 设置二维数组a(n,n),根据构成规律实施递推: 递推关系: a(i,j)=a(i-1,j-1)+a(i-1,j) (i=3,，n;j=2，i-1) 初始值: a(i,1)=a(i,i)=1 (i=1,2,，n)为了打印输出左右对称的等腰数字三角形, 设置二重循环: 设置i控制打印n行，每一行开始换行，打印40-3i个前导空格；设置j循环控制打印第i行的各数组元素a(i,j)。（2）杨辉三角形

30、程序实现/ 杨辉三角形 #includevoid main()int n,i,j,k,a2020; printf( 请输入行数n: ); scanf(%d,&n); for(i=1;i=n;i+) ai1=1;aii=1; / 确定初始条件 for(i=3;i=n;i+)for(j=2;j=i-1;j+) aij=ai-1j-1+ai-1j; / 递推得到每一数组元素 for(i=1;i=n;i+) / 控制输出n行 for(k=1;k=40-3*i;k+) printf( ); for(j=1;j=i;j+) / 控制输出第i行的元素 printf(%6d,aij); printf(n);

31、（3） 程序运行示例运行程序，输入n=10，则打印10行杨辉三角形如图59-2所示。 图59-2 10行的杨辉三角形3. 应用变量迭代设计（1） 设计要点杨辉三角形实际上是二项展开式各项的系数，即第n+1行的n+1个数分别是从n个元素中取0，1，n个元素的组合数c(n,0),c(n,1),，c(n,n)。注意到 c(n,0)=1 c(n,k)=(n-k+1)/k*c(n,k-1) (k=1,2,n)根据这一递推规律，可不用数组，直接应用变量递推求解。（2）迭代程序设计/ 应用变量迭代求解 #includevoid main()int m,n,cnm,k; printf( 请输入行数n: );

32、scanf(%d,&n); for(k=1;k=40;k+) printf( ); printf(%6d n,1); / 输出第1行的1 for(m=1;m=n-1;m+) for(k=1;k=40-3*m;k+) printf( ); cnm=1; printf(%6d,cnm); / 输出每行开始的1 for(k=1;k=m;k+) cnm=cnm*(m-k+1)/k; / 计算第m行的第k个数 printf(%6d,cnm); printf(n); 由以上两个不同的递推实现杨辉三角可以看到，递推方式并不是一成不变的，往往有多种方式可供选择。3.4.2 折叠方阵1. 案例提出定义n阶间断折

33、叠方阵是把从起始数1开始的n2个整数折叠为n行n列的n阶方阵：起始数1置于方阵的左上角，然后从起始数开始递增，每一层从第1行开始，先竖向下再折转向右，层层折叠地排列为间断折叠方阵。n阶回转折叠方阵是把起始数1置于方阵的左上角，然后从起始数开始递增，偶数层从第1行开始，先竖向下再折转向右；奇数层从第1列开始，先横向右再竖向上，呈首尾连接，层层折叠地排列为回转折叠方阵。下图所示为5阶间断折叠方阵与5阶回转折叠方阵。1 2 5 10 17 1 2 9 10 254 3 6 11 18 4 3 8 11 249 8 7 12 19 5 6 7 12 2316 15 14 13 20 16 15 14

34、13 2225 24 23 22 21 17 18 19 20 215阶间断折叠方阵 5阶回转折叠方阵 试递推构造并输出指定n阶间断折叠方阵与回转折叠方阵。2. 折叠方阵递推设计设置二维数组z，从给定的起始数1开始，按递增1取值，据间断折叠方阵的构造特点给二维数组z(n,n)赋值。显然起始数1赋值给z(1,1)。除z(1,1)外，n阶方阵还有叠折的n1层：第i层(i=2,3,n)的起始位置为(1,i)，随后列号y不变行号x递增，至x=i时折转，行号x不变列号y递减，至y=1时该层结束，在每一位置分别按递增值赋值给z(x,y)。间断递推过程描述： n=1;z11=1;for(i=2;i=m;i+

35、) /* 方阵共m层 */ x=1;y=i;n+; zxy=n; while(x1) zx-y=+n; 回转递推过程的偶数层与间断递推过程相同，奇数层赋值改变为：if(i%2=1) x=i;y=1;n+; zxy=n; while(y1) z-xy=+n; 在一个程序中构造这两种折叠方阵，可设置选择交互变量t实现。赋值完成，用二重循环打印输出顺时针折叠方阵。3. 两种折叠方阵程序设计/* 两种折叠方阵 */#includevoid main() int i,m,n,t,x,y,z2020; printf( 1:间断型 2：回转型，请选择:); scanf(%d,&t); printf( m阶折

36、叠方阵,请确定m:); scanf(%d,&m); n=1;z11=n; /* n与数组z赋初值 */ for(i=2;i=m;i+) /* 方阵共m层 */ if(t=1 | t=2 & i%2=0) x=1;y=i;n+; /* 间断型，回转型的偶数层赋值*/ zxy=n; while(x1) zx-y=+n; else /* 回转型的奇数层赋值 */ x=i;y=1;n+; zxy=n; while(y1) z-xy=+n; if(t=1) printf( %d阶间断折叠方阵：n,m);else printf( %d阶回转折叠方阵：n,m);for(x=1;x=m;x+) /* 打印m阶

37、折叠方阵 */ for(y=1;y=m;y+)printf(%4d,zxy); printf(n);4. 程序变通 如果以上两种方阵起始不是1，而是某一指定的整数a,只须把变量n赋初值1改成赋初值a，即n=a即可。试把输出方阵的语句修改为：printf(%4d,zyx);即x,y互换，请观察输出的两种折叠方阵有什么改变？3.5 整数划分问题正整数s（简称为和数）的划分（又称分划或拆分）是把s分成为若干个正整数（简称为零数或部分）之和，划分式中允许零数重复，且不记零数的次序。试求s=12共有多少个不同的划分式？展示出所有这些划分式。3.5.1 整数划分递推设计1探索划分的递推关系为了建立递推关系

38、，先对和数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；5由以上各划分看到，除和数本身k=k这一特殊划分式外，其它每一个划分式至少为两项之和。约定在所有划分式中零数作不减排列，探索和数k的划分式与和数k1的划分式存在以下递推关系：（1）在所有和数k1的划分式前加零数1都是和数k的划分式。（2）和数k1的划分式的前两个零数作比较，如果第1个零数x1小于第2个零数x2，则把第1个零数加1后成为和数k的划分式。2递推算法设计设置三维数

39、组a，a(k, j, i)为和数k的第j个划分式的第i个数。从k=2开始，显然递推的初始条件为：a(2,1,1)=1；a(2,1,2)=1; a(2,2,1)=2。根据递推关系，实施递推：（1）实施在k1所有划分式前加1操作a(k,j,1)=1; for(t=2;t=k;t+) a(k,j,t)=a(k1,j,t1); / k1的第t1项变为k的第t项 （2）若k1划分式第1项小于第2项，第1项加1，变为k的第i个划分式 if(a(k1,j,1)a(k1,j,2) a(k,i,1)=a(k1,j,1)+1; for(t=2;t=k1;t+) a(k,i,t)=a(k1,j,t); 以上递推算法的时间复杂度与空间复杂度为O(n2u)，其中u为n划分式个数。注意到u随n增加非常快，难以估算其数量级，其时间复杂度与空间复杂度是很高的。3整数划分的程序实现/ 整数s划分展示 #include void main() int s,i,j,k,t,u; static int a2180021; printf(input s(s=20):);