信息学奥赛-入门级 题库
翻硬币
题目描述:
一摞硬币共有m枚,每一枚都是正面朝上。取下最上面的一枚硬币,将它翻面后放回原处。然后取下最上面的2枚硬币,将他们一起翻面后再放回原处。再取3枚,取4枚……直至m枚。然后再从这摞硬币最上面的一枚开始,重复刚才的做法。这样一直做下去,直到这摞硬币中的每一枚又都是正面朝上为止。例如,m为1时,翻两次即可。m为2时,翻3次即可;m为3时,翻9次即可;m为4时,翻11次即可;m为5时,翻24次即可;…;m为30时,翻899次即可;…
输 入:
仅有的一个数字是这摞硬币的枚数m,0<m<1000。
输 出:
为了使这摞硬币中的每一枚又都是正面朝上所必需翻的次数。
输入样例:
30
输出样例:
899
程 序:
program Programl;
var m:integer;
function solve (m:integer):integer;
vat i,t,d:integer;
flag:boolean;
begin
if (m=1)then
so1ve:= ①
else begin
d:=2*m+1;
t:= 2;
i:= 1;
flag:=False;
repeat
if (t=1)then
begin
solve:= ②
flag:=True;
end
else if ( ③ )then
begin
solve:=i*m-1;
flag:=True;
end
else
t:= ④ ;
i:=i+1;
until flag;
end
end;
begin
read (m);
if ((m>0) and (m<1000)) then
writeln ( ⑤ );
end.
在 a,b,c,d,e,f 六件物品中,按下面的条件能选出的物品是:
(1)a,b 两样至少有一样
(2)a,d 不能同时取
(3)a,e,f 中必须有 2 样
(4)b,c 要么都选,要么都不选
(5)c,d 两样中选一样
(6)若 d 不选,则 e 也不选
平面上有三条平行直线,每条直线上分别有 7,5,6 个点,且不同直线上三个点都不在同一条直线上。问用这些点为顶点,能组成多少个不同三角形?
PROGRAM CHU7_1;
FUNCTION FUN(X:INTEGER):INTEGER; BEGIN
IF(X=0)OR(X=1)THEN FUN:=3
ELSE FUN:=X-FUN(X-2)
END; BEGIN
WRITELN(FUN(9)); READLN;
END.
输出:
PROGRAM CHU7_2;
VAR I,J,F:INTEGER;
A:ARRAY[1..8]OF INTEGER;
BEGIN
FOR I:=1 TO 8 DO BEGIN
F:=I MOD 2;
IF F=0 THEN A[I]:=0
ELSE A[I]:=1; FOR J:=1 TO I DO
IF F=0 THEN A[I]:=A[I]+J ELSE A[I]:=A[I]*J
END;
FOR I:=1 TO 8 DO WRITE(A[I]:5);
END.
输出
PROGRAM CHU7_3;
VAR P,Q,S,T:INTEGER; BEGIN
READLN(P);
FOR Q:=P+1 TO 2*P DO BEGIN
T:=0; S:=(P*Q)MOD(Q-P); IF S=0 THEN
BEGIN
T:=P+Q+(P*Q)DIV(Q-P); WRITE(T:4);
END;
END;
READLN END.
输入:12 输出:
PRGORAM CHU7_4;
VAR N,K,I:INTEGER; A:ARRAY[1..40]OF INTEGER;
PROCEDURE FIND(X:INTEGER); VAR S,I1,J1:INTEGER;
P:BOOLEAN;
BEGIN
I1:=0; P:=TRUE; WHILE P DO
BEGIN
I1:=I1+1; S:=0;
FOR J1:=1 TO N DO
IF A[J1]>A[I1]THEN S:=S+1; IF(S=X-1)THEN
BEGIN
WRITELN(A[I1]); P:=FALSE
END; END
END;
BEGIN
READLN(N,K); FOR I:=1 TO N DO
READ(A[I]); FIND(K); FIND(N-K);
END.
输入:10 4
12 34 5 65 67 87 7 90 120 13
输出:
在 A,B 两个城市之间设有 N 个路站(如下图中的 S1,且 N<100),城市与路站之间、路站和路站之间各有若干条路段(各路段数≤20,且每条路段上的距离均为一个整数)。
A,B 的一条通路是指:从 A 出发,可经过任一路段到达 S1,再从 S1 出发经过任一路段,…最后到达 B。通路上路段距离之和称为通路距离(最大距离≤ 1000)。当所有的路段距离给出之后,求出所有不同距离的通路个数(相同距离仅记一次)。
例如:下图所示是当 N=1 时的情况:

从 A 到 B 的通路条数为 6,但因其中通路 5+5=4+6,所以满足条件的不同距离的通路条数为 5。
算法说明:本题采用穷举算法。
数据结构:N:记录 A,B 间路站的个数
数组 D[I,0]记录第 I-1 到第 I 路站间路段的个数D[I,1],D[I,2],…记录每个路段距离
数组 G 记录可取到的距离
程 序 清 单 :

级数求和
[问题描述]:
已知:Sn= 1+1/2+1/3+…+1/n。显然对于任意一个整数K,当n足够大的时候,Sn大于K。
现给出一个整数K(1<=k<=15),要求计算出一个最小的n;使得Sn>K。
[输入]
键盘输入 k
[输出]
屏幕输出 n
[输入输出样例]
输人:1
输出:2
选数
[问题描述]:
已知 n 个整数 x1,x2,…,xn,以及一个整数 k(k<n)。从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。例如当 n=4,k=3,4 个整数分别为 3,7,12,19 时,可得全部的组合与它们的和为:
3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=34。
现在,要求你计算出和为素数共有多少种。
例如上例,只有一种的和为素数:3+7+19=29)。
[输入]:
键盘输入,格式为:
n , k (1<=n<=20,k<n)
x1,x2,…,xn (1<=xi<=5000000)
[输出]:
屏幕输出,格式为:
一个整数(满足条件的种数)。
[输入输出样例]:
输入:
4 3
3 7 12 19
输出:
1
产生数
[问题描述]:
给出一个整数 n(n<10^30) 和 k 个变换规则(k<=15)。
规则:
一位数可变换成另一个一位数:
规则的右部不能为零。
例如:n=234。有规则(k=2):
2-> 5
3-> 6
上面的整数 234 经过变换后可能产生出的整数为(包括原数):
234
534
264
564
共 4 种不同的产生数
问题:
给出一个整数 n 和 k 个规则。
求出:
经过任意次的变换(0次或多次),能产生出多少个不同整数。
仅要求输出个数。
[输入]:
键盘输人,格式为:
n k
x1 y1
x2 y2
... ...
xn yn
[输出]:
屏幕输出,格式为:
一个整数(满足条件的个数):
[输入输出样例]:
输入:
234 2
2 5
3 6
输出:
4
过河卒
[问题描述]:
如图,A 点有一个过河卒,需要走到目标 B 点。卒行走规则:可以向下、或者向右。同时在棋盘上的任一点有一个对方的马(如上图的C点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 C 点上的马可以控制 9 个点(图中的P1,P2 … P8 和 C)。卒不能通过对方马的控制点。

棋盘用坐标表示,A 点(0,0)、B 点(n,m)(n,m 为不超过 20 的整数,并由键盘输入),同样马的位置坐标是需要给出的(约定: C<>A,同时C<>B)。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。
[输入]:
键盘输入
B点的坐标(n,m)以及对方马的坐标(X,Y){不用盘错}
[输出]:
屏幕输出
一个整数(路径的条数)。
[输入输出样例]:
输入:
6 6 3 2
输出:
17
如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢,请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。

将N个红球和M个黄球排成一行。例如:N=2,M=3可得到以下6种排法:
红红黄黄黄 红黄红黄黄 红黄黄红黄 黄红红黄黄 黄红黄红黄 黄黄黄红红
问题:当N=4,M=3时有多少种不同排法?(不用列出每种排法)
program exp1;
var i,j,k,n,,L0,L1,LK:Integer;
a :array [0..20] of integer;
begin
readln(n,k);
for i:=0 to n-1 do a[i]:=i+1;
a[n]:=a[n-1];L0:=n-1; Lk:=n-1;
for I:=1 to n-1 do
begin
L1:=L0-k; if (l1<0) then L1:=L1+n;
If (l1=Lk) then begin
A[L0]:=a[n]; Lk:=Lk-1; a[n]:=a[Lk]; l0:=lk
End;
Else
Begin
A[l0]:=a[l1];l0:=l1;
End;
End;
A[L0]:=a[n];
For I:=0 to n-1 do write(a[I]:40;
Writeln;
End.
输入:10 4
输出:
program exp2;
var n,jr,jw,jb:integer;
ch1:char;
ch:array[1..20]d char;
begin
readln(n);
for i:=1 to n do read(ch[i]):
jr:=1;jwz=n;jb:=n;:
while (jr<=jw)do
begin
if(ch[jw]='R')
then begin
ch1:=Ch[jr];Ch[jr]:=ch[jw];ch[jw]:=ch1:jr:=jr+13
end
else if ch[jw]='W'
then jw:=jw-1
else begin
ch1:=ch[jw];ch[jw]:=ch[jb];ch[jb]:=ch1;jw:=jw-1;jb:=jb-1;
end
end;
for i:=1 to n do write(ch[i]);
writeln;
end.
输入:10
RBRBWWRBBR
输出:
Pmgram exp3;
Var I,j,p,n,q,s:integer;
a :array[1..20]of integer;
begin
readln(p,n,q);j :=21;
while (n>0)do
begin
j:=j-1;a[j]:=n mod 10;n:=n div 10;
end;
s:=0;
for i:=j t0 20 do s:=s*p+a[i];
writeln(s);j :=21;
while (s>O)do
begin j:=j-1;a[j]:=s mod q;s:=s div q;end;
for i:=j to 20 do write(a[i]);readln;
end.
输入:7 3051 8
输出:
问题描述:将n个整数分成k组(k≤n,要求每组不能为空),显然这k个部分均可得到一个各自的和s1,s2,……sk,定义整数P为:

问题求解:求出一种分法,使P为最小(若有多种方案仅记一种〉
程序说明:
数组:a[1],a[2],...A[N]存放原数
s[1],s[2],...,s[K]存放每个部分的和
b[1],b[2],...,b[N]穷举用临时空间
d[1],d[2],...,d[N]存放最佳方案
程序:


问题描述:工厂在每天的生产中,需要一定数量的零件,同时也可以知道每天生产一个零件的生产单价。在N天的生产中,当天生产的零件可以满足当天的需要,若当天用不完,可以放到下一天去使用,但要收取每个零件的保管费,不同的天收取的费用也不相同。
问题求解:求得一个N天的生产计划(即N天中每天应生产零件个数),使总的费用最少。
输入:N(天数N<=29)
每天的需求量(N个整数)
每天生产零件的单价(N个整数)
每天保管零件的单价(N个整数)
输出:每天的生产零件个数(N个整数)
例如:当N=3时,其需要量与费用如下:

生产计划的安排可以有许多方案,如下面的三种:

程序说明:
b[n]:存放每天的需求量
c[n]:每天生产零件的单价
d[n]:每天保管零件的单价
e[n]:生产计划
程序:


