Tháp Hà Nội xuôi

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ó theo chiều kim đồng hồ.

         

     

Điều kiện này quy định ba phép chuyển 1 tầng tháp giữa các cọc như sau:

1® 2, hoặc 2  ® 3, hoặc 3  ® 1.

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

Suy nghĩ một chút bạn sẽ thấy cái lợi của nguyên tắc "Bức ảnh buộc phải có". Đặt tên các tầng tháp theo thứ tự từ nhỏ đến lớn là 1..n. Ta mô tả mỗi tấm ảnh như một bộ ba (a:[A], b:[B], c:[C]) trong đó A, B và C là các tầng tháp đặt tại mỗi vị trí tương ứng. Gọi a là vị trí xuất phát, b là vị trí đích, bài toán trên có thể được phát biểu như sau:

Gỉa thiết:  (a:[1..n], b:[ ], c:[ ])

                 …

Kết luận:  (a:[ ], b:[1..n], c:[ ])

Với ý nghĩa là cho biết bức ảnh ban đầu và cuối cùng. Hãy liệt kê ít nhất các bức ảnh cần có ở giữa ba dấu chấm (…) sao cho bộ ảnh giải thích được quá trình chuyển tháp theo các điều kiện cho trước.

Mỗi bức ảnh được gọi là một hình trạng. Ngoài hai hình trạng đầu tiên và cuối cùng, một trong những hình trạng buộc phải có sẽ là  (a:[n ],b:[ ],c:[1..n-1 ]). Tiếp đó là hình trạng  (a:[ ],b:[n ],c:[1..n-1 ])thu được sau lệnh chuyển  a  ® b

Gọi Hnx(n,a,b) là thủ tục giải bài toán tháp Hà Nội xuôi, chuyển tháp n tầng từ vị trí a sang vị trí b. Ta xét hai trường hợp.

a) Trường hợp vị trí b đứng sát vị trí a theo chiều kim đồng hồ:

Theo trường hợp này ta có các cặp (a, b) sau đây: (1, 2), (2, 3) và (3, 1).

Đặc tả cho điều kiện của trường hợp này là b = (a 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 xuôi theo chiều kim đồng hồ sẽ được tính theo công thức trên.

Nếu vị trí các cọc được bố trí như sau

j        k          l

thì giữa a và b có ba tình huống, cụ thể là

Tình huống	j	k	l
1	a	b
2		a	b
3	b		a
Tháp Hà Nội xuôi Đặc tả a và b kề nhau b = (a mod 3)+1

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 cổ, 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. b = (a mod 3)+1 Để chuyển n tầng từ a sang b theo 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.	Hnx(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.	Hnx(n – 1, 6 – a – b, b)

Đoạn trình cho trường hợp này sẽ là

if b = (a mod 3)+1 then

begin {b ke a}

Hnx(n-1,a,6-a-b);

inc(d);

writeln(f,d,'. ',a,' -> ',b);

Hnx(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 kim đồng hồ:

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

Tình huống	j	k	l
1	a		b
2	b	a
3		b	a
Tháp Hà Nội xuôi Đặc tả a và b không kề nhau b ¹ (a mod 3) + 1

Các hình trạng buộc phải có khi đó sẽ là:

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 theo chiều kim đồng hồ. b ¹ (a 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.	Hnx(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...	Hnx(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  *)

(*******************************

          Ha Noi xuoi

*******************************)

uses crt;

var d: longint;

f: text;

procedure Hnx(n,a,b: byte);

begin

if n = 0 then exit;

if b = (a mod 3)+1 then

begin {b ke a}

Hnx(n-1,a,6-a-b);

inc(d);

writeln(f,d,'. ',a,' -> ',b);

Hnx(n-1,6-a-b,b);

end

else {b cach a qua vi tri c}

begin

Hnx(n-1,a,b);

inc(d);

writeln(f,d,'. ',a,' -> ',6-a-b);

Hnx(n-1,b,a);

inc(d);

writeln(f,d,'. ',6-a-b,' -> ',b);

Hnx(n-1,a,b);

end;

end;

procedure runHnx(n: byte);

begin

d :=  0;

assign(f,'hnx.out');

rewrite(f);

writeln('-----------------');

Hnx(n,1,2);

writeln(f,'Total: ',d,' step(s)');

close(f);

readln;

end;

BEGIN

runHnx(3);

END.

Lời gọi runHnx(3) chuyển n tầng tháp từ cọc 1 sang cọc 2 sẽ cho ta kết quả sau:

1. 1 -> 2 2. 2 -> 3 3. 1 -> 2 4. 3 -> 1 5. 2 -> 3 6. 1 -> 2 7. 2 -> 3 8. 1 -> 2

9. 3 -> 1 10. 1 -> 2 11. 3 -> 1 12. 2 -> 3 13. 1 -> 2 14. 3 -> 1 15. 1 -> 2 Total: 15 step(s)