Tower of Hanoi
Permainan ini ditemukan Édouard Lucas, ahli matematika Perancis pada tahun 1883. Ada sebuah legenda tentang candi Indian yang berisi ruang besar dengan tiga tiang yang dikelilingi 64 cakram emas. Pendeta Brahma menjalankan tugas dari peramal di masa lalu, sesuai dengan aturan permainan ini. Menurut legenda ini, bila permainan ini diselesaikan, maka dunia akan kiamat. Tidak jelas benar apakah Lucas yang menemukan legenda ini atau terinspirasi olehnya.
Tujuan dari permainan ini adalah untuk memindahkan seluruh tumpukan disk/cakram dari satu tiang ke tiang yang lain, mengikuti aturan berikut:
- Hanya satu cakram yang boleh dipindahkan dalam satu waktu.
- Setiap perpindahan berupa pengambilan cakram teratas dari satu tiang dan memasukkannya ke tiang lain, di atas cakram lain yang mungkin sudah ada di tiang tersebut.
- Tidak boleh meletakkan cakram di atas cakram lain yang berukuran lebih kecil.
Jumlah langkah minimal yang bisa dicapai untuk menyelesaikan permainan ini mengikuti rumus 2n-1, dimana n adalah jumlah disk/cakram. Dan bila legenda di atas itu benar, dan juga bila pendeta itu bisa memindahkan satu cakram setiap detiknya, maka paling sedikit akan memakan waktu 264−1 detik atau kurang lebih 585 miliar tahun.
0 comments:
Post a Comment