Bài toán Tháp Hà Nội (Tower of Hanoi): giải thích đệ quy, công thức 2ⁿ − 1, code C++ và Python

Phát biểu bài toán Tháp Hà Nội

Bài toán Tháp Hà Nội (Tower of Hanoi) được nhà toán học Pháp Édouard Lucas giới thiệu năm 1883. Bài toán có 3 chiếc cọc thẳng đứng là A (cọc nguồn), B (cọc trung gian) và C (cọc đích).

Ban đầu, trên cọc A có n chiếc đĩa tròn đánh số từ 1 (nhỏ nhất ở trên cùng) đến n (lớn nhất ở dưới đáy), xếp chồng nhỏ trên lớn dưới. Bạn cần chuyển toàn bộ n đĩa từ cọc A sang cọc C theo hai quy tắc:

1. Mỗi bước chỉ nhấc đúng 1 chiếc đĩa nằm ở trên cùng của một cọc sang cọc khác.
2. Tuyệt đối không đặt một chiếc đĩa lớn hơn nằm đè lên trên một chiếc đĩa nhỏ hơn.

Nếu dò từng bước rời rạc với n = 4 hay n = 5 đĩa, bạn sẽ rất dễ rối. Nhưng khi nhìn qua lăng kính của đệ quy, cấu trúc lời giải lại vô cùng mạch lạc.

Tư duy đệ quy 3 bước: Làm sao nhấc được đĩa lớn nhất ở đáy?

Hãy tự hỏi: Làm thế nào để chuyển được chiếc đĩa lớn nhất thứ n từ đáy cọc A sang đáy cọc C?

Vì đĩa thứ n lớn hơn mọi đĩa còn lại:

• Để nhấc được đĩa n khỏi cọc A, phía trên nó ở cọc A phải hoàn toàn trống (mọi đĩa từ 1 đến n - 1 phải rời khỏi A).
• Để đặt được đĩa n xuống cọc C, bản thân cọc C lúc đó cũng phải hoàn toàn trống (nếu C đang chứa bất kỳ đĩa nhỏ nào, đặt đĩa n lên sẽ phạm luật ngay!).

Cọc A và C đều không được chứa n - 1 đĩa nhỏ — vậy tất cả n - 1 đĩa nhỏ bắt buộc phải đang xếp chồng lên nhau trên cọc trung gian B! Nhận xét đó chia bài toán chuyển n đĩa từ nguon sang dich (nhờ cọc trungGian) thành 3 bước:

1. Bước 1 (Dọn đường): Gọi đệ quy chuyển khối n - 1 đĩa nhỏ từ cọc nguon (A) sang cọc trungGian (B), lấy dich (C) làm trung gian tạm.
2. Bước 2 (Chuyển đáy): Chuyển trực tiếp đĩa lớn nhất thứ n từ cọc nguon (A) sang cọc dich (C).
3. Bước 3 (Xếp lên đích): Gọi đệ quy chuyển khối n - 1 đĩa nhỏ từ cọc trungGian (B) sang đặt lên trên đĩa n ở cọc dich (C), lấy nguon (A) làm trung gian tạm.

Trong suốt Bước 3, chiếc đĩa thứ n nằm yên ở đáy cọc C. Vì nó lớn nhất, mọi đĩa từ 1 đến n - 1 đều đặt đè lên nó hợp lệ như thể cọc C đang trống!

Ví dụ từng bước với n = 3 đĩa

Hình dưới đây minh họa 4 mốc trạng thái chính khi giải Tháp Hà Nội với n = 3 đĩa (đĩa 1 xanh lá nhỏ nhất, đĩa 2 xanh dương, đĩa 3 cam lớn nhất):

Bảng liệt kê trọn vẹn 7 bước di chuyển của n = 3 đĩa từ cọc A sang cọc C:

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// Giải bài toán Tháp Hà Nội bằng đệ quy: chuyển n đĩa từ cọc nguồn sang cọc đích
void thapHaNoi(int n, char nguon, char trungGian, char dich, vector<string>& cacBuoc) {
    if (n == 0) return;

    // Bước 1: Chuyển n - 1 đĩa nhỏ phía trên từ cọc nguồn sang cọc trung gian
    thapHaNoi(n - 1, nguon, dich, trungGian, cacBuoc);

    // Bước 2: Chuyển đĩa lớn nhất thứ n từ cọc nguồn sang cọc đích
    cacBuoc.push_back(to_string(n) + ":" + nguon + "->" + dich);

    // Bước 3: Chuyển n - 1 đĩa từ cọc trung gian sang cọc đích
    thapHaNoi(n - 1, trungGian, nguon, dich, cacBuoc);
}

int main() {
    for (int n : {1, 2, 3}) {
        vector<string> cacBuoc;
        thapHaNoi(n, 'A', 'B', 'C', cacBuoc);
        cout << cacBuoc.size() << ":";
        for (const string& b : cacBuoc) cout << " " << b;
        cout << "\n";
    }
    return 0;
}

def thap_ha_noi(n, nguon="A", trung_gian="B", dich="C", cac_buoc=None):
    """Giải bài toán Tháp Hà Nội bằng đệ quy, trả về danh sách các bước chuyển."""
    if cac_buoc is None:
        cac_buoc = []
    if n == 0:
        return cac_buoc

    # Bước 1: Chuyển n - 1 đĩa nhỏ từ cọc nguồn sang cọc trung gian
    thap_ha_noi(n - 1, nguon, dich, trung_gian, cac_buoc)

    # Bước 2: Chuyển đĩa lớn nhất thứ n từ cọc nguồn sang cọc đích
    cac_buoc.append(f"{n}:{nguon}->{dich}")

    # Bước 3: Chuyển n - 1 đĩa từ cọc trung gian sang cọc đích
    thap_ha_noi(n - 1, trung_gian, nguon, dich, cac_buoc)
    return cac_buoc


