2014程序设计竞赛培训题解答(1)

1、2014程序设计竞赛培训题解答（1）1. 统计n! 尾部零试统计正整数n的阶乘n!=123n尾部连续零的个数。数据检测：n=2015；n=20142015解：以下试用两种不同的算法分别进行求解。（1） 基本求积算法1） 算法概要注意到输入整数n规模可能较大，n! 尾部零的个数也就相应地多，设计a数组存储n!的各位数字，a1存储个位数字，a2存储十位数字，余类推。 试模拟整数竖式乘运算实施精确计算（详见第8章）。首先通过常用对数累加和s=lg2+lg3+lgn确定n!的位数m=s+1,即a数组元素的个数。设置2重循环，模拟整数竖式乘法实施各数组元素的累乘：乘数k：k=2,3,n；累乘积各位aj：

2、j=1,2,m；实施乘运算： t=aj*k+g; / 第j位乘k，g为进位数 aj=t%10; / 乘积t的个位数字存于本元素 g=t/10; / 乘积t的十位以上数字作为进位数尾部连续零的个数统计： 从j=1时低位aj开始，aj=0时j+;作统计，直到aj!=0时结束。2） 算法描述/ 计算n!（n10000）尾部零个数,c134#include #include void main() int j,k,m,n,a40000; long g,t;double s; printf( 请输入正整数n(n10000): ); scanf(%d,&n); / 输入n s=0; for(k=2;k=n

3、;k+) s+=log10(k); / 对数累加确定n!的位数m m=(int)s+1; for(k=1;k=m;k+) ak=0; / 数组清零 a1=1;g=0; for(k=2;k=n;k+) for(j=1;j=m;j+) t=aj*k+g; / 数组累乘并进位 aj=t%10; g=t/10; j=1; while(aj=0) j+; printf( %d! 尾部连续零共%d个。n,n,j-1); / 输出n! 尾部零个数（2） 统计“5”因子设计1） 设计思路注意到n! 尾部连续零是n!中各相乘数2，3，n中“2”的因子与“5”的因子相乘所得，一个“2”的因子与一个“5”的因子得一

4、个尾部“0”。显然，n!中各个相乘数2，3，n中“2”的因子数远多于“5”的因子数，因而n! 尾部连续零的个数完全由n!中各个相乘数2，3，n中的“5”因子个数决定。设n!中各个相乘数2，3，n中“5”的因子个数为s，显然有其中x为不大于x的最大正整数，正整数m满足。这里统计s只需设计一个简单的条件循环即可实现。2） 算法描述/ 统计“5”因子设计,c135 #include void main() long n,s,t; printf( 请输入正整数n: ); scanf(%ld,&n); / 输入n s=0;t=1; while(tn，把m换算为n， m数量级估算平均为n*logn，因而基

5、本求积算法的时间复杂度为O(n2logn)，空间复杂度为O(nlogn)。统计“5”因子的设计大大简化了n! 尾部连续零个数的统计，算法的时间复杂度为O(logn)，空间复杂度为O(1)，显然大大优于基本求积算法。统计“5”因子设计可大大拓展n的范围，例如输入n为20142015，可得20142015! 尾部连续零共5035500个，这一点基本求积算法因时间复杂度与空间复杂度太高而难以实现。若案例稍加变通，需求n!结果所有数字中零的个数，基本求积算法（修改统计零的个数）可实现，而统计“5”因子算法却无法完成。以上3个简单案例的求解都列举了两个不同的算法设计，并分析与比较了这些不同算法的时间复杂

6、度。可见求解一个实际案例时，算法可能有多种多样，我们不必局限于某一个定式或某一种模式，可根据案例的具体实际确定算法进行设计求解。当面临处理的数据规模很大、或运行算法的时间很长时，选择时间复杂度低的算法是必要的，这也是我们进行算法设计所追求的目标。2. 求最大公约数求n个正整数的最大公约数 ()。解：对于3个或3个以上整数，最大公约数有以下性质：(m1,m2,m3)=(m1,m2),m3)(m1,m2,m3,m4)=(m1,m2,m3),m4),应用这一性质，要求n个数的最大公约数，先求出前n1个数的最大公约数b，再求第n个数与b的最大公约数；要求n1个数的最大公约数，先求出前n2个数的最大公约

