[MATH GAME] Tower of Hanoi

Subject: [MATH GAME] Tower of Hanoi Mon Oct 25, 2010 6:00 pm

Menara Hanoi, yang diciptakan oleh Édouard Lucas pada tahun 1883, adalah salah satu permainan puzzle yang menggunakan tumpukan keping. Terdiri dari tiga batang (kolom) dan sejumlah keping dengan ukuran berbeda yang dapat masuk/keluar kolom. Tujuan permainan ini adalah memindahkan semua tumpukan keping dari satu kolom ke kolom lain. Aturan permainan ini adalah sebagai berikut :kabur:

- Hanya satu keping yang boleh dipindahkan untuk satu langkah
- Pada setiap langkah, satu keping yang paling atas di satu kolom dipindahkan dari kolom tersebut lalu ditumpukkan ke kolom lain
- Keping tidak boleh ditumpuk ke atas keping yang lebih kecil

Penyelesaian dengan Cara Rekursif
Misalkan ada tiga kolom, namai A, B, C. Tujuan disini adalah memindahkan n keping dari kolom A ke kolom C. Langkah-langkah yang dilakukannya adalah:
1) Pindahkan (n-1) keping teratas dari A ke B
2) Pindahkan keping n dari A ke C
3) Pindahkan (n-1) keping teratas dari B ke C

Perlu dicatat bahwa "langkah" 1 dan 3, bukan satu langkah. Tetapi justru "langkah" tersebut terdiri dari sejumlah langkah yang ditempuhnya. Dan "langkah" 1 dan 3 yang dikandungnya juga terdiri dari sejumlah langkahnya lagi yang ditempuhnya. Hal ini menunjukkan bahwa penyelesaian ini dilakukan secara rekursif.
Agar lebih jelas, perhatikan langkah-langkah pada gambar berikut ini.

[MATH GAME] Tower of Hanoi Tower_of_Hanoi_4

Banyak Langkah Minimum
Pada permainan ini, banyak langkah minimum yang diperlukan untuk memindahkan semua n keping dari satu kolom ke kolom lain adalah 2ⁿ - 1. Pernyataan ini dapat dibuktikan secara induksi :kabur:

- Untuk 1 keping, jelaslah hanya membutuhkan 1 langkah
- Asumsikan untuk n keping dibutuhkan 2ⁿ - 1. Sekarang untuk (n+1) keping, banyak langkah yang dibutuhkan adalah memindahkan n keping, sesuai dengan langkah-langkah yang telah disebutkan, adalah:
(2ⁿ - 1) + 1 + (2ⁿ - 1) = 2*2ⁿ - 1 = 2ⁿ⁺¹ - 1
Dan pernyataan ini sesuai dengan yang diasumsikan

Sumber:
- http://en.wikipedia.org/wiki/Tower_of_Hanoi

» [C] Tower of Hanoi (with ADT Stack)
» [Game] Make A Wish And Destroy It!
» [Flash Game] BCl3
» [game] Induksi Kalimat (6-15 Kata)
» [Flash Game] Black Roses (Demo)