inthink.guide
KedaiKembali ke laman utama

Main. Ramal. Faham.

Menara Hanoi

Main dengan 3–5 cakera, minta petunjuk mengikut kedudukan semasa dan pelajari strategi rekursif melalui dua animasi ringkas. Buka contoh langkah demi langkah apabila diperlukan.

Main Menara Hanoi
ABCCakera 44Cakera 33Cakera 22Cakera 11

Alihkan timbunan kecil untuk membebaskan cakera terbesar.

Peraturan Menara Hanoi

  1. Pindahkan seluruh timbunan dari tiang A ke C.
  2. Pindahkan satu cakera pada satu masa, sentiasa yang paling atas.
  3. Jangan letakkan cakera besar di atas yang lebih kecil.

Main Menara Hanoi

Pilih tiang asal kemudian destinasi. Nombor menunjukkan saiz: 1 paling kecil. Undur satu langkah atau mula semula untuk mencuba cara lain.

0 langkah
ABCCakera 33Cakera 22Cakera 11

Pilih tiang asal kemudian destinasi.

Petunjuk bermula daripada kedudukan semasa dan tidak menggerakkan cakera. Lencongan yang sah masih boleh diselesaikan.

Cara menyelesaikan Menara Hanoi

Fikirkan cakera terbesar dahulu. Dalam contoh empat cakera, tiga yang kecil menghalangnya. Selesaikan masalah kecil itu sebelum memindahkan cakera 4.

  1. Alihkan timbunan kecil

    Pindahkan cakera 1, 2 dan 3 dari A ke B menggunakan C sebagai tiang bantuan. Biarkan cakera 4 di A. Kini C kosong dan cakera 4 terdedah.

    ABCCakera 44Cakera 33Cakera 22Cakera 11

  2. Pindahkan cakera terbesar

    Pindahkan cakera 4 dari A ke C. Langkah ini meletakkannya di tempat akhir.

    ABCCakera 44Cakera 33Cakera 22Cakera 11

  3. Bawa timbunan kecil ke destinasi

    Pindahkan cakera 1, 2 dan 3 dari B ke C menggunakan A. Semuanya muat di atas cakera 4 dan teka-teki selesai.

    ABCCakera 44Cakera 33Cakera 22Cakera 11

Setiap timbunan kecil mengulang rancangan sama: alihkan cakera di atas yang terbesar, pindahkan cakera itu, kemudian bawa timbunan kecil ke atasnya. Untuk satu cakera, pindahkan terus. Inilah rekursi; peranan asal, destinasi dan bantuan berubah dalam setiap submasalah.

Belajar dengan meramal matlamat seterusnya

Contoh empat cakera ini berasingan dan tidak mengubah permainan anda. Jeda, lihat satu langkah, jawab ramalan atau buka penerangan.

1. Buka laluan untuk cakera terbesar

Lihat tiga cakera kecil memberi ruang kepada cakera 4. Ramalkan tempatnya sebelum cakera besar bergerak.

Contoh berasingan empat cakera

Matlamat: pindahkan 3 cakera dari A ke B, menggunakan C sebagai bantuan.

ABCCakera 44Cakera 33Cakera 22Cakera 11

Buka laluan dahulu: pindahkan tiga cakera atas dari A ke B.

Langkah 0 daripada 8

2. Ulang masalah lebih kecil

Cakera 4 sudah di C. Baki tugas ialah masalah tiga cakera dengan peranan tiang baharu.

Contoh berasingan empat cakera

Matlamat: pindahkan 3 cakera dari B ke C, menggunakan A sebagai bantuan.

ABCCakera 44Cakera 33Cakera 22Cakera 11

Cakera 4 kekal di C. Kini selesaikan tiga cakera dari B ke C.

Untuk memindahkan tiga cakera dari B ke C menggunakan A, ke mana cakera 1 pergi dahulu?

Langkah 0 daripada 7

Penyelesaian langkah demi langkah

Contoh bermula dengan semua cakera di A dan berakhir di C. Buka terus; permainan anda kekal.

Bilangan langkah minimum

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