7、数b，再求第n1个数与b的最大公约数；依此类推。因而，要求n个整数的最大公约数，需应用n1次欧几里德算法来完成。为输入与输出方便，把n个整数设置成m数组，m数组与变量a,b,c,r与m数组设置为长整型变量，个数n与循环变量k设置为整型，这就是数据结构。设置k（1n-1）循环，完成n-1次欧几里德算法，最后输出所求结果。/ 求n个整数的最大公约数,c143#include /C头文件的调用void main() int k,n; long a,b,c,r,m100; printf(请输入整数个数n: );/ 输入原始数据 scanf(%d,&n); printf(请依次输入%d个整数: ,n);

8、 for(k=0;k=n-1;k+) printf(n请输入第%d个整数： ,k+1); scanf(%ld,&mk); b=m0; for(k=1;k=n-1;k+) / 控制应用n1次欧几里德算法 a=mk; if(ab r=a%b; while(r!=0) a=b;b=r; / 实施辗转相除 r=a%b; printf(%ld,m0); / 输出求解结果 for(k=1;k=n-1;k+) printf(,%ld,mk); printf()=%ldn,b);程序运行示例：请输入整数个数n: 4请依次输入4个整数:请输入第1个整数： 10247328请输入第2个整数： 12920544请输

9、入第3个整数： 17480736请输入第4个整数： 22859424(10247328,12920544,17480736,22859424)=2016/ 实现欧几里德算法的函数,c144long gcd(long a,long b) long c,r;if(ab r=a%b; while(r!=0) a=b;b=r; / 实施辗转相除 r=a%b; return b;/ 求n个整数的最大公约数,c145#includevoid main() int k,n; long x,y,m100; printf(请输入整数个数n: ); scanf(%d,&n); printf(请依次输入%d个整数:

10、 ,n); for(k=0;k=n-1;k+) printf(n请输入第%d个整数： ,k+1); scanf(%ld,&mk); x=m0; for(k=1;k=n-1;k+) y=mk; x=gcd(x,y); printf(%ld,m0); for(k=1;k=n-1;k+) printf(,%ld,mk); printf()=%ldn,x);3. 喝汽水某学院有m个学生参加南湖春游，休息时喝汽水。南湖商家公告：（1） 买1瓶汽水定价1.40元，喝1瓶汽水（瓶不带走）1元。（2） 为节约资源，规定3个空瓶可换回1瓶汽水，或20个空瓶可换回7瓶汽水。 （3） 为方面顾客，可先借后还。例如借

11、1瓶汽水，还3个空瓶；或借7瓶汽水，还20个空瓶。问m个学生每人喝1瓶汽水（瓶不带走），至少需多少元？输入正整数m(2m10000)，输出至少需多少元（精确到小数点后第2位）。解：注意到春游喝汽水无需带走空瓶，根据商家的规定作以下分析。 （1） 如果人数为20人，买13瓶汽水，借7瓶汽水，饮完20瓶汽水后还20个空瓶（即相当于换回7瓶汽水还给商家），两清。此时每人花费为13/20*1.40=0.91元 （2） 如果人数为3人，买2瓶汽水，借1瓶汽水，饮完3瓶汽水后还3个空瓶（即相当于换回1瓶汽水还给商家），两清。此时每人花费为2/3*1.40=0.93元（3） 如果只有2人或1人，每人喝1瓶汽

