Bài toán Tháp Hà Nội là một bài toán trong lĩnh vực giải thuật. Bài toán được đặt tên theo tên của thành phố Hà Nội, nơi được cho là nơi phát minh ra trò chơi này.
Mô tả bài toán:
Bài toán gồm 3 cột (đóng vai trò như 3 chỗ đặt đĩa), n đĩa được đánh số từ 1 đến n, có kích thước khác nhau, đặt trên cột 1 sao cho đĩa nhỏ ở trên và đĩa lớn ở dưới. Yêu cầu di chuyển toàn bộ n đĩa từ cột 1 sang cột 3 sao cho không đặt đĩa lớn hơn lên đĩa nhỏ hơn trong quá trình di chuyển các đĩa.
Giải thuật:
- Bước 1: Di chuyển n-1 đĩa từ cột 1 sang cột 2.
- Bước 2: Di chuyển đĩa thứ n từ cột 1 sang cột 3.
- Bước 3: Di chuyển n-1 đĩa từ cột 2 sang cột 3.
Với n > 1, các bước 1 và 3 được thực hiện bằng cách đệ quy với n - 1 thay cho n.