2014程序设计竞赛培训题解答(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

void main()

{ int j,k,m,n,a[40000];

long g,t;double s;

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 ，显然有

2555m n n n s ??????=+++????????????

L

其中[x]为不大于x 的最大正整数，正整数m 满足155m m n +≤<。

这里统计s 只需设计一个简单的条件循环即可实现。 2） 算法描述

// 统计“5”因子设计,c135 #include void main() { long n,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） 数据检测与复杂度分析

基本求积算法为双循环设计，循环频数为mn 。注意到m>n ，把m 换算为n ， m 数量级估

算平均为n*logn ，因而基本求积算法的时间复杂度为O(n 2

logn)，空间复杂度为O(nlogn)。

统计“5”因子的设计大大简化了n! 尾部连续零个数的统计，算法的时间复杂度为O(logn)，空间复杂度为O(1)，显然大大优于基本求积算法。

统计“5”因子设计可大大拓展n 的范围，例如输入n 为20142015，可得20142015! 尾部连续零共5035500个，这一点基本求积算法因时间复杂度与空间复杂度太高而难以实现。

若案例稍加变通，需求n!结果所有数字中零的个数，基本求积算法（修改统计零的个数）可实现，而统计“5”因子算法却无法完成。

以上3个简单案例的求解都列举了两个不同的算法设计，并分析与比较了这些不同算法的时间复杂度。可见求解一个实际案例时，算法可能有多种多样，我们不必局限于某一个定式或某一种模式，可根据案例的具体实际确定算法进行设计求解。当面临处理的数据规模很大、或运行算法的时间很长时，选择时间复杂度低的算法是必要的，这也是我们进行算法设计所追求的目标。

2. 求最大公约数

求n 个正整数011,,,n m m m -L 的最大公约数 (011,,,n m m m -L )。

解：对于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 //C 头文件的调用 void main() { int k,n;

long a,b,c,r,m[100];

printf("请输入整数个数n: "); // 输入原始数据 请输入正整数n: 2015

2015! 尾部连续零共502个。

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

long gcd(long a,long b)

{ long c,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;

}

return b;

}

// 求n个整数的最大公约数,c145

#include

void main()

{ int k,n;

long x,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()

{ long m,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

void main()

{ int i,j,k,i2,j2,k2,n,s,t,w,z,max,p[9000],q[1500];

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) 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

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; // 求最简真分数和 }

}

printf(" 最简真分数共m=%ld 个。 \n",m); printf(" 其和 s=%.5f \n",s); }

4. 程序运行与分析

6. 佩尔方程

佩尔(Pell)方程是关于x,y 的二次不定方程，表述为 122=?-y n x （其中n 为非平方正整数）

当x=1或x=-1，y=0时，显然满足方程。常把x,y 中有一个为零的解称为平凡解。?我们要求佩尔方程的非平凡解。

佩尔方程的非平凡解很多，这里只要求出它的最小解，即x,y?为满足方程的最小正数的解，又称基本解。

输入非平方整数n ，输出佩尔方程：221x n y -?=的一个基本解。 数据测试： n=73;n=2014

1. 案例背景

佩尔(Pell)方程是关于x,y 的二次不定方程，表述为 122=?-y n x （其中n 为非平方正整数）

当x=1或x=-1，y=0时，显然满足方程。常把x,y 中有一个为零的解称为平凡解。?我们要求佩尔方程的非平凡解。

佩尔方程的非平凡解很多，这里只要求出它的最小解，即x,y?为满足方程的最小正数的

最简真分数分母在[a,b]内,请确定a,b: 100,999 最简真分数共m=300788个。 其和 s=150394.00000

解，又称基本解。

对于有些n ，尽管是求基本解，其数值也大得惊人。这么大的数值，如何求得？其基本解具体为多少？可以说，这是自然界对人类计算能力的一个挑战。十七世纪曾有一位印度数

学家说过，要是有人能在一年的时间内求出x 2-92y 2

=1的非平凡解，他就算得上一名真正的数学家。

由此可见，佩尔方程的求解是有趣的，其计算也是繁琐的。

试设计程序求解佩尔方程：17322=?-y x 。

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 void main() {double a,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. 程序运行与分析

为了提高求解方程的范围，数据结构设置为双精度（double ）型。如果设置为整形或长整形，方程的求解范围比设置为双精度型要小。例如n=73时，设置整形或长整形就不可能求出相应方程的解。可见，数据结构的设置对程序的应用范围有着直接的影响。

以上枚举设计是递增枚举，枚举复杂度与输入的n 没有直接关系，完全取决于满足方程的y 的数量。解的y 值小，枚举的次数就少。解的y 值大，枚举的次数就多。对某些n ，相应佩尔方程解的位数太大，枚举求解无法完成。例如当n=991时，相应佩尔方程的基本解达30位。此时依据以上枚举求解是无法实现的，只有通过某些专业算法（例如连分数法）才能进行求解。

7. 分数不等式

解不等式

21

4332211m n n m <+++++<

Λ 这里正整数m1,m2从键盘输入（m1

数据测试：m1=2015,m2=2016

为一般计，解不等式

21

4332211m n n m <+++++<

Λ （2） 这里正整数m1,m2从键盘输入（m1

设和变量为s ，递增变量为i ，两者赋初值为0。

在s<=m1的条件循环中，根据递增变量i 对s 累加求和，直至出现s>m1退出循环，赋值c=i ，所得c 为n 解区间的下限。

继续在s<=m2的条件循环中，根据递增变量i 对s 累加求和，直至出现s>m2退出循环，

解PELL 方程: x^2-ny^2=1. 请输入非平方整数 n:73 方程x^2-73y^2=1的基本解为: x=2281249, y=267000

通过赋值d=i-1，所得d 为n 解区间的上限。注意，解的上限是d=i-1，而不是i 。

然后打印输出不等式的解区间[c,d]。 3. 解分数不等式程序设计

// 解分数不等式,c241 #include #include void main()

{ long c,d,i,m1,m2; double s;

printf(" 请输入正整数m1,m2(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. 程序运行与分析

以上枚举算法的循环次数取决于解n 的上限d ，当输入的参数m2越大时，n 也就越大，枚举的复杂度也就越高。

不等式中的上下限可取任意实数，请修改程序，把上下限m1,m2改为从键盘输入的任意实数（0.5

8. 代数和不等式

试解下列关于正整数n 的代数和不等式

n

d 1

61514131211±+-++-+

<Λ （其中d 为从键盘输入的正数）

请输入正整数m1,m2(m1

式中符号为二个“+”号后一个“-”号，即分母能被3整除时为“-”。 数据测试：d=4;d=6

一般地，解不等式

n

d 1

61514131211±+-++-+

<Λ （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 void main() { long d,n,k; double s;

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+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. 程序运行示例

请输入正整数d: 5

5<1+1/2-1/3+1/4+1/5-1/6+…+-1/n 的解：

n>=203939

n=203936

n=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,...）至少都可以保证是离散解，对于区间解的下限还需要继续检测。

为求区间解的下限，需要对第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

void main()

{ long d,n,k;

double s;

printf(" 请输入正整数d: ");

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+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）程序运行示例

注意：前一个是离散解，而后一个是区间解。 6. 分析与变通

以上两个枚举算法的循环次数取决于解n 的上限，当输入的参数d 越大时，n 的上限也就越大，枚举的复杂度也就越高，求解也就变得越困难。

例如当d 逐渐增加到d>7时，解值n 会迅速增长而变得非常大，甚至超出相应变量的范围或计算机的计算范围，这时就不可能得到不等式的解。

变通：请把不等式中“二正一负”的规律改变为“三正一负”，程序应如何修改？求出修改后的不等式大于5的解。

9. 基于素数的代数和

定义和：

1

212131111997755331)(+-±+-++--=

n n n s Λ (和式中第k 项±(2k-1)/(2k+1)的符号识别：分子分母中有且只有一个素数，取“+”；

分子分母中没有素数或两个都是素数时取“-”。)

1) 求s(2016)(精确到小数点后5位)。

2) 设1<=n<=2016，当n 为多大时，s(n)最大。 3) 设1<=n<=2016，当n 为多大时，s(n)最接近0。

在求和之前应用“试商判别法”对第k 个奇数2k-1是否为素数进行标注： 若2k-1为素数，标注a[k]=1； 否则，若2k-1不是素数，a[k]=0。 设置k 循环（1～n ），循环中分别情况求和：

若a[k]+a[k+1]=1，即(2k-1)与(2k+1)中有且只有一个素数，实施“+”；

否则，若a[k]+a[k+1]!=1，即(2k-1)与(2k+1)中没有素数或有两个素数，实施“-”。 同时，设置存储最大值的变量smax ，存储最接近“0”的绝对值变量mi 。

请输入正整数d: 7

7<1+1/2-1/3+1/4+1/5-1/6+…+-1/n 的解：

n=82273511 n>=82273513

在循环中，每计算一个和值s，与smax比较确定最大值，同时记录此时的项数k1；

因和s可正可负，s的绝对值与mi比较确定最接近“0”的绝对值，记录此时的项数k2，同时记录此时的和值s2。

最后，求和循环结束时输出所求值。

3. 基于素数的分数和程序设计

// 基于素数的分数和,c251

#include

#include

void main()

{ int t,j,n,k,k1,k2,a[3000];

double s,s2,smax,mi;

printf(" 请输入整数n: ");

scanf("%d",&n);

for(k=1;k<=n+1;k++) a[k]=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) a[k]=1; // 标记第k个奇数2k-1为素数

}

s=0;smax=0;mi=10;

for(k=1;k<=n;k++)

{if(a[k]+a[k+1]==1) // 判断a[k]与a[k+1]中有一个素数

s+=(double)(2*k-1)/(2*k+1); // 实施加

else

s-=(double)(2*k-1)/(2*k+1); // 否则，实施减

if(s>smax)

{ smax=s;k1=k;} // 比较求最大值smax

if(fabs(s)

{ mi=fabs(s);k2=k;s2=s;} // 绝对值比较求最接近0点

}

printf("s(%d)=%.5f \n",n,s);

printf("当k=%d时s有最大值: %.5f\n",k1,smax);

printf("当k=%d时s=%.5f最接近0. \n",k2,s2);

}

4. 程序运行与分析

以上枚举算法的运算量是n ，但标注素数的运算量为3/2

n ，因而枚举算法的时间复杂度

为O(3/2

n

)。

变通： 请把题目中的条件“分子分母中有且只有一个素数，取‘+’”，改为“分子分母中至少有一个素数，取‘+’”，程序作何修改？并求出结果。

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(2～sqrt(a))循环枚举，如果k 是a 的因数，则a/k 也是a 的因数。显然k ≤a/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; 请输入整数n: 2016 s(2016)=-212.88337 当k=387时s 有最大值: 35.88835 当k=785时s=-0.04341最接近0.

printf(" 求区间[x,y]中整数的因数比最大值."); printf(" 请输入整数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=b^2,去掉重复因数b t=s/a; if(max

{max=t;a1=a;s1=s;}

}

printf(" 整数%.0f 的因数比最大：%.4f \n",a1,max); printf(" %.0f 的因数和为：\n",a1); printf(" %.0f=1",s1); // 输出其因数和式 for(k=2;k<=a1/2;k++) if(fmod(a1,k)==0) printf("+%.0f",k); }

（3） 程序运行与分析

设输入参数y 的数量级为n ，双重枚举循环的运算量为3/2

n ，即可知算法的时间复杂度为

O(3/2

n

)。

变通：如果整数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 已经相当庞大。

求区间[x,y]中整数的因数比最大值.请输入整数x,y: 1,2016 整数1680的因数比最大：2.5429

1680的因数和为：

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

11. 双和二组

把给定偶数2n 分解为6个互不相等的正整数a,b,c,d,e,f ，然后把这6个数分成(a,b,c)与(d,e,f)两个3元组，若这两个3元组具有以下双和相等特性：

f e d c b a f

e d c b a 111111++=++++=++

则把3元组(a,b,c)与(d,e,f)（约定a

4+10+12=5+6+15=26

1/4+1/10+1/12=1/5+1/6+1/15=13/30

输入正整数n(n ≤100)，搜索所有基于n 的双和二组。若没有探索到相应的双和二组，则输出“无解”。

数据测试：n=98

枚举设计要点

因6个不同正整数之和至少为21，即整数n ≥11。 （1） 枚举循环设置

设置a,b 与d,e 枚举循环。注意到a+b+c=n ，且a

设置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*b*c*(e*f+f*d+d*e) (*) 若式（*）不成立，即倒数和不相等，则返回。 （3） 省略相同整数的检测

同时注意到两个3元组中若部分相同部分不同，不能有和相等且倒数和也相等，即式（*）不可能成立（证略）。因而可省略排除以上6个正整数中是否存在相等的检测。

若式（*）成立，打印输出和为n 的双和二组，并用x 统计解的个数。 3. 双和数组程序设计

// 双和数组探索 ,c261 #include #include void main()

{ int a,b,c,d,e,f,x,n; 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++)

{ 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(" (%3d,%3d,%3d)；\n",d,e,f); }

if(x>0) printf(" 共以上%d 组解！\n",x); else printf(" 无解！\n"); }

4. 程序运行与分析

输入n=26，即得唯一一个双和二组如上面所示。输入任何小于26的整数n 均无解。可见存在双和二组的n 最小值为n=26。

由循环设置可知枚举复杂度为O(4

n )，显然不适宜对较大整数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元组具有以下两个和积相等特性：

i

h g f e d c b a i

h g f e d c b a ??=??=??++=++=++

则把(a,b,c)、(d,e,f)与( g,h,i) (约定a

请输入整数n: 98 1: ( 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组解！

编程基础练习题

第二章基本数据类型和运算 因为题目略有删减，可能编号不连续，请见谅 一、单项选择题 1．下列数据中属于“字符串常量”的是（A ）。 A. "a"B．{ABC} C．?abc\0?D．?a? 4．字符串"ABC"在内存占用的字节数是（ B ）。 A．3 B．4C．6 D．8 5．字符串" \?ABCD\? "内存占用的字节数是（ C ）。 A．4 B．6 C．7D．8 6．在C语言中,合法的长整型常数是（ A ）。 A．0L B．4962710 C．0.054838743 D．2.1869e10 7. 在C语言中,合法的短整型常数是（ D ）。 A．0L B．0821 C．40000 D．0x2a 8.下列数据中不属于“字符常量”的是（ C ）。 A．…\xff?B．…\160?C．?070?D．070 9．char型常量的内存中存放的是（ A ）。 A．ASCII代码值B．BCD代码值C．内码值D．十进制代码值 11.常数的书写格式决定了常数的类型和值，03322是（ B ）。 A、16进制int类型常数 B、8进制int类型常数 C、10进制int类型常数 D、10进制long int类型常数 12．“e2”是( D ) 。 A、实型常数100 B、值为100的整型常数 C、非法标识符 D、合法标识符 13. 要为字符型变量a赋初值，下列语句中哪一个是正确的（ A ）。 A、char a=?3?; B、char a=”3”; C、char a=%; D、char a=*; 14. 要为float类型变量x、y、z赋同一初值3.14，下列说明语句哪一个是正确的（C ）。 A、float x,y,z=3.14; B、float x,y,z=3*3.14; C、float x=3.14,y=3.14,z=3.14; D、float x=y=z=3.14; 15. 语句float pi=3.1415926535; 将（ D ）。 A、导致编译错误 B、说明pi为初值3.1415926535的单精度实型常数 C、导致运行时的溢出错误 D、说明pi为初值3.141593的单精度实型常数 16. 算术运算符、赋值运算符和关系运算符的运算优先级按从高到低依次为（ B）。 A、算术运算、赋值运算、关系运算 B、算术运算、关系运算、赋值运算 C、关系运算、赋值运算、算术运算 D、关系运算、算术运算、赋值运算 17. 关系运算符中优先级最低的运算符是（ C ）。 A、“>=”和“<=” B、“>”和“<” C、“==”和“!=” D、“<=”和“<” 18. 逻辑运算符中，运算优先级按从高到低依次为（ D ）。 A、&&，!，|| B、||，&&，! C、&&，||，! D、！，&&，|| 19. 对C程序在作逻辑运算时判断操作数真、假的表述，下列哪一个是正确的（ A ）。 A、0为假非0为真 B、只有1为真 C、-1为假1为真 D、0为真非0为假 20. 表达式x&&1等效于（ C ）

C语言程序设计竞赛题及其答案

数学与统计学院 第三届计算机程序设计竞赛题 竞赛需知： 1、答案必须写在答题纸上。 2、程序采用C/JAVA/VB/VFP语言实现均可。 3、考虑到各种因素，程序的键盘输入和结果输出可以用伪代码或者自然语言表示。但是必 须说明输入变量和输出变量。 4、题目最好能用完整、正确的语言程序来解决问题，如确实无法编写完整语言程序的，可 以写出程序主要框架和流程，必要时可以用伪代码或者自然语言描述算法（程序）。 一、玫瑰花数（20分） 如果一个四位数等于它的每一位数的4次方之和，则称为玫瑰花数。例如： + + 1634+ =， 4^4 4^3 4^6 4^1 编程输出所有的玫瑰花数。 #include void main() { int i,j,k,l,m; for(i=999;i<=9999;i++) { j=i/1000; k=i%10; l=i/100-10*j; m=i/10-100*j-10*l; if(i==j*j*j*j+k*k*k*k+l*l*l*l+m*m*m*m) printf("%d\n",i); } } 二、菱形图案（20分） 对给定的奇数n，编程打印菱形图案。 输入样例： 7 输出样例： * *** ***** ******* ***** *** * #include #include void main() {

int i,j,k; int n; scanf("%d",&n); for(i=0;i #include void main() { int i,j,x,y; float r; int a,b,count=0; printf("请输入矩阵的行列i,j:"); scanf("%d%d",&i,&j); printf("请输入圆心的坐标点及半径x,y,r:"); scanf("%d%d%f",&x,&y,&r); for(a=0;a

程序设计语言 习题与答案

第六章习题 P159-161 一、复习题 1、简述自然语言与形式语言的概念以及区别、汇编语言与机器语言的概念及区别。 自然语言是某一社会发展中形成的一种民族语言，而形式语言是进行形式化工作的元语言，它是以数学和数理逻辑为基础的科学语言。用机器指令形式编写的程序称为机器语言，用带符号或助记符的指令和地址代替二进制代码成为语言进化的目标。这些使用助记符语言的语言后来就被称之为汇编语言。（P144- P146） 2、试述计算机语言的类型，它们各有什么特点？ 1.机器语言，是最低级的语言，由二进制码组成，最早期的程序员通过在纸带上打点来写程序 2.汇编语言，用助记符和地址符代替了二进制码，更易于编写。 3.高级语言，相对于汇编语言又上升了一步，更接近于自然语言，如C语言、Pascal、Java、C#等都是高级语言。（P145-147） 3、列举程序设计语言的几种范型。 程序语言大致分为命令式程序设计语言、面向对象的程序设计语言、函数式程序设计语言和逻辑型程序设计语言等范型。（P147-149） 4、简述语言虚拟机。 提示：语言虚拟机是某种语言的解释器。语言虚拟机是建立在硬件和操作系统之上，针对不同的硬件和操作系统有不同的虚拟机，通过语言虚拟机屏蔽掉硬件的差异。这样使得硬件系统能够支持这种语言编写的程序的有效执行。目前最流行的语言虚拟机是Java虚拟机。（P156） 5、计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？ 提示：主要有编译、解释等方式，也有两种方式的混合使用的形式。 编译是使用编译器将高级语言编写的源程序转换成计算机可以执行的机器语言可执行程序，也可以理解为用编译器产生可执行程序的动作。编译方式是一次编译，然后执行程序可以反复多次执行。 解释是另一种将高级语言转换为可执行程序的方式。与编译不同，解释性语言的程序不需要编译，省了道工序，解释性语言在运行程序的时候才翻译，每个语句都是执行的时候才翻译。这样解释性语言每执行一次就要翻译一次，效率比较低。 近来随着网络的发展，为了实现跨平台但同时又保证一定的效率，出现了编译、解释混合的方式，先用伪编译形成效率较高中间代码，再用语言虚拟机进行解释执行，以屏蔽掉硬件的差异。 (P154-157) 6、请画出编译程序的总框图。如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？ 作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，

程序设计比赛试题

程序设计比赛试题 最少钱币数： 【问题描述】 这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了6种钱币面值为2、5、10、20、50、100，用来凑15元，可以用5个2元、1个5元，或者3个5元，或者1个5元、1个10元，等等。显然，最少需要2个钱币才能凑成15元。 你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。 【要求】 【数据输入】输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值M （1<=M<=2000，整数），接着的一行中，第一个整数K（1<=K<=10）表示币种个数，随后是K个互不相同的钱币面值Ki(1<=Ki<=1000)。输入M=0时结束。 【数据输出】每个测试用例输出一行，即凑成钱数值M最少需要的钱币个数。如果凑钱失败，输出“Impossible”。你可以假设，每种待凑钱币的数量是无限多的。 【样例输入】 15 6 2 5 10 20 50 100 1 1 2 【样例输出】 2 Impossible

Feli的生日礼物 【问题描述】 Felicia的生日是11月1日（和Kitty是同一天生的哦）。于是Feli请来Kitty一起过生日。Kitty带来了最新款的“Kitty猫”玩具准备送给Feli，不过她说，这份礼物可不是白送的。Feli要帮她一个忙，才能够得到心仪已久的玩具。Kitty说，“Kitty猫”玩具已经卖出了n!个，n<=10^100*_*，Kitty想知道确切的数字，而不是无聊的“一个数加个感叹号”。Feli听了大吃一惊。要知道，算出n!是一个无比艰巨的任务。Feli告诉Kitty，就算Feli算出n!，Kitty也看不下去，因为当n=20时，计算机的长整型已经存不下了（Kitty只能接受1-9之间的数字）。于是Kitty说，你只要告诉我n!最后一位非0的数就可以了。Feli想了想，立刻动手写了个程序算出了正确的答案。现在，请你也试试看！注意哦，AC的男生将会得到一个“Hello Kitty”计算器（可编程，CPU 1THz，Mem 1TMB），AC的女生将会得到一个仿真“Hello Kitty”宠物（善解人意，无须喂养，智商1101，附带写情书功能）。 【要求】 【数据输入】每行一个n，直到输入数据结束 【数据输出】对应输入的n，每行输出一个答案 【样例输入】 1101 【样例输出】 8

《程序设计基础》练习题

《程序设计基础》综合练习题1009 姓名：学号： 一．选择题(以熟悉概念为主) 1．在C++的结构化程序设计框架中，程序的基本组成单元是___。 A．函数B．类 C．关系D．数据结构 2．下列特性中， C 与C++ 共有的是_____。 A. 继承 B. 封装 C. 多态性 D. 函数定义不能嵌套 3．面向对象程序设计思想的主要特征中，不包含____。 A．继承性B．封装性和信息隐藏性 C．功能分解、逐步求精D．多态性 4．在C++中所有的函数名称后面都紧跟着一对____，其中既可以没有内容，也可以包含函有选举权的参数。 A．( ) B．< > C．[ ] D．{ } 5．在C++的面向对象程序设计中，类与类之间通过____来实现独立性。 A．友元B．继承C．派生D．封装 6．下列哪个是C++语言的有效标识符？____。 A．_No1 B．No.1 C．12345 D．int 7．在C++语言中，所有函数说明都必须指明返回值类型，没有返回值的函数应说明为____类型的函数。 A．int B．char C．float D．void 8．下列字符常量的写法中，错误的是____。 A．?\105?B．?*?C．????D．?\a? 9．下列变量的存储分配方式中，系统不为其分配内存空间的是____。 A．auto变量B．register变量C．static变量D．extern变量 10．如int型变量x的初始值为1，变量y和t皆为int型，且表达式y=(t=x,x+=t, t)，则变量y的值为____。 A．0 B．1 C．2 D．不确定 11．下列关于C++运算符结合性的说法中，正确的是____。 A．赋值运算符是左结合的B．复合赋值运算符是左结合的 C．单目运算符是左结合的D．双目算术符是左结合的 12．表达式18/5*sqrt(4.0)/5值的数据类型是____。 A．int B．double C．float D．不确定 13．下列代码的输出结果是____。 int j=int( ); double d=double( ); cout<

程序设计竞赛试题和题解

程序设计竞赛试题和题解 付浩fuch@https://www.doczj.com/doc/616648131.html, Contents 完全平方数 (2) 拉丁方阵 (3) 取石子游戏 (5) 乡村医院 (7) 未知星球 (9) 无聊的游戏 (10) 最短路径 (12)

完全平方数 描述 一个非负整数n是完全平方数当且仅当存在非负整数m，使得n=m2 据说完全平方数具有某种神奇的力量，谁知道呢。 聪明的你一定想到了，这道题的任务就是编写一个程序，判断给定的n是否是完全平方数。 输入格式 输入包含多组数据。 每组数据占一行，包含一个非负整数n，n不超过109 输入以n=-1结束 输出格式 对每组输入数据输出一行，如果n是完全平方数则输出”Yes”，否则输出”No” 输入样例 1 2 3 4 -1 输出样例 Yes Yes No No Yes 解答 一般的语言都有开平方运算吧？

拉丁方阵 描述 拉丁方阵是一种n×n的方阵，方阵中恰有n种不同的元素，每种元素恰有n个，并且每种元素在 一行和一列中恰好出现一次。著名数学家和物理学家欧拉使用拉丁字母来作为拉丁方阵里元素的 符号，拉丁方阵因此而得名。例如下图是一个3×3的拉丁方阵： 如果一个拉丁方阵的第一行和第一列按照元素的先后顺序来排列，那么这称为拉丁方阵的标准型，例如下图就是一个3x3的拉丁方阵标准型，第一行和第一列都是”1 2 3”。 你的任务是，编写一个程序读入一个方阵，判断其是否为拉丁方阵；进一步地，判断是否为标准型。 输入格式 输入包含多组数据。 每组数据第一行为正整数n，表示方阵的大小。 其后n行，每行有n个1到n之间的整数，整数之间恰有一个空格，表示方阵的内容。 输入保证1≤n≤100 输入以n=0结束，不要处理这个数据。 输出格式 每组数据对应于一行输出。如果输入是拉丁方阵，但不是标准型则输出1；如果输入是标准型则 输出2；如果输入不是拉丁方阵则输出0 输入样例 2 1 1

《计算机程序设计基础》课后练习题参考答案

《计算机程序设计基础》课后练习题1 一．判断题 (1)（错）事件过程由某个用户事件或系统事件触发执行，但不能被其他过程调用。 (2)（错）若X＝2, Y＝5，则表达式 Y－2>X AND X＋2＞Y 的结果为：True。 (3)（错）常量是指在程序运行过程中其值可以改变的那些量。 (4)（错，timer没有）VB工具箱中的所有控件都具有宽度（Width）和高度（Height）属 性。 (5)（错）定义变量：Dim max,min as Single , 则max 和 min 的数据类型均为Single。 (6)（对）如果创建的菜单项的标题是一个减号“-”，则该菜单项显示为一条分隔线。 (7)（错）标准模块文件的扩展名是“*.VBP”。 (8)（错，都不能）定时器控件可以响应Click事件，但不能响应DbClick事件。 (9)（错）在默认情况下，数组下标下界的缺省值为1。 (10)（对）在使用字体对话框时，需要对其Flags属性先进行相应设置。 二．单选题 (11)在Visual Basic中，表示鼠标单击事件的是 C 。 A）Activate B）DoubleClick C）Click D）MouseDown (12)用于设置计时器时间间隔的属性是 A 。 A）Interval B）Name C）Left D）Top (13)函数Int(10*Rnd)是在 D 范围内的整数。 A）[1，10] B）[1，10] C) [0，9) D）[0，9] (14)Select case语句结构的结尾应使用 D 。 A）End B） End Case C） End Sub D） End Select (15)改变了容器的坐标系后，该容器的 A 属性值不会改变。 A）left B）scaleleft C）scaletop D）scalewidth (16)执行下列语句后，列表框中各表项顺序为 D List1.Clear For i=1 to 4 : List1.AddItem i-1,0 ：Next i A）B）C）D） (17)输入对话框InputBox的返回值的类型是 A 。

程序设计基础练习题(全答案版)

《程序设计基础——C#.NET》练习 参考答案： 一、选择题 https://www.doczj.com/doc/616648131.html,的目的就是将____A____作为新一代操作系统的基础,对互联网的设计思想进行扩展。A．互联网 B. Windows C. C# D. 网络操作系统 2.假设变量x的值为10,要输出x值,下列正确的语句是__C__。 A．System.Console.writeline(“x”) B. System.Cosole.WriteLine(“x”) C. System.Console.WriteLine(“x={0}”,x) D. System.Console.WriteLine(“x={x}”) 3.要退出应用程序的执行,应执行下列的_A___语句。 A. Application.Exit(); B. Application.Exit; C. Application.Close(); D. Application.Close; 4.关于C#程序的书写,下列不正确的说法是__D________。 A．区分大小写 B．一行可以写多条语句 C．一条语句可以写成多行 D．一个类中只能有一个Main（）方法，因此多个类中可以有多个Main（）方法 5. 在C#语言中，下列能够作为变量名的是__C__。 A．if B. 3ab C. b_3a D. a-bc 7. 能正确表示逻辑关系“a≥5或a≤0”的C#语言表达方式是__D__。 A．a>=5 or a<=0 B. a>=5|a<=0 C. a>=5&&a<=0 D. a>=5||a<=0 8. 以下程序的输出结果是___C_____。 A. 5 B. 4 C. 6 D. 不确定 9. If语句后面的表达式应该是__A___。 A．逻辑表达式 B. 条件表达式 C. 算术表达式 D. 任意表达式10．有如下程序:

第六届程序设计比赛题目与答案

一、鸡兔同笼 问题描述 一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物 输入数据 第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a (a < 32768)。 输出要求 n行，每行输出对应一个输入。输出是两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用空格分开。如果没有满足要求的情况出现，则输出2个0。 输入样例 2 3 20 输出样例 0 0 5 10 解题思路 这个问题可以描述成任给一个整数N，如果N是奇数，输出0 0，否则如果N是4的倍数，输出N / 4 N / 2，如果N不是4的倍数，输出N/4+1 N/2。这是一个一般的计算题，只要实现相应的判断和输出代码就可以了。题目中说明了输入整数在一个比较小的范围内，所以只需要考虑整数运算就可以了。 参考程序 1.#include 2.void main( ) 3.{ 4.int nCases, i, nFeet; //nCases 表示输入测试数据的组数，nFeet表示输入的脚数。 5.scanf("%d", &nCases); 6.for(i = 0; i < nCases; i++){ 7.scanf("%d", &nFeet); 8.if(nFeet %2 != 0) // 如果有奇数只脚，则输入不正确， 9.// 因为不论2只还是4只，都是偶数 10.printf("0 0\n"); 11.else if (nFeet%4 != 0) //若要动物数目最少，使动物尽量有4只脚 12.//若要动物数目最多，使动物尽量有2只脚 13.printf("%d %d\n", nFeet / 4 + 1, nFeet / 2); 14.else printf("%d %d\n", nFeet / 4, nFeet / 2); 15.} 16.}

程序设计基本训练题集

程序设计基本训练题集 （C语言程序设计） C语言程序设计精品课程组

一、基础题 1. 编程，统计在所输入的50个实数中有多少个正数、多少个负数、多少个零。 2. 编程，输入一个10进制正整数，然后输出它所对应的八进制、十六进制数。 3. 输入20个整数存入一个整型数组，输出其中能被数组中其它（只需其中一个）元素整除的那些数组元素。 4. 输入两个数组（数组元素个数自定），输出在两个数组中都出现的元素（如 a[5]={2,3,4,5,6}，b[6]={3,5,7,9,10,-1}，则输出3、5）。 5. 输入两个数组（数组元素个数自定），输出在两个数组中都不出现的元素（如 a[5]={2,3,4,5,6}，b[6]={3,5,7,9,10,-1}，则输出2、4、6、3、7、9、10、-1）。6．给定年份year，判别该年份是否闰年，要求： 6-1 一般算法； 6-2 用宏实现：定义一个宏以判别该年份是否闰年。 7．给定一个日期（年/月/日）计算该日期是所在年的第几天。 8. 编写一个函数，处理n行、n列的二维数组：将每一行的元素同除以该行上绝对值最大的元素。 9. 设计一个函数，求给出数的补码。 10．编写一个程序，输入月份号，输出该月份的英文月名，要求用指针数组处理。 11. 编写函数，求m行、n列的二维数组全体元素中负数的个数。 12. 编写函数，返回在一个整数组中出现次数最多的数及其出现次数。 13. 编写函数，在n个元素的一维数组中，统计比相邻元素大的数组元素个数并将统计数返回（不考虑a[0]和a[n-1]）,要求以指针变量而不是数组名作参数。 14. 编写函数，在n个元素的一维数组中，找出最大值、最小值并传送到调用函数。 15. 编写一个函数，统计m行n列二维数组中有多少个正数、多少个负数，多少个零，并返回统计结果。 16．输入一个数组，删除数组中的负数。 17．有4名学生每个学生考4门课程，要求在用户输入学生学号以后能输出该生的全部成绩，用指针型函数来实现。请编写函数float *search(). main() {static float score[][4]={{60,76,80,90},{45,86,57,90},{58,95,80,71},{78,50,60,85}}; float *search(),p; int I,m; printf(“enter the number of student:”); scanf(“%d”,&m); printf(“the score of NO.%dare:\n”,m); p=search(score,m); for(I=0;I<4;I++) printf(“%52f\t”,*(p+I)); } float *search(float (pointer)[4],int n)

程序设计大赛试题及答案

试题 1、数学黑洞（程序文件名maths.c/maths.cpp） 【问题描述】 任给一个4位正整数，其各位数位上的数字不全相同，将数字重新组合成一个最大的数与最小的数相减，重复这个过程，最多7步，必得6174。对任给的4位正整数（各位数位上的数字不全相同），编程输出掉进黑洞的步数。 【输入】 一行，一个4位正整数n（1000< n<9999） 【输出】 掉进黑洞的步数 输入 1234 输出 3 2、进制转换（程序文件名conver.c/conver.cpp） 【问题描述】 任给一个十进制整数n,及正整数m(m<=16且m≠10), 将n转换成m进制并输出。 【输入】 一行，两个整数n，m（0 ≤ n ≤ 500000，2 ≤ m ≤ 16，且m≠10），中间用一个空格隔开，其中n 表示十进制数。 【输出】 转换后的数 【输入输出样例】 输入 255 8 输出 377 3、分数线划定（程序文件名score.c/score.cpp） 【问题描述】 公务员选拔工作正在 A 市如火如荼的进行。为了选拔优秀人才，A 市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的150%划定，即如果计划录取m名公务员，则面试分数线为排名第m*150%（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。 【输入】 第一行，两个整数n，m（5 ≤ n ≤ 5000，3 ≤ m ≤ n），中间用一个空格隔开，其中n 表示报名参加笔试的选手总数，m 表示计划录取的人数。输入数据保证m*150%向下取整后小于等于n。 第二行到第 n+1 行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号k（1000 ≤ k ≤ 9999）和该选手的笔试成绩s（1 ≤ s ≤ 100）。数据保证选手的报名号各不相同。 【输出】 第一行，有两个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。 从第二行开始，每行包含两个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。 【输入输出样例】 输入 6 3 1000 90 3239 88 2390 95 7231 84 1005 95 1001 88

程序设计基本训练题集

程序设计基本训练题集，给你拿去做着玩吧！！ 一、基础题 1. 编程，统计在所输入的50个实数中有多少个正数、多少个负数、多少个零。 2. 编程，输入一个10进制正整数，然后输出它所对应的八进制、十六进制数。 3. 输入20个整数存入一个整型数组，输出其中能被数组中其它（只需其中一个）元素整除的那些数组元素。 4. 输入两个数组（数组元素个数自定），输出在两个数组中都出现的元素（如a[5]={2,3,4,5,6}，b[6]={3,5,7,9,10,-1}，则输出3、5）。 5. 输入两个数组（数组元素个数自定），输出在两个数组中都不出现的元素（如a[5]={2,3,4,5,6}，b[6]={3,5,7,9,10,-1}，则输出2、4、6、3、7、9、10、-1）。 6．给定年份year，判别该年份是否闰年，要求： 6-1 一般算法； 6-2 用宏实现：定义一个宏以判别该年份是否闰年。 7．给定一个日期（年/月/日）计算该日期是所在年的第几天。 8. 编写一个函数，处理n行、n列的二维数组：将每一行的元素同除以该行上绝对值最大的元素。 9. 设计一个函数，求给出数的补码。 10．编写一个程序，输入月份号，输出该月份的英文月名，要求用指针数组处理。 11. 编写函数，求m行、n列的二维数组全体元素中负数的个数。 12. 编写函数，返回在一个整数组中出现次数最多的数及其出现次数。 13. 编写函数，在n个元素的一维数组中，统计比相邻元素大的数组元素个数并将统计数返回（不考虑a[0]和a[n-1]）,要求以指针变量而不是数组名作参数。 14. 编写函数，在n个元素的一维数组中，找出最大值、最小值并传送到调用函数。 15. 编写一个函数，统计m行n列二维数组中有多少个正数、多少个负数，多少个零，并返回统计结果。16．输入一个数组，删除数组中的负数。 17．有4名学生每个学生考4门课程，要求在用户输入学生学号以后能输出该生的全部成绩，用指针型函数来实现。请编写函数float *search(). main() {static float score[][4]={{60,76,80,90},{45,86,57,90},{58,95,80,71},{78,50,60,85}}; float *search(),p; int I,m; printf(“enter the number of student:”); scanf(“%d”,&m); printf(“the score of NO.%dare:\n”,m); p=search(score,m); for(I=0;I<4;I++) printf(“%52f\t”,*(p+I)); } float *search(float (pointer)[4],int n) {} 18．有4名学生每个学生考4门课程，要求在用户找出有不及格课程的学生学号并输出全部成绩，用指针来实现。 19．编写一个函数实现将一个整数按逆序存放到一个数组中。

C语言程序设计大赛题目

日本一位中学生发现一个奇妙的“定理”，请角谷教授证明，而教授无能为力，于是产生角谷猜想。猜想的内容是：任给一个自然数，若为偶数除以2，若为奇数则乘3加1，得到一个新的自然数后按照上面的法则继续演算，若干次后得到的结果必然为1。请编程验证。 *问题分析与算法设计 本题是一个沿未获得一般证明的猜想，但屡试不爽，可以用程序验证。 题目中给出的处理过程很清楚，算法不需特殊设计，可按照题目的叙述直接进行证。 *程序说明与注释 #include int main() { int n,count=0; printf("Please enter number:"); scanf("%d",&n); /*输入任一整数*/ do{ if(n%2) { n=n*3+1; /*若为奇数，n乘3加1*/ printf("[%d]:%d*3+1=%d\n",++count,(n-1)/3,n); } else { n/=2; /*若为偶数n除以2*/ printf("[%d]: %d/2=%d\n",++count,2*n,n); } }while(n!=1); /*n不等于1则继续以上过程*/ }

数论中著名的“四方定理”讲的是：所有自然数至多只要用四个数的平方和就可以表示。请编程证此定理。 *问题分析与算法设计 本题是一个定理，我们不去证明它而是编程序验证。 对四个变量采用试探的方法进行计算，满足要求时输出计算结果。 #include #include int main() { int number,i,j,k,l; printf("Please enter a number="); scanf("%d",&number); /*输入整数*/ for(i=1;i int main() { int a,b,c,d; printf("Please enter a number:"); scanf("%d",&a); /*输入整数*/ b=a*a*a; /*求整数的三次方*/ printf("%d*%d*%d=%d=",a,a,a,b); for(d=0,c=0;c

小学生程序设计复赛练习题

小学生程序设计比赛练习题 1.幸运数字 (luck.pas/c/cpp) 【问题描述】 今年圣诞节，小明收到了很多礼物，每个礼物上都有一个数字，表示对小明的祝福。可是小明有自己的想法，对小明来说，4或者7的倍数是幸运数字。 现在，小明想要知道所有数字中幸运数字之和是多少？请你帮帮小明！ Sheryl gōngchéng zài quánguó de Brada ruǎnjiàn gōngsī. Tā de gōngzuò shì kāifā Windows cāozuò xìtǒng. Zài Brada bǎoshǒu de ràng rén nányǐ zhìxìn. Tāmen shènzhì cónglái méiyǒu shǐyòng de túxíng xiǎnshìqì! Yīncǐ,Sheryl de cāozuò xìtǒng yùnxíng zài wénběn móshì hé zài yóu zìfú zǔchéng de xìtǒng chuāngkǒu. Sheryl juédìng, měi gè chuāngkǒu dōu yǒu yīgè ID, zhè shì yīgè zīběn yīngwén zìmǔ ('yī'dào'Z'). Yóuyú měi gè chuāngkǒu yǒu yīgè wéi yī de ID, bùnéng yǒu chāoguò 26 gè chuāngkǒu zài tóngyī shíjiān. Rú nǐ suǒ zhī, suǒyǒu de Windows shì chángfāngxíng. Zài zhè zhǒng chǒulòu de Windows xìtǒng de píngmù, chuāngkǒu de kuàngjiàyǐ jīběn xíngchéng yóu tā de ID xìn. Tú 1 xiǎnshì, zhǐyǒu píngmù shàng de yīgè chuāngkǒu, gāi chuāngkǒu de ID shì'A'. Windows kěnéng huì chóngdié. Tú- 2 xiǎnshì chuāngkǒu de qíngkuàng B duì chuāngkǒu a. Hé tú- 3 de dǐng bù shì tígōng le gèng fùzá de chóngdié. Dāngrán, rúguǒ yīgè chuāngkǒu de mǒu xiē bùfèn shì yóu qítā chuāngkǒu zhē zhù, nǐ bùnéng zài píngmù shàng kàn dào de bùfèn. 字典- 查看字典详细内容 【输入】 第一行一个整数n，表示小明收到了n份圣诞礼物。 第二行包含n个整数，第i个数a[i]表示第i份礼物上的数字。 【输出】 输出小明心目中的幸运数字之和。 【样例解释】 小明的幸运数字必须是4或者7的倍数，这里符合条件的有：12+14+16=42 【数据范围】 40%的数据，n<=100, 0

Html5程序设计基础教程(练习题参考答案)

第1章HTML 5概述 一、选择题 1．A 2．D 3．C 4．C 二、填空题 1．HyperText Markup Language 2． 3．HTML 4．UTF-8 5．