Có 9 chiếc đồng hồ điện tử treo trên một bảng theo sơ đồ 3 ´ 3.
Các đồng hồ được mã số từ 1 đến 9 theo trật tự từ trái qua phải, từ hàng trên
xuống hàng dưới. Mỗi đồng hồ có 4 điểm chỉ giờ ứng với các giờ 12, 3, 6 và 9.
Giờ hiện trỏ của mỗi đồng hồ ứng với điểm sáng à.
Để điều khiển các đồng hồ người ta sử dụng 9 phím với các chức năng được mô tả
như trong hình vẽ. Khi nhấn vào một phím thì có 4 đồng hồ đồng loạt nhảy điểm
sáng đi 90o theo chiều kim đồng hồ để cộng thêm 3 giờ tính từ giờ
hiện trỏ. Thí dụ, khi nhấn phím 1 thì 4 đồng hồ 1, 2, 4 và 5 sẽ được chỉnh giờ
theo luật trên. Biết giờ hiện tại của các đồng hồ. Hãy xác định một dãy ngắn
nhất các phím cần nhấn để các đồng hồ đồng loạt trỏ 12 giờ.
|
|
¨
|
|
|
|
¨
|
|
|
|
¨
|
|
|
|
Sơ
đồ bố trí
9
đồng hồ
|
||||
|
à
|
|
¨
|
|
¨
|
|
¨
|
|
à
|
|
¨
|
|
|
|||||
|
|
¨
|
|
|
|
à
|
|
|
|
¨
|
|
|
|
|
|
‚
|
ƒ
|
|
|
9h
|
|
‚ 6h
|
|
ƒ 9h
|
|
|
|
„
|
…
|
†
|
|
||||||
|
|
¨
|
|
|
|
à
|
|
|
|
¨
|
|
|
|
|
‡
|
ˆ
|
‰
|
|
|
à
|
|
¨
|
|
¨
|
|
¨
|
|
¨
|
|
à
|
|
|
|
|
|
|
|
|
|
¨
|
|
|
|
¨
|
|
|
|
¨
|
|
|
|
|
|
|
|
|
|
„ 9h
|
|
… 12h
|
|
† 3h
|
|
|
|
|
|
|
|
||||||
|
|
à
|
|
|
|
¨
|
|
|
|
¨
|
|
|
|
|
|
|
|
|
|
¨
|
|
¨
|
|
¨
|
|
¨
|
|
¨
|
|
¨
|
|
|
9
phím
điều
khiển
|
||||
|
|
¨
|
|
|
|
à
|
|
|
|
à
|
|
|
|
|||||
|
‡ 12h
|
|
ˆ 6h
|
|
‰ 6h
|
|
|
|
1
|
2
|
3
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4
|
5
|
6
|
|
|
9
đồng hồ, à giờ
đang trỏ
|
|
|
|
7
|
8
|
9
|
|
||||||||||
Dữ liệu vào: tệp văn bản DONGHO.INP gồm
12 dòng
3 dòng đầu tiên gồm 9 số trỏ giờ tại thời điểm đầu bố trí theo ma
trận 3´
3.
Dòng thứ i trong số 9 dòng tiếp theo, i = 1, 2, 3, 4 ghi 4 số tự
nhiên thể hiện mã số của 4 đồng hồ sẽ
nhảy điểm sáng 90o khi ta nhấn phím i.
Các số trên cùng dòng cách nhau qua dấu cách.
Dữ liệu ra: Tệp văn bản DONGHO.OUT gồm
hai thông tin:
- Bài toán có nghiệm (ghi
số 1) hoặc vô nghiệm (ghi số 0).
- Dãy phím ngắn nhất cần
nhấn cho trường hợp có nghiệm.
|
DONGHO.INP
|
DONGHO.OUT
|
|
9 6 9
9 12 3
12 6 6
1 2 4 5
2 3 5 6
4 5 7 8
5 6 8 9
1 2 3 5
1 4 5 7
3 5 6 9
5 7 8 9
2 5 6 8
|
1
1 2 4 4
|
|
Ý
nghĩa: Nhấn lần lượt các phím 1, 2, 4, 4
cả
9 đồng hồ đều đồng loạt trỏ 12 giờ.
|
|
Tag: gia sư tin học, gia sư tin học tại nhà
Thuật toán
Ta nhận thấy rằng do các đồng hồ hoạt động độc lập với nhau
nên dãy phím cần nhấn là giao hoán, nghĩa là có thể liệt kê dãy phím đó theo
trật tự tùy ý. Thí dụ, nhấn các phím 1, 2, 3 sẽ mang lại kết quả như khi nhấn
dãy phím 2, 1, 3 hoặc theo bất kì hoán vị nào của 3 phím đó. Ngoài ra, nếu một
phím được nhấn đến một bội lần của 4 thì điểm sáng trỏ giờ sẽ quay lại đúng vị
trí ban đầu, do đó ta không dại gì mà nhấn một phím qúa 3 lần. Từ hai nhận xét
trên ta thấy rằng có thể dùng kỹ thuật vét cạn, cụ thể là xét các tổ hợp dãy
phím p[1..9], p[i] = 0..3 biểu thị số lần bấm phím i. Với mỗi tổ hợp p ta tính
xem các đồng hồ được cập nhật ra sao. Nếu cả 9 đồng hồ đều nhảy về thời điểm 12
giờ thì ta chọn phương án có số lần bấm phím ít nhất trong số các tổ hợp ứng
viên.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1
|
2
|
3
|
|
1
|
2
|
3
|
|
1
|
2
|
3
|
|
|
|
4
|
5
|
6
|
|
4
|
5
|
6
|
|
4
|
5
|
6
|
|
|
|
7
|
8
|
9
|
|
7
|
8
|
9
|
|
7
|
8
|
9
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1
|
|
|
|
2
|
|
|
|
3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1
|
2
|
3
|
|
1
|
2
|
3
|
|
1
|
2
|
3
|
|
|
|
4
|
5
|
6
|
|
4
|
5
|
6
|
|
4
|
5
|
6
|
|
|
|
7
|
8
|
9
|
|
7
|
8
|
9
|
|
7
|
8
|
9
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4
|
|
|
|
5
|
|
|
|
6
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1
|
2
|
3
|
|
1
|
2
|
3
|
|
1
|
2
|
3
|
|
|
|
4
|
5
|
6
|
|
4
|
5
|
6
|
|
4
|
5
|
6
|
|
|
|
7
|
8
|
9
|
|
7
|
8
|
9
|
|
7
|
8
|
9
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7
|
|
|
|
8
|
|
|
|
9
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Chức
năng của các phím điều khiển
|
||||||||||||
Dưới đây là một vài chi tiết sử dụng trong chương
trình. Ta khởi tạo sẵn mảng hai chiều mô
tả chức năng của các phím điều khiển, phim[i,j] cho biết khi nhấn phím i
thì đồng hồ j sẽ được chỉnh.
var
phim: array[1..9,1..4] of integer;
Sau khi đọc
dữ liệu ứng với thí dụ cụ thể thì mảng phim sẽ được gán trị như sau:
phim =
((1,2,4,5),
(2,3,5,6),
(4,5,7,8),
(5,6,8,9),
(1,2,3,5),
(1,4,5,7),
(3,5,6,9),
(5,7,8,9),
(2,5,6,8));
Bạn cũng nên mô tả sẵn một kiểu mảng 9 phần tử để biểu thị
các phím và các đồng hồ.
type mi1 = array[1..9] of
integer;
var
dongHo: mi1;
f: text;
imin, imax: longint;
Bạn có thể sử
dụng 9 vòng for lồng nhau ứng với 9 phím, mỗi vòng biến
thiên từ 0 đến 3 ứng với số lần nhấn phím.
Biến ts dùng để
tính tổng số lần nhấn phím. Dễ thấy, mỗi phím được nhấn tối đa 3 lần, vậy 9
phím sẽ được nhấn tối đa 9.3 = 27 lần. Ta lấy 28 làm gía trị khởi đầu cho việc
tính tsmin - tổng số lần nhấn phím ít nhất. Ta cũng nên chuyển các số trên mặt
đồng hồ là (12,3,6,9) sang các số hệ 4 là (0,1,2,3) để cho tiện tính toán. Hàm
Sum(p) tính tổng 9 phần tử của mảng p - đó chính là tổng số lần nhấn phím của
phương án p. Hàm KiemTra(q) thực hiện việc kiểm tra xem 9 đồng hồ có cùng trỏ
đến 12h hay không, q[i] là số lần đồng
hồ i được cập nhật khi thực hiện phương án p.
Bạn cũng có thể
sử dụng hệ 4 để xử lí như sau: Các phương án nhấn 9 phím biến thiên từ
(0,0,0,0,0,0,0,0,0) đến (3,3,3,3,3,3,3,3,3) ứng với imin = 0 và imax = 49-1 = 218-1 =
(1 shl 18) - 1 = 262143. Ta cho i biến thiên từ imin đến imax. Với mỗi i ta xây
dựng phương án nhấn phím bằng cách gọi thủ tục Split(i,p) chuyển số i sang dạng
biểu diễn hệ 4 để ghi vào mảng p, trong đó p[j] sẽ là số lần nhấn phím j. Biết
p ta dễ dàng cập nhật các đồng hồ.
Chương trình dưới
đây cài đặt 2 phương án vét cạn, Run1 –
chín vòng for lồng nhau và Run2 - tính toán theo hệ 4.
(* Pascal *)
(* Dong ho *)
const bl = #32; fn = 'DONGHO.INP'; gn = 'DONGHO.OUT';
type mi1 = array[1..9] of integer;
var
dongHo,kq: mi1;
f,g: text;
imin, imax: longint;
s, tsmin: integer;
var
phim: array[1..9,1..4] of integer;
procedure Split(x:
longint; var a: mi1);
var i: integer;
begin
for i := 1 to 9 do
begin
a[i] := x mod 4;
x := x div 4;
end;
end;
procedure Doc;
var i,j: integer;
begin
assign(f,fn); reset(f);
for i:=1 to 9 do
read(f,dongHo[i]);
for i:=1 to 9 do
for j:=1 to 4 do
read(f,phim[i,j]);
close(f);
end;
procedure Ghi;
var i,j: integer;
begin
assign(g,gn);
rewrite(g);
if tsmin = 28 then
writeln(g,0) { vo nghiem }
else
begin { co nghem }
writeln(g,1);
for i := 1 to 9 do
for j := 1 to c[i]
do write(g,i,bl);
writeln(g);
end;
close(g);
end;
procedure Init;
var i: integer;
begin
for i:=1 to 9 do dongHo[i]
:= (dongHo[i] div 3) mod 4;
imin := 0;
imax := 1;
imax := (imax shl 18 - 1);
end;
function KiemTra(var q: mi1): Boolean;
var i: integer;
begin
KiemTra := false;
for i:=1 to 9 do
if (dongHo[i]+q[i])
mod 4 <> 0 then exit;
KiemTra := true;
end;
function Sum(var q: mi1): integer;
var i,s: integer;
begin
s := 0;
for i:=1 to 9 do s :=
s+q[i];
Sum := s;
end;
procedure XuLiFor;
var j,k,ts: integer;
q,p: mi1; { p[i] – so
lan nhan phim i }
i,ikq: longint;
begin
tsmin := 28; { = 3*9+1 }
for p[1] := 0 to 3 do
for p[2] := 0 to 3 do
for p[3] := 0 to 3 do
for p[4] := 0 to 3 do
for p[5] := 0 to 3 do
for p[6] := 0 to 3 do
for p[7] := 0 to 3
do
for p[8] := 0 to 3
do
for p[9] := 0 to 3
do
begin
fillchar(q,sizeof(q),0);
for j := 1 to
9 do
begin
for k := 1
to 4 do
inc(q[phim[j,k]],p[j]);
end;
if KiemTra(q)
then
begin
ts :=
Sum(p);
if ts <
tsmin then
begin
tsmin :=
ts;
kq := p;
end;
end;
end;
end;
procedure XuLi;
var j,k,ts: integer;
q,p: mi1;
i,ikq: longint;
begin
tsmin := 28; { = 3*9+1 }
for i:=imin to imax do
begin
Split(i,p); { bam phim j p[j] lan }
fillchar(q,sizeof(q),0);
for j := 1 to 9 do
begin
for k := 1 to 4 do
inc(q[phim[j,k]],p[j]);
end;
if KiemTra(q) then
begin
ts := Sum(p);
if ts < tsmin
then
begin
tsmin := ts;
ikq := i;
end;
end;
end;
Split(ikq,kq);
end;
procedure Run1;
begin
Doc; Init;
XuLiFor; Ghi;
end;
procedure Run2;
begin
Doc; Init;
XuLi; Ghi;
end;
BEGIN
Run1;
END.
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