程序设计竞赛培训题解答1要点.docx
- 文档编号:18240624
- 上传时间:2023-08-14
- 格式:DOCX
- 页数:72
- 大小:89.98KB
程序设计竞赛培训题解答1要点.docx
《程序设计竞赛培训题解答1要点.docx》由会员分享,可在线阅读,更多相关《程序设计竞赛培训题解答1要点.docx(72页珍藏版)》请在冰点文库上搜索。
程序设计竞赛培训题解答1要点
2014程序设计竞赛培训题解答
(1)
1.统计n!
尾部零
试统计正整数n的阶乘n!
=1×2×3×…×n尾部连续零的个数。
数据检测:
n=2015;n=20142015
解:
以下试用两种不同的算法分别进行求解。
(1)基本求积算法
1)算法概要
注意到输入整数n规模可能较大,n!
尾部零的个数也就相应地多,设计a数组存储n!
的各位数字,a[1]存储个位数字,a[2]存储十位数字,余类推。
试模拟整数竖式乘运算实施精确计算(详见第8章)。
首先通过常用对数累加和s=lg2+lg3+…+lgn确定n!
的位数m=s+1,即a数组元素的个数。
设置2重循环,模拟整数竖式乘法实施各数组元素的累乘:
乘数k:
k=2,3,…,n;
累乘积各位a[j]:
j=1,2,…,m;
实施乘运算:
t=a[j]*k+g;//第j位乘k,g为进位数
a[j]=t%10;//乘积t的个位数字存于本元素
g=t/10;//乘积t的十位以上数字作为进位数
尾部连续零的个数统计:
从j=1时低位a[j]开始,a[j]=0时j++;作统计,直到a[j]!
=0时结束。
2)算法描述
//计算n!
(n<10000)尾部零个数,c134
#include
#include
voidmain()
{intj,k,m,n,a[40000];
longg,t;doubles;
printf("请输入正整数n(n<10000):
");
scanf("%d",&n);//输入n
s=0;
for(k=2;k<=n;k++)
s+=log10(k);//对数累加确定n!
的位数m
m=(int)s+1;
for(k=1;k<=m;k++)a[k]=0;//数组清零
a[1]=1;g=0;
for(k=2;k<=n;k++)
for(j=1;j<=m;j++)
{t=a[j]*k+g;//数组累乘并进位
a[j]=t%10;
g=t/10;
}
j=1;
while(a[j]==0)j++;
printf("%d!
尾部连续零共%d个。
\n",n,j-1);//输出n!
尾部零个数
}
(2)统计“5”因子设计
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,显然有
其中[x]为不大于x的最大正整数,正整数m满足
。
这里统计s只需设计一个简单的条件循环即可实现。
2)算法描述
//统计“5”因子设计,c135
#include
voidmain()
{longn,s,t;
printf("请输入正整数n:
");
scanf("%ld",&n);//输入n
s=0;t=1;
while(t<=n)
{t=t*5;s=s+n/t;}//循环统计尾部连续0的个数
printf("%ld!
尾部连续零共%ld个。
\n",n,s);//输出结果
}
(3)数据检测与复杂度分析
请输入正整数n:
2015
2015!
尾部连续零共502个。
基本求积算法为双循环设计,循环频数为mn。
注意到m>n,把m换算为n,m数量级估算平均为n*logn,因而基本求积算法的时间复杂度为O(n2logn),空间复杂度为O(nlogn)。
统计“5”因子的设计大大简化了n!
尾部连续零个数的统计,算法的时间复杂度为O(logn),空间复杂度为O
(1),显然大大优于基本求积算法。
统计“5”因子设计可大大拓展n的范围,例如输入n为20142015,可得20142015!
尾部连续零共5035500个,这一点基本求积算法因时间复杂度与空间复杂度太高而难以实现。
若案例稍加变通,需求n!
结果所有数字中零的个数,基本求积算法(修改统计零的个数)可实现,而统计“5”因子算法却无法完成。
以上3个简单案例的求解都列举了两个不同的算法设计,并分析与比较了这些不同算法的时间复杂度。
可见求解一个实际案例时,算法可能有多种多样,我们不必局限于某一个定式或某一种模式,可根据案例的具体实际确定算法进行设计求解。
当面临处理的数据规模很大、或运行算法的时间很长时,选择时间复杂度低的算法是必要的,这也是我们进行算法设计所追求的目标。
2.求最大公约数
求n个正整数
的最大公约数(
)。
解:
对于3个或3个以上整数,最大公约数有以下性质:
(m1,m2,m3)=((m1,m2),m3)
(m1,m2,m3,m4)=((m1,m2,m3),m4),…
应用这一性质,要求n个数的最大公约数,先求出前n−1个数的最大公约数b,再求第n个数与b的最大公约数;要求n−1个数的最大公约数,先求出前n−2个数的最大公约数b,再求第n−1个数与b的最大公约数;……
依此类推。
因而,要求n个整数的最大公约数,需应用n−1次欧几里德算法来完成。
为输入与输出方便,把n个整数设置成m数组,m数组与变量a,b,c,r与m数组设置为长整型变量,个数n与循环变量k设置为整型,这就是数据结构。
设置k(1~n-1)循环,完成n-1次欧几里德算法,最后输出所求结果。
//求n个整数的最大公约数,c143
#include
voidmain()
{intk,n;
longa,b,c,r,m[100];
printf("请输入整数个数n:
");//输入原始数据
scanf("%d",&n);
printf("请依次输入%d个整数:
",n);
for(k=0;k<=n-1;k++)
{printf("\n请输入第%d个整数:
",k+1);
scanf("%ld",&m[k]);
}
b=m[0];
for(k=1;k<=n-1;k++)//控制应用n−1次欧几里德算法
{a=m[k];
if(a
{c=a;a=b;b=c;}//交换a,b,确保a>b
r=a%b;
while(r!
=0)
{a=b;b=r;//实施"辗转相除"
r=a%b;
}
}
printf("(%ld",m[0]);//输出求解结果
for(k=1;k<=n-1;k++)
printf(",%ld",m[k]);
printf(")=%ld\n",b);
}
程序运行示例:
请输入整数个数n:
4
请依次输入4个整数:
请输入第1个整数:
10247328
请输入第2个整数:
12920544
请输入第3个整数:
17480736
请输入第4个整数:
22859424
(10247328,12920544,17480736,22859424)=2016
//实现欧几里德算法的函数,c144
longgcd(longa,longb)
{longc,r;
if(a
{c=a;a=b;b=c;}//交换a,b,确保a>b
r=a%b;
while(r!
=0)
{a=b;b=r;//实施"辗转相除"
r=a%b;
}
returnb;
}
//求n个整数的最大公约数,c145
#include
voidmain()
{intk,n;
longx,y,m[100];
printf("请输入整数个数n:
");scanf("%d",&n);
printf("请依次输入%d个整数:
",n);
for(k=0;k<=n-1;k++)
{printf("\n请输入第%d个整数:
",k+1);
scanf("%ld",&m[k]);
}
x=m[0];
for(k=1;k<=n-1;k++)
{y=m[k];
x=gcd(x,y);
}
printf("(%ld",m[0]);
for(k=1;k<=n-1;k++)
printf(",%ld",m[k]);
printf(")=%ld\n",x);
}
3.喝汽水
某学院有m个学生参加南湖春游,休息时喝汽水。
南湖商家公告:
(1)买1瓶汽水定价1.40元,喝1瓶汽水(瓶不带走)1元。
(2)为节约资源,规定3个空瓶可换回1瓶汽水,或20个空瓶可换回7瓶汽水。
(3)为方面顾客,可先借后还。
例如借1瓶汽水,还3个空瓶;或借7瓶汽水,还20个空瓶。
问m个学生每人喝1瓶汽水(瓶不带走),至少需多少元?
输入正整数m(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瓶汽水(瓶不带走),此时每人花费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*x+2*y)*1.40+t元。 (5)费用最低的算法描述 //喝汽水 main() {longm,t,x,y; printf("请输入m: ");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+11=19为素数,则3,5,11称为一个基于15的全素组。 定义所有基于n的全素组中和最大的称为最大全素组。 输入整数n(n≤3000),输出基于n的全素组的个数,并输出一个最大全素组。 数据测试: 2015 //全素组探求,c221 #include #include voidmain() {inti,j,k,i2,j2,k2,n,s,t,w,z,max,p[9000],q[1500]; longm; 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)p[i]=1;//奇数i为素数时标记p[i]=1 } w=0; for(i=3;i<=n;i=i+2) if(p[i]==1) {w++;q[w]=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;k<=w;k++) {s=q[i]+q[j]+q[k];//统计3个素数之和s if(p[s]==1) {m++;//统计全素组个数 if(s>max)//比较并记录最大全素组 {max=s;i2=q[i];j2=q[j];k2=q[k];} } } printf("共有%ld个全素组;\n",m); if(m>0) printf("一个最大全素组为: %d+%d+%d=%ld\n",i2,j2,k2,max); } 4.程序运行示例与分析 请输入整数n: 2015 共有1345431个全素组; 一个最大全素组为: 1997+2003+2011=6011 5.最简真分数 统计分母在指定区间[10,99]的最简真分数(分子小于分母,且分子分母无公因数)共有多少个,并求这些最简真分数的和。 设计求解一般情形: 统计分母在指定区间[a,b]的最简真分数的个数,并求这些最简真分数的和(正整数a,b从键盘输入)。 设分数分子为i,分母为j,最简真分数的个数为m,其和为s。 在指定范围[a,b]内枚举分数的分母j: a~b; 同时对每一个分母j枚举分子i: 1~j-1。 对每一分数i/j,置标志t=0,然后进行是否存在公因数的检测。 如果分子i与分母j存在大于1的公因数u,说明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 #include #include voidmain() {inta,b,i,j,t,u;longm=0; doubles; 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;//求最简真分数和 } } printf("最简真分数共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=73;n=2014 1.案例背景 佩尔(Pell)方程是关于x,y的二次不定方程,表述为 (其中n为非平方正整数) 当x=1或x=-1,y=0时,显然满足方程。 常把x,y中有一个为零的解称为平凡解。 我们要求佩尔方程的非平凡解。 佩尔方程的非平凡解很多,这里只要求出它的最小解,即x,y为满足方程的最小正数的解,又称基本解。 对于有些n,尽管是求基本解,其数值也大得惊人。 这么大的数值,如何求得? 其基本解具体为多少? 可以说,这是自然界对人类计算能力的一个挑战。 十七世纪曾有一位印度数学家说过,要是有人能在一年的时间内求出x2-92y2=1的非平凡解,他就算得上一名真正的数学家。 由此可见,佩尔方程的求解是有趣的,其计算也是繁琐的。 试设计程序求解佩尔方程: 。 2.枚举设计要点 应用枚举试值来探求佩尔方程的基本解。 设置y从1开始递增1取值,对于每一个y值,计算a=n*y*y后判别: 若a+1为某一整数x的平方,则(x,y)即为所求佩尔方程的基本解。 若a+1不是平方数,则y增1后再试,直到找到解为止。 应用以上枚举探求,如果解的位数不太大,总可以求出相应的基本解。 如果基本解太大,应用枚举无法找到基本解,可约定一个枚举上限,例如10000000。 可把y<=10000000作为循环条件,当y>10000000时结束循环,输出“未求出该方程的基本解! ”而结束。 3.解PELL方程程序设计 //解PELL方程: x^2-ny^2=1,c231 #include #include voidmain() {doublea,m,n,x,y; printf("解PELL方程: x^2-ny^2=1.\n"); printf("请输入非平方整数n: "); scanf("%lf",&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("方程x^2-%.0fy^2=1的基本解为: \n",n); printf("x=%.0f,y=%.0f\n",x,y); break; } } if(y>10000000) printf("未求出该方程的基本解! "); } 4.程序运行与分析 解PELL方程: x^2-ny^2=1. 请输入非平方整数n: 73 方程x^2-73y^2=1的基本解为: x=2281249,y=267000 为了提高求解方程的范围,数据结构设置为双精度(double)型。 如果设置为整形或长整形,方程的求解范围比设置为双精度型要小。 例如n=73时,设置整形或长整形就不可能求出相应方程的解。 可见,数据结构的设置对程序的应用范围有着直接的影响。 以上枚举设计是递增枚举,枚举复杂度与输入的n没有直接关系,完全取决于满足方程的y的数量。 解的y值小,枚举的次数就少。 解的y值大,枚举的次数就多。 对某些n,相应佩尔方程解的位数太大,枚举求解无法完成。 例如当n=991时,相应佩尔方程的基本解达30位。 此时依据以上枚举求解是无法实现的,只有通过某些专业算法(例如连分数法)才能进行求解。 7.分数不等式 解不等式 这里正整数m1,m2从键盘输入(m1 数据测试: m1=2015,m2=2016 为一般计,解不等式 (2) 这里正整数m1,m2从键盘输入(m1 设和变量为s,递增变量为i,两者赋初值为0。 在s<=m1的条件循环中,根据递增变量i对s累加求和,直至出现s>m1退出循环,赋值c=i,所得c为n解区间的下限。 继续在s<=m2的条件循环中,根据递增变量i对s累加求和,直至出现s>m2退出循环,通过赋值d=i-1,所得d为n解区间的上限。 注意,解的上限是d=i-1,而不是i。 然后打印输出不等式的解区间[c,d]。 3.解分数不等式程序设计 //解分数不等式,c241 #include #include voidmain() {longc,d,i,m1,m2; doubles; printf("请输入正整数m1,m2(m1 "); scanf("%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为: %ld≤n≤%ld\n",c,d); } 4.程序运行与分析 请输入正整数m1,m2(m1 2015,2016 满足不等式的正整数n为: 1018402≤n≤1019411 以上枚举算法的循环次数取决于解n的上限d,当输入的参数m2越大时,n也就越大,枚举的复杂度也就越高。 不等式中的上下限可取任意实数,请修改程序,把上下限m1,m2改为从键盘输入的任意实数(0.5 8.代数和不等式 试解下列关于正整数n的代数和不等式 (其中d为从键盘输入的正数) 式中符号为二个“+”号后一个“-”号,即分母能被3整除时为“-”。 数据测试: d=4;d=6 一般地,解不等式 (4) (其中d为从键盘输入的正数) 式中符号为二个“+”号后一个“-”号,即分母能被3整除时为“-”。 注意到式中出现减运算,可能导致不等式的解分段。 设置条件循环,每三项(包含二正一负)一起求和。 若加到1/n+1/(n+1)-1/(n+2)后,代数和s>d,退出循环,得一个区间解[n+1,∞]。 注意,此时n还须进行进一步检测。 然后回过头来一项项求和,包括对n的检测,得离散解。 3.程序设计 //解不等式: d<1+1/2-1/3+1/4+1/5-1/6+...±1/n,c242 #include voidmain() {longd,n,k; doubles; printf("请输入正整数d: "); scanf("%d",&d); printf("%d<1+1/2-1/3+1/4+1/5-1/6+…+-1/n的解: \n",d); n=1;s=0; while (1) {s=s+1.0/n+1.0/(n+
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 程序设计 竞赛 培训 题解 要点