（信息学奥赛辅导）程序设计试题汇编（答案）

信息学奥林匹克竞赛辅导——程序设计试题答案部分 第1页

程序设计试题及答案

（备注：试题难度评价采取五★级评价体系，分基础、容易、一般、稍难、难五个等级。

其中的一、二、三★级都属于程序设计的基础试题级别，同学们稍加思考均有能力求得正确解答。

对于四★级试题属于程序设计试题基础级别的思考题.

五★级难度试题在此没有涉及，在程序设计高级试题中另行讲解。对于基础和容易两个级别的程序设计试题，若能够给出语句分类（如If条件语句、条件语句嵌套、循环语句、多重循环语句等）的将尽量给出。若属于13大类别的将尽量标注。）

程序设计试题几大分类：

1、素数类问题（求素数的几种算法）： 2、数据排序问题（数据排序的几种方法）： 3、最大公约数和最小公倍数问题（几种算法）：

4、公式求解类问题（如求圆周率π、自然常数e、解方程等等）： 5、编号相反处理问题：

6、约瑟夫问题（或猴子选大王问题、密码问题）： 7、回文数问题：

8、高精度数值计算问题： 9、数值计算问题：

10、 进制相互转换问题： 11、 字符串倒置问题： 12、 排列与组合类问题：

13、 因子、质因子（质因数）类相关问题：

答案部分：

（程序设计的源程序没有统一的标准答案，实现程序的算法也是多种多样，但结果是唯一的，算法也有优劣之分，一个程序的优劣，关键在于是否找到了好的算法，以下程序和算法不一定就是最佳算法和最佳程序，只能仅供参考，希望同学们能够对某些程序提出更好的算法来改进程序） （经常碰到的判断是否为素数、是否为回文数、求两个数的最大公约数、求两个数的最小公倍数等问题的子函数源程序，请务必记住！）

①判断是否为素数，若是素数则返回true，若不是素数则返回false：

function prime(x:longint):boolean; var

j,y:longint; begin

prime:=true;

if x<2 then prime:=false; y:=trunc(sqrt(x)); for j:=2 to y do

if (x mod j = 0) then

begin prime:=false; exit; end;

信息学奥林匹克竞赛辅导——程序设计试题答案部分 第2页

end;

备注：1～100之间所有的素数：2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53 59、61、67、71、73、79、83、89、97。（共25个）

②判断是否为回文数，若是回文数则返回true，若不是回文数则返回false：

function huiwen(n:longint):boolean; var

m,i,j:longint;

a:array[1..10] of integer; begin

if n<0 then begin huiwen:=false; exit; end; m:=n; i:=0; huiwen:=true; repeat i:=i+1;

a[i]:=m mod 10; m:=m div 10; until m=0;

for j:=1 to (i div 2) do if a[j]<>a[i-j+1] then

begin huiwen:=false; exit; end; end;

③求最大公约数子函数，返回两个正整数的最大公约数，采用辗转相除法算法； function gcd(a,b:longint):longint; begin

if b=0 then gcd:=a

else gcd:=gcd(b,a mod b); end;

④求最小公倍数：lcm=a*b div gcd(a,b);

（以下程序设计试题来自《奥赛经典（语言篇）》） 第2章 基本语句与程序结构

例题部分：

1、 求梯形的面积。（梯形面积公式：S?（★，测试数据①

1h(a?b)） 2?b?b2?4ac2、 求一元二次方程ax＋bx＋C＝0的两个实根。（求根公式：x1,2?）

2a2

（★，测试数据a＝1，b＝－5，c＝6；答案：x1＝2、x2＝3）

3、 输入一个三位的自然数，然后把这个数的百位与个位对调，输出对调后的结果。

（★）

4、 输入三个数a、b、c，首先判断这三个数能否构成三角形，若能，则求出三角形的面积。 （提示：海伦公式S?d(d?a)(d?b)(d?c)，其中d?a?b?c，a、b、c为边长） 2（★，If条件语句，测试数据a＝5，b＝6，c＝7；答案：14.7）

信息学奥林匹克竞赛辅导——程序设计试题答案部分 第3页

5、 从键盘读入三个数，按从大到小的顺序把它们打印出来。（★，If条件语句） 6、 输入三角形的三边，判断它是否是直角三角形。

（★，If条件语句，测试数据①3、4、5；②4、5、6；答案①Yes；②No） program ex7; var a,b,c:integer; begin

reanln(a,b,c);

if (a*a+b*b=c*c ) or ( b*b+c*c=a*a ) or (c*c+a*a=b*b ) then writeln(‘yes’) else writeln(‘no’); end.

7 编写一个根据用户键入的两个操作数和一个运算符，由计算机输出运算结果的程序。（★★★）