12、水（瓶不带走），此时每人花费1元。（4） 注意到0.910.931，因而有以下的最省钱算法：1） 把m人分为x=m/20个大组，每组20人。每组买13瓶汽水（借7瓶汽水），饮完后还20个空瓶（即相当于换回7瓶汽水还给商家），两清。2） 剩下t=m-x*20人，分为y=t/3个小组，每组3人。每组买2瓶汽水（借1瓶汽水），饮完后还3个空瓶（即相当于换回1瓶汽水还给商家），两清。3） 剩下t=m-x*20-y*3人，每人花1元喝1瓶。该算法得所花费用最低为：(13*x+2*y)*1.40+t元。（5） 费用最低的算法描述/ 喝汽水 main() long m,t,x,y;printf( 请输入m：

13、); scanf(%ld,&m);x=m/20; / 分x个大组，每组买13瓶汽水，借7瓶t=m-20*x; / 剩下大组外的t人y=t/3; / 剩下t人分y个小组，每组买2瓶汽水，借1瓶t=m-20*x-3*y; / 剩下大小组外的t人，每人花1元喝1瓶printf( 喝%ld瓶汽水，需%.2f元。n,m,(13*x+2*y)*1.40+t); 该算法有输入，即输入人数m；有处理，即依次计算大组数x、小组数y与剩下的零散人数t；有输出，即输出最省费用。4. 全素组如果不大于指定整数n的3个素数之和仍为素数，则把这3个素数称为一个基于n的全素组。例如对于n=15, 素数3,5,11之和3+5

14、+11=19为素数，则3,5,11称为一个基于15的全素组。定义所有基于n的全素组中和最大的称为最大全素组。输入整数n（n3000），输出基于n的全素组的个数，并输出一个最大全素组。数据测试： 2015 / 全素组探求，c221 #include #include void main() int i,j,k,i2,j2,k2,n,s,t,w,z,max,p9000,q1500;long m; printf( 请输入整数n: ); scanf(%d,&n); for(i=3;i=3*n;i=i+2) t=1;z=(int)sqrt(i);for(j=3;j=z;j=j+2) if(i%j=0)

15、t=0;break;if(t=1) pi=1; / 奇数i为素数时标记pi=1w=0;for(i=3;i=n;i=i+2)if(pi=1)w+;qw=i; / 共w个不大于n的奇素数赋给q数组m=0; max=0;for(i=1;i=w-2;i+) / 设置三重循环枚举所有三个素数组for(j=i+1;j=w-1;j+)for(k=j+1;kmax) / 比较并记录最大全素组max=s;i2=qi;j2=qj;k2=qk; printf( 共有%ld个全素组; n,m); if(m0) printf( 一个最大全素组为：%d+%d+%d=%ldn,i2,j2,k2,max);4. 程序运行示例

16、与分析请输入整数n: 2015共有1345431个全素组;一个最大全素组为：1997+2003+2011=6011 5. 最简真分数 统计分母在指定区间10,99的最简真分数(分子小于分母，且分子分母无公因数)共有多少个，并求这些最简真分数的和。设计求解一般情形：统计分母在指定区间a,b的最简真分数的个数,并求这些最简真分数的和(正整数a,b从键盘输入)。设分数分子为i，分母为j，最简真分数的个数为m，其和为s。在指定范围a,b内枚举分数的分母j:ab；同时对每一个分母j枚举分子i:1j-1。对每一分数i/j，置标志t=0，然后进行是否存在公因数的检测。如果分子i与分母j存在大于1的公因数u，

17、说明i/j非最简真分数,应予舍略。因为分子分母同时约去u后，分母可能不在a,b，即使在a,b时前面已作了统计求和。注意到公因数u的取值范围为2,i，因而设置u循环在2,i中枚举，若满足条件 j%u=0 & i%u=0说明分子分母存在公因数，标记t=1后退出，不予统计与求和。否则保持原t=0，说明分子分母无公因数，用n实施迭代“m=m+1或m+”统计个数，应用s实施迭代求和。为操作方便分子分母等变量设置为整型。注意到和可能存在小数，和变量s设置为双精度double型，因而求和时要注意把分数i/j转变为double型。3求最简真分数程序设计/ 求分母在a,b的最简真分数的个数及其和,c222 #i

18、nclude #include void main()int a,b,i,j,t,u;long m=0; double s; printf( 最简真分数分母在a,b内,请确定a,b: );scanf(%d,%d,&a,&b); / 输入区间的上下限 s=0; for(j=a;j=b;j+) / 枚举分母 for(i=1;i=j-1;i+) / 枚举分子 for(t=0,u=2;u=i;u+) / 枚举因数 if(j%u=0 & i%u=0) t=1;break; / 分子分母有公因数舍去 if(t=0) m+; / 统计最简真分数个数 s+=(double)i/j; / 求最简真分数和 pri

19、ntf( 最简真分数共m=%ld个。 n,m);printf( 其和 s=%.5f n,s);4. 程序运行与分析最简真分数分母在a,b内,请确定a,b: 100,999最简真分数共m=300788个。其和 s=150394.00000 6. 佩尔方程佩尔(Pell)方程是关于x,y的二次不定方程，表述为 （其中n为非平方正整数）当x=1或x=-1，y=0时，显然满足方程。常把x,y中有一个为零的解称为平凡解。我们要求佩尔方程的非平凡解。佩尔方程的非平凡解很多，这里只要求出它的最小解，即x,y为满足方程的最小正数的解，又称基本解。输入非平方整数n，输出佩尔方程：的一个基本解。数据测试： n=7

20、3;n=20141. 案例背景佩尔(Pell)方程是关于x,y的二次不定方程，表述为 （其中n为非平方正整数）当x=1或x=-1，y=0时，显然满足方程。常把x,y中有一个为零的解称为平凡解。我们要求佩尔方程的非平凡解。佩尔方程的非平凡解很多，这里只要求出它的最小解，即x,y为满足方程的最小正数的解，又称基本解。对于有些n，尽管是求基本解，其数值也大得惊人。这么大的数值，如何求得？其基本解具体为多少？可以说，这是自然界对人类计算能力的一个挑战。十七世纪曾有一位印度数学家说过，要是有人能在一年的时间内求出x2-92y2=1的非平凡解，他就算得上一名真正的数学家。由此可见，佩尔方程的求解是有趣的，

21、其计算也是繁琐的。试设计程序求解佩尔方程：。2. 枚举设计要点应用枚举试值来探求佩尔方程的基本解。设置y从1开始递增1取值，对于每一个y值，计算a=n*y*y后判别:若a+1为某一整数x的平方，则(x,y)即为所求佩尔方程的基本解。若a+1不是平方数，则y增1后再试，直到找到解为止。应用以上枚举探求，如果解的位数不太大，总可以求出相应的基本解。如果基本解太大，应用枚举无法找到基本解，可约定一个枚举上限，例如10000000。可把y10000000时结束循环，输出“未求出该方程的基本解！”而结束。3. 解 PELL方程程序设计/ 解 PELL方程: x2-ny2=1, c231 #include

22、 #include void main()double a,m,n,x,y; printf( 解PELL方程: x2-ny2=1.n); printf( 请输入非平方整数 n:); scanf(%lf,&n); m=floor(sqrt(n+1); if(m*m=n) printf( n为平方数,方程无正整数解!n); return; y=1;while(y10000000)printf( 未求出该方程的基本解！); 4. 程序运行与分析 解PELL方程: x2-ny2=1.请输入非平方整数 n:73方程x2-73y2=1的基本解为: x=2281249, y=267000 为了提高求解方程的

23、范围，数据结构设置为双精度（double）型。如果设置为整形或长整形，方程的求解范围比设置为双精度型要小。例如n=73时，设置整形或长整形就不可能求出相应方程的解。可见，数据结构的设置对程序的应用范围有着直接的影响。以上枚举设计是递增枚举，枚举复杂度与输入的n没有直接关系，完全取决于满足方程的y的数量。解的y值小，枚举的次数就少。解的y值大，枚举的次数就多。对某些n，相应佩尔方程解的位数太大，枚举求解无法完成。例如当n=991时，相应佩尔方程的基本解达30位。此时依据以上枚举求解是无法实现的，只有通过某些专业算法（例如连分数法）才能进行求解。7. 分数不等式解不等式 这里正整数m1,m2从键盘

