Friday, March 28, 2014

Tháp Hà Nội thẳng



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 abđứng kề nhau trên đường thẳng.
-          Hai cọc ab 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 ab 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)

Tháp Hà Nội ngược



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 sát nó về hướng ngược chiều kim đồng hồ.
Điều kiện này quy định ba phép chuyển 1 tầng tháp như sau:
 3 ¬ 2, hoặc  1 ¬ 2, hoặc  1 ¬ 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
Bài này tương tự như bài Hà Nội xuôi. Ta chỉ cần xác định điều kiện kề giữa hai cọc tháp và lưu ý đến chiều chuyển các tầng tháp ngược chiều quay của kim đồng hồ.
a) Trường hợp vị trí b đứng sát vị trí a ngược chiều kim đồng hồ:
Theo trường hợp này ta có các cặp (a, b) sau đây: (3, 2), (2, 1) và (1, 3).
Hoán đổi vị trí của hai đại lượng a và b trong điều kiện kề của bài toán Hà Nội xuôi ta thu được điều kiện kề trong trường hợp này là
a = (b mod 3)+1
Tình huống
j
k
l
1
a

b
2
b
a

3

b
a
Tháp Hà Nội ngược
Đặc tả a và b kề nhau a = (b mod 3) + 1

Với ý nghĩa là, nếu biết mã số vị trí a thì vị trí b sát sau a ngược chiều kim đồng hồ sẽ được tính theo công thức trên.
Dựa vào các hình trạng buộc phải có ta có thể mô tả việc chuyển tháp trong trường hợp này giống như trong bài toán tháp Hà Nội xuôi, cụ thể là:
Hình trạng
Ý nghĩa
Lệnh
(a: [1..n], b: [ ], c: [ ])
Hình trạng ban đầu với vị trí b sát vị trí a.
a = (b mod 3) + 1
Để chuyển n tầng từ a sang b ngược chiều kim đồng hồ 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.
Hnn(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.
Hnn(n - 1, 6 - a - b, b)


Đoạn trình cho trường hợp này sẽ là
if a = (b mod 3)+1 then
begin {b ke a}
hnn(n-1,a,6-a-b);
inc(d);
writeln(f,d,'. ',a,' -> ',b);
hnn(n-1,6-a-b,b);
end…

b) Trường hợp vị trí b không đứng sát vị trí a theo chiều ngược kim đồng hồ:
Các cặp (a, b) khi đó sẽ là: (1, 2), (2, 3) và (3, 1). Đặc điểm chung của các cặp này là: nếu đi từ a đến b ngược chiều kim đồng hồ chúng ta phải vượt qua c là vị trí nằm giữa ab.

Tình huống
j
k
l
1
a
b

2

a
b
3
b

a
Tháp Hà Nội ngược
Đặc tả a và b không kề nhau
a ¹ (b mod 3) + 1
       Các hình trạng buộc phải có khi đó sẽ rất giống với tình huống tương tự của bài toán Hà Nội xuôi:
Hình trạng
Ý nghĩa
Lệnh
(a: [1..n], c: [ ], b: [ ])
Hình trạng ban đầu với vị trí b cách a qua c ngược chiều kim đồng hồ.
a ¹ (b mod 3) + 1
Để chuyển n tầng từ a sang b cách qua vị trí c = 6 - a - b ta phải...

...


