Menara Hanoi

Menara Hanoi merupakan sebuah permainan kuno yang sejak dulu dimainkan oleh biarawan-biarawan Budha di China atau India.

Menurut legenda Menara Hanoi, seorang biarawan memiliki 3 tonggak dan diharuskan memindahkan 64 piringan (disk atau cakram). Biarawan berusaha memindahkan semua piringan dari tonggak A ke tonggak C dengan bantuan tonggak B dengan ketentuan pemindahan piringan (disk atau cakram) dilakukan satu persatu dan piringan (disk atau cakram) yang memiliki diameter yang lebih besar tidak boleh diletakkan di atas piringan yang memiliki diameter yang lebih kecil.
Secara rekursif, cara memindahkan seluruh piringan adalah sebagai berikut:
1) Pindahkan (N-1) piringan yang paling atas (satu per satu) dari tonggak asal
(A) ke tonggak bantu (B).
2) Pindahkan piringan ke-N (piringan terakhir) dari tonggak asal (A) ke tonggak
tujuan (C).
3) Pindahkan (N-1) piringan dari tonggak bantu (B) ke tonggak tujuan (C).
Misalkan mn = jumlah langkah minimal untuk memindahkan n buah piringan dari satu tonggak ke tonggak lain. mn tidak dipengaruhi asal dan tujuan tonggak dan tidak tergantung dari banyaknya piringan yang terletak di bawah n buah piringan yang dipindah tersebut.
Langkah 1, memerlukan mk-1 kali perpindahan.
Langkah 2, memerlukan 1 kali perpindahan.
Langkah 3, memerlukan mk-1 kali perpindahan.
Jadi jumlah keseluruhan perpindahan minimal adalah :
mk = mk-1 + 1 + mk-1
= 2 mk-1 + 1
Kondisi awal terjadi jika k = 1 (jumlah langkah minimal untuk memindahkan 1 piringan dari A ke C). Jelas bahwa hanya dibutuhkan 1 kali perpindahan, atau m1 = 1.
Maka didapat persamaan rekursif m1, m2, .... sebagai berikut :
mk = mk-1 + 1 + mk-1 (relasi rekurensi)
m1 = 1 (kondisi awal)
Untuk memindahkan 64 piringan dihitung dengan m64 yang setelah dihitung besarnya adalah 1,844674 . 1019 detik atau 5.84542 . 1011 tahun.