program ex71;

var a,b,s:integer;(real) begin

reanln(a,b); s:=a+b; writeln(s); end.

program ex72;

var a,b,s:integer;(real) begin

reanln(a,b); s:=a-b; writeln(s); end.

program ex73;

var a,b,s:integer;(real) begin

reanln(a,b); s:=a*b; writeln(s); end.

program ex74; var a,b,s:(real); begin

reanln(a,b); s:=a/b; writeln(s); end.

8 输入一个年号，判断它是否为闰年。

（★，If条件语句，测试数据①1900；②2000；③2008；答案：①No；②Yes；③Yes） program ex8; var a:integer;

信息学奥林匹克竞赛辅导——程序设计试题答案部分 第4页

begin readln(a);

if (a mod 4=0 ) and (( a mod 100 ) mod 400=0 ) then writeln(‘yes’) else writeln(‘no’); end.

9 编程计算S＝1＋2＋3＋?＋100。（★，循环语句， 答案：5050）

program e; var I,s:integer; begin s:=0;

for i:=1 to 100 do s:=s+I; writeln(s); end.

相关练习：

（1）S?1?111????； 23100program e1;

var I:integer; s:real; begin s:=0;

for i:=1 to 100 do s:=s+1/I; writeln(s); end.

（2）S?1?2???100； program e2; var I,s:integer; begin s:=0;

for i:=1 to 100 do s:=s+I*i; writeln(s); end.

（3）S?2?4?6???100； program e3; var I,s:integer; begin s:=0;

for i:=1 to 50 do s:=s+I*2;

222信息学奥林匹克竞赛辅导——程序设计试题答案部分 第5页

writeln(s); end.

（4）S?1?4?7?10???100； program e; var I,s:integer; begin s:=0;

for i:=1 to 100 do if I mod 3=1 then s:=s+I; writeln(s); end.

（相关练习答案：（1）5.19（保留2为小数）；（2）338350；（3）2550；（4）1717） a) 根据公式

?26?1?111????，计算圆周率的π值。 2232n2（★★，循环语句，测试数据n＝10000；答案：3.1414971639）

program e; var i:longint; s:real; begin

writeln; s:=0;

for i:=1 to 10000 do s:=s+1/(i*i); writeln(sqrt(6*s)); end.

b) 计算n!。（n!＝1×2×3×?×n，取n＝10）

（★★，循环语句，10！＝3628800） program e11; const n=10; var I,s:integer; begin s:=1;

for i:=1 to n do s:=s*i; writeln(s); end.

c) 已知一对兔子，每个月可以生一对小兔，而小兔过一个月后也可生一对小兔。即兔子的对数

是：第一个月1对，第二个月2对，第三个月3对，第四个月5对，??，假设兔子的生育期是12个月，并且不死，问一年后，这对兔子有多少对活着的后代？（Fibonacci数列问题） （★★，循环语句， 1、2、3、5、8、13、21、34、55、89、144、233；答案233）

program work(input,output); var i:integer;{循环变量}

信息学奥林匹克竞赛辅导——程序设计试题答案部分 第46页

（测试数据：25！＝15511210043330985984000000；） program e; var

a,b,c:array[0..1000] of byte; n,i,j,k:integer; procedure cheng; var

i,j,k:integer; begin

for i:=1 to a[0] do for j:=1 to b[0] do begin

c[i+j-1]:=c[i+j-1]+(a[i]*b[j] mod 10);

c[i+j]:=c[i+j]+(a[i]*b[j] div 10)+(c[i+j-1] div 10); c[i+j-1]:=c[i+j-1] mod 10; end; end;

procedure shuchu; var

i:integer; begin

while c[c[0]]=0 do dec(c[0]);

for i:=c[0] downto 1 do write(c[i]); end;

{============main=========} begin

writeln; writeln('input n(<=100):'); readln(n); c[1]:=1; for i:=1 to n do begin

j:=1000;

while c[j]=0 do dec(j); a[0]:=j;

for k:=j downto 1 do begin a[k]:=c[k]; c[k]:=0; end;

b[1]:=i mod 10; b[2]:=(i div 10) mod 10; b[3]:=(i div 100) mod 10; b[0]:=3; cheng; end;

write(n,'!='); shuchu; end.

6、 编程计算Xn，其中X、n的值由键盘输入（必须为正整数并且X<50、n<10）。

（测试数据：X＝49，n＝9； 答案：1628413597910449） program e; var

a,b,c:array[0..1000] of byte; x,n,i,j,k:integer; procedure cheng; var

i,j,k:integer; begin

for i:=1 to a[0] do for j:=1 to b[0] do begin

c[i+j-1]:=c[i+j-1]+(a[i]*b[j] mod 10);

