程序设计竞赛培训题解答(一)要点

1、392014程序设计竞赛培训题解答（1）1.统计n!尾部零试统计正整数n的阶乘n!=1 X2X3XiX n尾部连续零的个数。数据检测：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，

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

3、t;10000):");scanf("%d",&n);/输入 ns=0;for(k=2;k<=n;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

4、”因子设计1)设计思路注意到n!尾部连续零是n!中各相乘数2, 3,，n中“2”的因子与“ 5”的因子相乘 所得，一个“ 2”的因子与一个“ 5”的因子得一个尾部“ 0”。显然，n!中各个相乘数2, 3,，n中“2”的因子数远多于“5”的因子数，因而n!尾 部连续零的个数完全由n!中各个相乘数2, 3,，n中的“5”因子个数决定。设n!中各个相乘数2, 3,，n中“5”的因子个数为s,显然有s = 口 三川旦- 5_52m_5m其中x为不大于x的最大正整数，正整数 m满足5m <n<5m41o这里统计s只需设计一个简单的条件循环即可实现。2)算法描述/统计"5"

5、因子设计，c135#include <stdio.h>void main() long n,s,t;printf(" 请输入正整数n:");scanf("%ld",&n);/输入 ns=0;t=1;while(t<=n)t=t*5;s=s+n/t;/循环统计尾部连续0的个数printf(" %ld!尾部连续零共 ld个。n",n,s);/输出结果(3)数据检测与复杂度分析请输入正整数n： 20152015!尾部连续零共502个基本求积算法为双循环设计，循环频数为mn>注意到m>n把m换算为n, m

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

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

8、再求第n 个数与b的最大公约数；要求 n-1个数的最大公约数，先求出前 n-2个数的最大公约数b, 再求第n-1个数与b的最大公约数；依此类推。因而，要求n个整数的最大公名数，需应用 n-1次欧几里德算法来完成。为输入与输出方便，把 n个整数设置成m数组，m数组与变量a,b,c,r与m数组设置为 长整型变量，个数n与循环变量k设置为整型，这就是数据结构。设置k (1n-1)循环，完成n-1次欧几里德算法，最后输出所求结果。/求n个整数的最大公约数，c143#include<stdio.h> /C头文件的调用void main() int k,n;long a,b,c,r,m100;

9、printf("请输入整数个数n: ");/输入原始数据scanf("%d",&n);printf("请依次输入 d整数：",n);for(k=0;k<=n-1;k+) printf("n请输入第人整数：",k+1);scanf("%ld",&mk);b=m0;for(k=1;k<=n-1;k+) a=mk；if(a<b) c=a;a=b;b=c; r=a%b;while(r!=0) a=b;b=r;r=a%b;printf("(%ld",m

10、0);for(k=1;k<=n-1;k+)printf(",%ld",mk);printf(")=%ldn",b);程序运行示例：/控制应用n-1次欧几里德算法/ 交换a,b ,确保a>b/ 实施"辗转相除"/输出求解结果请输入整数个数n： 4请依次输入4个整数：请输入第1个整数：10247328请输入第2个整数：12920544请输入第3个整数：17480736请输入第4个整数：22859424(10247328,12920544,17480736,22859424)=2016/实现欧几里德算法的函数，c144 long

11、 gcd(long a,long b) long c,r;交换a,b ,确保a>bif(a<b)c=a;a=b;b=c;/r=a%b;while(r!=0)/实施"辗转相除" a=b;b=r;r=a%b;return b;/求n个整数的最大公约数，c145#include<stdio.h>void main() int k,n;long x,y,m100;printf("请输入整数个数 n: "); scanf("%d",&n);printf("请依次输入 整数：",n);for(k

12、=0;k<=n-1;k+) printf("n请输入第整数：",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)

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

14、当 于换回1瓶汽水还给商家），两清。此时每人花费为2/3*1.40=0.93 元（3）如果只有2人或1人，每人喝1瓶汽水（瓶不带走），此时每人花费1元。（4）注意到0.91<0.93<1 ,因而有以下的最省钱算法：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

