inthink.guide
TokoKembali ke beranda

Mainkan. Prediksi. Pahami.

Menara Hanoi

Mainkan 3–5 cakram, minta petunjuk berdasarkan posisi saat ini, dan pelajari strategi rekursif lewat dua animasi singkat. Buka contoh langkah demi langkah kapan saja.

Main Menara Hanoi
ABCCakram 44Cakram 33Cakram 22Cakram 11

Pindahkan tumpukan kecil untuk membebaskan cakram terbesar.

Aturan Menara Hanoi

  1. Pindahkan seluruh tumpukan dari tiang A ke C.
  2. Pindahkan satu cakram setiap langkah, selalu dari bagian paling atas.
  3. Jangan letakkan cakram besar di atas cakram yang lebih kecil.

Main Menara Hanoi

Pilih tiang asal lalu tujuan. Angka menunjukkan ukuran: 1 paling kecil. Batalkan langkah atau mulai ulang untuk mencoba cara lain.

0 langkah
ABCCakram 33Cakram 22Cakram 11

Pilih tiang asal, lalu tujuan.

Petunjuk memakai posisi saat ini dan tidak memindahkan cakram. Jalan memutar yang sah tetap dapat diselesaikan.

Cara menyelesaikan Menara Hanoi

Pikirkan cakram terbesar dahulu. Pada contoh empat cakram, tiga cakram kecil menghalanginya. Selesaikan masalah kecil itu sebelum memindahkan cakram 4.

  1. Sisihkan tumpukan kecil

    Pindahkan cakram 1, 2, dan 3 dari A ke B dengan C sebagai bantuan. Biarkan cakram 4 di A. Kini C kosong dan cakram 4 terbuka.

    ABCCakram 44Cakram 33Cakram 22Cakram 11

  2. Pindahkan cakram terbesar

    Pindahkan cakram 4 dari A ke C. Satu langkah ini menaruhnya di posisi akhir.

    ABCCakram 44Cakram 33Cakram 22Cakram 11

  3. Bawa tumpukan kecil ke tujuan

    Pindahkan cakram 1, 2, dan 3 dari B ke C dengan bantuan A. Semuanya dapat diletakkan di atas cakram 4 dan teka-teki selesai.

    ABCCakram 44Cakram 33Cakram 22Cakram 11

Setiap tumpukan kecil memakai rencana yang sama: sisihkan cakram di atas yang terbesar, pindahkan cakram besar itu, lalu bawa tumpukan kecil ke atasnya. Untuk satu cakram, pindahkan langsung. Inilah rekursi; peran tiang asal, tujuan, dan bantuan berubah pada tiap submasalah.

Belajar dengan memprediksi tujuan berikutnya

Contoh empat cakram ini terpisah dari permainanmu. Jeda, lihat satu langkah, jawab prediksi, atau buka penjelasan.

1. Buka jalan untuk cakram terbesar

Lihat tiga cakram kecil memberi ruang bagi cakram 4. Prediksi tempatnya sebelum cakram besar bergerak.

Contoh empat cakram terpisah

Tujuan: pindahkan 3 cakram dari A ke B, dengan bantuan C.

ABCCakram 44Cakram 33Cakram 22Cakram 11

Buka jalan dahulu: pindahkan tiga cakram teratas dari A ke B.

Langkah 0 dari 8

2. Ulangi masalah yang lebih kecil

Cakram 4 sudah di C. Sisanya adalah masalah tiga cakram dengan peran tiang berbeda.

Contoh empat cakram terpisah

Tujuan: pindahkan 3 cakram dari B ke C, dengan bantuan A.

ABCCakram 44Cakram 33Cakram 22Cakram 11

Cakram 4 tetap di C. Selesaikan tiga cakram dari B ke C.

Untuk memindahkan tiga cakram dari B ke C dengan A, ke mana cakram 1 bergerak dahulu?

Langkah 0 dari 7

Solusi langkah demi langkah

Contoh dimulai dengan semua cakram di A dan berakhir di C. Buka langsung; permainanmu tidak berubah.

Jumlah langkah minimum

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

Solusi standar memindahkan tumpukan kecil dua kali dan cakram terbesar sekali: T(n) = 2T(n − 1) + 1. Satu cakram perlu satu langkah, jadi minimum untuk n cakram adalah 2ⁿ − 1.

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

3 cakram — 7 langkah

Awal: semua cakram di A. Tujuan: C. Cakram 1 paling kecil.

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

Awal: semua cakram di A. Tujuan: C. Cakram 1 paling kecil.

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

Awal: semua cakram di A. Tujuan: C. Cakram 1 paling kecil.

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

Bagaimana jika posisiku berbeda dari contoh?

Semua posisi yang mematuhi ukuran dapat mencapai C. Mengulangi posisi adalah putaran, bukan jalan buntu. Rumus tadi berlaku untuk awal standar, bukan sisa langkah dari posisi sembarang. Gunakan petunjuk dari posisi sebenarnya.

Teka-teki →