c[i+j]:=c[i+j]+(a[i]*b[j] div 10)+(c[i+j-1] div 10); c[i+j-1]:=c[i+j-1] mod 10;

信息学奥林匹克竞赛辅导——程序设计试题答案部分 第47页

end; end;

procedure shuchu; var

i:integer; begin

while c[c[0]]=0 do dec(c[0]);

for i:=c[0] downto 1 do write(c[i]); end;

{============main=========} begin

writeln; writeln('input x(<50) and n(<10):'); readln(x,n); c[1]:=1; for i:=1 to n do begin

j:=1000;

while c[j]=0 do dec(j); a[0]:=j;

for k:=j downto 1 do begin a[k]:=c[k]; c[k]:=0; end;

b[1]:=x mod 10; b[2]:=(x div 10) mod 10; b[3]:=(x div 100) mod 10; b[0]:=3; cheng; end;

write(x,'^',n,'='); shuchu; end.

7、 求789789?789（共29组789）除以79的商和余数。

（答案：余数8 商：999733911126316189607328847835176949100重复一次9997339） program e;

const w=3*29; m=79; var

a,b:array[0..w] of integer; x,i,j:integer; begin

writeln; a[0]:=0;

for i:=1 to 29 do begin a[3*i-2]:=7; a[3*i-1]:=8; a[3*i]:=9; end; i:=0; j:=1; repeat

x:=a[i]*100+a[i+1]*10+a[i+2]; b[j]:=x div m; j:=j+1;

a[i]:=(x mod m) div 100; a[i+1]:=((x mod m) div 10) mod 10; a[i+2]:=(x mod m) mod 10; i:=i+1; until i=w-1;

b[j]:=(a[w-1]*10+a[w]) div m;

writeln('yu shu:',(a[w-1]*10+a[w]) mod m); write('shang:'); if b[1]=0 then

for i:=2 to j-1 do write(b[i]) else

for i:=1 to j-1 do write(b[i]); writeln; end. 8、

排列与组合程序设计试题

（有关排列与组合的基本理论和公式：

信息学奥林匹克竞赛辅导——程序设计试题答案部分 第48页

加法原理：做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类

中办法中有m2种不同的方法，……，杂第n类办法中有mn种不同方法。那么完成这件事共有N＝m1＋m2＋…＋mn种不同的方法，这一原理叫做加法原理。

乘法原理：做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有

m2种不同的方法，……，做第n步有mn种不同的方法，那么完成这件事共有 N＝m1×m2×…×mn种不同的方法，这一原理叫做乘法原理。

公式：阶乘公式n!?n?(n?1)?(n?2)?3?2?1，规定0！＝1；

n全排列公式Pn?n!

选排列公式Pn?n(n?1)(n?2)?(n?m?1)?mn!mmm、P?C?Pnnm

(n?m)!n!?(n?1)! n 圆排列：n个不同元素不分首位围成一个圆圈达到圆排列，则排列数为：

mn

Pnmn(n?1)(n?2)?(n?m?1)n!0组合数公式C?m?、规定Cn??1

Pmm!m!(n?m)!012nmn?mmmm?1、Cn、Cn?Cn?Cn???Cn?2n） Cn?Cn?1?Cn?Cn

加法原理、乘法原理、排列、组合练习：

1. 用数字0、1、2、3能组成多少个三位数：

（提示：先确定百位数，只能是1、2、3之间的数字；再确定十位数，可以为0、1、2、3任何一个；最后确定个位数，可以为0、1、2、3任何一个。根据乘法原理，共有3×4×4＝48个。） 2. 有编号为1、2、3、4、5的五本书需要摆放在书架上，问有多少种不同的摆放方案数。

5（提示：此题为全排列，故摆放方案总数为P5?5!?120中。也可以按乘法原理思考，即摆放第

一本书有5种选择，摆放第二本数有4种选择，??，最后结果为5×4×3×2×1即5！） 3. 有编号为1、2、3、4、5的五本书需要任选3本书摆放在书架上，问有多少种不同方案。

（提示：可以根据选排列公式计算，也可以根据乘法原理计算，答案为5×4×3＝60） 4. 有编号为1、2、3、4、5的五本书需要任选3本书，问有多少种方法。

（提示：此题为组合问题，答案为C5?35?4?3＝10） 3!5. 五种不同颜色的珠子串成一串，问有多少种不同的方法。

（提示：此题属于圆排列问题，答案为（5－1）！＝24）

6. 把两个红球、两个蓝球、三个黄球摆放在球架上，问有多少种方案。

（提示：摆放方案总数为（2＋2＋3）！种，但是两个红球一样，所以要除以2！，同理两个蓝球，

