12. Tháp Hà Nội

Chắc hẳn bạn đã từng nghe về trò chơi “Tháp Hà Nội” – một trong những bài toán nổi tiếng nhất trong lĩnh vực đệ quy. Trò chơi này đòi hỏi sự khéo léo và sáng tạo để di chuyển một ngọn tháp gồm nhiều đĩa từ một cọc sang một cọc khác. Tuy đơn giản nhưng giải pháp cho trò chơi này lại không hề dễ dàng.

Nguyên Tắc Trò Chơi

Trò chơi “Tháp Hà Nội” gồm ba que di chuyển. Trên mỗi que được xếp chồng từ trên xuống dưới theo thứ tự giảm dần về kích thước đĩa, tức là đĩa lớn nhất ở dưới cùng và đĩa nhỏ nhất ở trên cùng. Các đĩa tạo thành một ngọn tháp hình nón.

Mục tiêu của trò chơi là di chuyển toàn bộ ngọn tháp từ một que sang que khác.

Các quy tắc sau phải được tuân thủ:

• Chỉ được di chuyển một đĩa mỗi lần.
• Chỉ có thể di chuyển đĩa trên cùng của một que.
• Đĩa trên cùng có thể được đặt lên một que khác nếu que đó trống hoặc đĩa trên cùng của que đó có kích thước lớn hơn đĩa đang di chuyển.

Số Lần Di Chuyển

Số lần di chuyển cần thiết để di chuyển một ngọn tháp gồm n đĩa có thể được tính bằng công thức: 2^n – 1.

Chương Trình Python Đệ Quy

Dưới đây là một đoạn mã Python đơn giản để giải trò chơi Tháp Hà Nội bằng phương pháp đệ quy:

def hanoi(n, source, helper, target):
    if n > 0:
        # Di chuyển một ngọn tháp có n-1 đĩa từ que gốc sang que trung gian
        hanoi(n - 1, source, target, helper)

        # Di chuyển đĩa lớn nhất từ que gốc sang que đích
        if source:
            target.append(source.pop())

        # Di chuyển ngọn tháp từ que trung gian sang que đích
        hanoi(n - 1, helper, source, target)

Hàm hanoi là một hiện thực của thuật toán được giới thiệu ở trên. Đầu tiên, chúng ta di chuyển một ngọn tháp có kích thước n-1 từ que gốc sang que trung gian bằng cách gọi đệ quy hanoi(n - 1, source, target, helper).

Sau đó, chỉ còn lại đĩa lớn nhất trên que gốc. Chúng ta di chuyển đĩa này sang que đích bằng cách sử dụng câu lệnh if source: target.append(source.pop()).

Cuối cùng, chúng ta di chuyển ngọn tháp từ que trung gian sang que đích bằng cách gọi đệ quy hanoi(n - 1, helper, source, target).

Trên đây là một giải pháp đệ quy để di chuyển một ngọn tháp có kích thước n. Thuật toán này sẽ kết thúc sau một số lần đệ quy hữu hạn, vì mỗi lần đệ quy sẽ làm giảm kích thước của ngọn tháp đi 1. Cuối cùng, chúng ta sẽ đạt được một ngọn tháp có kích thước n = 1, tức là chỉ việc di chuyển đĩa đơn giản.

Nếu bạn muốn xem các bước di chuyển trong quá trình đệ quy, bạn có thể chạy đoạn mã Python sau đây:

def hanoi(n, source, helper, target):
    if n > 0:
        # Di chuyển một ngọn tháp có n-1 đĩa từ que gốc sang que trung gian
        hanoi(n - 1, source, target, helper)

        # Di chuyển đĩa lớn nhất từ que gốc sang que đích
        if source:
            target.append(source.pop())

        # Di chuyển ngọn tháp từ que trung gian sang que đích
        hanoi(n - 1, helper, source, target)

source = [3, 2, 1]
helper = []
target = []

hanoi(len(source), source, helper, target)

Chúng ta đã thay đổi cấu trúc dữ liệu một chút. Thay vì chỉ truyền các ngăn xếp đĩa vào hàm, chúng ta truyền các bộ ba (tuple) vào hàm. Mỗi bộ ba bao gồm ngăn xếp và tên của ngăn xếp đó.

Hy vọng rằng bạn đã hiểu về trò chơi “Tháp Hà Nội” và sự quyến rũ của nó. Hãy thử phát triển một chương trình Python để giải trò chơi này và tận hưởng cảm giác thành công khi hoàn thành nhiệm vụ!