当前位置:首页 >> 学科竞赛 >> (中学信息学奥赛辅导)程序设计试题锦集

(中学信息学奥赛辅导)程序设计试题锦集


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

第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; 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:

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

第2页

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 ? (★,测试数据① 2、 求一元二次方程 ax2+bx+C=0 的两个实根。 (求根公式: x1,2 ?

1 h( a ? b) ) 2
?b ? b 2 ? 4ac ) 2a

(★,测试数据 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) 5、 从键盘读入三个数,按从大到小的顺序把它们打印出来。 (★,If 条件语句) 6、 输入三角形的三边,判断它是否是直角三角形。 (★,If 条件语句,测试数据①3、4、5;②4、5、6;答案①Yes;②No) 7、 编写一个根据用户键入的两个操作数和一个运算符, 由计算机输出运算结果的程序。 (★★★) 8、 输入一个年号,判断它是否为闰年。

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

第3页

(★,If 条件语句,测试数据①1900;②2000;③2008;答案:①No;②Yes;③Yes) 9、 编程计算 S=1+2+3+?+100。 (★,循环语句, 答案:5050) 相关练习: (1) S ? 1 ?

(4) S ? 1 ? 4 ? 7 ? 10 ? ? ? 100 ; (相关练习答案: (1)5.19(保留 2 为小数)(2)338350; ; (3)2550; (4)1717) 10、根据公式

1 1 1 ; ? ??? 2 3 100 (3) S ? 2 ? 4 ? 6 ? ?? 100 ;

(2) S ? 1 ? 2 ? ? ? 100 ;
2 2 2

?2
6

? 1?

1 1 1 ? 2 ? ? ? 2 ,计算圆周率的π 值。 2 2 3 n

