Cara Menguasai Tower of Hanoi
Ringkasan: Tower of Hanoi diselesaikan dengan satu aturan rekursif: untuk memindahkan n cakram ke pasak target, pertama pindahkan n-1 cakram ke pasak tengah, kemudian pindahkan cakram terbesar ke target, lalu pindahkan n-1 cakram ke atasnya. Terapkan aturan ini di setiap level dan Anda selalu mencapai jumlah gerakan minimum. Minimumnya selalu satu kurang dari pangkat dua: 3 cakram butuh 7 gerakan, 4 cakram butuh 15, 5 butuh 31, 6 butuh 63, 7 butuh 127.
Apa Permainan Ini
Tower of Hanoi dimulai dengan tumpukan cakram di pasak paling kiri, yang terbesar di bawah, yang terkecil di atas. Tujuan Anda: pindahkan seluruh tumpukan ke pasak paling kanan, dengan mematuhi dua aturan. Pindahkan satu cakram sekaligus. Jangan pernah menaruh cakram lebih besar di atas yang lebih kecil.
Hanya itu. Tidak ada timer, tidak ada keacakan, tidak ada informasi tersembunyi. Hanya logika dan anggaran gerakan.
PlayMemorize berskala dari 3 cakram hingga 7 cakram. Anggaran gerakan dimulai di atas minimum optimal sehingga pemula masih bisa menang sambil mempelajari polanya; saat level naik, anggaran semakin ketat mendekati minimum matematis.
Jumlah gerakan minimum: 3 cakram = 7 gerakan; 4 cakram = 15 gerakan; 5 cakram = 31 gerakan; 6 cakram = 63 gerakan; 7 cakram = 127 gerakan. Setiap level membutuhkan sekitar dua kali lipat gerakan dari level di bawahnya, ditambah satu. Jika Anda melebihi anggaran gerakan, putaran berakhir sebagai kekalahan.
Algoritma Rekursif
Semua hal dalam Tower of Hanoi mengikuti satu pola, diterapkan berulang kali di setiap skala:
Untuk memindahkan n cakram dari pasak A ke pasak C, menggunakan pasak B sebagai penyimpanan sementara:
- Pindahkan n-1 cakram dari A ke B (menggunakan C sebagai sementara)
- Pindahkan cakram terbesar dari A ke C
- Pindahkan n-1 cakram dari B ke C (menggunakan A sebagai sementara)
Itulah algoritma lengkapnya. Di setiap level teka-teki, Anda menjalankan struktur tiga langkah yang sama. Keindahannya adalah langkah 1 dan 3 sendiri merupakan instans lebih kecil dari masalah yang sama, diselesaikan dengan aturan yang sama.
Mari telusuri 3 cakram untuk membuatnya konkret. Tujuan: pindahkan semua tiga dari pasak 1 ke pasak 3.
- Langkah 1 (pindahkan 2 cakram dari pasak 1 ke pasak 2): pindahkan cakram 1 ke pasak 3, pindahkan cakram 2 ke pasak 2, pindahkan cakram 1 ke pasak 2.
- Langkah 2 (pindahkan cakram 3 dari pasak 1 ke pasak 3): satu gerakan.
- Langkah 3 (pindahkan 2 cakram dari pasak 2 ke pasak 3): pindahkan cakram 1 ke pasak 1, pindahkan cakram 2 ke pasak 3, pindahkan cakram 1 ke pasak 3.
Total: 7 gerakan. Optimal.
Pemikiran Tiga Fase. Sebelum menyentuh cakram apa pun, sebutkan tiga fase dengan lantang: “Bersihkan n-1 cakram ke tengah; pindahkan yang terbesar ke target; bangun ulang n-1 cakram di atasnya.” Di setiap level rekursi, Anda mengulangi struktur yang sama dengan satu cakram lebih sedikit. Anda tidak menghafal urutan gerakan - Anda menjalankan pola fraktal.
Tip: Sebelum membuat gerakan apa pun, tanyakan: “Apa cakram terbesar yang perlu saya pindahkan sekarang?” Semua yang Anda lakukan sebelum memindahkan cakram itu adalah persiapan. Mempertahankan kerangka ini mencegah gerakan tak bertujuan dan membuat Anda tetap di jalur optimal.
Mengapa Jumlah Gerakan Tetap
Jumlah gerakan minimum mengikuti langsung dari algoritma. Menyelesaikan n cakram membutuhkan penyelesaian n-1 cakram dua kali (langkah 1 dan 3) ditambah satu gerakan cakram terbesar (langkah 2). Jadi total T(n) = 2 kali T(n-1) ditambah 1. Dengan T(1) = 1, ini menghasilkan: 1, 3, 7, 15, 31, 63, 127 untuk jumlah cakram 1 hingga 7.
Setiap angka adalah satu kurang dari pangkat dua. Tiga cakram: 8 dikurangi 1 = 7. Empat cakram: 16 dikurangi 1 = 15. Lima cakram: 32 dikurangi 1 = 31. Enam cakram: 64 dikurangi 1 = 63. Tujuh cakram: 128 dikurangi 1 = 127.
Ini bukan kebetulan - ini adalah konsekuensi langsung dari menyelesaikan n-1 cakram dua kali setiap kali Anda menyelesaikan n cakram. Setelah Anda memahami ini, Anda berhenti memandang Hanoi sebagai teka-teki yang harus ditebak dan mulai memandangnya sebagai algoritma yang harus dijalankan.
Taktik Berdasarkan Kesulitan
3 hingga 4 cakram (pembelajaran): Pada level ini, anggaran gerakan nyaman. Fokus pada penamaan setiap cakram secara mental - “kecil,” “sedang,” “besar” - sehingga Anda tidak pernah bingung cakram mana yang ditargetkan. Telusuri tiga fase sebelum menyentuh apa pun. Setelah setiap permainan, jelaskan fase-fasenya dengan lantang: “Saya membersihkan dua cakram ke tengah, memindahkan yang besar, membangun kembali di atasnya.”
Tip: Cakram terbesar harus dipindahkan tepat sekali per solusi penuh. Jika Anda ingin memindahkannya lagi, Anda telah merusak struktur algoritma. Gerakan tunggal cakram terbesar adalah tonggak pencapaian - semua sebelumnya adalah membersihkan jalan; semua sesudahnya adalah menumpuk di atasnya.
5 hingga 6 cakram (menengah): Anggaran gerakan semakin ketat. Setiap gerakan yang mengembara merugikan Anda. Terapkan algoritma rekursif secara ketat di setiap level. Saat Anda merekursi dari n ke n-1 cakram, fokus mental Anda harus bergeser: Anda sekarang menyelesaikan teka-teki Hanoi yang lebih kecil dengan kumpulan pasak “sumber,” “target,” dan “bantu” yang berbeda. Lacak peran mana yang dimainkan setiap pasak di setiap level rekursi.
Pertukaran Pasak Bantu. Di setiap level rekursi, satu pasak adalah sumber, satu adalah target, dan satu adalah bantu. Peran-peran ini berputar saat Anda merekursi. Saat memindahkan n-1 cakram dari pasak 1 ke pasak 2, pasak 3 adalah bantu. Saat kemudian memindahkan n-2 cakram dari pasak 1 ke pasak 3, pasak 2 adalah bantu. Lacak pertukaran ini secara sadar - ini adalah sumber kebingungan yang paling umum pada 5 dan 6 cakram.
7 cakram (tantangan): Dengan 127 gerakan minimum dan anggaran yang ketat, Anda tidak bisa berpikir gerakan demi gerakan. Berpikirlah fase demi fase. Sebelum memulai, petakan struktur tingkat teratas: pindahkan 6 cakram ke tengah (63 gerakan), pindahkan cakram terbesar ke kanan (1 gerakan), pindahkan 6 cakram ke kanan (63 gerakan). Kemudian subdivisi setiap fase 6-cakram dengan cara yang sama. Perencanaan dari atas ke bawah ini mengurangi beban kognitif dan mencegah kesalahan kehilangan jejak fase mana yang sedang Anda kerjakan.
Perhatian: Pada 7 cakram, mencoba menghafal urutan gerakan demi gerakan tidak dapat diandalkan dan tidak diperlukan. Percayai algoritma. Ketika Anda menerapkan aturan rekursif di setiap titik percabangan, gerakan yang benar selalu ditentukan. Keraguan dan keragu-raguan adalah cara Anda membuang gerakan dan menghabiskan anggaran.
Kesalahan Umum
Memperlakukannya seperti teka-teki coba-coba. Gerakan acak terkadang tampak produktif tetapi membentuk jalan buntu. Hanoi adalah algoritma, bukan teka-teki yang diselesaikan dengan eksperimentasi. Hilangkan keacakan dari pemikiran Anda sepenuhnya.
Kehilangan jejak peran pasak. Pada tiga pasak identik, “sumber,” “target,” dan “bantu” bisa kabur, terutama pada jumlah cakram lebih tinggi. Sebelum memulai, beri label pasak secara eksplisit dalam pikiran: KIRI = awal, TENGAH = tengah, KANAN = target. Gunakan label ini secara konsisten di setiap level rekursi.
Memindahkan cakram terbesar lebih dari sekali. Pada level rekursi teratas, cakram terbesar bergerak tepat sekali. Jika Anda merasa ingin memindahkannya lagi, berhenti - struktur algoritma telah rusak. Kembali ke kerangka tiga fase dan identifikasi di mana Anda menyimpang.
Pos Pemeriksaan Cakram Terbesar. Di setiap level rekursi, cakram ke-n harus dipindahkan tepat sekali. Setelah menyelesaikan sub-fase pertama (memindahkan n-1 cakram ke pasak bantu), cakram ke-n harus bebas dan belum dipindahkan. Setelah langkah 2, harus berada di pasak target. Jika tidak, Anda telah menyimpang dari algoritma.
Kehabisan gerakan. Ini hanya terjadi ketika Anda tidak mengikuti algoritma, atau ketika Anda telah membuat dan kemudian secara mental “membatalkan” gerakan (mengubah pikiran di tengah eksekusi dan mencoba jalur berbeda). Berkomitmenlah pada algoritma. Itu optimal - tidak ada jalur yang lebih baik.
Perhatian: Setelah Anda memutuskan gerakan menggunakan algoritma rekursif, berkomitmenlah. Mempertanyakannya di tengah eksekusi menyebabkan gerakan terbuang. Algoritma menjamin optimalitas - percayai dan jalankan tanpa ragu.
Rencana Latihan
Minggu 1 - Internalisasi algoritma (3 cakram). Mainkan permainan 3-cakram setiap hari. Setelah setiap permainan, jelaskan tiga fase dengan lantang. Ulangi sampai polanya begitu familiar sehingga Anda bisa menarasikan seluruh solusi sebelum membuat gerakan pertama.
Minggu 2 - Peningkatan skala (4 hingga 5 cakram). Pindah ke permainan 4-cakram. Rekursi sekarang masuk dua level. Setelah setiap permainan, telusuri strukturnya: “Saya merekursi ke 3, memindahkan cakram besar, merekursi lagi.” Mainkan tiga hingga empat permainan pada 4 cakram, kemudian pindah ke 5.
Minggu 3 - Tekanan (6 cakram). Pada 6 cakram, anggaran gerakan menjadi kendala yang mengikat. Mainkan dengan algoritma sebagai satu-satunya panduan. Targetkan menyelesaikan dua permainan 6-cakram dalam lima gerakan dari minimum (63 gerakan). Lacak jumlah gerakan Anda dan saksikan turun menuju 63 selama minggu ini.
Minggu 4 - Penguasaan (7 cakram). Coba teka-teki 7-cakram. Terapkan perencanaan fase dari atas ke bawah sebelum menyentuh cakram apa pun. Tiga kemenangan berturut-turut pada 7 cakram dengan jumlah gerakan mendekati 127 menandakan penguasaan sejati.
Tip: Catat jumlah gerakan Anda per level cakram. Menyaksikan hitungan turun menuju minimum dari satu sesi ke sesi berikutnya adalah sinyal eksternal paling jelas bahwa pola rekursif sedang diinternalisasi. Jumlah gerakan di atas 130 untuk 7 cakram berarti gerakan yang mengembara masih muncul; di bawah 135 dengan konsistensi berarti strukturnya sudah solid.
Tower of Hanoi adalah salah satu dari sedikit permainan di mana penguasaan bersifat absolut dan terukur. Entah Anda mengetahui algoritma rekursif dan menjalankannya, atau tidak. Setelah Anda menguasainya, setiap tingkat kesulitan menghasilkan logika yang sama. Perlambat, beri nama fase Anda, percayai algoritma, dan solusinya selalu ada.
Menara Hanoi
Klasik · pindahkan seluruh menara cakram ke tiang lain, satu per satu, tidak pernah yang besar di atas yang kecil
Main sekarang - gratisTanpa akun. Bisa di perangkat apa saja.
