Tài liệu Bài toán tháp Hà nội Cái nhìn từ Lý thuyết Độ phức tạp tính toán

Trong các sách báo về Toán học và Tin

học hiện đại, có một bài toán rất nổi tiếng,

mang tên Bài toán Tháp Hà nội, với nội

dung như sau:

Có n đĩa có lỗ ở giữa, kích thước

nhỏ dần, xếp chồng lên nhau ở cọc A, to ở

dưới, bé ở trên. Hãy tìm cách chuyển

chồng đĩa này sang cọc C với những điều

kiện sau:

1) Mỗi lần chỉ được chuyển 1 đĩa;

2) Không bao giờ được xếp đĩa to lên

trên đĩa con, dù chỉ là tạm thời;

3) Được phép dùng cọc B làm cọc trung

gian.









B C A

Hình 1



Trước hết ta tìm cách giải bài toán. Ta

có nhận xét:

a) Trường hợp n = 1 : Chuyển đĩa từ cọc

A → C.

b) Trường hợp n = 2 : Lần lượt chuyển

như sau:

ã Chuyển đĩa 1 từ cọc A → B;

ã Chuyển đĩa 2 từ cọc A → C;

ã Chuyển đĩa 1 từ cọc B → C.

Như vậy với n = 1, 2 bài toán coi như đã

biết cách giải.

Bây giờ giả sử ta đã biết cách giải bài

toán với n - 1 đĩa, khi đó chúng ta có thể

giải bài toán n đĩa như sau: