2012年宁波市第27届中小学程序设计竞赛 初中组 初赛试题
min:=av[i];
for j:=1 to i-1 do
if min>(dp[j]+dp[i-j]) then min:=dp[j]+dp[i-j] end
else begin
min:=30000;
for j:=1 to i-1 do
if min>(dp[j]+dp[i-j]) then min:=dp[j]+dp[i-j] end;
dp[i]:=min; end;
writeln(dp[n]); end.
输入：16 32 45 61 76 89 104 121 133 159 输出：_______
20
四、完善程序 (前4空，每空2.5分；后6空，每空3分，共28分)
1．（冗余关系）有一篇作文，第一行表示作文中的句子数目n和人物数目m，下面n句（每句一行）描述人物关系的句子，描述了m个人的关系(n<=1000)。每条句子的格式为：X Y。它的意思是：X认识Y， Y也认识X。现在要你求出文中冗余关系的数目。注意: 假如A认识B，B认识C，则A也认识C。冗余关系的定义是指：即使没有这条关系，原图的所有关系照样成立。
例如输入数据为： 3 4 1 4 1 3 4 3
则输出为：1
输出结果说明：共有1个句子冗余（最后一句）。因为4和3的相识关系可从前面两句推出。请完善下面程序。
const maxnm=1000; var
n,m,i,j,k,t,tot,tmp:integer;
a:array[1..maxnm] of integer;
begin
readln(n,m); tot:=0;
for i:=1 to m do (1) ; for k:=1 to n do begin readln(i,j);
if a[i]=a[j] then
(2)
- 6 -
2012年宁波市第27届中小学程序设计竞赛 初中组 初赛试题
else begin
if a[i]
for t:=1 to m do
if a[t]=tmp then (3) ; end
else begin tmp:=a[i];
for t:=1 to m do
if a[t]=tmp then (4) ; end; end; end;
writeln(tot); end.
2. (统计数字群个数) 某矩阵由数字0到9组成，其中0表示隔板（无法通过），数字
1到9表示可以通过。一个数字群为：从某个数字非0数字出发，沿着可通行数字所能到达的所有数字（行走方向可以是上下左右），这些相互能到达的数字即组成同一数字群。给出矩阵，统计该矩阵包含的数字群的个数。
输入数据第一行表示矩阵的行数m和列数n，接下来m行，每行有连续的n个字符，每个字符均为数字0到9。输出数据只有一个，即该矩阵中包含的数字群个数。
例如输入数据如下： 3 8 01234000 10030008 79000600 则输出数据如下： 4
请完善下面程序。
const maxm=50; maxn=80; var
m,n,i,j,k,tot:integer;
a:array[1..maxm,1..maxn] of 0..1; b:array[1..4000,1..2] of integer; st:string;
procedure bfs(p,q:integer); var x,y,f,t:integer; begin
f:=1;t:=1;
b[t,1]:=p;b[t,2]:=q;
- 7 -
第1个群:5个数字 0 1 2 3 4 0 0 0 第2个群: 3个数字
1 0 0 3 0 0 0 8 0 7 9 0 0 0 6 0 0 0 第4个群: 1个数字6
第3个群: 1个数字8
2012年宁波市第27届中小学程序设计竞赛 初中组 初赛试题
a[p,q]:=0; inc(t); repeat
for k:=1 to 4 do begin
if k=1 then begin x:=p+1;y:=q; end; if k=2 then begin x:=p;y:=q+1; end; if k=3 then begin x:=p-1;y:=q; end; if k=4 then begin x:=p;y:=q-1; end;
if (x>0) and (x<=m) and (y>0) and (y<=n) and (a[x,y]=1) then begin b[t,1]:=x; b[t,2]:=y;
(5) inc(t); end; end;
(6) ;
p:=b[f,1];q:=b[f,2]; (7) ; end;
begin
readln(m,n);
fillchar(a,sizeof(a),0); for i:=1 to m do begin readln(st);
for j:=1 to n do
if (8) then a[i,j]:=1 end; tot:=0;
for i:=1 to m do for j:=1 to n do
if (9) then begin bfs(i,j);
(10) ; end; writeln(tot); end.
- 8 -