24、输入（m1m2）。数据测试：m1=2015,m2=2016 为一般计，解不等式 （2）这里正整数m1,m2从键盘输入（m1m2）。设和变量为s，递增变量为i，两者赋初值为0。在sm1退出循环，赋值c=i，所得c为n解区间的下限。继续在sm2退出循环，通过赋值d=i-1，所得d为n解区间的上限。注意，解的上限是d=i-1，而不是i。然后打印输出不等式的解区间c,d。3. 解分数不等式程序设计/ 解分数不等式,c241 #include #includevoid main() long c,d,i,m1,m2; double s; printf( 请输入正整数m1,m2(m1m2): ); sca

25、nf(%ld,%ld,&m1,&m2); i=0;s=0; while(s=m1) i=i+1;s=s+sqrt(i)/(i+1); c=i; do i=i+1;s=s+sqrt(i)/(i+1); while(s=m2); d=i-1; printf( 满足不等式的正整数n为: %ldn%ld n,c,d);4. 程序运行与分析请输入正整数m1,m2(m1m2): 2015,2016满足不等式的正整数n为: 1018402n1019411 以上枚举算法的循环次数取决于解n的上限d，当输入的参数m2越大时，n也就越大，枚举的复杂度也就越高。不等式中的上下限可取任意实数，请修改程序，把上下限m1

26、,m2改为从键盘输入的任意实数（0.5m1d，退出循环，得一个区间解n+1,。注意，此时n还须进行进一步检测。然后回过头来一项项求和，包括对n的检测，得离散解。3. 程序设计/ 解不等式：d1+1/2-1/3+1/4+1/5-1/6+.1/n ,c242 #include void main() long d,n,k; double s; printf( 请输入正整数d: ); scanf(%d,&d); printf( %dd) break; n=n+3; printf( n=%ld n,n+1); / 得一个区间解 k=1;s=0; while(k0) s=s+1.0/k; else s=

27、s-1.0/k; if(sd) / 得到离散解 printf( n=%ld n,k); k+; 4. 程序运行示例请输入正整数d: 55=203939n=203936 n=203938 注意：前一个是区间解，后2个是离散解。要特别注意，不要遗失离散解。5. 程序改进（1）改进要点上面的程序通过循环累加和判断可以得到区间解的下限，但离散解必须从头开始逐一试探才能够获得。如果设置条件循环，首先对前两项求和（即3/2）, 然后从第三项开始，每三项（包含一负二正）一起求和。若加到-1/n+1/(n+1)+1/(n+2)后，代数和sd，退出循环，得到第一个离散解n+2，且可以证明所有小于n+2的值都不是

28、解。注意，n+2只是第一个离散解，同时所有n+2+3k（k=1,2,.）至少都可以保证是离散解，对于区间解的下限还需要继续检测。为求区间解的下限，需要对第n+2项后的代数项进行逐项累加，并检测项n+2+3k-2或者n+2+3k-1（k=1,2,.）（由于项n+2+3k已经是离散解，因此并不需要对它们进行检测），直至sd止。这时所得的项n+2+3k-2或者n+2+3k-1即为区间解的下限。（2）程序设计/ 解不等式：d1+1/2-1/3+1/4+1/5-1/6+.1/n ，c243 #include void main() long d,n,k; double s; printf( 请输入正整数

29、d: ); scanf(%d,&d); printf( %dd) break; n=n+3; printf( n=%ld n,n+2);/ 打印第一个离散解n+2 k=n+2; while(1) if(s=s-1.0/(+k)d)break; if(s=s+1.0/(+k)d)break; s=s+1.0/(+k);printf( n=%ld n,k);/ 打印离散解k printf( n=%ld n,k);/ 打印区间解（3）程序运行示例请输入正整数d: 77=82273513 注意：前一个是离散解，而后一个是区间解。6. 分析与变通以上两个枚举算法的循环次数取决于解n的上限，当输入的参数d

30、越大时，n的上限也就越大，枚举的复杂度也就越高，求解也就变得越困难。例如当d逐渐增加到d7时，解值n会迅速增长而变得非常大，甚至超出相应变量的范围或计算机的计算范围，这时就不可能得到不等式的解。变通：请把不等式中“二正一负”的规律改变为“三正一负”，程序应如何修改？求出修改后的不等式大于5的解。9. 基于素数的代数和定义和： (和式中第k项(2k-1)/(2k+1)的符号识别：分子分母中有且只有一个素数，取“+”；分子分母中没有素数或两个都是素数时取“-”。)1) 求s(2016)(精确到小数点后5位)。2) 设1=n=2016，当n为多大时，s(n)最大。3) 设1=n=2016，当n为多大

