Bài viết sưu tầm

Bài toán tháp Hà Nội

Cho ba cọc 1, 2, 3. Ở cọc 1 ban đầu có n đĩa sắp xếp theo thứ tự to dần từ dưới lên trên. Hãy dịch chuyển n đĩa đó sang cọc thứ  3 sao cho:

-       Mỗi lần chỉ chuyển một đĩa.

-       Trong mỗi cọc không cho phép đĩa to nằm trên đĩa nhỏ hơn.

Bài toán xác định  khi biết được từng đĩa đang nằm ở cọc nào. Hay nói cách khác, có hai cách xác định:

1- Cọc 1 hiện đang chứa những đĩa nào? Cọc 2 hiện đang chứa những đĩa nào? Và cọc 3 đang chứa những đĩa nào.

2- Đĩa lớn thứ i hiện đang nàm ở cọc nào? ( i = 1 .. n )

Như vậy cách mô tả trạng thái bài toán không duy nhất, vấn đề là chọn cách mô tả nào để đạt được mục đích dễ dàng nhất.

Theo trên, với cách thứ nhất ta phải dùng 3 danh sách động vì số đĩa trên mỗi cọc là khác nhau trong từng thời điểm khác nhau.

Cách thứ hai, nhìn qua thì khó mô tả nhưng dựa vào khái niệm về bộ có thứ tự trong toán học, cách này mô tả bài toán hiệu quả hơn. Thật vậy, nếu gọi x_i là cọc chứa đĩa lớn thứ i, trong đó x_iÎ{1, 2, 3}, iÎ{1 ..n}. Khi đó bộ có thứ tự (x₁, x₂, . . ,x_n) có thể dùng làm dạng mô tả trạng thái đang xét của bài toán. Với cách mô tả này,

Trạng thái đầu là (1,1,. . .,1)

Trạng thái cuối là (3,3,. . .,3)