Tháp Hà Nội cổ

Có ba cọc cắm tại ba vị trí là 1, 2 và 3 như hình 5. Trên một cọc, gọi là cọc a có một chồng gồm n đĩa bằng gỗ hình tròn to nhỏ khác nhau được xuyên lỗ ở giữa tựa như những đồng xu và đặt chồng lên nhau để tạo ra một toà tháp. Người chơi phải chuyển được toà tháp sang cọc b ¹ a theo các quy tắc sau:

(1) Người chơi được sử dụng cọc còn lại để đặt tạm các tầng tháp.

(2) Mỗi lần chỉ được chuyển 1 tầng tháp từ một cọc sang một trong hai cọc còn lại.

(3) Không bao giờ được đặt tầng tháp lớn lên trên tầng tháp nhỏ.

Hãy tìm cách giải bài toán trên với số lần chuyển ít nhất.

Thuật toán

Chắc chắn là bạn đã biết cách giải bài toán trên. Tuy nhiên để có thể giải dễ dàng các biến thể của bài toán tháp Hà Nội chúng ta thử tìm hiểu một cách lập luận sau.

Giả sử ta quan sát một người chơi giỏi, tức là người chuyển được n tầng tháp từ cọc 1 sang cọc 2 với số lần chuyển tối thiểu. Ta dùng một chiếc máy ảnh chụp từng kết quả trung gian sau mỗi bước chuyển của người chơi này. Tổng số bức ảnh, trừ tấm ảnh ban đầu, chính là số bước chuyển các tầng. Trong số các bức ảnh chắc chắn phải có một bức như hình 10. 

Tại sao vậy? Tại vì chừng nào chưa dỡ được n - 1 tầng tháp ở phía trên của vị trí 1 để chuyển sang vị trí 3 thì anh ta không thể chuyển được tầng tháp cuối, tức là tầng lớn nhất sang vị trí 2.

Gọi Hn(n,a,b) là thủ tục chuyển n tầng tháp từ vị trí a sang vị trí b ¹ a, ta thấy:

-          Nếu n = 0: không phải làm gì;

-          Nếu n > 0 ta phải thực hiện ba bước sau:

·    Thoạt tiên chuyển n – 1 tầng tháp từ vị trí a sang vị trí c = 6 – a – b:

Hn(n-1,a,6-a-b)

·    Sau đó chuyển tầng lớn nhất từ vị trí a sang vị trí b:

a ® b

·    Cuối cùng chuyển n – 1 tầng tháp từ c sang b:

Hn(n-1,6-a-b,b)

Để ý rằng, do ta mã hoá các cọc là 1, 2 và 3 cho nên biết hai trong ba vị trí đó, là x, y chẳng hạn, ta dễ dàng tính được vị trí còn lại z theo hệ thức

z = 6–x–y

Thủ tục chuyển tháp n tầng từ cọc a sang cọc b được viết bằng Pascal như sau:

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

begin

if n = 0 then exit;

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

write(a, '->',b,' ');

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

end;

Chọn phương thức ghi tệp hoặc màn hình

Có thể chọn một trong hai cách ghi kết quả vào tệp văn bản hoặc hiển thị lên màn hình. Bạn chỉ cần lưu ý rằng màn hình được định nghĩa như là một tệp văn bản. Chính xác hơn là như sau. Trong Turbo Pascal vùng đệm màn hình, tức là nơi chứa dữ liệu để xuất ra màn hình, được định nghĩa dưới dạng một tệp. Nếu ta mở một tệp với tên rỗng như sau:

assign(f,'');

rewrite(f);

trong đó f là biến kiểu tệp văn bản được khai báo như sau

var f: text;

thì sau đó mọi lệnh

write(f,…);

sẽ xuất dữ liệu ra màn hình.

Ngược lại, khi tên tệp trong lệnh mở tệp nói trên khác rỗng, thí dụ:

assign(f,'hanoi.out');

rewrite(f);

thì sau đó mọi lệnh

write(f,…);

sẽ ghi dữ liệu vào tệp hanoi.out trên đĩa.

Chương trình hoàn chỉnh dưới đây sẽ ghi kết quả vào tệp văn bản hanoi.out được mở trên đĩa. Trước khi ghi chính thức, bạn hãy chạy thử chương trình với lệnh mở tệp có tên rỗng để kiểm tra kết quả trên màn hình. Sau khi thấy ưng ý, bạn hãy viết tên tệp cụ thể để lưu kết quả vào đĩa.

Chương trình sử dụng biến đếm d nhằm đếm số bước chuyển.

(*   Pascal   *)

uses crt;

var d: longint;

f: text;

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

begin

if n = 0 then exit;

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

inc(d);

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

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

end;

procedure runHn(n: byte);

begin

d :=  0;

assign(f,'hanoi.out');

rewrite(f);

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

Hn(n,1,2);

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

close(f);

readln;

end;

BEGIN

runHn(3);

END.

Khi thực hiện chương trình Hanoi.pas với n = 3 ta thu được kết quả sau:

1. 1 -> 2

2. 1 -> 3

3. 2 -> 3

4. 1 -> 2

5. 3 -> 1

6. 3 -> 2

7. 1 -> 2

Total: 7 step(s)