31、时，s(n)最接近0。在求和之前应用“试商判别法”对第k个奇数2k-1是否为素数进行标注：若2k-1为素数，标注ak=1；否则，若2k-1不是素数，ak=0。设置k循环（1n），循环中分别情况求和：若ak+ak+1=1，即(2k-1)与(2k+1)中有且只有一个素数，实施“+”；否则，若ak+ak+1!=1，即(2k-1)与(2k+1)中没有素数或有两个素数，实施“-”。同时，设置存储最大值的变量smax，存储最接近“0”的绝对值变量mi。在循环中，每计算一个和值s，与smax比较确定最大值，同时记录此时的项数k1；因和s可正可负，s的绝对值与mi比较确定最接近“0”的绝对值，记录此时的项数k

32、2，同时记录此时的和值s2。最后，求和循环结束时输出所求值。3. 基于素数的分数和程序设计/ 基于素数的分数和,c251 #include#includevoid main() int t,j,n,k,k1,k2,a3000; double s,s2,smax,mi; printf( 请输入整数n: ); scanf(%d,&n); for(k=1;k=n+1;k+) ak=0; for(k=2;k=n+1;k+) for(t=0,j=3;j=sqrt(2*k-1);j+=2) if(2*k-1)%j=0) t=1;break; if(t=0) ak=1; / 标记第k个奇数2k-1为素数 s

33、=0;smax=0;mi=10; for(k=1;ksmax) smax=s;k1=k; / 比较求最大值smax if(fabs(s)mi) mi=fabs(s);k2=k;s2=s; / 绝对值比较求最接近0点 printf(s(%d)=%.5f n,n,s);printf(当k=%d时s有最大值: %.5fn,k1,smax);printf(当k=%d时s=%.5f最接近0. n,k2,s2); 4. 程序运行与分析请输入整数n: 2016s(2016)=-212.88337当k=387时s有最大值: 35.88835当k=785时s=-0.04341最接近0.以上枚举算法的运算量是n，

34、但标注素数的运算量为，因而枚举算法的时间复杂度为O()。变通： 请把题目中的条件“分子分母中有且只有一个素数，取+”，改为“分子分母中至少有一个素数，取+”，程序作何修改？并求出结果。10. 整数的因数比 设整数a的小于其本身的因数之和为s，定义 p(a)=s/a为整数a的因数比。事实上，a为完全数时，p(a)=1。例如，p(6)=1。有些资料还介绍了因数之和为数本身2倍的整数，例如p(120)=2。试求指定区间x,y中整数的因数比的最大值。数据测试：x=1,y=2014 一般地，求指定区间x,y中整数的因数比最大值。为了求整数a的因数和s,显然1是因数。设置k(2sqrt(a)循环枚举，如果

35、k是a的因数，则a/k也是a的因数。显然ka/k。如果a=b*b，显然k=b,a/k=b，此时k=a/k。而因数b只有一个，所以此时必须从和s中减去一个b，这样处理以避免重复。设置max存储因数比最大值。枚举区间内每一整数a，求得其因数和s。通过s/a与max比较求取因数比最大值。对比较所得因数比最大的整数，通过试商输出其因数和式。3. 因数比程序设计/ 求x,y范围内整数的因数比最大值,c252 #include #include void main() double a,s,a1,s1,b,k,t,x,y,max=0; printf( 求区间x,y中整数的因数比最大值.); printf(

36、 请输入整数x,y:); scanf(%lf,%lf,&x,&y); for(a=x;a=y;a+) / 枚举区间内的所有整数a s=1;b=sqrt(a); for(k=2;k=b;k+) / 试商寻求a的因数k if(fmod(a,k)=0) s=s+k+a/k; / k与a/k是a的因数，求和 if(a=b*b) s=s-b; / 如果a=b2,去掉重复因数b t=s/a; if(maxt) max=t;a1=a;s1=s; printf( 整数%.0f的因数比最大：%.4f n,a1,max); printf( %.0f的因数和为：n,a1); printf( %.0f=1,s1);