Penyelesaian biasa memindahkan timbunan kecil dua kali dan cakera terbesar sekali: T(n) = 2T(n − 1) + 1. Satu cakera memerlukan satu langkah, maka minimum bagi n cakera ialah 2ⁿ − 1.

3 cakera: 7 langkah. 4 cakera: 15 langkah. 5 cakera: 31 langkah.

3 cakera — 7 langkah

Mula: semua cakera di A. Destinasi: C. Cakera 1 paling kecil.

  1. Pindahkan cakera 1 dari A ke C.
  2. Pindahkan cakera 2 dari A ke B.
  3. Pindahkan cakera 1 dari C ke B.
  4. Pindahkan cakera 3 dari A ke C.
  5. Pindahkan cakera 1 dari B ke A.
  6. Pindahkan cakera 2 dari B ke C.
  7. Pindahkan cakera 1 dari A ke C.
4 cakera — 15 langkah

Mula: semua cakera di A. Destinasi: C. Cakera 1 paling kecil.

  1. Pindahkan cakera 1 dari A ke B.
  2. Pindahkan cakera 2 dari A ke C.
  3. Pindahkan cakera 1 dari B ke C.
  4. Pindahkan cakera 3 dari A ke B.
  5. Pindahkan cakera 1 dari C ke A.
  6. Pindahkan cakera 2 dari C ke B.
  7. Pindahkan cakera 1 dari A ke B.
  8. Pindahkan cakera 4 dari A ke C.
  9. Pindahkan cakera 1 dari B ke C.
  10. Pindahkan cakera 2 dari B ke A.
  11. Pindahkan cakera 1 dari C ke A.
  12. Pindahkan cakera 3 dari B ke C.
  13. Pindahkan cakera 1 dari A ke B.
  14. Pindahkan cakera 2 dari A ke C.
  15. Pindahkan cakera 1 dari B ke C.
5 cakera — 31 langkah

Mula: semua cakera di A. Destinasi: C. Cakera 1 paling kecil.

  1. Pindahkan cakera 1 dari A ke C.
  2. Pindahkan cakera 2 dari A ke B.
  3. Pindahkan cakera 1 dari C ke B.
  4. Pindahkan cakera 3 dari A ke C.
  5. Pindahkan cakera 1 dari B ke A.
  6. Pindahkan cakera 2 dari B ke C.
  7. Pindahkan cakera 1 dari A ke C.
  8. Pindahkan cakera 4 dari A ke B.
  9. Pindahkan cakera 1 dari C ke B.
  10. Pindahkan cakera 2 dari C ke A.
  11. Pindahkan cakera 1 dari B ke A.
  12. Pindahkan cakera 3 dari C ke B.
  13. Pindahkan cakera 1 dari A ke C.
  14. Pindahkan cakera 2 dari A ke B.
  15. Pindahkan cakera 1 dari C ke B.
  16. Pindahkan cakera 5 dari A ke C.
  17. Pindahkan cakera 1 dari B ke A.
  18. Pindahkan cakera 2 dari B ke C.
  19. Pindahkan cakera 1 dari A ke C.
  20. Pindahkan cakera 3 dari B ke A.
  21. Pindahkan cakera 1 dari C ke B.
  22. Pindahkan cakera 2 dari C ke A.
  23. Pindahkan cakera 1 dari B ke A.
  24. Pindahkan cakera 4 dari B ke C.
  25. Pindahkan cakera 1 dari A ke C.
  26. Pindahkan cakera 2 dari A ke B.
  27. Pindahkan cakera 1 dari C ke B.
  28. Pindahkan cakera 3 dari A ke C.
  29. Pindahkan cakera 1 dari B ke A.
  30. Pindahkan cakera 2 dari B ke C.
  31. Pindahkan cakera 1 dari A ke C.

Bagaimana jika kedudukan saya berbeza?

Setiap kedudukan yang mematuhi saiz boleh sampai ke C. Kedudukan berulang ialah gelung, bukan jalan buntu. Formula tadi untuk permulaan biasa, bukan baki langkah bagi kedudukan sebarang. Gunakan petunjuk untuk papan semasa.

Teka-teki →