Hanoi Tower

Ada sebuah legenda di Vietnam. Di suatu tempat terdapat sebuah kuil. Beberapa pendeta tinggal di kuil tersebut. Pendeta-pendeta tersebut memindahkan 64 buah keping yang berbeda ukuran dari satu tiang ke tiang lain. Karena keping-keping yang harus dipindahkan mudah pecah, maka mereka harus memindahkannya dengan hati-hati. Mereka hanya bisa memindahkan satu per satu dan keping yang lebih besar tidak boleh berada di atas keping yang lebih kecil. Untuk itu digunakan sebuah tiang lain untuk penumpukan sementara. Saat para pendeta selesai memindahkan keping-keping tersebut, dunia berakhir.
Jika legenda tersebut benar, dan jika para pendeta mampu memindahkan keping-keping tersebut dengan efektif, maka jumlah langkah minimal yang harus dilakukan oleh para pendeta adalah 2 pangkat 64 dikurangi 1, sama dengan 18.446.744.073.709.551.615 langkah. Berapa waktu yang diperlukan untuk memindahkan keping-keping tersebut? Jika kecepatan pergerakan satu keping adalah satu detik, waktu minimal yang diperlukan untuk memindahkan seluruh keping adalah sekitar 585.000.000.000 tahun. Berikut adalah cara penghitungan waktu tersebut

Dalam suatu cerita lain, keping-keping terbuat dari emas, dan para pendeta hanya mampu memindah satu keping dalam satu hari. Bagi yang berminat, silakan pembaca untuk menghitung sendiri berapa waktu yang diperlukan, jika para pendeta hanya mampu memindahkan satu keping per hari.

Terinspirasi oleh legenda tersebut. Pada tahun 1883, seorang ahli Matematika dari Perancis Edouard Lucas memperkenalkan permainan Hanoi Tower. Hanoi Tower adalah permainan dengan logika. Ada beberapa algorithma yang telah dipublish untuk menyelesaikan persoalan Hanoi Tower. Seperti Recursive Solution, Non-Recursive Solution, Binary Solution dan lainnya. Selain bisa diterapkan pada permainan Hanoi Tower, algorithma Recursive Solution biasa dipakai untuk memecahkan masalah faktor rial. Tiga faktor rial (ditulis 3!) adalah 3x2x1 = 6. Empat faktorial, 4!= 4x3x2x1 sama dengan 24. Ada unsur pengulangan pada algorithma ini.