Menara Hanoi
Menara Hanoi adalah teka-teki matematika klasik. Tiga tiang, tumpukan cakram berbagai ukuran, dan dua aturan ketat: pindahkan satu cakram setiap kali, dan jangan pernah meletakkan cakram besar di atas yang kecil.
Tiga tiang dan kerucut cakram
Papan ini punya tiga tiang. Ukuran cakram semuanya berbeda, dan cakram dimasukkan ke tiang. Di awal, seluruh set berada di satu tiang, diurutkan menurut ukuran, yang terbesar di bawah dan yang terkecil di atas, sehingga tumpukannya berbentuk kerucut. Tujuannya adalah memindahkan seluruh menara itu ke tiang lain.
Tiga aturan
1. Pindahkan hanya satu cakram setiap kali. 2. Satu langkah mengambil cakram teratas dari sebuah tumpukan dan meletakkannya di tumpukan lain, atau di tiang kosong. 3. Cakram yang lebih besar tidak boleh berada di atas cakram yang lebih kecil. Tiga aturan itulah seluruh permainannya. Dengan aturan ini, setiap posisi yang sah adalah cara membagi cakram ke tiang-tiang sementara setiap tiang tetap terurut.
Solusi terpendek adalah 2ⁿ − 1
Jumlah langkah paling sedikit untuk menyelesaikan menara n cakram adalah 2ⁿ − 1. Satu cakram butuh 1 langkah. Dua cakram butuh 3. Tiga butuh 7, empat 15, dan lima 31. Setiap cakram baru menggandakan solusi sebelumnya dan menambah satu langkah yang membawa cakram terbesar: jika n − 1 cakram butuh T langkah, maka n cakram butuh 2T + 1. Rumus rekursif itu tepat sama dengan 2ⁿ − 1. Delapan cakram, menara tertinggi di aplikasi PictorX, butuh 255 langkah. Tidak ada jalur sah yang lebih pendek.
Cara kerja rekursi
Untuk memindahkan n cakram dari tiang awal ke tiang tujuan, dengan tiang yang tersisa sebagai tiang bantu: 1. Pindahkan n − 1 cakram teratas dari tiang awal ke tiang bantu. 2. Pindahkan cakram terbesar dari tiang awal langsung ke tiang tujuan. 3. Pindahkan n − 1 cakram dari tiang bantu ke tiang tujuan, di atas cakram terbesar. Langkah 2 sah karena cakram terbesar boleh berada di tiang mana pun. Langkah 1 dan 3 adalah teka-teki yang sama, dengan satu cakram lebih sedikit. Pemanggilan berakhir pada satu cakram, yang dipindahkan sekali. Jika diuraikan, hasilnya 2ⁿ − 1 langkah, dan tidak ada langkah yang pernah meletakkan cakram besar di atas yang kecil.
Legenda 64 cakram emas
Matematikawan Prancis Édouard Lucas memperkenalkan teka-teki ini pada tahun 1883. Bersamanya ia menceritakan legenda tentang sebuah kuil India di Kashi Vishwanath, tempat para pendeta memindahkan tumpukan 64 cakram emas dengan aturan yang sama. Menurut legenda, ketika langkah terakhir dilakukan, dunia akan berakhir. Enam puluh empat cakram butuh 2⁶⁴ − 1 langkah: 18.446.744.073.709.551.615. Dengan satu langkah sempurna per detik, siang dan malam, itu sekitar 585 miliar tahun. Para pendeta tidak akan selesai.
Mainkan di PictorX
Buka Menara Hanoi dan menara empat cakram sudah ada di tiang awal. Minimumnya lima belas langkah. Seret cakram teratas ke tiang lain, atau klik satu tiang lalu tiang yang Anda inginkan. Tombol 1, 2, dan 3 melakukan hal yang sama. Cakram besar di atas cakram kecil akan ditolak. Cakram berkisar dari 1 hingga 8, jadi Anda bisa mencocokkan 1, 3, 7, 15, 31, 63, 127, dan 255 dengan rumusnya. Langkah memainkan satu langkah dari solusi terpendek. Selesaikan memainkan sisanya. Tonton 3 cakram menampilkan strategi rekursif yang bergerak. Urungkan dan Ulangi menelusuri langkah-langkah Anda. Simpan PNG, atau buka papan di editor PictorX.
Pertanyaan yang sering diajukan
Apa aturan Menara Hanoi?
Pindahkan satu cakram setiap kali. Ambil cakram teratas dari sebuah tiang dan letakkan di tiang lain. Jangan pernah meletakkan cakram besar di atas yang kecil. Seluruh menara mulai di satu tiang dan harus berakhir di tiang lain.
Berapa langkah yang dibutuhkan solusi terpendek?
2ⁿ − 1. Satu cakram 1 langkah, dua cakram 3, tiga 7, empat 15, dan lima 31. Setiap tambahan cakram menggandakan solusi sebelumnya dan menambah satu langkah.
Siapa yang menciptakan Menara Hanoi?
Matematikawan Prancis Édouard Lucas memperkenalkannya pada tahun 1883. Kisah para pendeta dan 64 cakram emas di Kashi Vishwanath adalah legenda yang ia sertakan pada teka-teki itu.
Berapa lama 64 cakram akan selesai?
2⁶⁴ − 1 langkah, yaitu 18.446.744.073.709.551.615. Dengan satu langkah per detik, itu sekitar 585 miliar tahun.
Related alat
Menara Hanoi
Pindahkan menara cakram di antara tiga tiang di peramban Anda. Satu cakram setiap kali, tidak pernah yang besar di atas yang kecil. Solusi terpendek adalah 2ⁿ − 1 langkah.
Jarum Buffon
Jatuhkan jarum ke lantai bergaris di browser. Hitung persilangannya dan saksikan eksperimen Buffon tahun 1777 memperkirakan π.
Jarum Buffon
Masalah jarum Buffon tahun 1777: mengapa jarum yang dijatuhkan pada garis sejajar memperkirakan π, bagaimana peluang jarum pendek 2l/(πd) berasal dari luas di bawah kurva sinus, dan mengapa eksperimen ini lambat konvergen.
Lingkaran perkalian
Hubungkan setiap angka pada lingkaran dengan kelipatannya. Gambar tabel perkalian, kardioid, atau figur benang di atas kertas, dengan kapur, atau pada kayu.
Konjektur Collatz
Jelajahi masalah Collatz 3n+1 di browser Anda. Telusuri barisan hujan es, tumbuhkan pohon Collatz geometris, dan perbesar fraktal Collatz kontinu.
Semut Langton
Jalankan semut Langton di browser. Saksikan simetri, kekacauan, dan jalan raya 104 langkah, lalu coba aturan warna-warni, beberapa semut, kisi heksagon, dan turmite.
Siap ke coba itu?
Buka PictorX di browser Anda — tidak instalasi, tidak credit kartu diperlukan ke mulai.
Main Menara Hanoi