15、*x+2*y）*1.40+t 元。（5）费用最低的算法描述/ 喝汽水main() long m,t,x,y;printf(" 请输入 m： "); scanf("%ld",&m);x=m/20;/t=m-20*x;/y=t/3;/分x个大组，每组买13瓶汽水，借 神剩下大组外的t人剩下t人分y个小组，每组买2瓶汽水，借1瓶t=m-20*x-3*y;/剩下大小组外的t人，每人花1元喝1瓶printf("喝口瓶汽水，需 .2f元。n”,m,(13*x+2*y)*1.40+t);该算法有输入，即输入人数m;有处理，即依次计算大组数x、小组数y

16、与剩下的零散人 数t;有输出，即输出最省费用。4.全素组如果不大于指定整数n的3个素数之和仍为素数，则把这 3个素数称为一个基于n的全 素组。例如对于n=15,素数3,5,11之和3+5+11=19为素数，则3,5,11称为一个基于15的 全素组。定义所有基于n的全素组中和最大的称为最大全素组。输入整数n （n<3000）,输出基于n的全素组的个数，并输出一个最大全素组。数据测试：2015/全素组探求，c221#include <stdio.h>#include <math.h>void main()int i,j,k,i2,j2,k2,n,s,t,w,z,max

17、,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) t=0;break; if(t=1) pi=1;/ w=0; for(i=3;i<=n;i=i+2)if(pi=1)w+;qw=i;/m=0; max=0;for(i=1;i<=w-2;i+)/for(j=i+1;j<=w-1;j+) for(k=j+1;k<=

18、w;k+) s=qi+qj+q时 if(ps=1) m+;/if(s>max) / printf(" if(m>0) printf("4.程序运行示例与分析奇数i为素数时标记pi=1共w个不大于n的奇素数赋给q数组设置三重循环枚举所有三个素数组统计3个素数之和s统计全素组个数比较并记录最大全素组max=s;i2=qi;j2=qj;k2=qk;共有%ld个全素组；n",m);一个最大全素组为：%d+%d+%d=%ldn",i2,j2,k2,max);请输入整数n: 2015共有1345431个全素组；一个最大全素组为：1997+2003+201

19、1=60115.最简真分数统计分母在指定区间10,99的最简真分数(分子小于分母，且分子分母无公因数)共有多 少个，并求这些最简真分数的和。设计求解一般情形：统计分母在指定区间a,b的最简真分数的个数，并求这些最简真分数的和(正整数a,b从键盘输入)。设分数分子为i ,分母为j ,最简真分数的个数为 m,其和为so在指定范围a,b内枚举分数的分母j:ab;同时对每一个分母j枚举分子i:1j-1。对每一分数i/j ,置标志t=0 ,然后进行是否存在公因数的检测。如果分子i与分母j?存在大于1的公因数u,说明i/j非最简真分数，应予舍略。因为分 子分母同时约去u后，分母可能不在a,b,即使在a,b

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

21、<math.h>void main()int a,b,i,j,t,u;10ng 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+;/统计最简真分数个

22、数s+=(double)i/j; /求最简真分数和printf("最简真分数共m=%ld个。n",m);printf("其和 s=%.5f n",s);4 .程序运行与分析最简真分数分母在a,b内，请确定a,b: 100,999最简真分数共m=300788f。其和 s=150394.000006.佩尔方程佩尔（Pell）方程是关于x,y的二次不定方程，表述为x2 -n y2 =1 （其中n为非平方正整数）当x=1或x=-1 , y=0时，显然满足方程。常把x,y中有一个为零的解称为平凡解。？我们 要求佩尔方程的非平凡解。佩尔方程的非平凡解很多，这里只要求

23、出它的最小解，即x,y?为满足方程的最小正数的 解，又称基本解。输入非平方整数n,输出佩尔方程：x2 -n y2 =1的一个基本解。数据测试：n=73;n=20141 .案例背景佩尔（Pell）方程是关于x,y的二次不定方程，表述为x2 -n y2 =1 （其中n为非平方正整数）当x=1或x=-1 , y=0时，显然满足方程。常把x,y中有一个为零的解称为平凡解。？我们 要求佩尔方程的非平凡解。佩尔方程的非平凡解很多，这里只要求出它的最小解，即x,y?为满足方程的最小正数的 解，又称基本解。对于有些n,尽管是求基本解，其数值也大得惊人。这么大的数值，如何求得？其基本 解具体为多少？可以说，这是

