[MATH GAME] Tower of Hanoi

Subject: [MATH GAME] Tower of Hanoi Tue Oct 26, 2010 8:40 am

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

Subject: Re: [MATH GAME] Tower of Hanoi Tue Oct 26, 2010 2:18 pm

wa dah pernah maen ini di Alfalink kawan

wa cuman bisa ampe yg 4 yg 5 susah :swt:

Subject: Re: [MATH GAME] Tower of Hanoi Wed Oct 27, 2010 11:18 am

Pusing ya..!? :hihi:
Tapi.. ane punya trik lho:
- Untuk langkah pertama, jika n (banyak keping) ganjil, pindahin keping pertama ke kolom 3, jika n genap, pindahin ke kolom 2
- Beri nomor pada tiap keping, keping terkecil bernomor 1. Nah, biar ga bakalan stuck nantinya, keping ditumpuk ke tumpukan yang kepingan teratasnya berparitas genap/ganjil beda (ga sama2 genap ga sama2 ganjil).