Tháp Hà Nội thẳng
Nội dung giống như bài toán tháp Hà Nội cổ chỉ sửa lại quy tắc (2) như
sau: (2) Mỗi lần chỉ được chuyển 1 tầng tháp từ một cọc sang cọc kề nó,
không được vòng từ 3 sang 1 hay 1 sang 3.
Điều
kiện này quy định bốn phép chuyển 1 tầng tháp như sau:
1® 2,2 ® 1, 2 ® 3, 3 ® 2
hoặc, theo cách biểu diễn khác:
1 <-> 2 <-> 3
tức là chỉ được chuyển qua lại giữa hai cọc kề nhau.
Giả thiết là các cọc được sắp thành hàng như sau:
1 = 2 = 3
Hãy tìm cách giải bài toán với số lần chuyển ít nhất.
Bài giải
Giống như đã phân tích trong các bài toán Hà Nội trước, ta có:
-
Hình trạng xuất phát: (a:[1..n], b:[ ], c:[ ])
-
…
-
Hình trạng kết
thúc: (a:[ ], b:[1..n], c:[ ])
-
Hình trạng buộc
phải có: (a:[n], b:[ ], c:[1..n – 1])
Ta phân biệt hai trường hợp:
-
Hai cọc a và b
đứng kề nhau trên đường thẳng.
-
Hai cọc a và b cách nhau qua c.
Trường hợp thứ nhất Nếu vị trí các cọc được bố trí
như sau
1 2 3
thì giữa a và b có bốn tình huống, cụ thể là:
|
Tình huống
|
1
|
2
|
3
|
|
1
|
a
|
b
|
|
|
2
|
b
|
a
|
|
|
3
|
|
a
|
b
|
|
4
|
|
b
|
a
|
|
Tháp Hà Nội
thẳng
Đặc tả a
và b kề nhau abs(a - b) = 1
|
|||
Trường hợp này được đặc tả là
abs(a-b) = 1
|
Hình
trạng
|
Ý nghĩa
|
Lệnh
|
|
(a:
[1..n], b: [ ], c: [ ])
|
Hình
trạng ban đầu với vị trí b kề vị trí a trên đường thẳng.
abs(a
-
b) = 1
Để
chuyển n tầng từ a sang b theo đường thẳng ta phải...
|
|
|
...
|
|
|
|
(a:
[n], b: [ ], c: [1..n -
1])
|
Chuyển (tạm) n - 1 tầng từ a qua
c = 6 - a - b.
|
Hnt(n -
1, a, 6 -
a -
b);
|
|
(a:
[ ], b: [n], c: [1..n -
1])
|
sau
đó chuyển tầng còn lại của a qua b.
|
a ®
b
|
|
...
|
|
|
|
(a:
[ ], b: [1..n], c: [ ])
|
Cuối
cùng chuyển n -
1 tầng từ c = 6 – a – b qua b là
hoàn tất.
|
Hnt(n -
1, 6 -
a -
b, b);
|
Trường
hợp thứ hai a và b cách nhau qua c trên
đường thẳng. Ta có c = 2 và chỉ có hai tình huống cho a và b như sau:
|
Tình huống
|
j
|
k
|
l
|
|
1
|
a
|
c
|
b
|
|
2
|
b
|
c
|
a
|
|
|
|
|
|
|
Hình trạng
|
Ý nghĩa
|
Lệnh
|
|
(a: [1..n], c: [ ], b: [ ])
|
Hình trạng ban đầu với vị trí b không kề với vị
trí a trên đường thẳng.
abs(a - b) ¹ 1
Ta có c = 2.
Để chuyển n tầng từ a sang b
cách qua vị trí c = 2 ta phải...
|
|
|
...
|
|
|
|
(a:
[n], c: [ ], b: [1..n -
1]
|
Chuyển (tạm) n - 1 tầng từ a qua b.
|
Hnt(n - 1, a, b)
|
|
(a:
[ ], c: [n], b: [1..n -
1])
|
sau đó chuyển (tạm) tầng
cuối của a qua c = 2.
|
a ® 2
|
|
...
|
|
|
|
(a:
[1..n-1], c: [n], b: [ ])
|
Rồi lại chuyển (tạm) n - 1 tầng từ b qua a nhằm giải phóng vị trí đích b.
|
Hnt(n - 1, b, a)
|
|
(a:
[1..n-1], c: [ ], b: [n])
|
để chuyển tầng lớn nhất n từ c = 2 qua b.
|
2 ® b
|
|
(a: [ ], c: [ ], b: [1..n])
|
Cuối cùng chuyển n - 1 tầng từ a qua b là hoàn tất.
|
Hnt(n - 1, a, b)
|
(* Pascal
*)
(****************************
HNT.PAS – Ha Noi thang
Chuyen n tang thap tu coc a
sang coc b theo duong thang
1->2, 2->1 hoac
2->3, 3->2
1 2 3
****************************)
uses crt;
var d: longint;
f: text;
procedure Hnt(n,a,b: byte);
begin
if n = 0 then exit;
if abs(a-b) = 1 then
begin
Hnt(n-1,a,6-a-b);
inc(d);
writeln(f,d,'. ',a,' -> ',b);
Hnt(n-1,6-a-b,b);
end
else
{-----------------------------
abs(a-b)=2 tuc la a = 1, b = 3
hoac a = 3, b = 1, do do c=2
------------------------------}
begin
Hnt(n-1,a,b);
inc(d);
writeln(f,d,'. ',a,' -> 2');
Hnt(n-1,b,a);
inc(d);
writeln(f,d,'. 2 -> ',b);
Hnt(n-1,a,b);
end;
end;
procedure runHnt(n: byte);
begin
d := 0;
assign(f,'hnt.out');
rewrite(f);
writeln('-----------------');
Hnt(n,1,2);
writeln(f,'Total: ',d,' step(s)');
close(f);
readln;
end;
BEGIN
runHnt(3);
END.
Kết quả
1. 1 -> 2
2. 2 -> 3
3. 1 -> 2
4. 3 -> 2
5. 2 -> 1
6. 2 -> 3
7. 1 -> 2
8. 2 -> 3
9. 1 -> 2
10. 3 -> 2
11. 2 -> 1
12. 3 -> 2
13. 1 -> 2
Total: 13 step(s)