24、自然界对人类计算能力的一个挑战。十七世纪曾有一位印度数 学家说过，要是有人能在一年的时间内求出x2-92y2=1的非平凡解，他就算得上一名真正的数学家。由此可见，佩尔方程的求解是有趣的，其计算也是繁琐的。试设计程序求解佩尔方程：x2 _ 73.y2 = 1。2 .枚举设计要点应用枚举试值来探求佩尔方程的基本解。设置y从1开始递增1取值，对于每一个y值，11算a=n*y*y后判别：若a+1为某一整数x的平方，则(x,y)即为所求佩尔方程的基本解。若a+1不是平方数，则y增1后再试，直到找到解为止。应用以上枚举探求，如果解的位数不太大，总可以求出相应的基本解。如果基本解太大，应用枚举无法找到基本解

25、，可约定一个枚举上限，例如10000000。可把y<=10000000作为循环条件，当y>10000000时结束循环，输出“未求出该方程的基本解！ ” 而结束。3 .解PELL方程程序设计/ 解 PELL 方程:xA2-nyA2=1, c231#include <math.h>#include <stdio.h>void main()double a,m,n,x,y;printf("解 PELL方程：xA2-nyA2=1.n");printf("请输入非平方整数n:");scanf("%lf",&a

26、mp;n);m=floor(sqrt(n+1);if(m*m=n) printf(" n为平方数，方程无正整数解！n");return;y=1;while(y<=10000000) y+;/设置y从1开始递增1枚举a=n*y*y;x=floor(sqrt(a+1);if(x*x=a+1)/检测是否满足方程 printf(" 方程 xA2-%.0fyA2=1 的基本解为:n",n);printf(" x=%.0f, y=%.0fn",x,y);break; if（y>10000000） printf（"未求出该方程

27、的基本解！"）； 4.程序运行与分析解PELL 方程：xA2-nyA2=1.请输入非平方整数n：73方程xA2-73yA2=1的基本解为： x=2281249,y=267000为了提高求解方程的范围，数据结构设置为双精度（ double ）型。如果设置为整形或长 整形，方程的求解范围比设置为双精度型要小。 例如n=73时，设置整形或长整形就不可能求 出相应方程的解。可见，数据结构的设置对程序的应用范围有着直接的影响。以上枚举设计是递增枚举，枚举复杂度与输入的n没有直接关系，完全取决于满足方程的y的数量。解的y值小，枚举的次数就少。解的 y值大，枚举的次数就多。对某些 n,相 应佩尔方

28、程解的位数太大，枚举求解无法完成。例如当 n=991时，相应佩尔方程的基本解达 30位。此时依据以上枚举求解是无法实现的，只有通过某些专业算法（例如连分数法）才能 进行求解。7.分数不等式解不等式mi234:二 m2这里正整数 m1,m2从键盘隼入（m1<m2。数据测试：m1=2015,m2=2016为一般计，解不等式1 1 , 12 , 3. Vn ,（2）m1一 十十一十 十<m212）2 34 n 1这里正整数 m1,m2从键盘隼入（m1<m2。设和变量为s,递增变量为i ,两者赋初值为0。在s<=m1的条件循环中，根据递增变量i对s累加求和，直至出现s>m

29、1退出循环，赋值 c=i ,所得c为n解区间的下限。继续在s<=m2的条件循环中，根据递增变量i对s累加求和，直至出现s>m2退出循环，通过赋值d=i-1 ,所得d为n解区间的上限。注意，解的上限是d=i-1 ,而不是i。然后打印输出不等式的解区间c,d。3 .解分数不等式程序设计/解分数不等式，c241#include <stdio.h>#include<math.h>void main()long c,d,i,m1,m2;double s;printf(" 请输入正整数 m1,m2(m1<m2):");scanf("%

30、ld,%ld”,&m1,&m2);i=0;s=0;while(s<=m1)i=i+1;s=s+sqrt(i)/(i+1);c=i;doi=i+1;s=s+sqrt(i)/(i+1);while(s<=m2);d=i-1;printf(" 满足不等式的正整数 n为：%ld <n<%ld n",c,d);4 .程序运行与分析请输入正整数 m1,m2(m1<m2): 2015,2016满足不等式的正整数 n为：1018402 0n< 1019411以上枚举算法的循环次数取决于解n的上限d,当输入的参数m2越大时，n也就越大,枚举

31、的复杂度也就越高。不等式中的上下限可取任意实数，请修改程序，把上下限m1,m2改为从键盘输入的任意实数（0.5<m1<m2。8.代数和不等式试解下列关于正整数n的代数和不等式d <1 1 -1 1 1 -1 ”2 34 5 6 n（其中d为从键盘输入的正数）式中符号为二个“ +”号后一个“-”号，即分母能被3整除时为“-数据测试：d=4;d=6般地，解不等式(4)11111 id .；：1 - ,一 一 一一 ,(其中d为从键盘输入的正数)式中符号为二个“ +”号后一个“-”号，即分母能被3整除时为“-”。注意到式中出现减运算，可能导致不等式的解分段。设置条件循环，每三项(包

32、含二正一负)一起求和。若加到 1/n+1/(n+1)-1/(n+2) 后, 代数和s>d,退出循环，得一个区间解n+1, 8。注意，此时n还须进行进一步检测。然后回过头来一项项求和，包括对 n的检测，得离散解。3 .程序设计/ 解不等式：d<1+1/2-1/3+1/4+1/5-1/6+.+ 1/n ,c242#include <stdio.h>void main() long d,n,k;double s;printf(" 请输入正整数d:");scanf("%d",&d);printf(" %d<1+1/

33、2-1/3+1/4+1/5-1/6+ n=1;s=0;while(1) s=s+1.0/n+1.0/(n+1)-1.0/(n+2);if(s>d) break;n=n+3;printf(" n>=%ld n",n+1);/k=1;s=0;while(k<=n) if(k%3>0) s=s+1.0/k;else s=s-1.0/k;if(s>d)/printf(" n=%ld n",k);k+;4.程序运行示例+-1/n 的解：n",d);得一个区间解得到离散解请输入正整数d： 55<1+1/2-1/3+1/4

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

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

36、);scanf("%d",&d);printf(" %d<1+1/2-1/3+1/4+1/5-1/6+-1/n 的解：n",d);n=3;s=3.0/2;while(1) s=s-1.0/n+1.0/(n+1)+1.0/(n+2);if(s>d) break;n=n+3;printf(" n=%ld n",n+2);/ 打印第一个离散解 n+2k=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);print

