inthink.guide
Cửa hàngVề trang chủ

Chơi. Dự đoán. Hiểu cách giải.

Tháp Hà Nội

Chơi với 3–5 đĩa, xin gợi ý từ bàn hiện tại và hiểu chiến lược đệ quy qua hai bài animation ngắn. Bạn có thể mở lời giải từng bước bất cứ lúc nào.

Chơi Tháp Hà Nội
ABCĐĩa 44Đĩa 33Đĩa 22Đĩa 11

Chuyển chồng đĩa nhỏ sang bên để dọn đường cho đĩa lớn nhất.

Luật chơi Tháp Hà Nội

  1. Chuyển toàn bộ chồng đĩa từ cột A sang cột C.
  2. Mỗi lần chỉ chuyển một đĩa, lấy đĩa trên cùng của một cột.
  3. Không đặt đĩa lớn lên trên đĩa nhỏ.

Chơi Tháp Hà Nội

Chọn cột nguồn rồi chọn cột đích. Số trên đĩa biểu thị kích thước: 1 là nhỏ nhất. Bạn có thể quay lại một bước hoặc làm lại để thử cách khác.

0 bước
ABCĐĩa 33Đĩa 22Đĩa 11

Chọn cột nguồn rồi chọn cột đích.

Gợi ý dựa trên bàn hiện tại và không tự chuyển đĩa. Đi vòng đúng luật vẫn có thể giải tiếp.

Cách giải Tháp Hà Nội

Hãy xét đĩa lớn nhất trước. Trong ví dụ bốn đĩa này, ba đĩa nhỏ đang chắn nó. Giải bài toán nhỏ đó trước khi chuyển đĩa 4.

  1. Chuyển chồng đĩa nhỏ sang bên

    Chuyển đĩa 1, 2 và 3 từ A sang B, dùng C làm cột phụ. Giữ đĩa 4 ở A. Lúc này C trống và đĩa 4 đã lộ ra.

    ABCĐĩa 44Đĩa 33Đĩa 22Đĩa 11

  2. Chuyển đĩa lớn nhất

    Chuyển đĩa 4 từ A sang C. Một bước này đưa đĩa lớn nhất tới vị trí cuối cùng.

    ABCĐĩa 44Đĩa 33Đĩa 22Đĩa 11

  3. Đưa chồng đĩa nhỏ về đích

    Chuyển đĩa 1, 2 và 3 từ B sang C, dùng A làm cột phụ. Chúng nằm được trên đĩa 4 và bài toán hoàn thành.

    ABCĐĩa 44Đĩa 33Đĩa 22Đĩa 11

Mỗi chồng nhỏ dùng lại kế hoạch ba phần: chuyển các đĩa phía trên sang bên, chuyển đĩa lớn nhất của chồng, rồi đưa chồng nhỏ lên nó. Khi chỉ còn một đĩa, chuyển thẳng đĩa đó. Đây là đệ quy; vai trò cột nguồn, cột đích và cột phụ đổi theo từng bài toán nhỏ.

Học bằng cách dự đoán mục tiêu tiếp theo

Các ví dụ bốn đĩa riêng này giữ nguyên ván bạn đang chơi. Bạn có thể tạm dừng, xem từng bước, trả lời dự đoán hoặc mở giải thích.

1. Dọn đường cho đĩa lớn nhất

Xem ba đĩa nhỏ nhường chỗ cho đĩa 4. Dự đoán chúng phải nằm ở đâu trước khi chuyển đĩa lớn nhất.

Ví dụ riêng với bốn đĩa

Mục tiêu: chuyển 3 đĩa từ A sang B, dùng C làm cột phụ.

ABCĐĩa 44Đĩa 33Đĩa 22Đĩa 11

Dọn đường trước: chuyển ba đĩa phía trên từ A sang B.

Bước 0 / 8

2. Lặp lại bài toán nhỏ

Đĩa 4 đã ở C. Công việc còn lại là cùng bài toán với ba đĩa và vai trò các cột đã đổi.

Ví dụ riêng với bốn đĩa

Mục tiêu: chuyển 3 đĩa từ B sang C, dùng A làm cột phụ.

ABCĐĩa 44Đĩa 33Đĩa 22Đĩa 11

Giữ đĩa 4 ở C. Giờ giải bài toán ba đĩa từ B sang C.

Để chuyển ba đĩa từ B sang C qua cột phụ A, đĩa 1 nên đi đâu trước?

Bước 0 / 7

Lời giải từng bước

