信息学奥赛辅导程序设计试题汇编答案.docx
《信息学奥赛辅导程序设计试题汇编答案.docx》由会员分享，可在线阅读，更多相关《信息学奥赛辅导程序设计试题汇编答案.docx（107页珍藏版）》请在冰点文库上搜索。
信息学奥赛辅导程序设计试题汇编答案
莱西市前车小学
2015年3月
程序设计试题及答案
（备注：
试题难度评价采取五★级评价体系，分基础、容易、一般、稍难、难五个等级，其中的一、二、三★级都属于程序设计的基础试题级别，同学们稍加思考均有能力求得正确解答，对于四★级试题属于程序设计试题基础级别的思考题，五★级难度试题在此没有涉及，在程序设计高级试题中另行讲解。
对于基础和容易两个级别的程序设计试题，若能够给出语句分类（如If条件语句、条件语句嵌套、循环语句、多重循环语句等）的将尽量给出。
若属于13大类别的将尽量标注。
）
程序设计试题几大分类：
1、素数类问题（求素数的几种算法）：
2、数据排序问题（数据排序的几种方法）：
3、最大公约数和最小公倍数问题（几种算法）：
4、公式求解类问题（如求圆周率π、自然常数e、解方程等等）：
5、编号相反处理问题：
6、约瑟夫问题（或猴子选大王问题、密码问题）：
7、回文数问题：
8、高精度数值计算问题：
9、数值计算问题：
10、进制相互转换问题：
11、字符串倒置问题：
12、排列与组合类问题：
13、因子、质因子（质因数）类相关问题：
答案部分：
（程序设计的源程序没有统一的标准答案，实现程序的算法也是多种多样，但结果是唯一的，算法也有优劣之分，一个程序的优劣，关键在于是否找到了好的算法，以下程序和算法不一定就是最佳算法和最佳程序，只能仅供参考，希望同学们能够对某些程序提出更好的算法来改进程序）
（经常碰到的判断是否为素数、是否为回文数、求两个数的最大公约数、求两个数的最小公倍数等问题的子函数源程序，请务必记住！
）
判断是否为素数，若是素数则返回true，若不是素数则返回false：
functionprime（x:
longint）:
boolean;
var
j,y:
longint;
begin
prime:
=true;
ifx<2thenprime:
=false;
y:
=trunc（sqrt（x））;
forj:
=2toydo
if（xmodj=0）then
beginprime:
=false;exit;end;
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：
functionhuiwen（n:
longint）:
boolean;
var
m,i,j:
longint;
a:
array[1..10]ofinteger;
begin
ifn<0thenbeginhuiwen:
=false;exit;end;
m:
=n;i:
=0;huiwen:
=true;
repeat
i:
=i+1;
a[i]:
=mmod10;
m:
=mdiv10;
untilm=0;
forj:
=1to（idiv2）do
ifa[j]<>a[i-j+1]then
beginhuiwen:
=false;exit;end;
end;
求最大公约数子函数，返回两个正整数的最大公约数，采用辗转相除法算法；
functiongcd（a,b:
longint）:
longint;
begin
ifb=0thengcd:
=a
elsegcd:
=gcd（b,amodb）;
end;
求最小公倍数：
lcm=a*bdivgcd（a,b）;
（以下程序设计试题来自《奥赛经典（语言篇）》）
第2章基本语句与程序结构
例题部分：
1、求梯形的面积。
（梯形面积公式：
）
（★，测试数据
2、求一元二次方程ax2＋bx＋C＝0的两个实根。
（求根公式：
）
（★，测试数据a＝1，b＝－5，c＝6；答案：
x1＝2、x2＝3）
3、输入一个三位的自然数，然后把这个数的百位与个位对调，输出对调后的结果。
（★）
4、输入三个数a、b、c，首先判断这三个数能否构成三角形，若能，则求出三角形的面积。
（提示：
海伦公式
，其中
，a、b、c为边长）
（★，If条件语句，测试数据a＝5，b＝6，c＝7；答案：
14.7）
5、从键盘读入三个数，按从大到小的顺序把它们打印出来。
（★，If条件语句）
6、输入三角形的三边，判断它是否是直角三角形。
（★，If条件语句，测试数据
3、4、5；
4、5、6；答案
Yes；
No）
7、编写一个根据用户键入的两个操作数和一个运算符，由计算机输出运算结果的程序。
（★★★）
8、输入一个年号，判断它是否为闰年。
（★，If条件语句，测试数据
1900；
2000；
2008；答案：
No；
Yes；
Yes）
9、编程计算S＝1＋2＋3＋…＋100。
（★，循环语句，答案：
5050）
相关练习：
（1）
；
（2）
；
（3）
；（4）
；
（相关练习答案：
（1）5.19（保留2为小数）；
（2）338350；（3）2550；（4）1717）
10、根据公式
，计算圆周率的π值。
（★★，循环语句，测试数据n＝10000；答案：
3.1414971639）
programe;
var
i:
longint;
s:
real;
begin
writeln;s:
=0;
fori:
=1to10000dos:
=s+1/（i*i）;
writeln（sqrt（6*s））;
end.
11、计算n!
。
（n!
＝1×2×3×…×n，取n＝10）
（★★，循环语句，10！
＝3628800）
12、已知一对兔子，每个月可以生一对小兔，而小兔过一个月后也可生一对小兔。
即兔子的对数是：
第一个月1对，第二个月2对，第三个月3对，第四个月5对，……，假设兔子的生育期是12个月，并且不死，问一年后，这对兔子有多少对活着的后代？
（Fibonacci数列问题）
（★★，循环语句，1、2、3、5、8、13、21、34、55、89、144、233；答案233）
13、求两个整数a与b的最大公约数和最小公倍数。
（★，循环语句、If条件语句，测试数据16和24，最大公约数8，最小公倍数48）
14、利用格利高公式求π。
，直到最后一项的值小于10－6为止。
（★★★，循环语句）（答案：
3.1415946569E+00）
programe2_32;
var
n,fh:
longint;
s,t,p:
real;
begin
writeln;n:
=1;s:
=0;t:
=1;fh:
=1;
while（abs（t）>=1e-6）do
begint:
=fh/n;s:
=s+t;n:
=n+2;fh:
=-fh;end;
p:
=4*s;
writeln（'pi=',p）;
end.
相关练习：
利用公式
，求π。
（计算前10000项时，答案为3.1415426536）
programe;
var
i,a,b:
longint;
x,s:
real;
begin
writeln;s:
=0;
fori:
=1to10000dobegina:
=（4*i-3）;b:
=（4*i-1）;s:
=s+1/（a*b）;end;
writeln（8*s）;
end.
15、求100～999中的水仙花数。
（若三位数ABC，ABC＝A3＋B3＋C3，则称ABC为水仙花数。
例如153，13＋53＋33＝153，则153是水仙花数。
）（★★，循环语句）
（答案：
153、370、371、407）
programe12;
var
i,a,b,c:
integer;
begin
writeln;
fori:
=100to999do
begin
a:
=idiv100;
b:
=（imod100）div10;
c:
=imod10;
ifi=a*a*a+b*b*b+c*c*cthenwrite（i:
8）;
end;
end.
16、试编写能够打印输出如下图形的程序。
（★★，循环语句）
AAAAAAAAA
AAAAAAA
AAAAA
AAA
A
programe;
constn=5;
var
i,j:
integer;
begin
writeln;
fori:
=1tondo
begin
write（'':
i）;
forj:
=1to（n-i）*2+1dowrite（'A'）;
writeln;
end;
end.
17、四个学生上地理课，回答我国四大淡水湖大小时这样说：
（★★★）
甲：
“最大洞庭湖，最小洪泽湖，鄱阳湖第三。
”
乙：
“最大洪泽湖，最小洞庭湖，鄱阳湖第二，太湖第三。
”
丙：
“最小洪泽湖，洞庭湖第三。
”
丁：
“最大鄱阳湖，最小太湖，洪泽湖第二，洞庭湖第三。
”
对于每个湖的大小，每个学生仅答对一个，请编程确定四个湖的大小。
习题部分：
1、已知三角形的两边a、b和夹角jc的值，求第三边（已知条件由键盘输入）。
（★）
（提示：
余角公式
）
（测试数据：
输入a＝3、b＝4、jc＝90；输出5）
programe2_5;
var
a,b,c,jc:
real;
begin
writeln（'inputa,b,jc:
'）;readln（a,b,jc）;
c:
=sqrt（a*a+b*b-2*a*b*cos（pi*jc/180））;
writeln（c:
8:
2）;
end.
2、编写程序把一个四位整数3581颠倒成1853。
（★）
programe;
constn=3581;
var
a,b,c,d:
integer;
begin
writeln;
a:
=nmod10;
b:
=（ndiv10）mod10;
c:
=（ndiv100）mod10;
d:
=ndiv1000;
writeln（a,b,c,d）;
end.
相关练习：
任意输入一个正整数，颠倒输出该数。
programe;
var
n:
longint;
begin
writeln;writeln（'inputaintegernumber:
'）;readln（n）;
repeat
write（nmod10）;n:
=ndiv10;
untiln=0;
end.
3、输入a、b、c三个数，打印出最大者。
（★，If条件语句）
programe;
var
a,b,c:
real;
begin
writeln（'inputthreenumberfora,b,c:
'）;
readln（a,b,c）;
if（a>b）and（a>c）thenwriteln（a）;
elseif（b>a）and（b>c）thenwriteln（b）;
elsewriteln（c）;
end.
4、从键盘读入两个数，比较其大小，把大数置于x，小数置于y。
请设计实现该功能的程序。
（★，If条件语句）（程序略）
5、输入三个数，判断以这三个数为边能否组成一个三角形。
若不能，则给出适当信息；若能，则进一步判断它们构的是锐角三角形、直角三角形还是钝角三角形，并输出其特征（等边、等腰、直角、一般）、求其面积。
（★★，If条件语句）
（算法分析：
对于判断是锐角、直角、还是钝角三角形，只需判断最大边的平方与其余两边的平方和的大小比较即可，小于则为锐角、等于则为直角、大于则为钝角。
）
（测试数据：
1、2、3；
3、4、5；
）4、4、7；
5、5、5；答案：
No；
直角、面积6.00；
钝角、等腰、面积6.78；
锐角、等边、面积10.83）
programe;
var
a,b,c,t,s,d,ja,jb,jc:
real;
begin
writeln（'inputthreenumberfora,b,c:
'）;
readln（a,b,c）;
ifa=a;a:
=b;b:
=t;end;
ifa=a;a:
=c;c:
=t;end;
if（abegin
if（a*aelseif（a*a=b*b+c*c）thenwriteln（'zhijiaosanjiaoxing.'）
elsewriteln（'dunjiaosanjiaoxing.'）;
if（a=b）and（b=c）and（c=a）thenwriteln（'dengbiansanjiaoxing.'）
elseif（（a=b）and（b<>c））or（（a=c）and（c<>b））or（（b=c）and（c<>a））then
writeln（'dengyaosanjiaoxing.'）
elseif（a*a<>b*b+c*c）thenwriteln（'yibansanjiaoxing.'）;
d:
=（a+b+c）/2;s:
=sqrt（d*（d-a）*（d-b）*（d-c））;writeln（'s=',s:
0:
2）;
end
elsewriteln（'NO!
'）;
end.
6、设我国目前的人口为11亿，且每年的增长率为1.5％。
问多少年后，我国的人口会翻一番？
（★）（答案：
47）
programe2_22;
var
i:
integer;
s:
real;
begin
writeln;s:
=11;i:
=0;
whiles<22do
begins:
=s*（1.015）;inc（i）;end;
writeln（i）;
end.
7、Fibonacci数列问题：
数列的头两个数分别是0和1，从第三个数开始，每个数皆为它的前两个数之和，即：
0，1，1，2，3，5，…，输出该数列的第50个数。
（★★，循环语句）
（答案：
7778742049）
programe;
{$N+,E+}
var
i:
integer;
x,y,z:
extended;
begin
writeln;x:
=0;y:
=1;write（x:
20:
0,y:
20:
0）;
fori:
=3to50do
beginz:
=x+y;write（z:
20:
0）;x:
=y;y:
=z;end;
end.
8、编写程序求出下式中n的最大值：
22＋42＋62＋…＋n2<1500。
（★★，循环语句）
（答案：
18）
programe2_24;
var
n,s:
integer;
begin
writeln;
s:
=0;n:
=0;
whiles<1500do
begininc（n,2）;inc（s,n*n）;end;
writeln（n-2）;
end.
9、把一元的钞票换成一分、二分和五分的硬币（每种至少一枚），问有多少种兑换方法？
（★★）（答案：
461）
programe2_29;
var
i,j,k,ans:
integer;
begin
ans:
=0;
fork:
=1to19do
forj:
=1to47do
fori:
=1to93do
if（k*5+j*2+i）=100theninc（ans）;
writeln（ans）;
end.
10、编写程序求最小正整数m、n（0（★★★★）
（算法：
这类数字很大且有效数字位数很多（超出最多有效位数extended数据类型有效数字18位）的数字问题，一定要另辟蹊径寻找突破口，注意到此题只要求最后三位数字相同，则我最多保留最后四位有效数字即可进行判断。
还请记住这样一个事实，如1989×1989＝3956121，3956121×1989＝7868724669，最后四位数字是“4669”，而我把3956121取其最后的四位数“6121”与1989相乘即6121×1989=12174669，最后四位数字也是“4669”，没有破坏最后四位有效数字的值，因此可以通过这种方法来编写此程序。
）
（答案：
m＝51；n＝1）；
programe;
var
m,n,i,j:
integer;
x,y,a,b:
longint;
begin
writeln;
form:
=2to60do
forn:
=1tom-1do
begin
x:
=1;y:
=1;
fori:
=1tomdobeginx:
=xmod10000;x:
=x*1989;a:
=xmod1000;end;
forj:
=1tondobeginy:
=ymod10000;y:
=y*1989;b:
=ymod1000;end;
ifa=bthenwriteln（'m=',m,'n=',n）;
end;
end.
11、编写程序提示用户输入一系列整数，用0作结束标志，统计其中有多少个正数。
（★）
programe;
var
count,x:
integer;
begin
writeln;writeln（'inputintegernumber（0--end）:
'）;count:
=0;
repeat
read（x）;
ifx>0theninc（count）;
until（x=0）;
writeln（'count=',count）;
end.
12、求自然常数
的值。
（提示：
0！
＝1，1！
＝1）（★★）
（1）直到第50项；
（2）直到最后一项小于10－5。
（答案：
（1）2.71828182845905E+0000；
（2）2.71828152557319E+0000）
（备注：
第2小问程序略，只须将更改语句“until（1/s）<1E-5;”即可求的解答）
programe2_35;
{$N+}
var
i,count:
integer;
e,s:
extended;
begin
e:
=1;count:
=0;
repeat
inc（count）;s:
=1;
fori:
=1tocountdos:
=s*i;
e:
=e+1/s;
untilcount=50;
writeln（e）;
end.
13、三齐王点兵的故事。
相传三齐王韩信才智过人，从不直接清点自己军队的人数，只是让士兵先后以三人一排、五人一排、七人一排地变换队形，而他每次只掠一眼队伍的排尾就知道总人数了（不超过100人）。
输入三次排尾的人数，输出总人数。
（★★）
programe2_36;
var
a,b,c,i:
integer;
begin
writeln（'shurup3（0~2）,p5（0~4）,p7（0~6）deweishu:
'）;
readln（a,b,c）;
fori:
=100downto1do
if（imod3=a）and（imod5=b）and（imod7=c）thenwriteln（i）;
ifi=1thenwriteln（'Noanswer!
'）;
end.
14、编写程序，计算N！
以十进制数形式表示的数中最右的非零数字，并找出在它右边有几个零。
例如12！
＝1×2×3×…×12＝479001600。
因此12！
的右边有2个零。
（★★★）
（提示：
碰到5、52、53、54…才会出现末尾是零，所以1000！
末尾零的个数为：
（1000div5）＋（1000div52）＋（1000div53）＋（1000div54）＝249）
（下面的程序没采用上面的算法，采取另一种算法实现了这一程序，显然上面的算法效率高）
（程序算法：
只需提供末尾几位有效数字即可，我采取提供四位有效数字相乘）
programI_11;
var
s:
longint;
i,d:
integer;
begin
writeln;
d:
=0;s:
=1;
fori:
=1to1000do
begin
s:
=s*i;
if（smod1000=0）thenbegins:
=sdiv1000;d:
=d+3;end;
if（smod100=0）thenbegins:
=sdiv100;d:
=d+2;end;
if（smod10=0）thenbegins:
=sdiv10;d:
=d+1;end;
s:
=smod10000;
end;
writeln;write（d）;
end.
15、编写程序，输出“字母塔”。
以此类推共26层。
A（★★）
ABA
ABCBA
……………
programe2_40;
var
i,j:
integer;
begin
writeln;
fori:
=1to26do
begin
forj:
=1to26-idowrite（''）;
forj:
=1toidowrite（chr（64+j））;
forj:
=i-1downto1dowrite（chr（64+j））;
writeln;
end;
end.
第4章数组类型
例题部分：
1、输入10个整数，把这10个数按从小到大的顺序排列。
（★★）
（冒泡法排序和选择法排序两种方法）
冒泡法排序：
programe1;
constn=10;
var
a:
array[1..10]ofinteger;
i,j,t:
integer;
begin
writeln（'input',n,'integernumber:
'）;
fori:
=1tondoread（a[i]）;
fori:
=1ton-1do
forj:
=1ton-ido
ifa[j]>a[j+1]thenbegint:
=a[j];a[j]:
=a[j+1];a[j+1]:
=t;end;
fori:
=1tondowrite（a[i]:
5）;
end.
2、折半查找。
（二分法查找）（★★）
3、旅馆里有一百个房间，从1到100编了号。
第一个服务员把所有的房间门都打开了，第二个服务员把所有编号是2的倍数的房间“相反处理
升级会员 