(a: [n], c: [ ], b: [1..n - 1]
Chuyển (tạm) n - 1 tầng từ a qua b.
Hnn(n - 1, a, b)
(a: [ ], c: [n], b: [1..n - 1])
sau đó chuyển (tạm) tầng còn lại của a qua c = 6 - a - b.
a ® 6 - a - b
...


(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...
Hnn(n - 1, b, a)
(a: [1..n-1], c: [ ], b: [n])
để chuyển tầng lớn nhất n từ c qua b.
6 - a - b ® 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.
Hnx(n - 1, a, b)

(*  Pascal  *)
(**************************************
Hano.pas – Hà Nội Ngược
Chuyển pháp ngược chiều kim đồng hồ.
*************************************)
uses crt;
var d: longint;
f: text;
procedure hnn(n,a,b: byte);
begin
if n = 0 then exit;
if a = (b mod 3)+1 then
begin {b ke a}
hnn(n-1,a,6-a-b);
inc(d);
writeln(f,d,'. ',a,' -> ',b);
hnn(n-1,6-a-b,b);
end
else {b cach a qua vi tri c}
begin
hnn(n-1,a,b);
inc(d);
writeln(f,d,'. ',a,' -> ',6-a-b);
hnn(n-1,b,a);
inc(d);
writeln(f,d,'. ',6-a-b,' -> ',b);
hnn(n-1,a,b);
end;
end;
procedure runhnn(n: byte);
begin
d :=  0;
assign(f,'hnn.out');
rewrite(f);
writeln('-----------------');
hnn(n,1,2);
writeln(f,'Total: ',d,' step(s)');
close(f);
readln;
end;
BEGIN
runHnn(3);
END.

Kết quả:
1. 1 -> 3
2. 3 -> 2
3. 1 -> 3
4. 2 -> 1
5. 3 -> 2
6. 1 -> 3
7. 3 -> 2
8. 1 -> 3
9. 2 -> 1
10. 1 -> 3
11. 2 -> 1
12. 3 -> 2
13. 2 -> 1
14. 3 -> 2
15. 1 -> 3
16. 3 -> 2
17. 1 -> 3
18. 2 -> 1
19. 3 -> 2
20. 1 -> 3
21. 3 -> 2
Total: 21 step(s)
Nhận xét
Mới xem ta có cảm tưởng rằng lời gọi Hnn(3,1,2)Hnx(3,1,2) để chuyển tháp 3 tầng từ cọc 1 sang cọc 2 phải cho cùng một số bước chuyển các tầng là 15. Tuy nhiên, lời gọi Hnn(3,1,2) cho ta 21 bước chuyển các tầng, trong khi lời gọi Hnx(3,1,2) chỉ cần 15 bước chuyển các tầng.
Suy ngẫm một chút bạn sẽ giải thích được nghịch lí này.
Hãy thử gọi Hà Nội ngược để chuyển tháp 3 tầng từ cọc 3 sang cọc 2:
Hnn(3,3,2)
Ta sẽ thấy chỉ cần 15 bước!!!
Lại gọi Hà Nội xuôi để chuyển tháp 3 tầng từ cọc 1 sang cọc 3:
Hnx(3,1,3)
Ta lại thấy 21 bước.
Như vậy, HnxHnnđối xứng lệch. Nếu hai cọc, nguồn và đích kề nhau thì số lần chuyển tháp 3 tầng sẽ là 15. Ngược lại, khi hai cọc đó không kề nhau thì số lần chuyển tháp 3 tầng sẽ là 21. Hai cọc 1 và 2 là kề nhau đối với tháp Hà Nội xuôi nhưng không kề nhau đối với tháp Hà Nội ngược. Tương tự, hai cọc 3 và 2 là kề nhau đối với tháp Hà Nội ngược nhưng không kề nhau đối với tháp Hà Nội xuôi.
Ta nhận xét rằng: nếu lấy hai số a, b khác nhau bất kì trong ba số 1, 2 và 3 thì giữa a và b chỉ xảy ra một trong hai trường hợp loại trừ nhau sau đây:
b = (a mod 3) +1, hoặc a = (b mod 3)+1
Do đó, quan hệ kề nhau trong hai bài toán Tháp Hà Nội xuôi và ngược là phủ định đối với nhau.

Hà Nội xuôi
Hà Nội ngược
b = (a mod 3)+1
a và b kề nhau
a và b không kề nhau
a = (b mod 3)+1
a và b không kề nhau
a và b kề nhau
Quan hệ kề nhau trong hai bài toán
tháp Hà Nội xuôi và ngược