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

《2014程序设计竞赛培训题解答(1)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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重循环，模拟整数竖式乘法实施各数组元素的累乘

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#includevoidmain(){intj,k,m,n,a[40000];longg,t;doubles;printf(

3、"请输入正整数n(n<10000):");scanf("%d",&n);//输入ns=0;for(k=2;k<=n;k++)49s+=log10(k);//对数累加确定n!的位数mm=(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,j-1);//输出n!尾部零个数}（2）统

4、计“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#includevoid

5、main(){longn,s,t;printf("请输入正整数n:");scanf("%ld",&n);//输入ns=0;t=1;while(t<=n){t=t5;s=s+n/t;}//循环统计尾部连续0的个数printf("%ld!尾部连续零共%ld个。",n,s);//输出结果}（3）数据检测与复杂度分析49请输入正整数n:20152015!尾部连续零共502个。基本求积算法为双循环设计，循环频数为mn。注意到m>n，把m换算为n，m数量级估算平均为nlogn，因而基本求积算法的时间复杂度为O(n2logn)，空间复杂度为O(nlogn)。统计“5”因子

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

7、于某一个定式或某一种模式，可根据案例的具体实际确定算法进行设计求解。当面临处理的数据规模很大、或运行算法的时间很长时，选择时间复杂度低的算法是必要的，这也是我们进行算法设计所追求的目标。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个

8、数与b的最大公约数；……