![2014程序设计竞赛培训题解答(1)_第1页](http://file1.renrendoc.com/fileroot_temp2/2021-1/6/48bdae02-b77b-4fb4-a1eb-b0b7d53ba21f/48bdae02-b77b-4fb4-a1eb-b0b7d53ba21f1.gif)
![2014程序设计竞赛培训题解答(1)_第2页](http://file1.renrendoc.com/fileroot_temp2/2021-1/6/48bdae02-b77b-4fb4-a1eb-b0b7d53ba21f/48bdae02-b77b-4fb4-a1eb-b0b7d53ba21f2.gif)
![2014程序设计竞赛培训题解答(1)_第3页](http://file1.renrendoc.com/fileroot_temp2/2021-1/6/48bdae02-b77b-4fb4-a1eb-b0b7d53ba21f/48bdae02-b77b-4fb4-a1eb-b0b7d53ba21f3.gif)
![2014程序设计竞赛培训题解答(1)_第4页](http://file1.renrendoc.com/fileroot_temp2/2021-1/6/48bdae02-b77b-4fb4-a1eb-b0b7d53ba21f/48bdae02-b77b-4fb4-a1eb-b0b7d53ba21f4.gif)
![2014程序设计竞赛培训题解答(1)_第5页](http://file1.renrendoc.com/fileroot_temp2/2021-1/6/48bdae02-b77b-4fb4-a1eb-b0b7d53ba21f/48bdae02-b77b-4fb4-a1eb-b0b7d53ba21f5.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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。
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024-2025年高中政治 第3单元 收入与分配 3.8.1 国家财政教案 新人教版必修1
- 专项学习 像科学家那样 教学设计-2023-2024学年科学四年级上册苏教版
- 2023八年级历史下册 第五单元 国防建设与外交成就第17课 外交事业的发展教案 新人教版
- 2023六年级语文下册 第五单元 口语交际:辩论配套教案 新人教版
- 《智能自动化档案管理规范》征求意见稿
- 基层医疗机构卫生应急技能竞赛复习试题附答案
- 人教版小学语文一年级单元测试题-全册
- 管道自动焊作业指导书
- 2023年湖南省农业科技服务中心招聘考试真题
- 第五章土石方明挖及支护施工
- 住宅排气管道系统工程技术标准
- 事业单位体检复检申请表
- 补益剂-参苓白术散(方剂学课件)
- 学前儿童游戏(中职学前教育专业)PPT完整版全套教学课件
- RFID与二维码技术 1-18单元教程配套完整版电子课件
- 企业主数据管理规范模板
- 口服药漏服原因分析品管圈鱼骨图对策拟定
- (市政污水管道工程)雨污分流施工组织方案
- GB/T 11064.2-2023碳酸锂、单水氢氧化锂、氯化锂化学分析方法第2部分:氢氧化锂含量的测定酸碱滴定法
- 唐山市丰润区宝龙石矿矿山地质环境保护与土地复垦方案专家评审意见
- 京东云自动化运维体系构建
评论
0/150
提交评论