menara hanoi

19
Menara Hanoi

Upload: vincentius-yosephat-suryo

Post on 12-Jan-2016

233 views

Category:

Documents


10 download

DESCRIPTION

task C# programing

TRANSCRIPT

Page 1: Menara Hanoi

Menara Hanoi

Page 2: 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.

Page 3: Menara Hanoi

Contoh

A B C

Page 4: Menara Hanoi

Contoh (lanjutan)

A B C

Page 5: Menara Hanoi

Contoh (lanjutan)

A B C

Page 6: Menara Hanoi

Contoh (lanjutan)

A B C

Page 7: Menara Hanoi

Contoh (lanjutan)

A B C

Page 8: Menara Hanoi

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

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

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

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

Contoh: 3 keping (lanjutan)

A B C

Page 13: Menara Hanoi

Contoh: 3 keping (lanjutan)

A B C

Page 14: Menara Hanoi

Contoh: 3 keping (lanjutan)

A B C

2. Pindahkan keping warna ungu ke C.

Page 15: Menara Hanoi

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

Contoh: 3 keping (lanjutan)

A B C

Page 17: Menara Hanoi

Contoh: 3 keping (lanjutan)

A B C

Page 18: Menara Hanoi

Contoh: 3 keping (lanjutan)

A B C

Page 19: Menara Hanoi

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?