Download - Menara Hanoi
![Page 1: Menara Hanoi](https://reader036.vdokumen.com/reader036/viewer/2022082403/563dbbb8550346aa9aafad1c/html5/thumbnails/1.jpg)
Menara Hanoi
![Page 2: Menara Hanoi](https://reader036.vdokumen.com/reader036/viewer/2022082403/563dbbb8550346aa9aafad1c/html5/thumbnails/2.jpg)
Tujuan• Memindahkan semua cakram/keping dari
sebelah kiri ke sebelah
Aturan
• Satu cakram yang dapat berpindah pada satu waktu tertentu.
• Cakram yang kecil tidak boleh diletakkan di bawah cakram yang besar.
![Page 3: Menara Hanoi](https://reader036.vdokumen.com/reader036/viewer/2022082403/563dbbb8550346aa9aafad1c/html5/thumbnails/3.jpg)
Contoh
A B C
![Page 4: Menara Hanoi](https://reader036.vdokumen.com/reader036/viewer/2022082403/563dbbb8550346aa9aafad1c/html5/thumbnails/4.jpg)
Contoh (lanjutan)
A B C
![Page 5: Menara Hanoi](https://reader036.vdokumen.com/reader036/viewer/2022082403/563dbbb8550346aa9aafad1c/html5/thumbnails/5.jpg)
Contoh (lanjutan)
A B C
![Page 6: Menara Hanoi](https://reader036.vdokumen.com/reader036/viewer/2022082403/563dbbb8550346aa9aafad1c/html5/thumbnails/6.jpg)
Contoh (lanjutan)
A B C
![Page 7: Menara Hanoi](https://reader036.vdokumen.com/reader036/viewer/2022082403/563dbbb8550346aa9aafad1c/html5/thumbnails/7.jpg)
Contoh (lanjutan)
A B C
![Page 8: Menara Hanoi](https://reader036.vdokumen.com/reader036/viewer/2022082403/563dbbb8550346aa9aafad1c/html5/thumbnails/8.jpg)
Strategi• Misalkan hanya ada sebuah cakram pada permainan ini.
– Ini mudah dilakukan: pindahkan saja dari sebelah kiri ke sebelah kanan.
• Misalkan hanya ada 2 buah cakram saja.– OK, pindahkan keping yang kecil ke tonggak di
tengah, keping kedua ke tonggak tujuan, kemudian keping yang di tengah ke tonggak tujuan.
• Misalkan ada 3 buah keping/cakram.– Pindahkan 2 keping teratas ke tonggak di tengah.– Pindahkan keping ktiga ke tonggak tujuan.– Pindahkan 2 keping dari tengah ke tujuan.
![Page 9: Menara Hanoi](https://reader036.vdokumen.com/reader036/viewer/2022082403/563dbbb8550346aa9aafad1c/html5/thumbnails/9.jpg)
Prinsip Induksi
• Prosedur untuk 3 keping tergantung pada prosedur untuk 2 keping.
• Prosedur untuk 4 keping tergantung pada prosedur untuk 3 keping.
• . . .
• Prosedur untuk 100 keping tergantung pada prosedur untuk 99 keping.
• . . .
![Page 10: Menara Hanoi](https://reader036.vdokumen.com/reader036/viewer/2022082403/563dbbb8550346aa9aafad1c/html5/thumbnails/10.jpg)
Penjelasan lain untuk hal yang sama: Rekursif• Misalkan ada 10 keping dipindahkan dari A ke C.
– Prosedurnya:• Pindahkan 9 keping teratas dr A ke B.• Pindahkan keping ke 10 dr A ke C.• Pindahkan ke sembilan buah keping dari B ke C.
• BAIK, tetapi bagaimana memindahkan 9 keping dari A ke B?– Gunakan prosedur yang sama secara rekursif:
• Pindahkan 8 keping teratas A ke C.• Pindahkan keping ke 9 dr A ke B.• Pindahkan ke delapan buah keping dari C ke B.
• . . . sampai tinggal hanya sebuah keping saja, yang mudah untuk dipindahkan.
![Page 11: Menara Hanoi](https://reader036.vdokumen.com/reader036/viewer/2022082403/563dbbb8550346aa9aafad1c/html5/thumbnails/11.jpg)
Contoh: 3 keping
A B C
1. Pindahkan 2 keping terkecil ke B. Gunakan prosedur untuk dua keping untuk memindahkan ini.
![Page 12: Menara Hanoi](https://reader036.vdokumen.com/reader036/viewer/2022082403/563dbbb8550346aa9aafad1c/html5/thumbnails/12.jpg)
Contoh: 3 keping (lanjutan)
A B C
![Page 13: Menara Hanoi](https://reader036.vdokumen.com/reader036/viewer/2022082403/563dbbb8550346aa9aafad1c/html5/thumbnails/13.jpg)
Contoh: 3 keping (lanjutan)
A B C
![Page 14: Menara Hanoi](https://reader036.vdokumen.com/reader036/viewer/2022082403/563dbbb8550346aa9aafad1c/html5/thumbnails/14.jpg)
Contoh: 3 keping (lanjutan)
A B C
2. Pindahkan keping warna ungu ke C.
![Page 15: Menara Hanoi](https://reader036.vdokumen.com/reader036/viewer/2022082403/563dbbb8550346aa9aafad1c/html5/thumbnails/15.jpg)
Contoh: 3 keping (lanjutan)
A B C
3. Pindahkan 2 keping terkecil dari B ke C. Gunakan prosedur untuk dua keping untuk memindahkan ini.
![Page 16: Menara Hanoi](https://reader036.vdokumen.com/reader036/viewer/2022082403/563dbbb8550346aa9aafad1c/html5/thumbnails/16.jpg)
Contoh: 3 keping (lanjutan)
A B C
![Page 17: Menara Hanoi](https://reader036.vdokumen.com/reader036/viewer/2022082403/563dbbb8550346aa9aafad1c/html5/thumbnails/17.jpg)
Contoh: 3 keping (lanjutan)
A B C
![Page 18: Menara Hanoi](https://reader036.vdokumen.com/reader036/viewer/2022082403/563dbbb8550346aa9aafad1c/html5/thumbnails/18.jpg)
Contoh: 3 keping (lanjutan)
A B C
![Page 19: Menara Hanoi](https://reader036.vdokumen.com/reader036/viewer/2022082403/563dbbb8550346aa9aafad1c/html5/thumbnails/19.jpg)
Beberapa pertanyaan
• Berapa banyak gerak perpindahan yang dibutuhkan untuk:– 3 keping?
– 6 keping?
– n keping (sebagai rumus mencakup n)?
• Apakah prosedur yang didefinisikan optimal? • Berapa banyak konfigurasi yang mungkin, untuk:
– 2 keping? 4 keping? n keping?
• Apakah semua konfigurasi dapat dicapai?