Menara Hanoi

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.

Contoh

A B C

Contoh (lanjutan)

A B C

Contoh (lanjutan)

A B C

Contoh (lanjutan)

A B C

Contoh (lanjutan)

A B C

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.

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.

• . . .

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.

Contoh: 3 keping

A B C

1. Pindahkan 2 keping terkecil ke B. Gunakan prosedur untuk dua keping untuk memindahkan ini.

Contoh: 3 keping (lanjutan)

A B C

Contoh: 3 keping (lanjutan)

A B C

Contoh: 3 keping (lanjutan)

A B C

2. Pindahkan keping warna ungu ke C.

Contoh: 3 keping (lanjutan)

A B C

3. Pindahkan 2 keping terkecil dari B ke C. Gunakan prosedur untuk dua keping untuk memindahkan ini.

Contoh: 3 keping (lanjutan)

A B C

Contoh: 3 keping (lanjutan)

A B C

Contoh: 3 keping (lanjutan)

A B C

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?