Tổng quan
Tháp Hà Nội được nhà toán học người Pháp Édouard Lucas phát minh năm 1883, gắn với truyền thuyết về các nhà sư di chuyển 64 chiếc đĩa vàng. Đây là minh họa thuần túy nhất về đệ quy: lời giải cho n đĩa được xây hoàn toàn từ lời giải cho n−1.
Bạn chỉ được chuyển đĩa trên cùng của một cọc và không bao giờ được đặt đĩa lớn lên đĩa nhỏ, vậy mà cả chồng đĩa luôn có thể được dời đi — và luôn với cùng một số bước tối thiểu đã được chứng minh.
Cách giải Tháp Hà Nội từng bước
- Nghĩ theo kiểu đệ quy: để chuyển n đĩa từ A sang C, trước hết dời n−1 đĩa trên cùng sang B.
- Chuyển đĩa lớn nhất trực tiếp từ A sang C.
- Chuyển n−1 đĩa từ B sang C, đặt lên trên đĩa lớn nhất.
- Mỗi lượt con n−1 đó lại là cùng bài toán nhỏ hơn một cỡ, cứ thế xuống đến một đĩa duy nhất (trường hợp cơ sở).
Mấu chốt
Giải n đĩa cần đúng 2ⁿ − 1 bước, vì T(n) = 2·T(n−1) + 1. Mỗi đĩa thêm vào nhân đôi khối lượng công việc — minh họa sống động về tăng trưởng theo hàm mũ từ một quy tắc cực kỳ đơn giản.
Biến thể & liên hệ
- Đây là ví dụ chuẩn để dạy đệ quy và ngăn xếp lời gọi trong các khóa học lập trình.
- Cũng có lời giải lặp dựa trên quy tắc đơn giản 'đĩa nhỏ nhất di chuyển ở mỗi lượt cách nhau một bước'.
- 64 đĩa trong truyền thuyết cần 2⁶⁴ − 1 bước — hơn 580 tỷ năm nếu mỗi giây một bước.
Câu hỏi thường gặp
Vì sao đúng 2ⁿ − 1 bước?
Vì chuyển n đĩa nghĩa là chuyển n−1 hai lần cộng đĩa lớn nhất một lần: T(n) = 2·T(n−1) + 1 với T(1) = 1, giải ra 2ⁿ − 1.
Đây có phải quay lui không?
Không — đây là đệ quy thuần. Mỗi nước đi đều thuộc lời giải tối ưu, nên không có gì bị hoàn tác.