Lát nền
Người
ta cần lát kín một nền nhà hình vuông cạnh dài n = 2k, (k là một số
tự nhiên trong khoảng 1..6) khuyết một phần tư tại góc trên phải bằng những viên
gạch màu hình thước thợ (chữ L) tạo bởi 3 ô vuông đơn vị như trong hình 2b. Hai
viên gạch kề cạnh nhau dù chỉ 1 đơn vị dài phải có màu khác nhau. Hãy cho biết
một cách lát với số màu ít nhất.
Dữ liệu vào: tệp văn bản NEN.INP chứa số tự nhiên n.
Dữ liệu
ra: tệp văn bản NEN.OUT. Dòng đầu tiên là hai số tự nhiên m biểu thị số viên gạch và c là số màu cần dùng cho việc lát nền.
Tiếp đến là một phương án lát nền tìm được, trong đó mỗi viên gạch lát được tạo
bởi ba chữ số giống nhau thể hiện màu của viên gạch đó. Các số trên mỗi dòng
cách nhau qua dấu cách.
|
NEN.INP
|
NEN.OUT
|
|
8
|
16 3
3 3 1 1
3 2 2 1
1 2 3 3
1 1 3 2
3 3 1 2 2 3 1 1
3 2 1 1 3 3 2 1
1 2 2 3 1 2 2 3
1 1 3 3 1 1 3 3
|
Thí dụ, với n = 8 ta có một
cách lát nền như sau:
Lời giải sau đây của bạn Lê Hoàng Hải, lớp 10 chuyên Tin, Đại học
Khoa học Tự nhiên, Đại học Quốc gia Hà Nội (năm 2002).
Để tính số viên gạch ta lấy ba phần tư diện tích hình vuông phủ nền nhà
chia cho 3 là diện tích 1 viên gạch thước thợ:
sogach:=((3*n*n) div 4) div 3;
|
3
|
3
|
1
|
1
|
|
|
|
|
|
3
|
2
|
2
|
1
|
|
|
|
|
|
1
|
2
|
3
|
3
|
|
|
|
|
|
1
|
1
|
3
|
2
|
|
|
|
|
|
3
|
3
|
1
|
2
|
2
|
3
|
1
|
1
|
|
3
|
2
|
1
|
1
|
3
|
3
|
2
|
1
|
|
1
|
2
|
2
|
3
|
1
|
2
|
2
|
3
|
|
1
|
1
|
3
|
3
|
1
|
1
|
3
|
3
|
|
Hình 3. Nền nhà với n = 8
|
|||||||
Về số màu,
với n = 2 thì chỉ cần 1 viên gạch màu
1. Với mọi n > 2 ta sẽ trình bày
một thuật toán cần tối đa ba màu.
Đầu tiên ta gọi thủ tục Init để khởi trị với hình vuông cạnh v = 2 nằm ở góc dưới trái của nền nhà
được biểu diễn dưới dạng một mảng hai chiều a: ba ô trong hình vuông 2 ´ 2 sẽ được điền giá trị
1, ô nằm ở góc trên phải được điền giá trị 2 (phần tô đậm, hình 6). Gọi hình
được khởi trị là A. Mỗi bước tiếp theo ta thực hiện ba thao tác biến hình sau
đây:
-
Tịnh tiến A đi lên theo đường chéo để thu được hình B
(xem thủ tục DichCheo).
-
Lật A sang phải (tức là lấy đối xứng gương qua trục tung)
để thu được hình C (xem thủ tục LatPhai).
-
Lật A lên trên (tức là lấy đối xứng gương qua trục hoành)
để thu được hình D (xem thủ tục LatLen).
Chú ý rằng khi lật ta cần thực hiện thêm phép hoán đổi
trị 1 và 3 cho nhau.
Mỗi lần lặp như vậy ta sẽ thu được hình vuông có cạnh
tăng gấp đôi hình trước. Khi v = n ta gọi thủ tục Fini để ghi ba mảnh D, A và C vào tệp kết quả.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3
|
3
|
1
|
1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3
|
2
|
2
|
1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1
|
2
|
3
|
3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1
|
1
|
3
|
2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3
|
3
|
1
|
2
|
1
|
1
|
1
|
1
|
|
3
|
3
|
1
|
2
|
2
|
3
|
1
|
1
|
|
|
|
|
|
|
|
|
|
|
3
|
2
|
1
|
1
|
|
|
|
|
|
3
|
2
|
1
|
1
|
3
|
3
|
2
|
1
|
|
1
|
2
|
1
|
1
|
1
|
1
|
1
|
1
|
|
1
|
2
|
2
|
3
|
|
|
|
|
|
1
|
2
|
2
|
3
|
1
|
2
|
2
|
3
|
|
1
|
1
|
|
|
|
|
|
|
|
1
|
1
|
3
|
3
|
|
|
|
|
|
1
|
1
|
3
|
3
|
1
|
1
|
3
|
3
|
Hình 6
Ta biểu diễn
nền nhà hình vuông qua một mảng hai chiều a với các dòng được mã số 1..n từ trên xuống và các cột được mã số từ
1..n từ trái qua phải. Khi đó viên
gạch ở góc dưới trái sẽ có toạ độ [n,
1]. Sau khi đọc dữ liệu để nhận giá trị n,
ta gán trị ban đầu cho 4 viên gạch ở góc dưới trái như sau:
a[n-1,1] := 1; a[n-1,2] := 2;
a[n,1] := 1; a[n,2] := 1;
Kí hiệu A là hình vuông cạnh dài
v đơn vị nằm tại góc dưới trái của nền nhà, tức là phần mảng v[n
– v + 1..n, 1..v] trong hình 7.
Khi đó các thủ tục di chuyển hình vuông A sẽ được mô tả như sau.
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
A
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
n – v + 1
|
3
|
3
|
1
|
2
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
...
|
3
|
2
|
1
|
1
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
n – 1
|
1
|
2
|
2
|
3
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
n
|
1
|
1
|
3
|
3
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
1
|
2
|
...
|
v
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Hình 7. Hình vuông a cạnh v
được chọn để biến hình
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Để dịch chéo hình vuông A ta copy
dần từng phần tử trong các dòng, từ dòng n
– v + 1 đến dòng cuối cùng, dòng thứ n
đến vị trí mới (h. 8).
(*---------------------------------------------
Dich hinh vuong A canh v,
a[n-v+1..n,1..v]o goc duoi trai di len theo
duong cheo chinh cua nen nha de nhan duoc manh B.
--------------------------------------------*)
procedure
DichCheo(v: word);
var i,j:word;
begin
for i := n-v+1
to n do
for j := 1 to
v do
a[i-v,j+v] := a[i,j];
end;
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A
|
|
|
|
|
|
|
C
|
|
n – v + 1
|
3
|
3
|
1
|
2
|
2
|
3
|
1
|
1
|
|
...
|
3
|
2
|
1
|
1
|
3
|
3
|
2
|
1
|
|
n – 1
|
1
|
2
|
2
|
3
|
1
|
2
|
2
|
3
|
|
n
|
1
|
1
|
3
|
3
|
1
|
1
|
3
|
3
|
|
|
1
|
2
|
...
|
v
|
|
|
|
|
|
Hình 9. Lật A qua phải để thu được C
|
||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Để lật phải hình vuông A ta cũng
chuyển dần từng phần tử trong các dòng, từ dòng n – v + 1 đến dòng cuối cùng, dòng thứ n đến vị trí mới. Tuy nhiên cần lưu ý thay đổi trị màu từ 1 sang
màu 3 và ngược lại. Thao tác này được thực hiện qua phép gán 4 – c, trong đó c là màu của ô gốc. Nếu c = 2 thì 4 – 2 = 2, tức là màu 2 không
thay đổi (h. 9).
(*--------------------------------------------
Lat hinh vuong canh v, a[n-v+1..n,1..v]
o goc duoi trai sang phai, doi
mau gach
de nhan duoc manh C.
----------------------------------------------*)
procedure
LatPhai(v: word);
var
i,j,v2:word;
begin
v2 := 2*v;
for i := n-v+1
to n do
for j := 1 to
v do
a[i,v2-j+1] := 4-a[i,j];
end;
Để lật hình vuông A lên trên ta cũng làm tương tự như lật phải (h. 10).
(*------------------------------------------
Lat hinh vuong
canh v, a[n-v+1..n,1..v]
o goc duoi len tren, doi mau
gach
de nhan duoc manh D.
--------------------------------------------*)
procedure
LatLen(v: word);
var
i,j,v2:word;
begin
v2 := n-2*v+1;
for i := 0 to
v-1 do
for j := 1 to
v do
a[v2+i,j] := 4-a[n-i,j];
end;
Bình luận
Thuật giải sử dụng hai phép biến hình cơ bản trong chương trình phổ
thông là phép dời hình (tịnh tiến) và đối xứng qua trục. Việc hoán đổi trị 1 và
3 cho nhau là một ý tưởng thông minh. Mỗi ô trong bảng được điền đúng một lần
do đó độ phức tạp tính toán của thuật toán là n2, trong khi các bài
giải khác đều phải sử dụng các phép dò tìm để xác định màu tô và gọi đệ quy nên
thường tốn kém về miền nhớ và thời gian hơn nhiều lần.
(* Pascal
*)
(****************************
LATNEN – lat nen nha
hinh vuong khuyet goc bang
cac vien gach mau hinh L
*****************************)
const
fn = 'NEN.INP'; {input file}
gn = 'NEN.OUT'; {output file}
bl = #32; {dau cach}
mn = 65; {kich thuoc toi da cua n}
var {n – chieu
dai canh nen nha}
f,g: text;
a: array[0..mn,0..mn] of byte; {nen nha}
{a[i] – mau vien
gach lat}
n,n2: word; {n2 = n/2}
sogach: word;
{-----------------------------
Doc du lieu va
khoi tri
----------------------------}
procedure
Init;
begin
{Doc du lieu}
assign(f,fn);
reset(f);
readln(f,n);
close(f);
n2 := n div 2;
sogach := ((3*n*n) div 4) div 3;
{Dat tam 4 o
vuong (2 X 2) tai goc duoi trai}
a[n-1,1] := 1;
a[n-1,2] := 2;
a[n,1] := 1; a[n,2]
:= 1;
end;
{-------------------------------
Ket thuc, ghi tep
-------------------------------}
procedure
Fini(somau:word);
var i,j: word;
begin
assign(g,gn);
rewrite(g);
writeln(g,sogach,bl,somau);
{ghi goc tren trai D}
for i := 1 to
n2 do
begin
for j := 1 to
n2 do
write(g,a[i,j],bl);
writeln(g);
end;
{ghi nua duoi
A va C}
for i := n2+1
to n do
begin
for j := 1 to
n do
write(g,a[i,j],bl);
writeln(g);
end;
close(g);
end;
(*---------------------------------------------
Dich hinh
vuong A canh v, a[n-v+1..n,1..v]
o goc duoi trai di len theo duong cheo
chinh cua nen nha
de nhan duoc manh B.
-----------------------------------------------*)
procedure
DichCheo(v: word); tự viết
(*--------------------------------------------
Lat hinh vuong
canh v, a[n-v+1..n,1..v]
o goc duoi trai sang phai, doi
mau gach
de nhan duoc manh C.
-----------------------------------------------*)
procedure
LatPhai(v: word); tự viết
(*--------------------------------------------
Lat hinh vuong
canh v, a[n-v+1..n,1..v]
o goc duoi len tren, doi mau
gach
de nhan duoc manh D.
-----------------------------------------------*)
procedure
LatLen(v: word); tự viết
procedure Run;
var v:word;
begin
Init; {khoi
tri voi n = 2}
if n = 2 then
begin
Fini(1); exit;
end;
v := 1;
repeat
v := v*2;
if v < n2 then DichCheo(v);
LatPhai(v);
LatLen(v);
until v = n2;
Fini(3);
end;
BEGIN
Run;
END.
Không có nhận xét nào:
Đăng nhận xét