for n in (1, 2, 3):
    buoc = thap_ha_noi(n)
    print(f"{len(buoc)}:", *buoc)

Chứng minh vì sao Tháp Hà Nội cần đúng 2ⁿ − 1 bước

Gọi T(n) là số bước tối thiểu để chuyển n đĩa. Theo cấu trúc 3 bước: chuyển n - 1 đĩa nhỏ sang cọc trung gian tốn ít nhất T(n - 1) bước, chuyển đĩa thứ n tốn 1 bước, và chuyển n - 1 đĩa nhỏ về cọc đích tốn thêm T(n - 1) bước. Ta có hệ thức truy hồi: \[\begin{gathered} T(n) = 2 \cdot T(n - 1) + 1 \\ \text{với } T(0) = 0, \; T(1) = 1 \end{gathered}\]

Cộng 1 vào hai vế: \[\begin{aligned} T(n) + 1 &= 2 \cdot (T(n - 1) + 1) \\ &= 2^2 \cdot (T(n - 2) + 1) \\ &= \dots = 2^n \cdot (T(0) + 1) = 2^n \\ \implies T(n) &= 2^n - 1 \end{aligned}\]

Như vậy, độ phức tạp thuật toán để liệt kê các bước chuyển là O(2ⁿ) thời gian và O(n) bộ nhớ ngăn xếp:

Các thời gian trong bảng chỉ là phép chia số bước cho tốc độ giả định, không phải số đo thực tế; việc in từng bước còn có chi phí riêng. Năm được tính xấp xỉ 365 ngày.

Mối liên hệ bất ngờ giữa Tháp Hà Nội và Phép toán bit

Nếu viết số thứ tự bước k (1 .. 2ⁿ - 1) ở hệ nhị phân và áp dụng phép toán bit, chiếc đĩa được nhấc lên ở bước k chính là vị trí của bit 1 thấp nhất (tính từ 1) của k:

Hơn nữa, cọc đi và cọc đến ở bước k cũng tính được trực tiếp từ (k & (k - 1)) % 3 và ((k | (k - 1)) + 1) % 3 mà không cần đệ quy. Phải ánh xạ tên cọc theo tính chẵn lẻ của n: với n lẻ dùng chỉ số [A, B, C], với n chẵn dùng [A, C, B], đúng như code. Bản C++ dùng số nguyên 64-bit và chỉ liệt kê với n nhỏ; không dịch bit bằng hoặc lớn hơn độ rộng kiểu:

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// Tìm đĩa được chuyển ở bước thứ k dựa vào vị trí bit 1 thấp nhất của k
int diaChuyenOBuoc(int k) {
    int dia = 1;
    while ((k & 1) == 0) {
        k >>= 1;
        dia++;
    }
    return dia;
}

// Giải Tháp Hà Nội không đệ quy bằng phép toán bit
vector<string> thapHaNoiTheoBit(int n) {
    // Nếu n lẻ thì thứ tự 3 cọc là A-B-C; nếu n chẵn thì đổi chỗ B và C
    string coc = (n % 2 == 1) ? "ABC" : "ACB";
    vector<string> cacBuoc;
    int tongBuoc = (1 << n) - 1;

    for (int k = 1; k <= tongBuoc; k++) {
        int dia = diaChuyenOBuoc(k);
        char tu = coc[(k & (k - 1)) % 3];
        char den = coc[((k | (k - 1)) + 1) % 3];
        cacBuoc.push_back(to_string(dia) + ":" + tu + "->" + den);
    }
    return cacBuoc;
}

int main() {
    for (int n : {1, 2, 3}) {
        vector<string> cacBuoc = thapHaNoiTheoBit(n);
        cout << cacBuoc.size() << ":";
        for (const string& b : cacBuoc) cout << " " << b;
        cout << "\n";
    }
    return 0;
}

def dia_chuyen_o_buoc(k):
    """Tìm số hiệu đĩa chuyển ở bước thứ k dựa vào vị trí bit 1 thấp nhất."""
    dia = 1
    while (k & 1) == 0:
        k >>= 1
        dia += 1
    return dia


def thap_ha_noi_theo_bit(n):
    """Giải Tháp Hà Nội không đệ quy bằng phép toán bit."""
    coc = "ABC" if n % 2 == 1 else "ACB"
    cac_buoc = []
    for k in range(1, 1 << n):
        dia = dia_chuyen_o_buoc(k)
        tu = coc[(k & (k - 1)) % 3]
        den = coc[((k | (k - 1)) + 1) % 3]
        cac_buoc.append(f"{dia}:{tu}->{den}")
    return cac_buoc


for n in (1, 2, 3):
    buoc = thap_ha_noi_theo_bit(n)
    print(f"{len(buoc)}:", *buoc)

Lỗi hay gặp

Luyện ngay trên Big-O Coding

Bài Tháp Hà Nội (Premium) áp dụng trực tiếp lời giải của bài. Bài giai thừa/Fibonacci (Premium) luyện điều kiện dừng; bài Trái hoặc phải (miễn phí) là bài mở rộng về quy tắc sinh đệ quy, không phải bài Tháp Hà Nội. Hãy bắt đầu ở bài đúng trình độ:

Câu hỏi thường gặp

Nguồn tham khảo

• Graham, Knuth, Patashnik: Concrete Mathematics — Chapter 1: Recurrent Problems
• 3Blue1Brown: Binary, Hanoi and Sierpinski (Part 1)
• MIT 6.006 Introduction to Algorithms: Recursion & Mathematical Induction