37、f(" n=%ld n",k);/打印离散解k/打印区间解printf(" n>=%ld n",k);(3)程序运行示例请输入正整数d: 77<1+1/2-1/3+1/4+1/5-1/6+-1/n 的解:n=82273511n>=82273513注意：前一个是离散解，而后一个是区间解。6 .分析与变通以上两个枚举算法的循环次数取决于解n的上限，当输入的参数 d越大时，n的上限也就越大，枚举的复杂度也就越高，求解也就变得越困难。例如当d逐渐增加到d>7时，解值n会迅速增长而变得非常大，甚至超出相应变量的范 围或计算机的计算范围，这时

38、就不可能得到不等式的解。变通：请把不等式中“二正一负”的规律改变为“三正一负”，程序应如何修改？求出修 改后的不等式大于5的解。9,基于素数的代数和定义和：/、 1357911. 2n-1s(n)二一一一一一 .一 - - -35791113 2n 1(和式中第k项±(2k-1)/(2k+1)的符号识别：分子分母中有且只有一个素数，取“+”;分子分母中没有素数或两个都是素数时取“-”。)1)求s(2016)(精确到小数点后5位)。2) 设1<=n<=2016,当n为多大时，s(n)最大。3) 设1<=n<=2016,当n为多大时，s(n)最接近0。在求和之前应

39、用“试商判别法”对第 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”的绝对值，记录此时的项数k2, 同时记录此时的和

