Trình mô phỏng Tháp Hà Nội

Cách dùng

1. 1 Nhấn Run để xem lời giải đệ quy di chuyển từng đĩa từ cọc A sang cọc C.
2. 2 Đĩa lớn hơn không bao giờ được đặt lên đĩa nhỏ hơn — quan sát quy tắc này được giữ đúng ở mọi bước.
3. 3 Dùng Shuffle để đổi số lượng đĩa, hoặc bước qua từng nước đi một.
4. 4 Số bước tối thiểu cho n đĩa là 2ⁿ − 1.

Vì sao dùng công cụ này

• Nhìn thấy phép đệ quy kinh điển: chuyển n−1 đĩa sang cọc phụ, di chuyển đĩa lớn nhất, rồi chuyển chúng trở lại.
• Hiểu vì sao số bước di chuyển tăng gấp đôi với mỗi đĩa thêm vào (2ⁿ − 1).
• Một ví dụ nhập môn hoàn hảo về phân rã bài toán đệ quy.
• Chạy hoàn toàn trên trình duyệt của bạn. Không cần đăng ký, không cần tải lên.

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

Trình mô phỏng Tháp Hà Nội là gì?

Trình mô phỏng Tháp Hà Nội minh họa lời giải đệ quy cho bài toán kinh điển ba cọc: để di chuyển n đĩa, nó chuyển n−1 đĩa sang cọc phụ, di chuyển đĩa lớn nhất, rồi chuyển n−1 đĩa đó trở lại — không bao giờ đặt đĩa lớn hơn lên đĩa nhỏ hơn, trong 2ⁿ−1 bước.

Tính năng

Ví dụ

3 disks

2³ − 1 = 7 moves (optimal)

Trường hợp sử dụng

1. 1

   Học về đệ quy

   Xem cách bài toán được rút gọn thành hai bài toán con nhỏ hơn.

2. 2

   Hiểu về tăng trưởng theo cấp số nhân

   Theo dõi số bước di chuyển tăng gấp đôi mỗi khi thêm một đĩa (2ⁿ − 1).

3. 3

   Dạy về chia để trị

   Minh họa một cách phân rã đệ quy rõ ràng.

Tài liệu tham khảo

• Tháp Hà Nội — Wolfram MathWorld — Wolfram MathWorld
• Tháp Hà Nội — Wikipedia

Công cụ liên quan