一. 工作安排问题 ( 25分 )
现有 N (N≤8) 件工作, 分别由 N 个人完成, 每人都完成一件,且只完成一件, 每人完成不同工作的时间不同. 试设计一种分配工作方案, 使完成 N 件工作所需的总时间最少.
原始数据由文本文件 EXAM1.TXT 给出, 其格式如下:
第 1 行: 工作任务数(N)
第 2 -- N+1 行: 第 i+1 行为第 i 个人完成各件工作所需的时间. 以上各数均为不超过 1000 的正整数.
计算结果可直接在屏幕上输出: 第一行为工作分配方案, 共 N 组, 每组数据的形式为 a-b, 其中 a 为工作人员编号, b 为他应完成的工作序号.
例: 设 EXAM1.TXT 的数据为:
4
2 15 13 4
10 4 14 15
9 14 16 13
7 8 11 9
对此, 一个正确的输出可以是
1-4, 2-2, 3-1, 4-3
TOTAL=28
{ 参考程序, 生成排列部分 }
program coi96_1; { Writed by Li xuewe}
const nn=20;
type row=array [1..20] of shortint;
var p: row;
n,i: integer; num:longint;
procedure wrtperm(n:integer; var s:row);
var i:integer;
begin
for i:=1 to n do write(s[i]:3);
writeln;
end;
procedure perm(n:integer; var p:row; var i:integer);
var j,j1,j2,t,m:integer;
begin
i:=n;
repeat dec(i) until (p[i]<p[i+1]) or (i<1);
if i>0 then
begin
j:=i+1;
for t:=i+1 to n do
if p[i]<p[t] then j:=t;
m:=p[i]; p[i]:=p[j]; p[j]:=m;
t:=(n-i) div 2;
for j:=1 to t do
begin
j1:=i+j; j2:=n-j+1; m:=p[j1]; p[j1]:=p[j2]; p[j2]:=m;
end;
end;
end;
begin {main}
writeln('输入N:(<=20)'); readln(n);
num:=1;
for i:=1 to n do p[i]:=i;
i:=1;
while i>0 do
begin
wrtperm(n,p); perm(n,p,i);
if i>0 then inc(num);
end;
writeln('num=',num);
end.
{其余部分由读者完成}
二. 圆盘问题 ( 35分 )
从左向右依次安放 4 根细柱 A,B,C,D. 在 A 上套有 N (N≤20) 个直径相同的圆盘, 从下到上依次用连续的小写字母 a,b,c,...编号, 将这些圆盘经过 B, C 单向地移入 D (即不允许从右向左移动). 圆盘可在 B,C 中暂存. 从键盘输入 N, 及前 N 个小写字母的一个排列, 它表示最后在 D 盘上形成的一个从下到上的圆盘序列. 请用文本文件 ANS2.TXT 输出形成这一排列的操作过程.
该文件的每一行为一个形如 "k M L" 的字母序列, 其中 k 为圆盘编号, M 为 k 盘原先的柱号, L 为新柱号. 或者直接在屏幕上输出"No", 表示不能生成这种排列.
例: ┃ ┃ ┃ ┃
键盘输入: ┃ ┃ ┃ ┃
3 d ━╋━ ┃ ┃ ┃
acb c ━╋━ ┃ ┃ ┃
则一个正确的输出文件 b ━╋━ ┃ ┃ ┃
可以是: a ━╋━ ┃ ┃ ┃
c A B ━━┻━━━┻━━━┻━━━┻━
b A C A B C D
a A D
b C D
c B D
参考程序:(TJCOI96.5_2)
program coi96_2; { write by li Xuewu }
var
ga,gb,gc,gd,trn:array [0..15] of byte;
fd:array [0..15] of char;
resl:array [1..200] of string[6];
fname:string[20];
text2:text;
i,n,kz,ks,topa1,topb1,topc1,topd1,temp:byte;
procedure result(topa,topb,topc:byte;var ks:byte);
var i:byte;
begin
if (topa=0)and(topb=0)and(topc=0) then
begin
writeln('input filename for output:');
readln(fname);
assign(text2,fname); rewrite(text2);
for i:=1 to ks do writeln(text2,resl[i]);
close(text2);
for i:=1 to ks do writeln(resl[i]);
halt(1);
end;
end;
procedure move1(var topa,topb,topc,topd,ks1:byte);
var t,i:byte;
begin
repeat
t:=0;
if ga[topa]=succ(gd[topd]) then
begin
t:=t+1; ks1:=ks1+1;
resl[ks1]:=chr(trn[ga[topa]]+ord('a')-1)+' A D';
topd:=topd+1; gd[topd]:=ga[topa]; topa:=topa-1;
end;
if gb[topb]=succ(gd[topd]) then
begin
t:=t+1; ks1:=ks1+1;
resl[ks1]:=chr(trn[gb[topb]]+ord('a')-1)+' B D';
topd:=topd+1; gd[topd]:=gb[topb]; topb:=topb-1;
end;
if gc[topc]=succ(gd[topd]) then
begin
t:=t+1; ks1:=ks1+1;
resl[ks1]:=chr(trn[gc[topc]]+ord('a')-1)+' C D';
topd:=topd+1; gd[topd]:=gc[topc]; topc:=topc-1;
end;
result(topa,topb,topc,ks1);
until t=0;
end;
procedure move2(topa,topb,topc,topd:byte;var ks:byte);
var kp,ks1:byte;
begin {1}
kz:=kz+1;
result(topa,topb,topc,ks);
move1(topa,topb,topc,topd,ks);
for kp:=1 to 3 do
begin {2}
case kp of
1: if(gb[topb]<gc[topc])and(topb>0) then
begin
ks1:=ks+1;
resl[ks1]:=chr(trn[gb[topb]]+ord('a')-1)+' B C';
topc:=topc+1; temp:=gb[topb]; gc[topc]:=temp; topb:=topb-1;
move2(topa,topb,topc,topd,ks1);
topb:=topb+1; gb[topb]:=temp; topc:=topc-1;
end;
2: if(ga[topa]<gc[topc])and(topa>0) then
begin
ks1:=ks+1;
resl[ks1]:=chr(trn[ga[topa]]+ord('a')-1)+' A C';
topc:=topc+1; temp:=ga[topa]; gc[topc]:=temp; topa:=topa-1;
move2(topa,topb,topc,topd,ks1);
topa:=topa+1; ga[topa]:=temp; topc:=topc-1;
end;
3: if(topa>0) then
begin
ks1:=ks+1;
resl[ks1]:=chr(trn[ga[topa]]+ord('a')-1)+' A B';
topb:=topb+1; temp:=ga[topa]; gb[topb]:=temp; topa:=topa-1;
move2(topa,topb,topc,topd,ks1);
topa:=topa+1; ga[topa]:=temp; topb:=topb-1;
end;
end;
end;{2}
if kz=1 then
begin writeln('No solution!'); halt(1); end;
kz:=kz-1
end; {1}
begin{main}
writeln('input disk number:');
readln(n);
writeln('input object column:(1-n char)');
for i:=1 to n do read(fd[i]);
readln;
for i:=1 to n do trn[i]:=ord(fd[i])-ord('a')+1;
for i:=1 to n do ga[trn[i]]:=i;
for i:=1 to n do write(trn[i]:2); writeln;
for i:=1 to n do write(ga[i]:2); writeln;
kz:=0; ks:=0;
topa1:=n; topb1:=0; topc1:=0; topd1:=0;
ga[0]:=0; gb[0]:=0; gc[0]:=100; gd[0]:=0;
move2(topa1,topb1,topc1,topd1,ks);
end.
三. 移球问题 ( 40分 )
给定 N 个盒子, 5≤N≤100, 第 i 个盒子装入 bi 个球, bi≥0,i=1,...,N, 球的总数为 M=b1+b2+...+bN, 4≤M≤10000. 在两个非空的盒子中各取一个球放入另外的一个盒子中, 称为一次操作. 现要求使用最少的操作次数, 将所有的球并入到一个盒子中. 请编写程序给出相应的操作方案, 及总操作次数.
说明:
(1) 按所给条件, 上述问题必有解,无须判断可解性.
(2) 原始数据由名为 EXAM3.TXT 的文本文件给出. 格式如下:
第一行: 一个整数, 为盒子个数(N).
第二行: 用空格分隔的 N 个整数, 为各盒子的小球个数(bi).
所给的数据都是正确的.
(3) 用文本文件输出计算结果 ( 文件名: ANS3.TXT ):
格式: 在前面的若干行中, 每一行为一组相同的操作. 例如:连续从1#,2#盒各取 5 个小球, 放入 3# 盒, 可写为: 1 2 3 5 , 即该行的四个数据依次为:
第 1 个盒号 第 2 个盒号 目标盒号 从第 1 个盒中移出的球数
最后一行有四个数据: 球的总数(M), 总操作次数 , 0, 0(结束标志)
(4) 测试时, 若实际操作次数比最少次数多 1-3 次, 可适当给分, 超过 3 次或操作过程中出现非法数据时, 不给分.
例: 设 EXAM3.TXT 的数据为
5
3 4 5 6 0
则一个正确的输出文件为:
2 3 4 3
1 2 4 1
1 3 4 2
18 6 0 0
{解答略}
|
网友评论：（只显示最新10条。评论内容只代表网友观点，与本站立场无关！）