40、值 s2o最后，求和循环结束时输出所求值。3 .基于素数的分数和程序设计/基于素数的分数和，c251#include<stdio.h> printf("s(%d)=%.5f n",n,s);#include<math.h>void 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

41、,j=3;j<=sqrt(2*k-1);j+=2)if(2*k-1)%j=0)t=1;break;if(t=0) ak=1;/s=0;smax=0;mi=10;for(k=1;k<=n;k+)if(ak+ak+1=1)/s+=(double)(2*k-1)/(2*k+1); / elses-=(double)(2*k-1)/(2*k+1); / if(s>smax) smax=s;k1=k; / if(fabs(s)<mi) mi=fabs(s);k2=k;s2=s; /标记第k个奇数2k-1为素数判断ak与ak+1中有一个素数实施加否则，实施减比较求最大值smax绝对

42、值比较求最接近0点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,但标注素数的运算量为n3/2 ,因而枚举算法的时间复杂度为 O(n3/2)。变通：请把题目中的条件“分子分母中有且只有一个素数，取+'”，改为“分子分母中至少有一个素数，

43、取+'”，程序作何修改？并求出结果。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)循环枚举，如果k是a的 因数，则a/k也是a的因数。显然kwa/k。如果a=b*b,显然k=b,a/k=b ,此时k=a/k。而因数b只有一个，所以此时必须从和

44、s中减去一个b,这样处理以避免重复。设置max存储因数比最大值。枚举区间内每一整数a,求得其因数和s。通过s/a与max比较求取因数比最大值。对比较所得因数比最大的整数，通过试商输出其因数和式。3.因数比程序设计/求x,y范围内整数的因数比最大值，c252#include <stdio.h>#include <math.h>void main() double a,s,a1,s1,b,k,t,x,y,max=0;printf(" printf(" scanf("%lf,%lf",&x,&y); for(a=x;a&

45、lt;=y;a+)/s=1;b=sqrt(a);for(k=2;k<=b;k+)/if(fmod(a,k)=0) s=s+k+a/k; / k if(a=b*b) s=s-b; / t=s/a;if(max<t) max=t;a1=a;s1=s; printf(" printf(" %.0f求区间x,y中整数的因数比最大值.");请输入整数x,y:");枚举区间内的所有整数a试商寻求a的因数k与a/k是a的因数，求和如果a=bA2,去掉重复因数bprintf(" %.0f=1",s1);for(k=2;k<=a1/2

46、;k+)if(fmod(a1,k)=0)printf("+%.0f",k);(3)程序运行与分析整数.0f的因数比最大:的因数和为：/%.4f n",a1,max); n",a1);输出其因数和式求区间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+56

47、0+840设输入参数y的数量级为n,双重枚举循环的运算量为n3/2 ,即可知算法的时间复杂度为O(n3/2)o变通：如果整数a的大小不加任何限制，其因数比p(a)是否存在某一个上限？如果把探求p(a)的最大值变换为探求整数 a的因数比p(a)等于某一指定整数，也许更具 吸引力。上面已提到：p(6)=1 , p(120)=2。事实上，已探求至U p(30240)=3 ; p(518666803200)=4。笔者彳#想p(a)=5 , p(a)=6等的整数a也是存在的，只是此时的整数a已经相当庞大。11. 双和二组把给定偶数2n分解为6个互不相等的正整数a,b,c,d,e,f，然后把这6个数分成(

48、a,b,c)与(d,e,f)两个3元组，若这两个3元组具有以下双和相等特性：a b c = d e f11111 + + = + +b c d e f则把3元组(a,b,c)与(d,e,f)(约定a<b<c, d<e<f,a<d )称为基于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(nW100),搜索所有基于n的双和二组。若没有探索到相应的双和二组, 则输出“无解”。数据测试：n=98枚举设计要点因6个

49、不同正整数之和至少为21,即整数n>11o(1)枚举循环设置设置a,b与d,e枚举循环。注意到a+b+c=n,且a<b<c,因而a,b循环取值为：a: 1(n-3)/3 ;因b比a至少大1, c比a至少大2, a的值最多为(n-3)/3 。b: a+1(n-a-1)/2 ;因c比b至少大1, b的值最多为(n-a-1)/2 。c=n-a-b ,以确保 a+b+c=rio设置d,e循环基本同上，注意到 d>a,因而d起点为a+1。(2)检验积相等把比较倒数和相等1/a+1/b+1/c =1/d+1/e+1/f 转化为比较整数相等 d*e*f*(b*c+c*a+a*b)=a

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

51、;%d",&n);x=0;for(a=1;a<=(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;e<=(n-d-1)/2;e+) c=n-a-b; f=n-d-e;/确保两组和相等if(a*b*c*(e*f+f*d+d*e)!=d*e*f*(b*c+c*a+a*b) continue;/排除倒数和不相等x+;printf(" %d: (%3d,%3d,%3d),",x,a,b,c); /统计并输出双和二组printf(&q

52、uot; (%3d,%3d,%3d)； n",d,e,f);if(x>0) printf("共以上dt!解！ 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组解！26的整数n均无解。可输入n=26,即得唯一一个双和二组如上面所示。输入任何小于 见存在双和二组的n最小值为n

53、=26。由循环设置可知枚举复杂度为 O(n4),显然不适宜对较大整数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 ia b c=d ef=g h i则把(a,b,c) 、(d,e,f) 与(g,h,i)(约定 a<b<c,d<e<f,g<h<i,a<d<g )称为一个基于 n 的 和积三组。例如，给定n=4

54、5,探索至“唯一基于 45的和积三组(4,20,21),(5,12,28),(7,8,30):4+20+21=5+12+28=7+8+30=454*20*21=5*12*28=7*8*30=1680输入正整数n(nW100),搜索所有基于n的和积三组。若没有探索到相应的和积三组, 则输出“无解”。数据测试：n=100 枚举设计要点因9个不同正整数之和至少为 45,因而可知正整数n>14。(1)设置枚举循环注意到a+b+c=n,且a<b<c,因而a,b循环取值为：a: 1(n-3)/3 ;因b比a至少大1, c比a至少大2,即a至多为(n-3)/3 。b: a+1(n-a-1)

55、/2 ;因c比b至少大1,即b至多为(n-a-1)/2 。c=n-a-b ,以确保 a<b<c 且 a+b+c=n。设置d,e循环与g,h循环基本同上，只是注意到d>a,因而d起点为a+1; g>d,因而g起点为d+1。(2)检测和积相等在设置的枚举循环中，确保了三个3元组和相等。若a*b*c=d*e*f=g*h*i,即积也相等，满足和积相等条件，搜索到基于n的一组和积三组，用x统计组数。(3)省略相同整数的检测注意到两个和相等的3元组中，若等号两边有部分数相同，部分数不同，不可能有积相 等(证略)。因而可省略排除以上9个正整数中是否存在相同整数的检测。即在检测积相等时

56、已排除出现整数相同的可能。3 .和积三组程序实现/和积三组探索,c262#include <stdio.h>void main()int a,b,c,d,e,f,g,h,i,j,x,n;long t;printf("请输入整数 n: "); scanf("%d",&n);x=0;for(a=1;a<=(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;e<=(n-d-1)/2;e+) for(g=d+1;g<=

57、(n-3)/3;g+) for(h=g+1;h<=(n-g-1)/2;h+) c=n-a-b; f=n-d-e;i=n-g-h; / t=a*b*c;if(d*e*f=t && g*h*i=t)设置循环实施枚举确保三组和等于n/排除积不相等 x+;printf(" %d: %3d %3d %3d; ",x,a,b,c);printf("%3d %3d %3d; ",d,e,f);printf("%3d %3d %3d; (%ld)n",g,h,i,t); if(x>0) printf("共以上dt!解！ n",x);else printf(" 无解！ n");4 .程序运行与分析请输入整数n： 1001: 6 45 49; 7 30 63; 9 21 70; (13230)2: 10 42 48; 12 28 60; 15 21 64; (20160)3: 16 39 45; 18 30 52; 20 26 54; (28080)共以上3组解请运行程序，探索存在基于 n的和积三组的整数n至少为多大？由循