Bài toán Tháp Hà Nội (Tower of Hanoi)

Tháp Hà Nội (Tower of Hanoi) là gì?

Bài toán Tháp Hà Nội (Tower of Hanoi) là một trò chơi toán học bao gồm 3 cột và với số đĩa nhiều hơn 1.

Dưới đây là hình minh họa bài toán Tháp Hà Nội (Tower of Hanoi) với trường hợp có 3 đĩa.

Các đĩa có kích cỡ khác nhau và xếp theo tự tự tăng dần về kích cỡ từ trên xuống: đĩa nhỏ hơn ở trên đĩa lớn hơn. Với số đĩa khác nhau thì ta có các bài toán Tháp Hà Nội (Tower of Hanoi) khác nhau, tuy nhiên lời giải cho các bài toán này là tương tự nhau. Lời giải tối ưu cho bài toán Tháp Hà Nội (Tower of Hanoi) là khi trò chơi chỉ có 3 cọc. Với số cọc lớn hơn thì lời giải bài toán vẫn chưa được khẳng định.

Qui tắc trò chơi toán học Tháp Hà Nội (Tower of Hanoi)

Nhiệm vụ của trò chơi là di chuyển các đĩa có kích cỡ khác nhau sang cột khác sao cho vẫn đảm bảo thứ tự ban đầu của các đĩa: đĩa nhỏ nằm trên đĩa lớn. Dưới đây là một số qui tắc cho trò chơi toán học Tháp Hà Nội (Tower of Hanoi):

Mỗi lần chỉ có thể di chuyển một đĩa từ cột này sang cột khác.

Chỉ được di chuyển đĩa nằm trên cùng (không được di chuyển các đĩa nằm giữa).
Đĩa có kích thước lớn hơn không thể được đặt trên đĩa có kích thước nhỏ hơn.

Dưới đây là hình minh họa cách giải bài toán Tháp Hà Nội (Tower of Hanoi) với trường hợp có 3 đĩa.

Bài toán Tháp Hà Nội (Tower of Hanoi) với số đĩa là n có thể được giải với số bước tối thiểu là 2n−1. Do đó, với trường hợp 3 đĩa, bài toán Tháp Hà Nội (Tower of Hanoi) có thể được giải sau 23−1 = 7 bước.

Giải thuật cho bài toán Tháp Hà Nội (Tower of Hanoi)

Để viết giải thuật cho trò chơi toán học Tháp Hà Nội (Tower of Hanoi), đầu tiên chúng ta cần tìm hiểu cách giải bài toán với số đĩa là 1 và 2. Chúng ta gán 3 cột với các tên là:

cotNguon: cột ban đầu chứa các đĩa

cotDich: cột cần di chuyển các đĩa tới

cotTrungGian: cột trung gian có mục đích làm trung gian trong quá trình di chuyển đĩa

Nếu chỉ có 1 đĩa, chúng ta chỉ cần di chuyển từ cotNguon tới cotDich.

Nếu có 2 đĩa:

Đầu tiên chúng ta di chuyển đĩa trên cùng (đĩa nhỏ nhất) tới cotTrungGian.

Sau đó chúng ta di chuyển đĩa ở dưới cùng (đĩa to hơn) tới cotDich.

Và cuối cùng di chuyển đĩa nhỏ nhất từ cotTrungGian về cotDich.

Từ hai giải thuật phần giải thuật trên chúng ta sẽ có giải thuật cho bài toán Tháp Hà Nội (Tower of Hanoi) cho 3 đĩa trở lên. Chúng ta chia ngăn xếp các đĩa thành hai phần: đĩa thứ lớn nhất (đĩa thứ n) là phần thứ nhất và (n-1) đĩa còn lại là phần thứ hai.

Mục đích của chúng ta là di chuyển đĩa thứ n từ cotNguon tới cotDich và sau đó đặt tất cả (n-1) đĩa còn lại lên trên nó. Bây giờ chúng ta có thể tưởng tượng ra cách giải bài toán trên dựa vào đệ qui theo các bước sau:

Bước 1: Di chuyển n-1 đĩa từ cotNguon tới cotTrungGian
Bước 2: Di chuyển đĩa thứ n từ cotNguon tới cotDich
Bước 3: Di chuyển n-1 đĩa từ cotTrungGian về cotDich

Giải thuật đệ qui cho bài toán Tháp Hà Nội (Tower of Hanoi) là:

Bắt đầu giải thuật Tháp Hà nội Hanoi(disk, cotNguon, cotDich, cotTrungGian)

   IF disk == 0, thì
      di chuyển đĩa từ cotNguon tới cotDich             
   ELSE
      Hanoi(disk - 1, cotNguon, cotTrungGian, cotDich)     // Bước 1
      di chuyển đĩa từ cotNguon tới cotDich           // Bước 2
      Hanoi(disk - 1, cotTrungGian, cotDich, cotNguon)     // Bước 3
   Kết thúc IF
   
Kết thúc giải thuật

Theo Tutorialspoint

Bài trước: Khái niệm cơ bản về đệ qui (Recursion)

Bài tiếp: Dãy Fibonacci trong Cấu trúc dữ liệu và giải thuật