Giải Bài toán Tháp Hà Nội bằng Đệ quy: Một câu đố hấp dẫn và thú vị!

Bài toán Tháp Hà Nội là một câu đố kinh điển mà chúng ta có thể giải bằng phương pháp đệ quy. Câu đố này bao gồm ba cột và một số đĩa có kích thước khác nhau, có thể đặt lên bất kỳ cột nào. Ban đầu, các đĩa được xếp thành chồng trên một cột theo thứ tự kích thước tăng dần, với đĩa nhỏ nhất ở trên cùng, tạo thành một hình nón.

Mục tiêu của câu đố là di chuyển toàn bộ các đĩa sang một cột khác, theo các quy tắc đơn giản sau:

  • Chỉ có thể di chuyển một đĩa mỗi lần.
  • Mỗi lần di chuyển, chúng ta lấy một đĩa từ một cột nguồn và đặt nó lên một cột đích. Cột đích có thể đã có sẵn các đĩa.
  • Không được đặt đĩa lớn hơn lên đĩa nhỏ hơn.
  • Có thể chuyển đĩa vào cột trung gian miễn là tuân thủ ba quy tắc trên.
    Hanoi Tower

Giải bằng cách suy nghĩ trước khi viết code

Để dễ hiểu hơn các bước giải quyết, chúng ta sẽ xem xét một ví dụ cụ thể. Giả sử chúng ta có 3 cột A, B, C đại diện cho 3 tháp và 3 đĩa. Ảnh dưới đây cho thấy trạng thái ban đầu.
Hanoi Tower 1

Để di chuyển toàn bộ 3 đĩa từ cột A sang cột C, bạn cần thực hiện các bước sau:

  • Chuyển đĩa 1 và 2 sang cột trung gian B.
  • Di chuyển đĩa 3 sang cột C.
  • Chuyển đĩa 1 và 2 sang cột C.

Bước 1: Di chuyển đĩa 1 từ cột A sang cột C

Hanoi Tower 2

Bước 2: Di chuyển đĩa 2 từ cột A sang cột B

Hanoi Tower 3

Bước 3: Di chuyển đĩa 1 từ cột C sang cột B

Mục đích của bước này là để dành chỗ trống trên cột C để di chuyển đĩa 3 từ cột A sang.
Hanoi Tower 4

Bước 4: Di chuyển đĩa 3 từ cột A sang cột C

Hanoi Tower 5

Bước 5: Di chuyển đĩa 1 từ cột B sang cột A

Hanoi Tower 6

Bước 6: Di chuyển đĩa 2 từ cột B sang cột C

Hanoi Tower 7

Bước 7: Di chuyển đĩa 1 từ cột A sang cột C

Khi hoàn tất bước này, chúng ta đã hoàn thành nhiệm vụ.
Hanoi Tower 8

Thuật toán đệ quy

Để giải bài toán Tháp Hà Nội, chúng ta có thể sử dụng thuật toán đệ quy với các bước sau:

  1. Di chuyển n-1 đĩa trên cùng từ cột nguồn sang cột trung gian.
  2. Di chuyển đĩa thứ n từ cột nguồn sang cột đích.
  3. Di chuyển n-1 đĩa từ cột trung gian sang cột đích, sử dụng cột nguồn làm trung gian.
  4. Trường hợp cơ bản của đệ quy là khi chỉ có một đĩa để di chuyển. Trong trường hợp này, chúng ta chỉ cần di chuyển đĩa từ cột nguồn sang cột đích.

Có thể viết thuật toán này dưới dạng hàm trong unit test bằng JUnit5.

Kết quả in ra màn hình các bước di chuyển