37、/ 输出其因数和式 for(k=2;k=a1/2;k+) if(fmod(a1,k)=0) printf(+%.0f,k); （3） 程序运行与分析求区间x,y中整数的因数比最大值.请输入整数x,y: 1,2016整数1680的因数比最大：2.54291680的因数和为： 4272=1+2+3+4+5+6+7+8+10+12+14+15+16+20+21+24+28+30+35+40+42+48+56+60+70+80+84+105+112+120+140+168+210+240+280+336+420+560+840 设输入参数y的数量级为n，双重枚举循环的运算量为，即可知算法的时间复杂度为

38、O()。变通：如果整数a的大小不加任何限制，其因数比p(a)是否存在某一个上限？如果把探求p(a)的最大值变换为探求整数a的因数比p(a)等于某一指定整数，也许更具吸引力。上面已提到：p(6)=1，p(120)=2。事实上，已探求到p(30240)=3；p(518666803200)=4。笔者猜想p(a)=5，p(a)=6等的整数a也是存在的，只是此时的整数a已经相当庞大。11. 双和二组把给定偶数2n分解为6个互不相等的正整数a,b,c,d,e,f，然后把这6个数分成(a,b,c)与(d,e,f)两个3元组，若这两个3元组具有以下双和相等特性： 则把3元组(a,b,c)与(d,e,f)（约定

39、abc，def,ad）称为基于n的双和二组。例如，对于n=26，存在基于26的双和二组(4,10,12),(5,6,15):4+10+12=5+6+15=261/4+1/10+1/12=1/5+1/6+1/15=13/30输入正整数n(n100)，搜索所有基于n 的双和二组。若没有探索到相应的双和二组，则输出“无解”。数据测试：n=98枚举设计要点因6个不同正整数之和至少为21，即整数n11。（1） 枚举循环设置设置a,b与d,e枚举循环。注意到a+b+c=n，且aba，因而d起点为a+1。（2） 检验积相等把比较倒数和相等1/a+1/b+1/c1/d+1/e+1/f转化为比较整数相等d*e*

40、f*(b*c+c*a+a*b)=a*b*c*(e*f+f*d+d*e) (*)若式（*）不成立，即倒数和不相等，则返回。（3） 省略相同整数的检测同时注意到两个3元组中若部分相同部分不同，不能有和相等且倒数和也相等，即式（*）不可能成立（证略）。因而可省略排除以上6个正整数中是否存在相等的检测。若式（*）成立，打印输出和为n的双和二组，并用x统计解的个数。3. 双和数组程序设计/ 双和数组探索 ,c261 #include#includevoid main() int a,b,c,d,e,f,x,n;printf( 请输入整数n: ); scanf(%d,&n);x=0;for(a=1;a=(

41、n-3)/3;a+) / 通过循环实现枚举for(b=a+1;b=(n-a-1)/2;b+)for(d=a+1;d=(n-3)/3;d+)for(e=d+1;e0) printf( 共以上%d组解！n,x);else printf( 无解！n);4. 程序运行与分析请输入整数n: 981: ( 2, 36, 60), ( 3, 5, 90)；2: ( 7, 28, 63), ( 8, 18, 72)；3: ( 7, 35, 56), ( 8, 20, 70)；4: ( 10, 33, 55), ( 12, 20, 66)；共以上4组解！ 输入n=26，即得唯一一个双和二组如上面所示。输入任何小于26的整数n均无解。可见存在双和二组的n最小值为n=26。由循环设置可知枚举复杂度为O()，显然不适宜对较大整数n的双和二组搜索。12. 和积三组设n为正整数，试把整数3*n分解为9个互不相同的正整数a,b,c,d,e,f,g,h,i，然后把这9个正整数分成(a,b,c)、(d,e,f)与( g,h,i)三个3元组，若这三个3元组具有以下两个和积相等特性： 则把(a,b,c)、(d,e,f)与( g,h,i) (约定abc,def,ghi,ad14。