(★★,循环语句,测试数据 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. 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、利用格利高公式求π 。

?

1 1 1 ? 1 ? ? ? ?? ,直到最后一项的值小于 10-6 为止。 4 3 5 7

(★★★,循环语句) (答案:3.1415946569E+00) program e2_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 begin t:=fh/n; s:=s+t; n:=n+2; fh:=-fh; end; p:=4*s; writeln('pi=',p); end. 相关练习:利用公式

?

8

?

1 1 1 ? ? ? ? ,求π。 1? 3 5 ? 7 9 ?11

(计算前 10000 项时,答案为 3.1415426536) program e; var i,a,b:longint; x,s:real; begin

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

第4页

writeln; s:=0; for i:=1 to 10000 do begin a:=(4*i-3); b:=(4*i-1); s:=s+1/(a*b); end; writeln(8*s); end. 3 3 3 15、求 100~999 中的水仙花数。 (若三位数 ABC,ABC=A +B +C ,则称 ABC 为水仙花数。例如 3 3 3 153,1 +5 +3 =153,则 153 是水仙花数。 ) (★★, 循环语句) (答案:153、370、371、407) program e12; var i,a,b,c:integer; begin writeln; for i:=100 to 999 do begin a:=i div 100; b:=(i mod 100) div 10; c:=i mod 10; if i=a*a*a+b*b*b+c*c*c then write(i:8); end; end. 16、试编写能够打印输出如下图形的程序。 (★★, 循环语句) AAAAAAAAA AAAAAAA AAAAA AAA A program e; const n=5; var i,j:integer; begin writeln; for i:=1 to n do begin write('':i); for j:=1 to (n-i)*2+1 do write('A'); writeln; end; end. 17、四个学生上地理课,回答我国四大淡水湖大小时这样说: (★★★) 甲: “最大洞庭湖,最小洪泽湖,鄱阳湖第三。 ” 乙: “最大洪泽湖,最小洞庭湖,鄱阳湖第二,太湖第三。 ” 丙: “最小洪泽湖,洞庭湖第三。 ” 丁: “最大鄱阳湖,最小太湖,洪泽湖第二,洞庭湖第三。 ” 对于每个湖的大小,每个学生仅答对一个,请编程确定四个湖的大小。 习题部分: 1、 已知三角形的两边 a、b 和夹角 jc 的值,求第三边(已知条件由键盘输入) 。 (提示:余角公式 c ? a ? b ? 2ab cos c )
2 2 2

(★)

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

第5页

(测试数据:输入 a=3、b=4、jc=90; 输出 5) program e2_5; var a,b,c,jc:real; begin writeln('input a,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。 (★) program e; const n=3581; var a,b,c,d:integer; begin writeln; a:=n mod 10; b:=(n div 10) mod 10; c:=(n div 100) mod 10; d:=n div 1000; writeln(a,b,c,d); end. 相关练习:任意输入一个正整数,颠倒输出该数。 program e; var n:longint; begin writeln; writeln('input a integer number:'); readln(n); repeat write(n mod 10); n:=n div 10; until n=0; end. 3、 输入 a、b、c 三个数,打印出最大者。 (★,If 条件语句) program e; var a,b,c:real; begin writeln('input three number for a,b,c:'); readln(a,b,c); if (a>b)and(a>c) then writeln(a); else if (b>a)and(b>c) then writeln(b); else writeln(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)

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

第6页

program e; var a,b,c,t,s,d,ja,jb,jc:real; begin writeln('input three number for a,b,c:'); readln(a,b,c); if a<b then begin t:=a; a:=b; b:=t; end; if a<c then begin t:=a; a:=c; c:=t; end; if (a<b+c) then begin if (a*a<b*b+c*c) then writeln('rui jiao san jiao xing.') else if(a*a=b*b+c*c) then writeln('zhi jiao san jiao xing.') else writeln('dun jiao san jiao xing.'); if (a=b)and(b=c)and(c=a) then writeln('deng bian san jiao xing.') else if ((a=b)and(b<>c))or((a=c)and(c<>b))or((b=c)and(c<>a)) then writeln('deng yao san jiao xing.') else if (a*a<>b*b+c*c) then writeln('yi ban san jiao xing.'); d:=(a+b+c)/2; s:=sqrt(d*(d-a)*(d-b)*(d-c)); writeln('s=',s:0:2); end else writeln('NO!'); end. 6、 设我国目前的人口为 11 亿, 且每年的增长率为 1.5%。 问多少年后, 我国的人口会翻一番? (★) (答案:47) program e2_22; var i:integer; s:real; begin writeln; s:=11; i:=0; while s<22 do begin s:=s*(1.015); inc(i); end; writeln(i); end. 7、 Fibonacci 数列问题:数列的头两个数分别是 0 和 1,从第三个数开始,每个数皆为它的前两个 数之和,即:0,1,1,2,3,5,?,输出该数列的第 50 个数。 (★★, 循环语句) (答案:7778742049) program e; {$N+,E+} var i:integer; x,y,z:extended; begin writeln; x:=0; y:=1; write(x:20:0,y:20:0); for i:=3 to 50 do begin z:=x+y; write(z:20:0); x:=y; y:=z; end; end. 8、 编写程序求出下式中 n 的最大值:22+42+62+?+n2<1500。 (★★, 循环语句) (答案:18) program e2_24; var n,s:integer; begin writeln; s:=0; n:=0;

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

第7页

while s<1500 do begin inc(n,2); inc(s,n*n); end; writeln(n-2); end. 9、 把一元的钞票换成一分、二分和五分的硬币(每种至少一枚) ,问有多少种兑换方法?(★★) (答案:461) program e2_29; var i,j,k,ans:integer; begin ans:=0; for k:=1 to 19 do for j:=1 to 47 do for i:=1 to 93 do if (k*5+j*2+i)=100 then inc(ans); writeln(ans); end. 10、编写程序求最小正整数 m、n(0<n<m)为何值时,1989m 与 1989n 的最后三位数字相同? (★★★★) (算法:这类数字很大且有效数字位数很多(超出最多有效位数 extended 数据类型有效数字 18 位)的数字问题,一定要另辟蹊径寻找突破口,注意到此题只要求最后三位数字相同, 则我最多保留最后四位有效数字即可进行判断。还请记住这样一个事实,如 1989×1989= 3956121,3956121×1989=7868724669,最后四位数字是“4669” ,而我把 3956121 取其最 后的四位数“6121”与 1989 相乘即 6121×1989=12174669,最后四位数字也是“4669” , 没有破坏最后四位有效数字的值,因此可以通过这种方法来编写此程序。 ) (答案:m=51; n=1) ; program e; var m,n,i,j:integer; x,y,a,b:longint; begin writeln; for m:=2 to 60 do for n:=1 to m-1 do begin x:=1; y:=1; for i:=1 to m do begin x:=x mod 10000; x:=x*1989; a:=x mod 1000; end; for j:=1 to n do begin y:=y mod 10000; y:=y*1989; b:=y mod 1000; end; if a=b then writeln('m=',m,' n=',n); end; end. 11、编写程序提示用户输入一系列整数,用 0 作结束标志,统计其中有多少个正数。 (★) program e; var count,x:integer; begin writeln; writeln('input integer number(0--end):'); count:=0; repeat read(x); if x>0 then inc(count); until(x=0); writeln('count=',count); end.

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

第8页

12、求自然常数 e ?

1 1 1 1 (提示:0!=1,1!=1) ? ? ? ? ? 的值。 0! 1! 2! n!


(★★)

(1) 直到第 50 项; (2)直到最后一项小于 10 5。 (答案: (1)2.71828182845905E+0000; (2)2.71828152557319E+0000) (备注:第 2 小问程序略,只须将更改语句“until (1/s)<1E-5;”即可求的解答) program e2_35; {$N+} var i,count:integer; e,s:extended; begin e:=1; count:=0; repeat inc(count); s:=1; for i:=1 to count do s:=s*i; e:=e+1/s; until count=50; writeln(e); end. 13、三齐王点兵的故事。相传三齐王韩信才智过人,从不直接清点自己军队的人数,只是让士兵 先后以三人一排、五人一排、七人一排地变换队形,而他每次只掠一眼队伍的排尾就知道总 人数了(不超过 100 人) 。输入三次排尾的人数,输出总人数。 (★★) program e2_36; var a,b,c,i:integer; begin writeln('shu ru p3(0~2),p5(0~4),p7(0~6) de wei shu:'); readln(a,b,c); for i:=100 downto 1 do if (i mod 3=a)and(i mod 5=b)and(i mod 7=c) then writeln(i); if i=1 then writeln('No answer!'); end. 14、编写程序,计算 N!以十进制数形式表示的数中最右的非零数字,并找出在它右边有几个零。 例如 12!=1×2×3×?×12=479001600。因此 12!的右边有 2 个零。 (★★★) 2 3 4 (提示:碰到 5、5 、5 、5 ?才会出现末尾是零,所以 1000!末尾零的个数为: (1000 div 5)+(1000 div 52)+(1000 div 53)+(1000 div 54)=249) (下面的程序没采用上面的算法,采取另一种算法实现了这一程序,显然上面的算法效率高) (程序算法:只需提供末尾几位有效数字即可,我采取提供四位有效数字相乘) program I_11; var s:longint; i,d:integer; begin writeln; d:=0; s:=1; for i:=1 to 1000 do begin s:=s*i; if (s mod 1000 =0) then begin s:=s div 1000; d:=d+3; end; if (s mod 100 = 0) then begin s:=s div 100; d:=d+2; end; if (s mod 10 = 0) then begin s:=s div 10; d:=d+1; end; s:=s mod 10000;

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

第9页

end; writeln; write(d); end. 15、编写程序,输出“字母塔” 。以此类推共 26 层。

A ABA ABCBA ?????

(★★)

program e2_40; var i,j:integer; begin writeln; for i:=1 to 26 do begin for j:=1 to 26-i do write(' '); for j:=1 to i do write(chr(64+j)); for j:=i-1 downto 1 do write(chr(64+j)); writeln; end; end. 第 4 章 数组类型 例题部分: 1、 输入 10 个整数,把这 10 个数按从小到大的顺序排列。 (★★) (冒泡法排序和选择法排序两种方法) 冒泡法排序: program e1; const n=10; var a:array[1..10] of integer; i,j,t:integer; begin writeln('input ',n,' integer number:'); for i:=1 to n do read(a[i]); for i:=1 to n-1 do for j:=1 to n-i do if a[j]>a[j+1] then begin t:=a[j]; a[j]:=a[j+1]; a[j+1]:=t; end; for i:=1 to n do write(a[i]:5); end. 2、 折半查找。 (二分法查找) (★★) 3、 旅馆里有一百个房间,从 1 到 100 编了号。第一个服务员把所有的房间门都打开了,第二个服 务员把所有编号是 2 的倍数的房间“相反处理” ,第三个服务员把所有编号是 3 的倍数的房间 作“相反处理” ,??,以后每个服务员都是如此。问第 100 个服务员来过后,哪几扇门是打 开的。 (所谓“相反处理”是:原来开着的门关上,原来关上的门打开。 ) (★★) (提示:对于任何一个编号,例如 8,它的因子只有 1、2、4、8,并且成对出现,当此数的因 子数为偶数个时将被关上, 当此数的因子数为奇数个时才会被打开。 考虑到因子成对出现的情 况,因此只有平方数的因子是奇数个的,所以门被打开的只能是平方数的房间,如 1,4 等) 4、 编写程序把任意十进制整数转换成二进制整数。 (★★) 2 2 5、 所谓“幻方” ,是一个行、列为奇数的方阵,把 1~n 这 n 个不同的数放入方阵中,使方阵的 每行、每列和每个对角线上的元素的和全部相等。下面给出幻方的一种排列方法: (1) 先把 1 放在第一行的中间位置;

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

第 10 页

下一个数放在上一个数的右上方; 若右上方已超出方阵的第一行,则下一个数放在下一列的最后一行上; 若右上方已超出方阵的最后一列,则下一个数放在上一行的第一列上; 若右上方已经有数,或右上方已超出方阵的第一行最后一列,则下一个数放在上一个 数的正下方。 编写程序,对输入小于 15 的 n,打印出相应的幻方。 (★★★) 6、 在一个字符数组 LET 中形成由 A 开始的连续 26 个大写字母构成的字串, 并将其倒置后仍放在 LET 中。 7、 随机输入一个长度不超过 255 的字符串,将其倒置后输出。 8、 随机输入一些国家的英文名字,以 end 作为输入结束标志,按字母顺序排序后输出。 9、 求 n 个字符串的最长公共子串,n<20,字符长度不超过 255。 例如 n=3,由键盘依次输入三个字符串为: what is local bus? Name some local bus. Local bus is high speed I/O bus close to the processor. 则最长公共子串为“local bus” 。 10、文本的整版。编写一个程序,从键盘以任意的方法输入句子,然后打印出来。打印时每行宽 度必须为 n 个字符。如果一行的最后一个单词超出了本行 n 个字符的范围,则应把它移到下 一行去。输入一个句子测试你的程序。 习题部分: 1、 输入 n 个整数,请找出最小数所在的位置,并把它与第一个数对调。 (★) program e4_2; var a:array[1..10]of integer; i,t,y:integer; begin writeln('input ten integer number:'); for i:=1 to 10 do read(a[i]); t:=a[1]; for i:=2 to 10 do if a[i]<t then t:=a[i]; for i:=1 to 10 do if a[i]=t then begin writeln('the min number is ',i,'th'); a[i]:=a[1]; a[1]:=t; end; for i:=1 to 10 do write(a[i]:8); end. 2、 用边排序边合并的方法把两个有序数列合并为一个新的有序数列,不得先合并再重新排序。 (★★) (测试数据:这里 a 组数据共 8 个:1 1 3 6 6 7 9 10; b 组数据共 5 个:0 1 2 3 4) program e4_3; var a:array[1..8] of integer; b:array[1..5] of integer; c:array[1..13] of integer; i,j,k,m,n:integer; begin writeln('input 8 integer number of square arrayA:'); for i:=1 to 8 do read(a[i]); writeln('input 5 integer number of square arrayB:'); for i:=1 to 5 do read(b[i]);

(2) (3) (4) (5)

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

第 11 页

j:=1; k:=1; m:=a[j]; n:=b[k]; for i:=1 to 13 do begin if m<n then begin c[i]:=m; inc(j); m:=a[j]; if j=9 then m:=maxint; end else begin c[i]:=n; inc(k); n:=b[k]; if k=6 then n:=maxint; end; end; for i:=1 to 13 do write(c[i]:4); end. 3、 将一个数插入到有序的数列中,插入后数列仍然有序。 (★★) (测试数据:有序数组为 1 1 3 6 6 7 9 10; 待插入数为 5) program e4_4; var i,j,n:integer; flag:boolean; a:array[1..9] of integer; begin writeln('input 8 integer square number:'); for i:=1 to 8 do read(a[i]); writeln('input a integer number to insert:'); readln(n); flag:=false; i:=1; repeat if a[i]>n then flag:=true else inc(i); until flag=true; for j:=9 downto i+1 do a[j]:=a[j-1]; a[i]:=n; for i:=1 to 9 do write(a[i]:4); end. 4、 有 N 个无序的数存放在 A 数组中,请将后面相同的数删成只剩下一个,并输出经过删除后的 数列。 (★★) (测试数据:数列为 1 3 5 3 7 5 3 1; 答案:1 3 5 7) program e4_5; var a:array[1..8] of integer; i,j,n:integer; begin writeln('input 8 integer number:'); for i:=1 to 8 do read(a[i]); for i:=2 to 8 do for j:=1 to i-1 do if a[i]=a[j] then a[i]:=maxint; for i:=1 to 8 do if a[i]<>maxint then write(a[i]:4); end. 5、 有 N 个人排队到 R 个相同的水龙头去打水,他们装满各自水桶的时间 T1、T2、?、TN 为整 数且互不相等, 应如何安排他们打水的顺序才能使他们花费的总时间最少? (花费的总时间等 于每个花费时间的总和)

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

第 12 页

6、 求一个五阶方阵中某个元素的位置:它在行上是最小的,在列上也是最小的,如果没有请输出 “NO FIND!。 ” (★★★) (分析:整个矩阵中的最小值,当然也是所在行和所在列的最小值,因此肯定能找到这样的 数)测试数据: 答案:2、1、3、6 11 4 2 7 8 5 9 23 1 25 3 22 21 18 15 17 16 24 12 6 13 10 19 20 14 program e; var i,j,x,y:integer; minx:integer; a:array[1..5,1..5] of integer; begin writeln; writeln('input number(5*5):'); for i:=1 to 5 do for j:=1 to 5 do read(a[i,j]); for i:=1 to 5 do begin minx:=a[i,1]; x:=i; y:=1; for j:=1 to 5 do if a[i,j]<minx then begin minx:=a[i,j]; y:=j; end; for j:=1 to 5 do if a[j,y]<minx then break; if j=5 then writeln('the number is ',minx,'[',x,']','[',y,']'); end; end. 第 5 章 过程与函数 例题部分: 1、 编程求:1!+3!+5!+7!+9!+11! 。 2、 求数字的乘积根。一个正整数的数字的乘积 N 的定义是:这个整数中非零数字的乘积。例如, 整数 999 的数字乘积为 9×9×9,即 729。729 的数字乘积为 7×2×9,即 126。126 的数字乘 积为 1×2×6,即 12。12 的数字乘积为 1×2,即 2。一个正整数的数字乘积根 N 是这样得到 的:反复取该整数的数字乘积,直到得到一位数字为止。例如,在上面的例子中数字的乘积根 是 2。编写一个程序,输入一个正整数(长度不超过 200 位数字) ,输出计算其数字乘积根的 每一步结果。 3、 汉诺(Hanoi)塔问题。设有 n 个大小不等的中空圆盘,按照从小到大(尺寸和序号)的顺序 叠套在立柱 A 上。另有两根立柱 B 和 C,如图所示。问题要求把全部圆盘从 A 柱(源柱)移 到 C 柱(目标柱) 。移动过程中可借助 B 柱(中间柱) 。移动时有如下要求: (1) 一次只能移动一个圆盘; (2) 不允许把大盘放在小盘上边; (3) 可使用任意一根立柱暂存圆盘。 A B C

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

第 13 页

4、 把一个十进制整数转化为 K 进制数(K≤10) 。 5、 八皇后问题:把八个皇后摆在 8×8 国际象棋棋盘格子内,使它们互不捕获对方。换言之,在 任何一行、一列或一条对角线上,仅能放置一个皇后。这一问题是由 19 世纪著名数学家高斯 (Gauss)于 1850 年首先提出的。 (答案共有 92 种解答) 6、 已知:切比雪夫多项式如下: (提示:运用递归函数计算)

(n ? 0) ?1 ? Tn ( x) ? ? x (n ? 1) ? 2 xT ( x) ? T ( x) ( n ? 2) n ?1 n?2 ?
对给定的不同的正整数,它是一些阶数不同的多项式,编程计算第 n 个多项式的值。 习题部分: 1、 编写一递归函数说明,用以计算组合数 C(M,N)(即 CN ) 。 2、 两个人玩井字游戏,在井字进分的九个空位上轮流画 O 或*,谁最先使自己的三个 O 或三个* 在一条直线上,谁就赢了。编写程序检查每一步是否走得正确,并告诉谁是胜利者。 第 6 章 集合与记录类型 例题部分: 1、 七段数码管问题。 2、 任意给出一个正整数 N,找一个正整数 M,使得 N*M 的值的数字由 0、1、?、C(C≤9)组 成,且这些数字至少出现一次。编写程序在整数范围内找出满足条件的最小 M。若没有给出 信息,则输出“No find!。 ” 例如:C=3、N=65 时,M=48,65×48=3210; C=8、N=125 时, “No find!。 ” (以下程序设计试题来自《计算机二级考试复习指南》 ) 1. 数列 ?
M

?e(1) ? e(2) ? 1, 称为 e 数列, ?e(n) ? (n ? 1)?e(n ? 1) ? (n ? 2)?e(n ? 2) (n ? 2)

(★★)

每一个 e(n) (n=1,2,?)称为 e 数。求[1,30000]之内: (1) 最大的 e 数; (2)e 数的数目。 (该数列前面几项为 1、1、3、11、53、??; 答案:①16687; ②8) program e; var a,b,c,n:longint; begin writeln; n:=3; a:=1; b:=1; repeat c:=(n-2)*a+(n-1)*b; a:=b; b:=c; inc(n); until c>30000; writeln('maxe=',a,' count=',n-2); end. 2. 计算并输出: S ?
1000 i ?1

。 ? i ? (i ? 1) 之值(精确到小数点后第 5 位)

1

(★)

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

第 14 页

(答案:0.99900) program e; var i:integer; s,n:real; begin writeln; s:=0; for i:=1 to 1000 do begin n:=i; s:=s+1/(n*(n+1)); end; writeln(s:0:5); end. 3. 已知 ?

? F (0) ? F (1) ? F (2) ? 1 ? F ( N ) ? F ( N ? 1) ? 2 F ( N ? 2) ? F ( N ? 3)

( N ? 2)

,求:

(★★)

4.

5.

6.

(1) F(50)(2)F(0)+F(1)+??+F(50) ; 。 (答案:①212101; ②-97262) program e; var i,a,b,c,d,s:longint; begin writeln; a:=1; b:=1; c:=1; s:=3; for i:=3 to 50 do begin d:=a-2*b+c; s:=s+d; a:=b; b:=c; c:=d; write(d:8); end; writeln; writeln('s=',s); end. 求满足:A·B=716699 并且 A+B 最小两个条件的 A 和 B。 (★★★) (答案:A=563; B=1273) program e; var a,x,s,mina,minb:longint; begin writeln; s:=716699; x:=trunc(sqrt(716699)); for a:=1 to x do if (716699 mod a=0)and(a+(716699 div a)<s) then begin s:=a+(716699 div a); mina:=a; minb:=(716699 div a); end; writeln('A=',mina,' B=',minb); end. 一自然数平方的末几位与该数相同时,称此数为自同构数。例如,由于 52=25,则称 5 为自同构 数。求出[1,700]以内的: (1)最大的自同构数; (2)自同构数数目。 (★★) (答案:①625 ②)7) program e; var i,count:longint; begin writeln; count:=0; for i:=1 to 9 do if (i*i-i) mod 10=0 then inc(count); for i:=10 to 99 do if (i*i-i) mod 100=0 then inc(count); for i:=100 to 700 do if (i*i-i) mod 1000=0 then begin inc(count); write(i:8); end; writeln; writeln('count=',count); end. 若某不含数字 0 的三位正整数,其平方数至少有三位同样的数字,则称该三位数为三重数。例如,

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

第 15 页

7.

8.

由于:511 =261121(有三位 1) ,所以 511 为三重数。求出: (★★★★) (1)按升序排列第 10 个三重数; (2)按升序排列前 10 个三重数之和; (答案: (1)258; (2)1826) program e1; var i,j,k,a,b,c,x,n,count,s:longint; aa:array[1..5]of integer; begin writeln; s:=0; count:=0; for i:=111 to 316 do begin a:=i div 100; b:=(i div 10) mod 10; c:=i mod 10; if ((a<>0)and(b<>0)and(c<>0)) then begin x:=i*i; aa[1]:=x div 10000; aa[2]:=(x div 1000) mod 10; aa[3]:=(x div 100) mod 10; aa[4]:=(x div 10) mod 10; aa[5]:=x mod 10; for j:=1 to 3 do begin n:=1; for k:=j+1 to 5 do if aa[j]=aa[k] then n:=n+1; if n>2 then begin writeln(i:8,x:8); s:=s+i; count:=count+1; break; end; end; end; if count=10 then break; end; writeln(s:8); end. 满足下列两个条件: (a)千位数字与百位数字相同(非 0) ,十位数字与个位数字相同; (b)是某 2 两位数的平方。的四位正整数称为四位平方数。例如,由于:7744=88 ,则称 7744 为四位平方 数。求出: (1)所有四位平方数的数目; (2)所有四位平方数之和。 (★★) (分析:最小四位数 1000 是 31.6 的平方,最大的四位数 9999 是 99.9 的平方) (答案:①1; ②7744) program e; var i,x,count,s:longint; begin writeln; count:=0; s:=0; for i:=32 to 99 do begin x:=i*i; if ((x div 1000)=((x div 100) mod 10))and(((x div 10) mod 10)=(x mod 10)) then begin inc(count); s:=s+x; end; end; writeln('count=',count,' s=',s); end. 其平方等于某两个正整数平方之和的正整数称为弦数。例如,由于 32+42=52,因此 5 为弦数。求 [121,130]之间: (1)弦数数目; (2)最小的弦数; (3)最大的弦数。 (★★★)

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

第 16 页

9.

(分析:设 a +b =c ,且 a<b,这样可以控制出现重复弦数) (答案:①4; ②122; ③130) program e; var i,j,k,x,count:longint; begin writeln; count:=0; for i:=121 to 130 do begin x:=trunc(sqrt(i*i/2)); for j:=1 to x do begin k:=trunc(sqrt(i*i-j*j)); if (i*i=j*j+k*k) then begin inc(count); writeln(i,'*',i,'=',j,'*',j,'+',k,'*',k); break; end; end; end; writeln('count=',count); end. 求满足以下三个条件: (a)X2+Y2+Z2=512; (b)X+Y+Z 之值最大; (c)X 最小。的一组 X、 Y、Z 的值。 (★★★★) (答案:X=22; Y=31; Z=34) program e1; var x,y,z,n,m,maxs,minx,xx,yy,zz:integer; begin writeln; n:=trunc(sqrt(51*51/3)); m:=trunc(sqrt((51*51-1*1)/2)); maxs:=0; minx:=51; for x:=n downto 1 do for y:=x to m do begin z:=trunc(sqrt(51*51-x*x-y*y)); if (z>y)and(x*x+y*y+z*z=51*51) then if ((x+y+z>maxs)or((x+y+z)=maxs)) then begin maxs:=x+y+z; xx:=x; yy:=y; zz:=z; end; end; writeln('x=',xx,' y=',yy,' z=',zz); end.

10. 计算 Y ?

eax ? e? ax x?a - ? x ? a) ? a?ln sin( (精度 10 4) (a=0.1、x=1.0) 。 2 2

(★)

(答案:0.0295) program e; var y,a,x:real; begin writeln; a:=0.1; x:=1.0; y:=(exp(a*x)-exp(-a*x))/2*sin(x+a)+a*ln((x+a)/2); writeln(y:0:4); end.

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

第 17 页

11. 倒勾股数是满足下列公式:

1 1 1 ,例如 ? 2 ? 2 (设 A>B>C)的一组(3 个)整数(A、B、C) 2 A B C 1 1 1 (156,65,60)是倒勾股数,因为 (★★) ? 2 ? 2 。问: 2 156 65 60

(1)A、B、C 之和小于 100 的倒勾股数有多少组? (2)满足(1)的诸组中,A、B、C 之和最小的是哪组? (提示:把公式转化为 A2B2=C2(A2+B2) ) (答案:①2; ②a=20, b=15, c=12) program e; var a,b,c,count,mins,mina,minb,minc:longint; begin writeln; count:=0; mins:=100; for c:=1 to 33 do for b:=c+1 to 49 do for a:=b+1 to 97 do if (a*a*b*b=c*c*(a*a+b*b))and(a+b+c<100) then begin inc(count); if (a+b+c<mins) then begin mins:=a+b+c; mina:=a; minb:=b; minc:=c; end; end; writeln('count=',count,' a=',mina,' b=',minb,' c=',minc); end. 12. 设有十进制数字 a、b、c、d、e,求在满足下列式子:abcd×e=dcba(a 非 0,e 非 0 非 1)的四位 数 abcd 中,求满足条件的最小的 abcd 和与之对应的 e。 (★★) (答案:1089; 9) program e1; var a,b,c,d,e,x,y:longint; begin writeln; for a:=1 to 9 do for b:=0 to 9 do for c:=0 to 9 do for d:=0 to 9 do for e:=2 to 9 do begin x:=a*1000+b*100+c*10+d; y:=d*1000+c*100+b*10+a; if (x*e=y) then begin writeln(x:8,e:8); exit; end; end; end. 13. 求方程: x ? 3x ? 1 ? 0 在区间(0,1)内的解,精度为 10 4。
3


(★★)

(答案:0.3473) program e; var x:real; begin writeln; x:=0.0001; repeat if (abs(x*x*x-3*x+1)<1e-4) then writeln(x:0:4); x:=x+0.0001;

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

第 18 页

until x>=1; end. 14. 按递增顺序产生序列 M 中最小的 80 个数。M 定义如下:数 1 属于 M;若 x 属于 M,则 y=2x+1, z=3x+1 也属于 M,并求: (★★★★) (1) 该序列第 50 个元素之值; (2)该序列前 50 个元素之和。 (答案: (1)172; (2)3853) program e; var i,j,k,t,p,n:longint; a:array[1..100] of longint; begin writeln; p:=1; a[p]:=1; n:=1; while p<50 do begin a[n+1]:=2*a[p]+1; a[n+2]:=3*a[p]+1; n:=n+2; for i:=1 to n-1 do for j:=1 to n-i do if a[j]>a[j+1] then begin t:=a[j]; a[j]:=a[j+1]; a[j+1]:=t; end; p:=p+1; end; writeln(a[p]:8); end. 15. 在 n 个一连串的方格内填写字母 A 或 B,但相邻两格内不能都填 B。求所有可能的填写方案数。 例如,当 n=3,可能的方案有 AAA、AAB、ABA、BAA、BAB 等 5 种。试求: (1)当 n=15 时, 所有可能的方案数是多少?(2)当 n=10 时,包含有 8 个字母 A 的方案数共有多少?(★★★) (提示:此题可以采用进制转换来解决。考虑到只包含了 A 与 B 两个字母,我们可以用二进制的 0 和 1 来代替,所以当全部是 A 时最小,此数为 0,当全部是 B 时最大为 2 n-1,我们让变量从 0~2 n-1 循环,然后将此数转换为相应的二进制数存储在数组中即可进行判断了。 ) (答案: (1)1597; (2)36) program e; var n,m,s,i,j,count:longint; flag:boolean; a:array[1..100] of integer; begin writeln('input n:'); readln(n); s:=1; count:=0; for i:=1 to n do s:=s*2; for i:=0 to s-1 do begin m:=i; for j:=1 to n do begin a[j]:=m mod 2; m:=m div 2; end; flag:=true; for j:=1 to n-1 do

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

第 19 页

if (a[j]=1)and(a[j+1]=1) then begin flag:=false; break; end; if flag=true then count:=count+1; end; writeln(count); end. program e; var n,m,s,i,j,count,na:longint; flag:boolean; a:array[1..100] of integer; begin writeln('input n:'); readln(n); s:=1; count:=0; for i:=1 to n do s:=s*2; for i:=0 to s-1 do begin m:=i; for j:=1 to n do begin a[j]:=m mod 2; m:=m div 2; end; flag:=true; for j:=1 to n-1 do if (a[j]=1)and(a[j+1]=1) then begin flag:=false; break; end; na:=0; for j:=1 to n do if a[j]=0 then na:=na+1; if (flag=true)and(na=8) then count:=count+1; end; writeln(count); end. 16. 给定自然数 1 到 n 的集合和自然数 m(m>n) ,求各元素之和等于 m 的子集。 (设 n=20,m=48) 。 (1)共有多少个符合上述条件的子集?(2)符合上述条件且子集元素数目为 5 的子集有多少? (★★★) (提示:集合的元素不能重复,此题可分 3~9 个元素类别集合讨论,下面给出第 2 问的源程序) (答案:①1674; ②488) program e1; const m=48; var a,b,c,d,e,f,g,count:integer; begin writeln; count:=0; for a:=1 to trunc(m/5) do for b:=a+1 to trunc((m-1)/4) do for c:=b+1 to trunc((m-1-2)/3) do for d:=c+1 to trunc((m-1-2-3)/2) do for e:=d+1 to 20 do if (a+b+c+d+e=m) then inc(count);

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

第 20 页

writeln('count5=',count); end. (以下程序设计试题来自《全国青少年信息学奥林匹克联赛――培训习题与解答(中学)) 》 1、 计算 1×2+3×4+5×6+??+49×50 的值。 (★) (答案:21450) program e; var i,x,s:longint; begin writeln; s:=0; x:=0; for i:=1 to 25 do begin x:=x+2; s:=s+x*(x-1); end; writeln(s); end. 2、 给定一串整数数列,求出所有的递增和递减子序列的数目。例如数列 7、2、6、9、8、3、5、2、1 可分为(7,2)(2,6,9)(9,8,3)(3,5)(5,2,1)五个子序列,答案就是 5。我们称 2、 、 、 、 、 9、3、5 为转折元素。 (★★★) program e; var a:array[1..9] of integer; i,j,k,n:integer; begin writeln('input 9 number'); for i:=1 to 9 do read(a[i]); n:=1; for i:=2 to 9-1 do if ((a[i]<a[i-1])and(a[i]<a[i+1]))or((a[i]>a[i-1])and(a[i]>a[i+1])) then n:=n+1; writeln(n:8); end. 3、 将 1~9 这 9 个数字分成三组(每个数字只能使用一次) ,分别组成三个三位数,且这三个三位数 的值构成 1:2:3 的比例,试求出所有满足条件的三个三位数。 (★★★) (分析:注意下面源程序所采用的算法,非常好) (答案: (192、384、576)(219、438、657)(273、546、819)(327、654、981) 、 、 、 ) program e; var a:array[0..9] of integer; i,g,s,b,k,t:integer; begin writeln; for i:=100 to 333 do begin for k:=0 to 9 do a[k]:=0; k:=i; g:=k mod 10; s:=(k div 10) mod 10; b:=k div 100; a[g]:=1; a[s]:=1; a[b]:=1; k:=2*i; g:=k mod 10; s:=(k div 10) mod 10; b:=k div 100; a[g]:=1; a[s]:=1; a[b]:=1; k:=3*i; g:=k mod 10; s:=(k div 10) mod 10; b:=k div 100; a[g]:=1; a[s]:=1; a[b]:=1; t:=0; for k:=1 to 9 do t:=t+a[k]; if t=9 then writeln(i:4,i*2:4,i*3:4); end;

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

第 21 页

end. 4、 回文算术:任给一个三位数 abc,算出 abc 与 cba 之和。若该和数不是回文数(回文数的定义是从 左读和从右读一样,如 5、121、1221 等) ,再按上述方法求和。以此类推,直到得到回文形式的和 数或者和数的位数已经超过 15 位时中止计算。 (★★★) (分析:注意此题中处理回文数判断的方法和处理数组高精度加法的方法) program e; var a,b:array[1..20] of integer; x,i,m:integer; hw:boolean; begin writeln; write('abc='); readln(x); for i:=1 to 15 do a[i]:=0; a[1]:=x mod 10; a[2]:=(x div 10) mod 10; a[3]:=x div 100; m:=3; hw:=false; while (hw=false)and(m<15) do begin for i:=1 to m do b[i]:=a[m-i+1]; i:=1; while (i<=m)and(a[i]=b[i]) do i:=i+1; if i>m then hw:=true else begin for i:=m downto 1 do write(a[i]); write('+'); for i:=m downto 1 do write(b[i]); write('='); for i:=1 to m do begin a[i]:=a[i]+b[i]; a[i+1]:=a[i+1]+a[i] div 10; a[i]:=a[i] mod 10; end; if a[m+1]>0 then m:=m+1; for i:=m downto 1 do write(a[i]); writeln; end; end; if hw then writeln('success!') else writeln('Fail!'); end. 5、求一个 n×n 数阵中的马鞍数,输出它的位置。所谓马鞍数,是指在行上最小而在列上最大的数。 (★★) (测试数据: (矩阵 1) (矩阵 2) 15 4 14 25 7 11 4 2 7 8 11 9 23 16 8 5 9 23 1 25 22 3 21 18 5 3 22 21 18 15 17 1 24 12 6 17 16 24 12 6 13 10 19 20 2 13 10 19 20 14 program e; const n=5; var i,j,min,x,y:integer; flag:boolean; a:array[1..n,1..n] of integer; begin writeln; writeln('input ',n,'*',n,' integer number:'); for i:=1 to n do

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

第 22 页

for j:=1 to n do read(a[i,j]); flag:=false; for i:=1 to n do begin min:=a[i,1]; x:=i; y:=1; for j:=1 to n do if a[i,j]<min then begin min:=a[i,j]; y:=j; end; for j:=1 to n do if a[j,y]>a[x,y] then break; if (j=n)and(a[x,y]>a[n,y]) then begin write(a[x,y],'(',x,',',y,')'); flag:=true; end; end; if flag=false then writeln('No find!'); end. 6、数学黑洞 6174。已知:一个任意的四位正整数(全相同的除外,如 1111) 。将数字重新组合成一个 最大的数和最小的数相减,重复这个过程,最多七步,必得 6174。即:7641-1467=6174。将永 远出不来。 求证:所有四位数数字(全相同的除外) ,均能得到 6174。输出掉进黑洞的步数。 (★★★) program e18; var a:array[1..4] of integer; i,j,d,k:integer; begin writeln('input a si wei shu:'); read(d); if (d mod 1111<>0) then while d<>6174 do begin a[1]:=d div 1000; a[2]:=(d mod 1000) div 100; a[3]:=(d mod 100) div 10; a[4]:=d mod 10; for i:=1 to 4 do for j:=i+1 to 4 do if a[i]<a[j] then begin k:=a[i]; a[i]:=a[j]; a[j]:=k; end; d:=1000*a[1]+100*a[2]+10*a[3]+a[4]-1000*a[4]-100*a[3]-10*a[2]-a[1]; writeln(1000*a[1]+100*a[2]+10*a[3]+a[4],'-',1000*a[4]+100*a[3]+10*a[2]+a[1],'=',d); end; end. (以下程序设计试题来自《青少年信息学竞赛题库》 ) 1、 输入 10 个正整数,计算它们的和,平方和。 program I_1; var i,s,d,p:integer; begin writeln('input ten positive number:'); s:=0; p:=0; for i:=1 to 10 do begin read(d); s:=s+d; p:=p+d*d; end;

(★)

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

第 23 页

writeln; write(s:8,p:8); end. 2、 统计 1——999 中能被 3 整除,且至少有一位数字是 5 的数。 (★) (答案:91) program I_4; var i,s:integer; begin writeln; s:=0; for i:=1 to 999 do begin if(i mod 3 = 0) and ((i mod 10 = 5) or ((i div 10) mod 10 =5) or ((i div 100)=5)) then begin write(i:8); s:=s+1; end; end; writeln; write(s:8); end. 3、 从键盘输入一个 20~50 之间的整数,统计出边长为整数,周长为输入数的不等边三角形的个数。 (测试数据:输入 27, 输出 18) (★★) program I_9; var x,y,z,k,s:integer; begin writeln; writeln('input a integer number(20<n<50):'); readln(s); k:=0; for x:=1 to (s div 3) do for y:=x to ((s-x) div 2) do begin z:=s-x-y; if (x+y)>z then begin writeln(x:4,y:4,z:4); k:=k+1; end; end; if (s mod 3)=0 then k:=k-1; write(k); end. 3 2 2 4、 一个整数的立方可以表示为两个整数的平方差,如 1985 =1971105 -1969120 。 3 2 2 编程:输入一个整数 N,自动将其写成 N =X -Y 。 (★★★) 3 2 2 2 (提示:N =X -Y =(X+Y)(X-Y),所以必有(X-Y)=N, (X+Y)=N 。 ) 3 2 2 (测试数据:N=2004; 答案 2004 =2009010 -2007006 ) program I_13; var n,x,y:longint; begin writeln; read(n); for y:=1 to maxlongint do begin x:=y+n; if (n*n=x+y) then begin writeln(n,'^3=',x,'^2-',y,'^2'); exit; end; end; end. 5、 任意给定平面上三个点 A(X1,Y1) ,B(X2,Y2) ,C(X3,Y3) ,试判断这三个点能否构成三角形。

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

第 24 页

能则求出它的面积。 (★★) (测试数据: program I_16; var x1,y1,x2,y2,x3,y3,a,b,c,d,e,k:real; begin writeln; write('input X1,Y1 X2,Y2 X3,Y3:'); read(x1,y1,x2,y2,x3,y3); a:=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); b:=sqrt((x2-x3)*(x2-x3)+(y2-y3)*(y2-y3)); c:=sqrt((x3-x1)*(x3-x1)+(y3-y1)*(y3-y1)); if a<b then begin k:=a; a:=b; b:=k; end; if a<c then begin k:=a; a:=c; c:=k; end; if a<b+c then begin d:=(a+b+c)/2; e:=sqrt(d*(d-a)*(d-b)*(d-c)); write('area=',e:8:3); end else write('bu neng gou cheng san jiao xing'); end. 2 2 2 2 2 2 6、 59=3 +5 +5 =1 +3 +7 ,即 59 可以分别等于两组不同的自然数(每组各 3 个数)的二次幂之和,请 找出 10 个最小的具有这种特性的数。 (★★★) (分析:注意此程序中 Goto 语句的用法) (答案: (27、1、1、5、3、3、3) (33、1、4、4、2、2、5) (38、1、1、6、2、3、5)等) program e; label 1; var m,a,b,c,n,a1,b1,c1,count:integer; begin writeln; count:=0; m:=0; 1:repeat begin inc(m); if count>=10 then exit; n:=0; for a:=1 to trunc(sqrt(m/3)) do for b:=a to trunc(sqrt((m-a*a)/2)) do for c:=b to trunc(sqrt(m-a*a-b*b)) do if (a*a+b*b+c*c>m) then goto 1 else if (a*a+b*b+c*c=m) then begin inc(n); if n=1 then begin a1:=a; b1:=b; c1:=c; end else if n=2 then begin inc(count); writeln(m:4,a1:4,b1:4,c1:4,a:4,b:4,c:4); goto 1; end; end; end; until count>=10; end. 7、 每一个素数的倒数都可以化为一个循环小数,例如:1/7 可以化为 0.(142857) ,1/13 可化为 0.(076923) 。编程把 17 的倒数化为循环小数。 (★★) (答案:0.(0588235294117647)) program I_25;

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

第 25 页

var a,b,c,i,j,k:integer; e:array[1..200] of integer; yes:boolean; begin writeln; a:=1; b:=17; for i:=1 to 200 do begin c:=a*10 div b; a:=10*a mod b; e[i]:=c; end; for i:=1 to 200 do for j:=i+1 to 200 do if (e[i]=e[j]) then begin yes:=true; for k:=1 to j-i do if e[i]<>e[j] then yes:=false; if yes=true then begin for k:=i to j-1 do write(e[k]); halt; end; end; end. 8、 求数列 1、5、17、53、161、。 。。前 20 项的和。 (提示: An=2+3×An-1) (★★) (答案:3486784380) program I_29; var an,am,s:real; i:integer; begin writeln; am:=1; s:=1; write(am:20:0); for i:=2 to 20 do begin an:=am*3+2; s:=s+an; am:=an; write(am:20:0); end; writeln; write('totle:',s:0:0); end. 9、 编一程序实现:由键盘输入年月日后,计算机能打印出该日期是星期几。 (★★) (提示:首先算出这一年的元旦是星期几。算法如下:①输入年份 year;②根据下面公式计算: d=year+( (year-1)div 4)-( (year-1)div 100)+( (year-1)div 400) d=d mod 7;那么 d=0 则表示为 Sunday、d=1 则表示为 Monday、……依此类推。 ③输入月份 month 和日期 day,计算该日期是这个年份中的第几天(x) ; ④计算(x+d-1)mod 7,得到星期几。 注意月份中的二月是 28 天还是 29 天,需看年份是否为闰年,闰年定义为:年份能被 400 整除的 是闰年,或者年份能被 4 整除但不能被 100 整除的是闰年,其它年份均不为闰年。闰年的计算方 法如下:若( (year mod 4=0)and(year mod 100<>0) )or(year mod 400=0)则为闰年。 ) program e; const

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

第 26 页

yd:set of 1..12=[1,3,5,7,8,10,12]; {月大的月份} yx:set of 1..12=[4,6,9,11]; {月小的月份} a:array[1..12] of integer=(0,31,59,90,120,151,181,212,243,273,304,334); {a 数组存放第 i 个月份的前 i-1 个月的天数} {因为这 12 个月的天数分别为 31,28,31,30,31,30,31,31,30,31,30,31,故前 i-1 个月的天数为不断叠 加} s:array[0..6] of string= ('Sunday','Monday','Tuesday','Wednesday','Thursday','Friday','Saturday'); var year,m,day,d,x:integer; r,flag:boolean; begin writeln('input year:'); readln(year); if (year mod 400=0)or((year mod 4=0)and(year mod 100<>0)) then r:=true else r:=false; repeat writeln('input month:'); readln(m); until (m in [1..12]); flag:=false; repeat writeln('input day:'); readln(day); if (m in yd)and(day in [1..31]) then flag:=true else if (m in yx)and(day in [1..30]) then flag:=true else if (m=2)and(r=true)and(day in [1..29]) then flag:=true else if (m=2)and(r=false)and(day in [1..28]) then flag:=true; until flag=true; d:=year+((year-1) div 4)-((year-1) div 100)+((year-1) div 400); {按公式计算 d} d:=d mod 7; {得到元旦为星期几} x:=a[m]+day; {x 表示该天是该年的第几天} if (m>2)and(r=true) then x:=x+1; {如果月份大于二月且该年为闰年,那么天数需要多加一天} x:=(x-1+d) mod 7; {x-1 表示在元旦的基础上,该天是第多少天} writeln('Today is ',s[x]); end. 10、编程实现:键盘输入年月,计算机能打印出该月的月历,如输入 2004、6,则输出: (★★★) SUM MON TUE WED THU FRI SAT 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 program e; const yd:set of 1..12=[1,3,5,7,8,10,12]; {月大的月份} yx:set of 1..12=[4,6,9,11]; {月小的月份} a:array[1..12] of integer=(0,31,59,90,120,151,181,212,243,273,304,334); var year,m,day,d,x,i:integer; r:boolean; begin writeln('input year:'); readln(year); if (year mod 400=0)or((year mod 4=0)and(year mod 100<>0)) then r:=true else r:=false; repeat writeln('input month:'); readln(m); until (m in [1..12]); if m in yd then day:=31

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

第 27 页

else if m in yx then day:=30 else if (m=2)and(r=true) then day:=29 else day:=28; d:=year+((year-1) div 4)-((year-1) div 100)+((year-1) div 400); {按公式计算 d} d:=d mod 7; {得到元旦为星期几} x:=a[m]; {x 表示该月是的前 m-1 个月的天数} if (m>2)and(r=true) then x:=x+1; {如果月份大于二月且该年为闰年,那么天数需要多加一天} x:=(x-1+d) mod 7; {x-1 表示在元旦的基础上,该天是第多少天,x 表示上个月最后一天是星期 几} writeln('SUM':4,'MON':4,'TUE':4,'WED':4,'THU':4,'FRI':4,'SAT':4); for i:=0 to x do write('':4); {上个月占用的星期用空格输出} for i:=1 to day do begin if (i+x) mod 7=0 then writeln; write(i:4); end; end. 11、写出两个 1,然后在它们中间插入 2,成 121;下一步是在上面数中每两个相邻的和数为 3 的数之 间插入 3, 成为 13231; 再下一步又在上面数中任意两个相邻的和数为 4 的数中插入 4, 成为 1432341; 由键盘输入 N,求出用上面方式构造出来的序列,其最后插入的数是 N。假设这个序列不超过 1000 项,给出 N=9 时的运算结果。 12、把所有 3 的方幂及不相等的 3 的方幂的和排列成递增序列:1、3、4、9、10、12、13、。 。。这个序 列的第 300 项是多少?(6840) 13、两个 1,两个 2,两个 3,这 6 个数可组成 6 位数 312132。这个数有如下特点:两个 1 之间隔一位, 两个 2 之间隔两位,两个 3 之间隔 3 位。231213 也是一个符合条件的 6 位数。用数字 1、2、3、4、 5、6、7、8 各两个,可以组成类似的 16 位数,请找出 10 个这样的 16 位数。 14、对于所有的数字不完全相同的三位数(不够三位数的前面补零也当成是三位数) 。我们定出如下计 算规则:用这个三位数的三个数字可组成的最大数减去可组成的最小数,则得到一个新的三位数; 对新的三位数还按照上面的规则继续算下去,最后会发现,我们陷入一个死循环里,或者说是跌入 了一个数的黑洞里。 用具体例子说明。 比如从三位数 123 开始, 计算如下 321-123=198; 981-189=792; 972-279=693;963-369=594;954-459=495;954-459=495;?. 从其他的任何三位数开始,最终也 都会停止在 495,我们把 495 叫做三位数的黑洞。类似地也存在着一个由一个数组成的四位数的黑 洞。请编程序把它找出来。 (6174) (答案:与前面的数学黑洞问题相似,故此程序略) 15、11,323,74947,63144136 这样的数叫回文数,它们的特点是最高位、最低位的数相同,次高位, 次低位相同,?.其中 11 是个更特殊的回文数,它的平方 121、立方 1331 也是回文数。这是最小 的一个具有这种性质的回文数。 请编程, 找出三次方小于 999999999 的具有上述性质的所有回文数。 (答案:1、2、11、101、111) (★★) program e; var i:longint; function huiwen(x:longint):boolean; var a,b:array[1..100] of integer; m,n,y:longint; hw:boolean; begin if x<1 then begin huiwen:=false; exit; end; for m:=1 to 100 do a[m]:=0; y:=x; m:=0;

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

第 28 页

repeat inc(m); a[m]:=y mod 10; y:=y div 10; until y=0; for n:=1 to m do b[n]:=a[m+1-n]; n:=1; while (n<=m)and(a[n]=b[n]) do inc(n); if n=m+1 then huiwen:=true else huiwen:=false; end; {=============main=============} begin writeln; for i:=1 to 999 do if (huiwen(i)=true)and(huiwen(i*i)=true)and(huiwen(i*i*i)=true) then write(i:8); end. 16、请编写程序,以简单算术表达式作为输入,构造对应的无括号表达式(无括号表达式的运算符写 在运算对象的后面) 如: 。 输入: (B-C) 应输出 ABC-*D+; A* +D, 输入: A+B) ( /C-D*E, 应输出 AB+C/DE*-。 17、键盘输入一个只含加、减、乘、除四则运算和括号的数学表达式,编程求出该表达式的值并输出 结果。 18、一只公鸡值5元,一只母鸡值3元,3只小鸡值1元,现用一百元要买一百只鸡,问有什么方案? (答案: (0、25、75)(4、18、78)(8、11、81)(12、4、84) , , , ) (★★) program e; var i,j,k:integer; begin writeln; for i:=1 to 20 do for j:=1 to 33 do begin k:=100-i-j; if (k mod 3=0)and(5*i+3*j+(k div 3)=100) then writeln(i:8,j:8,k:8); end; end. (来自其它试题) 1、 某超市为了促销,规定:购物不足 50 元的按原价付款,超过 50 不足 100 的超过部分按九折付款, 超过 100 元的,超过部分按八折付款。编一程序完成超市的自动计费的工作。 (★) program e; var n,money:real; begin writeln; writeln('input the money number:'); readln(n); money:=0; if n<=50 then money:=n else if (n>50)and(n<=100) then money:=50+(n-50)*0.9 else money:=50+(100-50)*0.9+(n-100)*0.8; writeln('money=',money:0:2); end. 2、 输入四个整数,排出名次后输出这四个数。如输入 75、99、67、98。则输出: (★★★) 75——3、99——1、67——4、98——2。 相关练习:任意输入 N 个整数,排出名次后输出这 N 个数。 program e; var

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

第 29 页

a:array[1..4] of integer; i,j,m:integer; begin writeln; for i:=1 to 4 do read(a[i]); for i:=1 to 4 do begin m:=1; write(a[i],'--'); for j:=1 to 4 do if a[j]>a[i] then inc(m); write(m,' '); end; end. 3、 任意输入一个正整数(<maxlongint) ,计算它各位数字上的和。 (★) (测试数据:35829083; 答案:38) program e; var n,s:longint; begin writeln; writeln('input n:'); readln(n); s:=0; while n>0 do begin s:=s+(n mod 10); n:=n div 10; end; writeln(s); end. 4、 1981 年,李氏兄弟三人核对自己的年龄。老三说,第一,我们三兄弟之间年龄之差是相等的;第 二,去年我们三兄弟的年龄数恰好都等于各自出生年份中各数之和的 2 倍。你能根据这两点提示, 编程计算出这兄弟三人的年龄和出生年月吗? (★★) (分析:假定这三兄弟均在 1900 年后出生) (答案:1981 年时,老大 43 岁 1938 年出生、老二 37 岁 1944 年出生、老三 31 岁 1950 年出生) program e; var a,b,c:integer; begin writeln; for a:=1 to 100 do for b:=a+1 to 100 do for c:=b+1 to 100 do if (c-b=b-a) then if((a-1)=2*(10+((1981-a)mod 10)+(((1981-a)div 10)mod 10))) then if ((b-1)=2*(10+((1981-b)mod 10)+(((1981-b)div 10)mod 10))) then if ((c-1)=2*(10+((1981-c)mod 10)+(((1981-c)div 10)mod 10))) then writeln(a:4,b:4,c:4); end. 5、 将 1~9 这 9 个数字分成三组,每组 3 个数字,每个数字只能且必须使用一次,并且每组中的 3 个 数字组成的三位数又要是完全平方数。请编程找出这样的数。 (★★) (分析:注意下面程序所采取的方法与前面类似问题的算法一样,非常好。答案:361、529、784) program e; var i,j,k,g,s,b,t,n:integer; a:array[0..9] of integer; begin writeln;

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

第 30 页

for i:=11 to 31 do for j:=i to 31 do for k:=j to 31 do begin for n:=0 to 9 do a[n]:=0; g:=i*i mod 10; s:=(i*i div 10) mod 10; b:=i*i div 100; a[g]:=1; a[s]:=1; a[b]:=1; g:=j*j mod 10; s:=(j*j div 10) mod 10; b:=j*j div 100; a[g]:=1; a[s]:=1; a[b]:=1; g:=k*k mod 10; s:=(k*k div 10) mod 10; b:=k*k div 100; a[g]:=1; a[s]:=1; a[b]:=1; t:=0; for n:=1 to 9 do t:=t+a[n]; if t=9 then writeln(i*i:8,j*j:8,k*k:8); end; end. 6、

素数类问题程序设计试题
(备注:除第 1 题写出判断素数子函数外,其余各题的判断素数子函数均相同,故省略,但同学 们在编程的时候不能省,否则程序将无法运行。 ) 1、 编程求正整数 M 与 N(M<N)之间的所有素数。 (★★,循环语句、If 条件语句) program e; var i,m,n:integer; function prime(x:longint):boolean; var j,y:longint; flag:boolean; begin y:=trunc(sqrt(x)); flag:=true; for j:=2 to y do if (x mod j = 0) then begin flag:=false; break; end; if x<2 then flag:=false; if flag=true then prime:=true else prime:=false; end; begin writeln; writeln('input two integer number for m and n (m<n):'); readln(m,n); for i:=m to n do if prime(i)=true then write(i:4); end. 2、 验证歌德巴赫猜想:任何一个充分大的偶数 N(N≥4) ,都可以用两个素数之和表示。例如:4=2 +2,6=3+3,8=3+5,98=17+79。 (★★,循环语句) 3、 歌德巴赫猜想之一是任何大于 5 的奇数都可表示为 3 个素数之和。请用 10 个大于 5 的奇数验证这 一论断。奇数用随机函数产生,把验证编写为过程,打印出每个数和组成该数的三个素数。 (★★) 4、 编写程序,判断任何一个大于 2 的整数是素数还是合数。 (★★) (素数算法:只需判断到这个数开平方的整数为止即可,如判断 25,则只需判断从 2~5 即可) (测试数据:2147483647; 答案:Yes) (源程序略) 5、 一个自然数是素数,且它的数字位置经过任意对换后仍为素数,则称为绝对素数,例如 13。试找 出所有两位数的绝对素数。 (★★) (答案:11、13、17、31、37、71、73、79、97) (源程序略) 6、 用筛选法求素数。 (★★★) 7、 若两素数之差为 2,则称该两素数为双胞胎数。求出[2,300]之内: (★★)

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

第 31 页

(1)最大的一对双胞胎数; (2)有多少对双胞胎数。 (答案:①281 和 283; ②19) (源程序略) 8、 若两个自然连续数乘积减 1 后是素数, 则称此两个自然连续数为友数对, 该素数称为友素数。 例如, 由于 2×3-1=5,因此,2 与 3 是友数对,5 是友素数。求[2,99]之间: (★★) (1)友数对的数目; (2)所有友素数之和。 (答案:①48; ②128044) (源程序略) n 9、 梅森尼数是指能使 2 -1 为素数的数 n。求[1,21]范围内: (★★) (1)有多少个梅森尼数?(2)最大的梅森尼数? (答案:①7; ②19) program e6_9; var i,count:longint; begin writeln; count:=0; for i:=1 to 21 do if prime(trunc(exp(i*ln(2))-1))=true then begin inc(count); write(i:8); end; writeln; writeln('count=',count); end. 10、一个素数(设为 p)依次从低位去掉一位,二位,?,若所得的各数仍都是素数,则称数 p 为超级 素数。例如 239 即是超级素数。试求[100,9999]之内: (★★) (1)超级素数的个数; (2)最大的超级素数。 (答案:①30; ②7393) program e6_9; var i,count:integer; begin writeln; for i:=100 to 999 do if (prime(i))and(prime(i div 10))and(prime(i div 100)) then inc(count); for i:=1000 to 9999 do if (prime(i))and(prime(i div 10))and(prime(i div 100))and(prime(i div 1000)) then begin inc(count); write(i:8); end; writeln; writeln('count=',count); end. 11、求 1000~1200 以内的所有纯素数。纯粹素数是这样定义的:一个素数,去掉最高位,剩下的数仍 为素数,再去掉剩下的数的最高位,余下的数还是素数。这样下去一直到最后剩下的个位数也还是 素数。 (纯素数不同于超级素数,注意二者的区别) (★★) (答案:1013、1097、1103) program I_14; var x:integer; begin writeln; for x:=1000 to 1200 do if prime(x)=true then if prime(x mod 1000)=true then if prime(x mod 100)=true then if prime(x mod 10)=true then write(x:8); end. 12、一个合数,去掉最低位,剩下的数仍是合数,再去掉剩下的数的最低位,余留下来的数还是合数,

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

第 32 页

这样反复,一直到最后公剩下的一位数仍是合数;我们把这样的数称为纯粹合数。求 100~500 之 间所有纯粹合数的个数。 (★★) (答案:58) program I_18; var i,s:integer; begin writeln; s:=0; for i:=100 to 500 do if (prime(i)=false) and (prime(i div 10)=false) and (prime(i div 100)=false) and ((i div 100)<>1) then begin write(i:8); inc(s); end; writeln; writeln(s); end. 13、试找出 5 个小于 160 而成等差数列的素数。 (★★) (答案:5、11、17、23、29;或 5、17、29、41、53) program I_28; var i,d:integer; begin writeln; for i:=2 to 160 do for d:=1 to 26 do if prime(i)=true then if prime(i+d)=true then if prime(i+2*d)=true then if prime(i+3*d)=true then if prime(i+4*d)=true then writeln(i:4,i+d:4,i+2*d:4,i+3*d:4,i+4*d:4) end. 14、如果两个素数之和的一半仍然是一个素数, 则这三个素数可以组成一个等差素数组, (3+7) 如 /2=5, 则(3,5,7)为一个等差素数组,编程求 100 以内的所有等差素数组。 (★★) (答案:共 46 组) program e6_9; var d,i:longint; begin writeln; for i:=2 to 100 do for d:=2 to 100 do begin if ((i+2*d)<100)and(prime(i)=true)and(prime(i+d)=true)and(prime(i+2*d)=true) then write(i:8,i+d:8,i+2*d:8,'':16); end; end. 15、某自然数 n 的所有素数因子的平方和等于 n, (n<100) ,请找出二个这样的自然数 n。 (★★) (答案:4、9、25、49) program e6_9; var i,j,s:integer; begin writeln; for i:=2 to 100 do begin

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

第 33 页

s:=0; for j:=2 to i do if (i mod j=0)and(prime(j)=true) then s:=s+j*j; if s=i then write(i:8); end; end. 16、

因子、质因子类问题程序设计试题
1、 任意输入一个正整数,输出它的质因子乘积形式。如 100=2×2×5×5。 (★★) program e2_25; var i,n:integer; begin writeln; writeln('input a integer number:'); readln(n); write(n,'='); while n>1 do begin for i:=2 to n do if n mod i=0 then begin n:=n div i; write(i); dec(i); if n>1 then write('*') else exit; end; end; end. 2、 求 2~1000 中的完数。 (因子(除开它本身)之和等于它本身的数称为完数,例如 28 的因子是 1、 2、4、7、14,并且 1+2+4+7+14=28,所以 28 是完数。(完数又称完全数) ) (★★) (答案:6、28、496) program e2_27; var i,j,n,s:integer; begin writeln; for i:=2 to 1000 do begin n:=i; s:=0; for j:=1 to n div 2 do if n mod j=0 then s:=s+j; if s=n then write(n:8); end; end. 3、 整数 36 的质因子共有 4 个,它们是 2,2,3,3,求整数 716539 的: (★★) (1)质因子个数; (2)最小质因子; (3)最大质因子。 (答案:①3; ②83; ③97) program e; var i,x,n:longint; begin writeln; n:=0; x:=716539; write(x,'=');

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

第 34 页

while (x>1) do begin for i:=2 to x do if (x mod i=0) then begin write(i); x:=x div i; inc(n); dec(i); if x>1 then write('*'); end; end; writeln; writeln('n=',n); end. 4、 若某整数 N 的所有因子之和等于 N 的倍数,则称 N 为多因子完备数。例如,28 是多因子完备数。 因为:1+2+4+7+14+28=56=28×2。试求[1,700]之内: (★★) (1)有多少个多因子完备数?(2)最大的一个多因子完备数是? (答案:①6; ②672) program e; var i,j,n,count:integer; begin writeln; count:=0; for i:=1 to 700 do begin n:=0; for j:=1 to i do if (i mod j=0) then n:=n+j; if (n mod i=0) then begin inc(count); write(i:8); end; end; writeln; writeln('count=',count); end. 5、 已知 24 有 8 个因子,而 24 正好被 8 整除。求[1,100]之间: (★★) (1)有多少个整数能被其因子的个数整除?(2)其中最大的整数是? (答案:①16; ②96) program e; var i,j,n,count:integer; begin writeln; count:=0; for i:=1 to 100 do begin n:=0; for j:=1 to i do if (i mod j=0) then inc(n); if (i mod n=0) then begin write(i:8); inc(count); end; end; writeln; writeln('count=',count); end. 6、 寻求并输出 3000 以内的亲密数对。亲密数对的定义为:若正整数 A 的所有因子(不包括 A)之和 为 B,B 的所有因子(不包括 B)之和为 A,且 A≠B,则称 A 与 B 为亲密数对。 (★★) (答案: [220,284][1184,1210][2620,2924] 、 、 ) program e; var i:integer;

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

第 35 页

function qinmi(n:integer):integer; var j,s:integer; begin s:=0; for j:=1 to n-1 do if (n mod j=0) then s:=s+j; qimi:=s; end; begin writeln; for i:=2 to 3000 do if (qinmi(i)<3000)and(qinmi(qinmi(i))=i)and(i<>qinmi(i)) then writeln(i:8,qinmi(i):8); end. 7、 一个自然数,若它的素因数至少是两重的(相同的素因数至少个数为二个,如:36=2*2*3*3) ,则 称该数为"漂亮数"。若相邻的两个自然数都是"漂亮数",就称它们为"孪生漂亮数",例如 8 和 9 就是一对"孪生漂亮数"。编程再找出一对"孪生漂亮数"。 (★★★) (分析:素因素至少是两重的则说明这个数至少能被素因素的平方整除,注意此程序退出语句用法) (答案:288 和 289、675 和 676) program e; var i:longint; function piaoliang(x:longint):boolean; var a,y:longint; flag:boolean; begin flag:=true; y:=x; if y<4 then begin flag:=false; exit; end; while y>1 do begin for a:=2 to y do begin if (y mod (a*a)<>0)and(a*a>y) then begin piaoliang:=false; exit; end else if (y mod (a*a)=0) then repeat y:=y div a; until (y mod a<>0); if a>y then break; end; end; if flag=true then piaoliang:=true else piaoliang:=false; end; begin writeln; i:=8; repeat inc(i); if (piaoliang(i)=true)and(piaoliang(i+1)=true) then begin writeln(i:8,i+1:8); exit; end; until(i>1000); end. 8、 6 的因子有 1、2、3、6,它们的和 1+2+3+6 与原数 6 的比值等于 2,比 6 小的数的这个比值都小于 2,比 6 大的数一直到 12,才有(1+2+3+4+6+12)/12=2.33,比值超过 2。 编程序,给出 120 以内

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

第 36 页

最大比值的统计表, 即从 6 开始计算此值, 得到更大的此值就输出, 再得到新的更大比值则再输出, 一直到 120,输出格 式为: (★★) 6 12 。。 。 2 2.33 。。(其中比值精确到小数点后第二位) 。 (答案: 6 12 24 36 48 60 120 2.00 2.33 2.50 2.53 2.58 2.80 3.00 ) program e; var i,j,k,s:integer; a:array[1..120] of integer; b:array[1..120] of real; begin writeln; a[1]:=6; b[1]:=2; k:=1; for i:=6 to 120 do begin s:=0; for j:=1 to i do if (i mod j=0) then s:=s+j; if (s/i)>b[k] then begin inc(k); a[k]:=i; b[k]:=s/i; end; end; for i:=1 to k do write(a[i]:8); writeln; for i:=1 to k do write(b[i]:8:2); end. 9、

约瑟夫类问题程序设计试题
1、 约瑟夫问题:N 个人围成一圈,从第一个人开始报数,数到 M 的人出圈;再由下一个人开始报数, 数到 M 的人出圈;??,输出依次出圈的人的编号。N、M 由键盘输入。 (★★★) (测试数据 N=8,M=3; 答案:3、6、1、5、2、8、4、7) program e; var m,n,i,count,x:integer; a:array[1..1000] of integer; begin writeln; writeln('input integer number for n(people number):'); readln(n); x:=0; writeln('input integer number for m:'); readln(m); for i:=1 to n do a[i]:=1; x:=0; count:=0; i:=0; repeat inc(i); if i=n+1 then i:=1; if a[i]=1 then inc(count); if count=m then begin count:=0; write(i,' '); a[i]:=0; inc(x); end; until(x=n); end. 2、 n 只猴子选大王,选举办法如下:从头到尾 1、2、3 报数,凡报 3 的退出;余下的从尾到头 1、2、 3 报数,凡报 3 的退出;余下的又从头到尾报数,还是报 3 的退出;依此类推,当剩下两只猴子时, 取这时报数报 1 的为王。若想当猴王,请问当初应占据什么位置?(★★★★) (算法分析:开始选举之前用 n 个数组存放数 1,当报数为 3 的倍数时,更改存放的数为 0(0 表

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

第 37 页

示淘汰出局) ,直到最后只有两个 1 为止) (测试数据:N=8; 答案:4) program e4_7; var a:array[1..1000] of integer; i,n,b,count:integer; begin writeln; write('input N:'); read(n); for i:=1 to n do a[i]:=1; count:=n; while count>1 do begin if count=2 then begin for i:=1 to n do if a[i]=1 then begin write(i); exit; end; end else begin b:=0; for i:=1 to n do begin if a[i]=1 then inc(b); if (b mod 3=0)and(b>0) then begin a[i]:=0; dec(count); b:=0; end; end; end; if count=2 then begin for i:=n downto 1 do if a[i]=1 then begin write(i); exit; end; end else begin b:=0; for i:=n downto 1 do begin if a[i]=1 then inc(b); if (b mod 3=0)and(b>0) then begin a[i]:=0; dec(count); b:=0; end; end; end; end; end. 3、 围绕着山顶有 10 个洞,一只狐狸和一只兔子住在各自的洞里。狐狸总想吃掉兔子。一天,兔子对 狐狸说: “你想吃我有一个条件,先把洞从 1~10 编上号,你从 10 号洞出发,先到 1 号洞找我;第 二次隔一个洞找我,第三次隔 2 个洞找我,以后依此类推,此数不限。若能找到我,你就可以饱餐 一顿。 不过在没有找到我以前不能停下来。 狐狸满口答应就开始找了, ” 它从早到晚进了 1000 次洞, 累得昏了过去也没找到兔子。问兔子躲在几号洞? (★★) (答案:2、4、7、9) program e4_8; var a:array[1..10] of integer; i,n:longint; begin

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

第 38 页

writeln; for i:=1 to 10 do a[i]:=1; n:=0; for i:=1 to 1000 do begin n:=n+i; if n mod 10=0 then a[10]:=0 else a[n mod 10]:=0; end; for i:=1 to 10 do if a[i]=1 then write(i:8); end. 4、 有 2N 个学生去春游,其中男女各半。为了增加乐趣,他们玩一个出圈游戏,游戏的规则是:所有 的学生围成一个圈,顺时针从 1 到 2N 编号,从 1 号开始以 1 到 M(M≥1)循环报数,报到 M 的 人退出,当有 N-1 个人出圈后,只剩下一个女生了,于是改变游戏规则从刚才的下一个人开始仍 以 1 到 M 反向(与原来的方向相反)报数,报到 M 的人退出,恰好最后一个出圈的是女生。问当 初他们是怎样排列的,同时按他们出圈的先后顺序输出各自的编号。以“O”表示男生, “*”表示 女生。 5、 编号为 1、2、3、?、N 的 N 个人按顺时针方向围坐一圈,每人持有一个密码(正整数) 。从指定 编号为 1 的人开始, 按顺时针方向自 1 开始顺序报数, 报到指定数 M 时停止报数, M 的人出列, 报 并将他的密码作为新的 M 值,从他在顺时针方向的下一个人开始,重新从 1 报数,依此类推,直 至所有的人全部出列为止。请设计一个程序求出出列的顺序,其中 N≤30,M 及密码值从键盘输 入。 6、

高精度算法程序设计试题
(在下面的高精度算法程序设计试题中,均采用子过程进行输入、输出和加、减、乘等操作,其中的 输出和输出操作通用,特别需仔细体会加、减、乘子过程的算法描述。 ) 1、 从键盘输入两个位数不超过 100 位的正整数 A 和 B,求 A+B 的值。 program e; var a,b,c:array[0..1000] of byte; s1,s2:string; procedure shuru; var i,j,code:integer; flag:boolean; begin repeat writeln('input A:'); readln(s1); flag:=true; a[0]:=length(s1); for i:=1 to a[0] do if (ord(s1[i])<48)or(ord(s1[i])>57) then flag:=false; until flag=true; for i:=1 to a[0] do val(s1[a[0]-i+1],a[i],code); repeat writeln('input B:'); readln(s2); flag:=true; b[0]:=length(s2); for i:=1 to b[0] do if (ord(s2[i])<48)or(ord(s2[i])>57) then flag:=false; until flag=true;

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

第 39 页

for i:=1 to b[0] do val(s2[b[0]-i+1],b[i],code); end; procedure jia; var i,t:integer; begin if a[0]>b[0] then t:=a[0] else t:=b[0]; for i:=1 to t do begin c[i]:=c[i]+(a[i]+b[i]); if c[i]>=10 then begin inc(c[i+1]); c[i]:=c[i] mod 10; end; 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; shuru; jia; shuchu; end. 2、 从键盘输入两个位数不超过 100 位的正整数 A 和 B,求 A-B 的值。 program e; var a,b,c:array[0..1000] of byte; s1,s2:string; procedure shuru; var i,j,code:integer; flag:boolean; begin repeat writeln('input A:'); readln(s1); flag:=true; a[0]:=length(s1); for i:=1 to a[0] do if (ord(s1[i])<48)or(ord(s1[i])>57) then flag:=false; until flag=true; for i:=1 to a[0] do val(s1[a[0]-i+1],a[i],code); repeat writeln('input B:'); readln(s2); flag:=true; b[0]:=length(s2); for i:=1 to b[0] do if (ord(s2[i])<48)or(ord(s2[i])>57) then flag:=false; until flag=true; for i:=1 to b[0] do val(s2[b[0]-i+1],b[i],code); end; procedure jian; var i:integer; begin

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

第 40 页

if (a[0]>b[0])or((a[0]=b[0])and(s1>s2)) then for i:=1 to a[0] do begin if a[i]-b[i]<0 then begin a[i+1]:=a[i+1]-1; a[i]:=a[i]+10; end; c[i]:=a[i]-b[i]; end else begin write('-'); for i:=1 to b[0] do begin if b[i]-a[i]<0 then begin b[i+1]:=b[i+1]-1; b[i]:=b[i]+10; end; c[i]:=b[i]-a[i]; end; 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; shuru; jian; shuchu; end. 3、 从键盘输入两个位数不超过 100 位的正整数 A 和 B,求 A*B 的值。 program e; var a,b,c:array[0..1000] of byte; s1,s2:string; procedure shuru; var i,j,code:integer; flag:boolean; begin repeat writeln('input A:'); readln(s1); flag:=true; a[0]:=length(s1); for i:=1 to a[0] do if (ord(s1[i])<48)or(ord(s1[i])>57) then flag:=false; until flag=true; for i:=1 to a[0] do val(s1[a[0]-i+1],a[i],code); repeat writeln('input B:'); readln(s2); flag:=true; b[0]:=length(s2); for i:=1 to b[0] do if (ord(s2[i])<48)or(ord(s2[i])>57) then flag:=false; until flag=true; for i:=1 to b[0] do val(s2[b[0]-i+1],b[i],code); end; procedure cheng;

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

第 41 页

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; shuru; cheng; shuchu; end. 4、 输入两个正整数 A 和 B,其中 A、B 都小于 32767,求 A/B 的值。要求计算结果精确到小数点后 N(1≤N≤200)位。 (★★★) (测试数据: ①输入 A=1,B=1997,N=25; 答案:0.0005007511266900350525788 ②输入 A=19997,B=197,N=15; 答案:101.507614213197969) program I_23; var a,b,c,n,i:integer; begin writeln; writeln('input A,B and N:'); readln(a,b,n); write(a,'/',b,'='); write(a div b); write('.'); a:=a mod b; for i:=1 to n do begin c:=a*10 div b; a:=10*a mod b; write(c); end; end. 5、 设计一个程序,当键入一个正整数 N(1≤N≤100)时,输出 N!的精确表示法。 (测试数据: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;

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

第 42 页

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

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

第 43 页

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、

排列与组合程序设计试题
(有关排列与组合的基本理论和公式: 加法原理:做一件事,完成它可以有 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; 全排列公式 Pn ? n !
n

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

第 44 页

选排列公式 Pn ? n(n ? 1)(n ? 2)? (n ? m ? 1) ?
m

n! m m m 、 Pn ? Cn ?Pm (n ? m)!

圆排列:n 个不同元素不分首位围成一个圆圈达到圆排列,则排列数为:

n! ? (n ? 1)! n

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

加法原理、乘法原理、排列、组合练习: 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 的五本书需要摆放在书架上,问有多少种不同的摆放方案数。 (提示:此题为全排列,故摆放方案总数为 P ? 5! ? 120 中。也可以按乘法原理思考,即摆放第 5
5

一本书有 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 ?
3

5? 4? 3 =10) 3!

五种不同颜色的珠子串成一串,问有多少种不同的方法。 (提示:此题属于圆排列问题,答案为(5-1) !=24) 6. 把两个红球、两个蓝球、三个黄球摆放在球架上,问有多少种方案。 (提示:摆放方案总数为(2+2+3) !种,但是两个红球一样,所以要除以 2! ,同理两个蓝球, 5. 除以 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。由此我们发现,每一个排列方式总是在其前 一个排列的基础上通过顺序逆转而得到。由此我们得到给定一个排列 P1P2P3??Pn 之后生成下 一个排列的算法如下: S1:求满足关系式 P(J-1)<P(J)的 J 的最大值,记为 I; S2:求满足关系式 P(K)>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;

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

第 45 页

(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]<plan[i-1]) do dec(i); end; procedure findj; begin j:=n; while plan[j]<plan[i-1] do dec(j); end; 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); 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

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

第 46 页

(6)1,4,5 (7)2,3,4 (8)2,3,5 (9)2,4,5 (10)3,4,5 从上面的组合方案可以看出:每一次的方案数都是在前一方案的基础上进行的。具体操作如下: S1:每次都先让最后的元素增加 1,直到增加到 N 为止(如上例中的(1) (3)方案,最后 (2) 一个元素的变化为由 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; until i=0; writeln('total ways=',total); end. 3、 任意输入 n 个正整数,编程给出这 n 个正整数的全排列。 (数据测试:n=5,这 5 个数分别为 2、7、9、3、1) program e; const maxn=10; var plan:array[1..maxn] of byte; m:array[1..maxn] of integer; i,j,n,total:integer; procedure print;

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

第 47 页

begin inc(total); write('(',total:5,'):'); for i:=1 to n do write(m[plan[i]]:5); writeln; end; procedure findi; begin i:=n; while(i>1)and(plan[i]<plan[i-1]) do dec(i); end; procedure findj; begin j:=n; while plan[j]<plan[i-1] do dec(j); end; 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); writeln('input ',n,' integer number:'); for i:=1 to n do read(m[i]); 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); end. 4、 选排列算法。有 N 本不同的书摆放在书架上,设其编号分别为 1、2、3、??、N,现要从其中取 出 R 本书摆放在另一个书架上,编程求解这 R 本书的不同摆放方案和摆放方案总数。 (算法分析:此问题的实质即求 N 个元素中取出 R 个元素的选排列。我们可以先求出从 N 个元素 中取出 R 个元素的组合方案,每求出一种组合方案后,马上求出这种组合方案的全排列即可) (测试数据:N=5,R=3;共 5×4×3 种选排列方案) program e; const maxn=10; var plan:array[1..maxn] of byte; p,z:array[1..maxn] of integer; i,j,k,n,r,total:integer; procedure print; begin inc(total); write('(',total:5,'):'); for k:=1 to r do write(p[plan[k]]:5); writeln;

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

第 48 页

end; procedure findi; begin i:=r; while(i>1)and(plan[i]<plan[i-1]) do dec(i); end; procedure findj; begin j:=r; while plan[j]<plan[i-1] do dec(j); end; procedure change; var k,h:integer; begin k:=plan[i-1]; plan[i-1]:=plan[j]; plan[j]:=k; for k:=i to ((r+i) div 2) do begin h:=plan[k]; plan[k]:=plan[r+i-k]; plan[r+i-k]:=h; end; end; procedure pailie; begin for i:=1 to r do begin plan[i]:=i; p[i]:=z[i]; end; print; repeat findi; if i>1 then begin findj; change; print; end; until i<=1; end; begin writeln; write('please input n and r:'); readln(n,r); total:=0; for i:=1 to r do z[i]:=i; pailie; repeat i:=r; while (i>0)and(z[i]=n+i-r) do dec(i); if i>0 then begin inc(z[i]); for j:=i+1 to r do z[j]:=z[j-1]+1; pailie; end; until i=0; writeln('total ways=',total); end. 5、 把小于等于整数 N 的所有合数重新排列,使每对相邻的数都有大于或等于 2 的公约数。比如说,N =9 时,4、8、6、9 就是一种合乎规则的排列。编一个程序,输入 N 后完成上述工作,并尽量使 排列有一定的“规律性” 。 (算法分析:先用素数子函数找出小于 N 的所有合数,按照顺序存入一个数组中,然后参照上面的 第 3 题即可求得这些合数的全排列,在每个全排列中判断是否合符题意的规则即可求得解答) program e; const maxn=10; var

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

第 49 页

plan:array[1..maxn] of byte; m:array[1..maxn] of integer; i,j,k,n:integer; function prime(x:longint):boolean; var j,y:longint; flag:boolean; begin y:=trunc(sqrt(x)); flag:=true; for j:=2 to y do if (x mod j = 0) then begin flag:=false; break; end; if x<2 then flag:=false; if flag=true then prime:=true else prime:=false; end; function gls(x,y:longint):longint; var a,b,t:longint; begin if x>y then begin a:=x; b:=y; end else begin a:=y; b:=x; end; repeat if (a mod b=0) then begin gls:=b; exit; end else begin t:=a mod b; a:=b; b:=t; end; until b=1; gls:=1; end; procedure guize; begin for i:=1 to n-1 do if gls(m[plan[i]],m[plan[i+1]])=1 then exit; for i:=1 to n do write(m[plan[i]]:4); writeln; end; procedure findi; begin i:=n; while(i>1)and(plan[i]<plan[i-1]) do dec(i); end; procedure findj; begin j:=n; while plan[j]<plan[i-1] do dec(j); end; 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(k); n:=0;

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

第 50 页

for j:=4 to k do if prime(j)=false then begin inc(n); m[n]:=j; end; for i:=1 to n do plan[i]:=i; guize; repeat findi; if i>1 then begin findj; change; guize; end; until i<=1; end. 6、

用数学推理或逻辑推理能解决的程序设计试题
1、 猴子吃枣问题。猴子摘了一堆枣,第一天吃了一半,还嫌不过瘾又吃了一个;第二天又吃了剩下的 一半零一个;以后每天如此。到第十天,猴子一看只剩下一个了。问最初有多少个枣? (分析:从第十天的一个枣开始倒数往前推理,则第九天为(1+1)×2=4 个,…,答案:1534) program e; const n=10; var i,x:integer; begin writeln; x:=1; i:=1; while i<n do begin inc(i); x:=(x+1)*2; end; writeln(x); end. 2、 警察局抓了 A、B、C、D 四名偷窃嫌疑犯,其中有一个人是小偷。审问中 A 说: “我不是小偷。 ” B 说: 是小偷。 说: “C ”C “小偷肯定是 D。 说: 在冤枉人。 ”D “C ”现在已经知道四个人中三个人 的是真话,一人说的是假话,问到底谁是小偷? (分析:因为牵扯 C 的线索最多,故从 C 入手。假设 C 是小偷,则 ABD 均说真话,C 说假话符合题 意。所以 C 是小偷) 。 3、 任何一个整数的立方都可以写成一串连续奇数之和,这就是著名的尼科梅彻斯定理。 13=1;23=3+5;33=7+9+11;43=13+15+17+19??,给出 n,求 n3 是哪些奇数之和? (提示:找出 n 与最小的奇数 x 之间的关系式即可,x=(1+2+…+(n-1))+1,即 x=n(n-1)+1。 ) 4、 求[1,100]之间有奇数个不同因子的整数。 (1)共多少个?(2)最大的一个是? (★) (分析:只有平方数的因子个数为奇数个,其它的数的因子都是成对出现) (答案:①10; ②100; 程序略) 5、 有 52 张扑克牌,使它们全部正面朝上。从第 2 张牌开始,把凡是 2 的倍数位置上的牌翻成正面朝 下;接着从第 3 张牌开始,把凡是 3 的倍数位置上的牌正面朝上的翻成正面朝下,正面朝下的翻成 正面朝上;接着从第 4 张牌开始,把凡是 4 的倍数位置上的牌按此规律翻转;依此类推,直到第 1 张要翻的牌是第 52 张牌为止。统计最后有几张牌正面朝上,并打印出来。 (算法分析:如果这个数的因子(包括 1 和它本身)总数为奇数时,将是正面朝上的,否则将正 面朝下。如 9 号位置这张牌,1 把它朝上,3 把它朝下,9 把它朝上。仔细分析:任何一个数的 因子都是成对出现,如 6:1×6、2×3,所以它将正面朝下;只有平方数如 9、16 等,因为它有 一对因子相同,这样产生了奇数个因子,所以它将正面朝上。 ) 6、 回文数是指正读和反读都一样的正整数。例如,5,121 等都是回文数。求出[1,500]以内的回

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

第 51 页

文数数目。 (答案:58) (分析:所有一位数都是回文数, (共 9 个) ,只有 11、22、33、……等二位数是回文数(共 9 个) , 三位数中当百位与个位相同时则为回文数, 如有 101、 111、 等 121 (共 4×10 个=40 个) ) 7、 甲、乙、丙三人共有 384 本书,先由甲分给乙、丙,所给书数分别等于乙、丙已有的书数,再由乙 分给甲、丙,最后由丙分给甲、乙,分法同前,结果三人图书数相等。编程求甲、乙、丙三人原各 有书多少本? (分析:从最后数本数相等往前推理。答案:甲=208;乙=112;丙=64) 8、 有这样的一个六位数字 labcde,将其乘以 3 后变成 abcdel,编程求这个数。 (分析:只有 7 乘以 3 的个位为 1,因此 e=7,即有 1abcd7×3=abcd71,由于 1abcd7 的个位的 7 乘以 3 等于 21,即向十位进 2 后变为 abcd71 的十位 7,因此可推出 1abcd7 的 d 乘以 3 的个位 应该等于(7-2)=5,而只有 5 乘以 3 的个位为 5,所以有 d=5,即有 1abc57×3=abc571, 同理往前推有 c 乘以 3 的个位为(5-1)=4,因此有 c=8,即有 1ab857×3=ab8571,b 乘以 3 的个位为(8-2)=6,因此 b=2,即有 1a2857×3=a28571,a 乘以 3 的个位为(2-0)=2, 因此 a=4,即有 142857×3=428571,所以六位数 labcde 应该为 142857) program I_27; var i:longint; begin writeln; for i:=110000 to 199999 do if i*3=(i mod 100000)*10+1 then write(i:8); end. 9、 设 a、b、c、d 为四个不同的正整数,前 3 个数组成等比数列,后 3 个数组成等差数列,且 c+d= 44,求 a、b、c、d 这四个数各为多少? 2 2 2 (分析:根据条件设 a=t,b=tq,c=tq ,d=2tq -tq。由 c+d=44,代入求得 3tq -tq=44, 即 tq(3q-1)=44,由于 44 可分解为 1×44、2×22、4×11 三种,分别讨论:如当 3q-1=1 时,则 tq=44,求得 q=2/3,t=66,代入求得 c=88/3 与已知它们为正整数相矛盾,故排除; 同理讨论其它,最后得出答案:①(22、22、22、22) ;②(1、4、16、28) ) 10、雨水淋湿了算术书的一道题, 个数字只能看清楚 3 个, 8 第一个数字虽然看不清, 但可看出不是 1, 2 [□×(□3+□) =8□□9,其中□表示淋湿的数字,请您将这些数字找出来。 ] (分析:个位数平方后是 9 的只有 3 和 7,从左边看,这个数能因式分解,并且这个数平方后产生 的四位数的千位数是 8,因此从这些特征入手分别将 13、23、33……等代入,只有 93 的平方为 2 8649,并且 93=3×31,所以到此可知道此等式为[3×(23+8) =8649) ] 。 11、李先生岁数的平方与他的夫人的岁数之和是 1053, 而他的夫人岁数的平方与他的岁数之和是 873, 问李先生和他的夫人的岁数各是多少? 2 2 (分析:设李先生的岁数为 a,他的夫人的岁数为 b。根据已知条件有 a =1053-b;b =873-a。 估计他们的岁数均为几十岁,则 1053-b 的大概范围在 1000~1030 之间,而在此之间的平方数 只有 32,即 a=32,代入可求得 b=29,恰巧满足两个条件,所以李先生 32 岁,他夫人 29 岁) 12、口袋里放着 12 个球,其中 3 个是红色的,3 个是白色的,6 个是黑色的。从中任取 8 个球(取后 放回) ,共有多少种不同的取法? (分析:因为一共有 12 个球,取出 8 个球后剩下 4 个球,那么取 8 个球的方法和取 4 个球的方法 一样多。现在只有红、白、黑三种颜色的球,分别用 A、B、C 表示,即 A+B+C=4,且 A 的范 围是 0~3,B 的范围是 0~3,C 的范围是 0~6,按照一定的规律讨论:如 A=0,B=0,C=4 即 是一种取法,计作(0,0,4) ,同理有(0,1,3) (0,2,2)等,共有 13 种不同的取法)


更多相关文档:

(信息学奥赛辅导)程序设计试题汇编(答案10)

(信息学奥赛辅导)程序设计试题汇编(答案10)_从业资格考试_资格考试/认证_教育...(以下程序设计试题来自《全国青少年信息学奥林匹克联赛――培训习题与解答(中学) ...

信息学奥赛辅导C语言教程免费学习_C/C++_教学视频大全

课程概述 针对中学阶段信息学奥林匹克竞赛进行相关的辅导,课程中涉及程序语言、算法以及竞赛真题训练。 目录(共5章)第1章 顺序结构程序设计...

奥赛分析措施

(初中版)/青少年信息学奥林匹克竞赛培训教材》 6、 《Pascal 语言:数据结构与算法---信息学奥林匹克复赛阶段辅导 教材 》 7、 语言程序设计及其习题集》 《C ...

程序设计竞赛辅导

Pascal基础题100道合集(... 14页 免费 小学Pascal教程 90页 免费 信息学奥林...程序设计竞赛辅导一、算法设计方法(一)枚举法(Enumeration) 枚举法亦称穷举法,它...

2010信息学奥赛复赛练习

2010年初一信息学奥赛选拔... 2页 免费喜欢此文档的还喜欢 (信息学奥赛辅导)程序设计... 51页 免费 NOIP复赛冲刺资料集锦10 45页 免费 信息学奥赛题库 79页...

信息学奥赛基础知识

(信息学奥赛辅导)程序设计... 51页 免费 信息学奥赛题库 79页 1财富值 信息...下表展示的是最流行的一套扩展 ASCII 字符 集和编码: 2.计算机硬件基础知识 ...

算法在信息学奥赛中的运用2

信息学奥赛题库 79页 1财富值 算法在信息学奥赛中的应用... 34页 免费 (信息学奥赛辅导)程序设计... 51页 免费 必背经典算法(pascal) 10页 免费 信息学奥...

信息学(计算机)奥林匹克培训与素质教育

(信息学奥赛辅导)程序设计... 51页 免费 信息学奥赛题库 79页 1财富值 信息...先举办全国信息学(计算机)奥林匹克分区联赛, 联 赛分高中组,初中组进行, 以普...

2011安徽省信息学竞赛AHOI省选试题(中学组)

52页 免费 (信息学奥赛辅导)程序设计... 51页 免费如要投诉违规内容,请到百度...2011安徽省信息学竞赛AHOI省选试题(中学组)2011安徽省信息学竞赛AHOI省选试题(...

NOIP基本程序题集(解法)

NOIP历年初赛阅读程序题 暂无评价 7页 8财富值 浙江省西店中学NOIP初赛练......NOIP基本程序题集 47页 免费 (信息学奥赛辅导)程序设计... 51页 免费 NOIP复习...
更多相关标签:
中学生信息学奥赛试题 | 信息学奥赛辅导 | 信息学奥赛初赛试题 | 信息学奥赛试题 | 小学信息学奥赛试题 | 初中信息学奥赛试题 | 全国信息学奥赛试题 | 小学生信息学奥赛试题 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com