[Mỗi ngày 1 thuật toán] Bài toán Tháp Hà Nội – Hanoi Tower

Để hưởng ứng sức nóng của chuỗi series “Mỗi ngày 1 thuật toán”, CodeGym sẽ đem đến cho bạn lời giải chi tiết cho bài toán kinh điển – Tháp Hà Nội. Không chỉ cung cấp mã nguồn Java, Python, bài viết dưới đây còn trình bày mã nguồn dạng Pseudo-code. Điều này giúp người đọc có cái nhìn rõ ràng hơn về giải thuật.

1. Ý tưởng chính của bài toán Tháp Hà Nội

Thuật toán Tháp Hà Nội (Hanoi Tower) là một bài toán cổ điển trong khoa học máy tính, được đề cập lần đầu tiên vào năm 1883. Bài toán Tháp Hà Nội như sau:

• Có 3 cọc (A, B, C)
• Trên cọc A có n đĩa (các đĩa có kích thước khác nhau, lớn nhất ở dưới, nhỏ nhất ở trên)
• Mục tiêu là chuyển toàn bộ n đĩa từ cọc A sang cọc C, với điều kiện:
  • Chỉ được chuyển 1 đĩa tại một thời điểm
  • Không được đặt một đĩa lớn hơn lên trên một đĩa nhỏ hơn

2. Thuật toán giải quyết 

• Di chuyển n – 1 đĩa từ cọc A sang cọc B (sử dụng cọc C làm trung gian)
• Di chuyển đĩa lớn nhất từ cọc A sang cọc C
• Di chuyển n – 1 đĩa từ cọc B sang cọc C (sử dụng cọc A làm trung gian)
• Độ phức tạp của thuật toán này là: 2^n – 1 bước di chuyển.

3. Hình ảnh minh hoạ bài toán Hanoi Tower với 3 đĩa

4. Hình ảnh minh hoạ bài toán Hanoi Tower với 4 đĩa

5. Mã nguồn Pseudo-code

• Hàm hanoi(n, fromPeg, auxPeg, toPeg) là hàm đệ quy để giải quyết bài toán Tháp Hà Nội với n đĩa.
• Nếu n = 1, chỉ cần di chuyển đĩa từ fromPeg sang toPeg bằng cách gọi hàm moveDisk().
• Nếu n > 1, thực hiện ba bướ c:
  • Di chuyển n-1 đĩa từ fromPeg sang auxPeg bằng cách gọi đệ quy hanoi(n-1, fromPeg, toPeg, auxPeg).
  • Di chuyển đĩa lớn nhất từ fromPeg sang toPeg bằng cách gọi hàm moveDisk().
  • Di chuyển n-1 đĩa từ auxPeg sang toPeg bằng cách gọi đệ quy hanoi(n-1, auxPeg, fromPeg, toPeg).
• Hàm moveDisk(fromPeg, toPeg) di chuyển đĩa từ fromPeg sang toPeg.

6. Mã nguồn Java

7. Mã nguồn Python