Trong một hội nghị khoa học có n nhà khoa học (KH) tổ chức thư giãn dưới hình thức sau. Họ đặt
một máy tính trong căn phòng hẹp, ngoài máy ra chỉ có thể chứa thêm 1 người,
màn hình máy tính hiện số 0. Sau đó mỗi nhà khoa học buộc phải thực hiện n thao
tác loại 1 và n thao tác loại 2 đan xen nhau, trong đó thao tác đầu tiên phải
là loại 1.
Tag: gia sư tin học, gia sư tin học tại nhà
|
Thao tác loại 1: Đọc
|
Thao tác loại 2: Ghi
|
|
s
Vào phòng;
s
Đọc và ghi nhớ số trên màn hình;
s
Ra khỏi phòng.
|
s
Vào phòng;
s
Lấy số nhớ trong đầu cộng thêm 1 và
hiển thị kết quả trên màn hình;
s
Ra khỏi phòng.
|
Khi hiển thị số mới trên màn
hình thì số cũ trên màn hình tự động bị xóa và người thực hiện thao tác loại 2
cũng quên luôn số đã nhớ.
Cho trước các giá trị n và m. Hãy bố trí một lịch thực hiện để các
nhà khoa học hoàn thành trọn vẹn cuộc chơi theo đúng yêu cầu và số cuối cùng
hiển thị trên màn hình là m.
Dữ liệu vào: Tệp văn bản KH.INP chứa 2 số
n và m trên một dòng cách nhau qua dấu cách.
Dữ liệu ra: Tệp văn bản KH.OUT chứa một
lịch thực hiện gồm một dãy tuần tự các dòng lệnh thuộc một trong hai dạng sau:
Dạng thứ nhất gồm hai số tự nhiên ghi cách nhau qua dấu cách, i t
cho biết nhà khoa học i thực hiện thao tác t; i Î {1,2,…,n}; t Î
{1,2}.
Dạng thứ hai gồm 4 số tự nhiên ghi cách nhau qua dấu cách, i t1
t2 k cho biết nhà khoa học i thực hiện k lần liên tiếp các thao tác
t1 và t2 đan xen nhau; i Î {1,2,…,n}; t Î
{1,2}; k > 0.
Nếu không có cách nào bố trí lịch thì ghi duy nhất một số 0.
Thí dụ,
|
KH.INP
|
KH.OUT
|
Ý nghĩa
|
|
3 4
|
1 1
3 1 2 3
1 2
2 1
1 1 2 2
2 2
2 1 2 2
|
Có 3 nhà khoa học tham
gia trò chơi thư giãn với nhiệm vụ sinh ra kết quả trên màn hình (MH) là số
4. Lịch thực hiện sẽ như sau:
Người số 1: Đọc. MH = 0.
Đầu(1) = 0.
Người số 3: (Đọc; Ghi) 3
lần. MH = 3.
Người số 1: Ghi. MH = Đầu(1)+1 = 0+1 = 1.
Người số 2: Đọc. Đầu(2) =
1, MH = 1.
Người số 1: (Đọc; Ghi) 2
lần. MH = 3.
Người số 2 Ghi. MH =
Đầu(2)+1 = 1+1 = 2.
Người số 2 (Đọc;Ghi) 2
lần. MH = 2+2 = 4.
Chú thích: Đầu(i) - số
nhớ trong đầu nhà khoa học thứ i.
|
Thuật toán
Ta sẽ chỉ ra rằng với mọi n ³ 2 và mọi m trong khoảng
2..n2 luôn luôn có một lịch thỏa yêu cầu của đầu bài (ta gọi là lịch hợp lệ) để màn hình (MH) đạt giá
trị m.
Sau khi mở tệp KH.INP và đọc hai giá trị n, m ta tiến hành
xếp lịch và ghi dần kết quả vào tệp KH.OUT mở sẵn. Trước hết ta nhận xét rằng
nếu một người thực hiện liên tiếp k lần một cặp thao tác (Đọc - Ghi, viết tắt
là ĐG), tức là sau 2k dòng lệnh
i 1
i 2
...
i 1
i 2
thì giá trị của MH được tăng thêm k đơn vị. Dãy 2k lệnh trên
có thể viết gộp lại thành một lệnh 4 thành phần là i 1
2 k.
Ta tính k = m div n
và r = m mod n, ta có m = k.n+r , 0 £ r < n, với ý nghĩa là để đạt được giá trị m trên
MH thì phải có k người thực hiện đầy đủ và liên tiếp n cặp thao tác ĐG, ngoài
ra phải có ít nhất một người thực hiện thêm r cặp thao tác ĐG. Do yêu cầu mỗi người buộc phải thực hiên n
thao tác Đ và n thao tác G, một lẽ tự nhiên, ta phải sử dụng 2 người ghi nhận
giá trị hiện có trên MH để khi cần sẽ trả lại giá trị đó (dĩ nhiên là phải cộng
thêm 1) nhằm đảm bảo cho các thao tác cần thiết được thực hiện liên tục. Xét 3 trường hợp sau đây.
Trường hợp 1: r = 0, tức là m = k.n. Ta cần k người thực hiện
liên tiếp n cặp thao tác ĐG. Tuy nhiên, do những người khác cũng phải thực hiện
đầy đủ n cặp thao tác ĐG cho mỗi người, nên ta chia các thao tác thành hai loại
là các thao tác vô ích là những thao
tác đến một thời điểm nào đó sẽ có một thao tác khác đặt lại giá trị cho MH.
Các thao tác còn lại được gọi là thao tác
có ích. Như vậy trường hợp này cần có k người thực hiện tổng cộng m = k.n
cặp thao tác có ích và mọi thao tác còn lại là vô ích. Lịch khi đó sẽ như sau.
1 1 - Người số 1 Đọc và nhớ số 0 trên màn hình.
Đầu(1) = 0.
i 1 2 n ; i =
k+1..n - Những người còn lại (mang mã số k+1..n) ĐG n lần vô ích.
1 2 - Người số 1 ghi số 1 lên màn hình (có ích), MH
= Đầu(1)+1 = 0 + 1 = 1.
1 1 2
n-1 - Người số 1 ĐG nốt n-1 lần có ích, MH = n.
i 1 2 n ; i
= 2..k
- Những người số 2..k ĐG n lần có ích, MH = n+(k-1).n = k.n = m.
Trường hợp 2: r ¹ 0 và k > 0. Ta có m = k.n+r, 0 < r < n, k > 0. Trường hợp này cần n-1 người
thực hiện các thao tác vô ích, 1 người thực hiện r cặp thao tác ĐG có ích và
cũng chính người đó phải thực hiện (n-r) cặp thao tác vô ích. Ta sử dụng 2
người , số 1 và số 2 như sau.
1 1 - Người số 1 Đọc và nhớ số 0. Đầu(1) = 0.
i 1 2 n ; i =
k+2..n - Những người mã số từ k+2 đến n ĐG n lần vô ích.
1 2 - Người số 1 Ghi 1 lên MH. MH = Đầu(1)+1 = 0 + 1 = 1.
2 1 - Người số 2 Đọc và nhớ số 1. Đầu(2) = 1.
1 1 2 n-r - Người số 1 ĐG n-r lần vô ích.
Tiếp đến là những thao tác có ích:
2 2 - Người số 2 Ghi số 2 lên MH, MH = Đầu(2)+1 = 1 + 1 =
2.
1 1 2 r-1 - Người số 1 ĐG nốt r-1 lần có ích, MH =
2+(r-1).
2 1 2 n-1 - Người số 2 ĐG nốt n-1 lần có ích, MH = 2+(r-1)+(n-1)
= n+r.
i 1 2 n ; i = 3..k+1 - Những người số 3..k+1 ĐG n lần có ích, MH = n+r+(k-1).n = k.n+r.
Trường hợp 3: r ¹ 0 và k = 0, do đó m = r ³ 2. Trường hợp này cần n-1
người thực hiện các thao tác vô ích, 1 người thực hiện r cặp thao tác ĐG có ích
và cũng chính người đó phải thực hiện (n-r) căp thao tác vô ích. Ta sử dụng 2
người , số 1 và số 2 như sau.
1 1 - Người số 1
Đọc và nhớ số 0 trên MH. Đầu(1) = 0.
i 1 2 n ; i = 3..n - Những người từ số 3 đến n ĐG n lần
vô ích.
2 1 2 n-1 - Người số 2
ĐG n-1 lần vô ích.
1 2 - Người số 1 Ghi số 1 lên MH. MH = Đầu(1)+1 = 0+1 =
1.
2 1 - Người số 2
Đọc số 1 trên MH. Đầu(2) = 1.
1 1 2 n-r+1 - Người số 1 ĐG n-r+1 lần vô ích.
2 2 - Người số 2 Ghi số 2 lên MH. MH = Đầu(2)+1 = 1+1 =
2.
1 1 2 r-2 - Người số 1 ĐG r-2 lần có ích, MH = 2 + (r-2) = r.
Phần dưới đây
trình bày cấu trúc dữ liệu và các thủ tục đọc và xếp lịch. Hai thủ tục phụ trợ Lenh2 và Lenh4
dùng để ghi một lệnh 2 tham biến dạng i t và lệnh 4 tham biến dạng i t1 t2
k vào output file g KH.OUT. Trong các chú thích dưới đây d[i] là số
trong đầu nhà KH thứ i, t[i] là số thao tác ĐG nhà KH i đã thực hiện, MH – màn
hình, kí hiệu MH = x cho biết ta không quan tâm đến giá trị của MH vì sớm muộn
giá trị này sẽ bị xóa.
uses crt;
const
fn = 'kh.inp'; gn = 'kh.out';
bl = #32; nl = #13#10; mn = 100;
{ bl – dấu cách; nl – xuống dòng }
type
mi1 = array[0..mn+1] of
integer;
var
f,g: text;
n, m, mh: integer;
d,t: mi1;
{ mh – Màn hình }
d[i] - so nho trong dau,
t[i] - con dem lenh cua
nguoi i }
procedure Doc;
begin
assign(f,fn); reset(f);
read(f,n,m); close(f);
end;
procedure Lenh2(i,tt: integer);
begin writeln(g,i,bl,tt); end;
procedure Lenh4(i,tt1,tt2,k: integer);
begin if k > 0 then writeln(g,i,bl,tt1,bl,tt2,bl,k); end;
procedure XepLich;
var k,r,i: integer;
begin
assign(g,gn); rewrite(g);
if (n < 2) or (m <
2) or (m > n*n) then
begin writeln(g,0);
close(g); exit; end;
k := m div n; { k nguoi
co ich }
r := m mod n; { va r thao
tac co ich }
if (r = 0) then
begin
Lenh2(1,1);
{MH=0,d[1]=0,t[1]=1}
for i := k+1 to n do
Lenh4(i,1,2,n);
{MH=x,t[i]=2n,i=k+1..n}
Lenh2(1,2); {MH=1}
Lenh4(1,1,2,n-1); {MH=n,t[1]=2n}
for i := 2 to k do Lenh4(i,1,2,n);
{ MH
=n+(k-1)n=kn=m,t[i]=2n,i=2..k}
close(g); exit;
end;
{ r > 0 }
if k > 0 then
begin { r,k > 0 }
Lenh2(1,1);
{MH=0,d[1]=0,t[1]=1}
{ Bo nhung nguoi vo ich
}
for i:=k+2 to n do
Lenh4(i,1,2,n);
{MH=x,t[i]=2n,i=k+2..n}
Lenh2(1,2); {1
Ghi;MH=1,t[1]=2}
Lenh2(2,1); {2
Doc;MH=1;d[2]=1,t[2]=1}
{ Cac thao tac vo ich
cua 1 }
Lenh4(1,1,2,n-r); {MH=x,t[1]=2+2(n-r)=2(n-r+1)}
{ Tu day la cac thao tac co ich }
Lenh2(2,2); {MH=2,t[2]=2}
Lenh4(1,1,2,r-1);
{MH=2+r-1,t[1]=2(n-r+1)+2(r-1)=2n}
Lenh4(2,1,2,n-1);{MH=2+r-1+n-1=n+r,t[2]=2n}
for i := 3 to k+1 do Lenh4(i,1,2,n);
{MH=n+r+(k-1)n=kn+r=m,t[i]=2n,i=3..k+1}
close(g); exit;
end;
{ k = 0, r > 0 }
Lenh2(1,1); {1
Doc,d[1]=0,t[1]=1}
{ Bo nhung nguoi vo ich }
for i:=3 to n do
Lenh4(i,1,2,n);{MH=x,t[i]=2n,i=3..n}
{ n-1 thao tac vo ich cua
2 }
Lenh4(2,1,2,n-1);{MH=x,t[2]=2(n-1)}
Lenh2(1,2); {1 Ghi,MH=1,t[1]=2}
Lenh2(2,1); {2
Doc,MH=1,d[2]=1,t[2]=2n-2+1=2n-1}
{ Cac thao tac vo ich cua 1 }
Lenh4(1,1,2,n-r+1);{MH=x,t[1]=2+2(n-r+1)=2(n-r+2)}
Lenh2(2,2); {MH=2,t[2]=2n}
Lenh4(1,1,2,r-2);{MH=2+r-2=r=m,t[1]=2(n-r+2)+2(r-2)=2n}
close(g);
end;
Bạn có thể viết
thêm thủ tục test để kiểm tra xem lịch đã xếp và ghi trong tệp KH.OUT có thỏa
các yêu cầu của đầu bài hay không. Thủ tục sử dụng các mảng sau đây. Mảng
d[1..n], d[i] là số nhớ trong đầu người số i. Mảng t[1..n], t[i] là số lần
người thứ i thực hiện các thao tác Đọc (1), Ghi (2). Do thao tác Đọc phải thực
hiện trước và hai thao tác Đọc - Ghi phải đan xen nên thời điểm sát trước thao
tác Đọc của người thứ i ta phải có t[i] là số
chẵn và thời điểm sát trước thao tác Ghi phải có t[i] là số lẻ. Mỗi lần đọc 1 dòng lệnh thủ tục
phải xét xem dòng lệnh đó chứa 2 hoặc 4 số. Thủ tục phải thực hiện các kiểm tra
sau đây.
Kiểm tra lệnh dạng i
v: 1 £ i £ n, v = 1 hoặc 2. Nếu v = 1 thì t[i] phải là số chẵn,
nếu v = 2 thì t[i] phải lẻ.
Kiểm tra lệnh dạng i
v1 v2 k: tương tự như trên.
Thực hiện lệnh i v: Nếu v = 1 (thao tác đọc) thì gán d[i] :=
MH; ngược lại, nếu v = 2 (ghi) thì gán MH := d[i] + 1. Trong cả hai trường hợp
đều tăng con đếm lệnh t[i] thêm 1 đơn vị.
Sau khi đọc xong tệp KH.OUT phải duyệt lại các con đếm để
đảm bảo rằng d[i] = 2.n với mọi i = 1..n. Cuối cùng kiểm tra xem MH = m?
procedure DocLenh(var i,t1,t2,k,v: integer);
begin
read(g,i,t1); v := 2;
if seekeoln(g) then exit;
readln(g,t2,k); v := 4;
end;
procedure XemLenh(i,t1,t2,k,KieuLenh: integer);
begin
if KieuLenh = 2 then
writeln(i,bl,t1)
else
writeln(i,bl,t1,bl,t2,bl,k);
end;
function Lenh(i,c: integer): Boolean;
begin
Lenh := false;
if (i < 1) or (i >
n) then exit;
case c of
1: begin
if odd(t[i]) then
exit;
inc(t[i]); d[i] :=
mh;
end;
2: begin
if not(odd(t[i]))
then exit;
inc(t[i]); mh :=
d[i]+1;
end;
else exit;
end;
Lenh := true;
end;
function KiemTraLenh(i,t1,t2,k,v: integer): Boolean;
var j: integer;
begin
if v = 2 then KiemTraLenh
:= Lenh(i,t1)
else
begin
KiemTraLenh := false;
for j := 1 to k do
begin
if not Lenh(i,t1)
then exit;
if not Lenh(i,t2)
then exit;
end;
KiemTraLenh := true;
end;
end;
procedure Test;
var i,t1,t2,k,v,n2:
integer;
begin
mh := 0;
fillchar(d,sizeof(d),0);
fillchar(t,sizeof(t),0);
assign(g,gn); reset(g);
while not Seekeof(g) do
begin
DocLenh(i,t1,t2,k,v);
XemLenh(i,t1,t2,k,v);
if not
KiemTraLenh(i,t1,t2,k,v) then
begin
writeln('Sai ');
close(g);
exit;
end;
end;
n2 := n+n;
for i:=1 to n do
if (t[i] <> n2)
then
begin
writeln('Sai ');
close(g);
exit;
end;
if (mh <> m) then
begin
writeln('Sai ');
close(g);
exit;
end;
writeln('Dung');
close(g);
end;
Độ phức tạp
Thuật toán phát sinh và ghi vào file kết quả tối đa 2.n2
dòng lệnh.
Nguồn:
SÁNG TẠO
TRONG THUẬT TOÁN
VÀ
LẬP TRÌNH
Không có nhận xét nào:
Đăng nhận xét