除以2！，三个黄球，除以3！，即摆放方案总数为

(2?2?3)!?210）

2!?2!?3!1、 排列算法。有N本不同的书摆放在书架上，设其编号分别为1、2、3、??、N，编程求解这N本

书的不同摆放方案和摆放方案总数。

（算法分析：此问题的实质即求N个元素的全排列。以N＝3为例，人工可以得到按字典顺序排列的排列方案如下，123、132、213、231、312、321。由此我们发现，每一个排列方式总是在其前

信息学奥林匹克竞赛辅导——程序设计试题答案部分 第49页

一个排列的基础上通过顺序逆转而得到。由此我们得到给定一个排列P1P2P3??Pn之后生成下一个排列的算法如下：

S1：求满足关系式P（J－1）P（I－1）的K的最大值，记为J； S3：将P（I－1）与P（J）互换；

S4：将PI与Pn互换，P（I－1）与P（n－1）互换，??，得到从PI到Pn部分的顺序逆转。 由上面算法所得到的就是所求排列的下一个排列。

下面源程序的算法即是通过此方法得以实现。举例说明，如239876541，按字典顺序排列下一个应该是241356789，按照上面的算法，我们给与验证。

（1）I＝3； （2）J＝8； （3）交换P（3－1）与P（8）的值，得249876531； （4）交换P（3）与P（9）、P（4）与P（8）、P（5）与P（7）、P（6）与P（6）的值，顺序逆转的操作到此为止，由此得到241356789。与预期结果相吻合。） program e;

const maxn=10; var

plan:array[1..maxn] of byte; i,j,n,total:integer; procedure print; begin

inc(total);

write('(',total:5,'):');

for i:=1 to n do write(plan[i]:5); writeln; end;

procedure findi; begin i:=n;

while(i>1)and(plan[i]

procedure findj; begin j:=n;

while plan[j]

procedure change; var

k,h:integer; begin

k:=plan[i-1]; plan[i-1]:=plan[j]; plan[j]:=k; for k:=i to ((n+i) div 2) do

begin h:=plan[k]; plan[k]:=plan[n+i-k]; plan[n+i-k]:=h; end; end; begin

write('please input n:'); readln(n); total:=0;

for i:=1 to n do plan[i]:=i; print; repeat findi;

if i>1 then begin findj; change; print; end; until i<=1;

writeln('total ways =',total);

信息学奥林匹克竞赛辅导——程序设计试题答案部分 第50页

end.

（备注：生成排列的方法很多，比较常用的还有标志位法，可以用一个数组C作为标志数组，另一个数组A存放排列好的元素，凡数组A中用过的元素，数组C中相应下标的位置成TRUE或数字1，否则置成FALSE或数字0。）

2、 组合算法。有N本不同的书摆放在书架上，设其编号分别为1、2、3、??、N，现要从其中取出

R本书，编程求解其不同的组合方案和方案总数。

（算法分析：此问题的实质即求N个元素中取出R个元素的组合方案。组合是没有元素先后顺序之分的，只在于元素的选择不同。先来观察一个具体的例子，当N＝5，R＝3时，其组合方案为： （1）1，2，3 （2）1，2，4 （3）1，2，5 （4）1，3，4 （5）1，3，5 （6）1，4，5 （7）2，3，4 （8）2，3，5 （9）2，4，5 （10）3，4，5

从上面的组合方案可以看出：每一次的方案数都是在前一方案的基础上进行的。具体操作如下：S1：每次都先让最后的元素增加1，直到增加到N为止（如上例中的（1）（2）（3）方案，最后一个元素的变化为由3增加到4再增加到5为止）。

S2：这时最后的元素不能再增加了，那么增加它前面的元素，（如上例中的（4），把倒数第二个元素的2增加1到3，那么此时把这个元素后面的所有元素依次增加1即可得到新的组合方案。再重复上面的操作即可得到全部的组合方案。

注意：在每个元素进行加1的操作中，最后一位数最大可达到N，倒数第二位最大只能达到 N－1，依此类推??，倒数第K位（K≤N）不得超过N－K＋1。） program e;

const maxn=10; var

plan:array[1..maxn] of byte; i,j,n,r,total:integer; procedure print; begin

inc(total);

write('(',total:5,'):');

for i:=1 to r do write(plan[i]:5); writeln; end; begin

write('please input n and r:'); readln(n,r); total:=0;

for i:=1 to r do plan[i]:=i; print; repeat i:=r;

while (i>0)and(plan[i]=n+i-r) do dec(i); if i>0 then begin

inc(plan[i]); for j:=i+1 to r do

plan[j]:=plan[j-1]+1; print; end;

本文来源：https://www.bwwdw.com/article/k37h.html