Các ví dụ bắt đầu với toàn bộ đĩa ở A và kết thúc ở C. Mở trực tiếp bất kỳ ví dụ nào; ván của bạn vẫn giữ nguyên.

Số bước tối thiểu

T(n) = 2T(n − 1) + 1 = 2ⁿ − 1

Lời giải chuẩn chuyển chồng nhỏ hai lần và đĩa lớn nhất một lần, nên T(n) = 2T(n − 1) + 1. Một đĩa cần một bước; vì vậy số bước tối thiểu cho n đĩa là 2ⁿ − 1.

3 đĩa: 7 bước. 4 đĩa: 15 bước. 5 đĩa: 31 bước.

3 đĩa — 7 bước

Trạng thái đầu: mọi đĩa ở A; đích: C. Đĩa 1 là nhỏ nhất.

  1. Chuyển đĩa 1 từ A sang C.
  2. Chuyển đĩa 2 từ A sang B.
  3. Chuyển đĩa 1 từ C sang B.
  4. Chuyển đĩa 3 từ A sang C.
  5. Chuyển đĩa 1 từ B sang A.
  6. Chuyển đĩa 2 từ B sang C.
  7. Chuyển đĩa 1 từ A sang C.
4 đĩa — 15 bước

Trạng thái đầu: mọi đĩa ở A; đích: C. Đĩa 1 là nhỏ nhất.

  1. Chuyển đĩa 1 từ A sang B.
  2. Chuyển đĩa 2 từ A sang C.
  3. Chuyển đĩa 1 từ B sang C.
  4. Chuyển đĩa 3 từ A sang B.
  5. Chuyển đĩa 1 từ C sang A.
  6. Chuyển đĩa 2 từ C sang B.
  7. Chuyển đĩa 1 từ A sang B.
  8. Chuyển đĩa 4 từ A sang C.
  9. Chuyển đĩa 1 từ B sang C.
  10. Chuyển đĩa 2 từ B sang A.
  11. Chuyển đĩa 1 từ C sang A.
  12. Chuyển đĩa 3 từ B sang C.
  13. Chuyển đĩa 1 từ A sang B.
  14. Chuyển đĩa 2 từ A sang C.
  15. Chuyển đĩa 1 từ B sang C.
5 đĩa — 31 bước

Trạng thái đầu: mọi đĩa ở A; đích: C. Đĩa 1 là nhỏ nhất.

  1. Chuyển đĩa 1 từ A sang C.
  2. Chuyển đĩa 2 từ A sang B.
  3. Chuyển đĩa 1 từ C sang B.
  4. Chuyển đĩa 3 từ A sang C.
  5. Chuyển đĩa 1 từ B sang A.
  6. Chuyển đĩa 2 từ B sang C.
  7. Chuyển đĩa 1 từ A sang C.
  8. Chuyển đĩa 4 từ A sang B.
  9. Chuyển đĩa 1 từ C sang B.
  10. Chuyển đĩa 2 từ C sang A.
  11. Chuyển đĩa 1 từ B sang A.
  12. Chuyển đĩa 3 từ C sang B.
  13. Chuyển đĩa 1 từ A sang C.
  14. Chuyển đĩa 2 từ A sang B.
  15. Chuyển đĩa 1 từ C sang B.
  16. Chuyển đĩa 5 từ A sang C.
  17. Chuyển đĩa 1 từ B sang A.
  18. Chuyển đĩa 2 từ B sang C.
  19. Chuyển đĩa 1 từ A sang C.
  20. Chuyển đĩa 3 từ B sang A.
  21. Chuyển đĩa 1 từ C sang B.
  22. Chuyển đĩa 2 từ C sang A.
  23. Chuyển đĩa 1 từ B sang A.
  24. Chuyển đĩa 4 từ B sang C.
  25. Chuyển đĩa 1 từ A sang C.
  26. Chuyển đĩa 2 từ A sang B.
  27. Chuyển đĩa 1 từ C sang B.
  28. Chuyển đĩa 3 từ A sang C.
  29. Chuyển đĩa 1 từ B sang A.
  30. Chuyển đĩa 2 từ B sang C.
  31. Chuyển đĩa 1 từ A sang C.

Nếu bàn của tôi khác lời giải mẫu thì sao?

Mọi cấu hình tuân thủ thứ tự kích thước đều có thể đi tới C. Trở lại trạng thái cũ là đi vòng, không phải bế tắc. Công thức trên áp dụng cho chồng ban đầu; nó không phải số bước còn lại từ một bàn bất kỳ. Dùng gợi ý để tìm bước tiếp theo từ bàn thực tế của bạn.

Puzzles →