Algoritma "Tower of Hanoi" (Menara Hanoi)

Seperti yang kita ketahui mengenai Nama menara yang di sebut sebagai "Tower of Hanoi" adalah Menara Hanoi. Menara Hanoi ini adalah sebuah permainan matematis atau teka-teki. Permainan ini terdiri dari tiga tiang dan sejumlah cakram dengan ukuran berbeda-beda yang bisa dimasukkan ke tiang mana saja. Permainan dimulai dengan cakram-cakram yang tertumpuk rapi berurutan berdasarkan ukurannya dalam salah satu tiang, cakram terkecil diletakkan teratas, sehingga membentuk kerucut.
Tujuan dari teka-teki ini adalah untuk memindahkan seluruh tumpukan 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 lebih kecil.

          Dan untuk yang menemukan teka - teki ini adalah Édouard Lucas, ahli matematika Perancis di tahun 1883. Ada sebuah legenda tentang candi Indian yang berisi ruang besar dengan tiga tiang yang dikelilingi 64 cakram emas. Pendeta Brahma, melaksanakan tugas dari peramal di masa lalu, sesuai dengan aturan teka-teki ini. Menurut legenda ini, bila teka-teki ini diselesaikan, dunia akan kiamat. Tidak jelas benar apakah Lucas menemukan legenda ini atau terinspirasi olehnya.
          Tapi tahukah kalian ??? ..... Bila legenda ini benar, dan pendeta itu bisa memindahkan satu cakram tiap detik, menggunakan pemindahan paling sedikit, maka akan memakan waktu 2⁶⁴−1 detik atau kurang lebih 584,582 milyar tahun.

   Nah sekarang kalian sudah tahu mengenai "Tower of Hanoi" kan.....Tapi... :) :( (-_-)a" yang jadi masalahnya saya bukan mau ngejelasin mengenai sejarah atau mengenai pa itu Menara hanoi ? Disini saya mau ngejelasin sebuah tugas yang saya emban dari mata kuliah Analisis Algoritma . Tugasnya yakni membuat sebuh algoritma dari teori "The tower of Hanoi". dan alhamdulillah akhirnya jadi, hasilnya adalah sebagai berikut :

Soal :
Diketahui Piringan, dimana sejumlah piringan dipindahkan dari tonggak satu ke tonggak lainnya dan dapat menggunakan tonggak bantuan . Sesuai gambar berikut :


Pindahkan piringan ketiang lainnya

Untuk malakukan semua itu, caranya semua piringan di tonggak A akan dipindahkan ke tonggak C secara satu persatu dan piringan yang besar tidak boleh diletakkan di atas piringan yang kecil.
Untuk lebih jelasnya soal prosesnya bisa lihat gambar di bawah ini:


Proses perpindahan Piringan dengan menggunakan Tiang pembantu.

Lalu lihat yang ini pula :


Perpindahan Piringan

Untuk menyelesaikan puzzle di atas dalam pemrograman, kita dapat menggunakan teknik rekursif. Rekursif adalah fungsi atau prosedure yang dapat memanggil dirinya sendiri.
Jadi algoritmanya adalah …

Kalau N = 1 maka
N dipindahkan dari A ke C secara langsung
Tapi kalau N > 1 maka
pindahkan N-1 dari A ke B
pindahkan N dari A ke C
pindahkan N-1 dari B ke C
catatan :
N = banyaknya piringan

Lihat skema perpindahan piringan dari "Tower of Hanoi" :

Nahhh.....untuk melakukan analisisnya sudah dilakukan diatas, untuk algoritmanya adalah sebagai berikut :
Algoritma Menara Hanoi dengan Program C++

#include<iostream>

using namespace std;

void MenaraHanoi(int N, char asal, char bantu, char tujuan);

int main()

{

    int piringan;

    cout<< "\nPROGRAM MENARA HANOI\n";

    cout<< "--------------------\n\n";

    cout<< "Banyaknya piringan: ";

    cin >> piringan;

    cout<< endl;

    MenaraHanoi(piringan,'A','B','C');

    return 0;

}

void MenaraHanoi(int N, char asal, char bantu, char tujuan)

{

    if(N == 1)

        cout<<"Piringan 1 dari "<<asal<< " ke " << tujuan <<endl;

    else

        {

            MenaraHanoi(N-1,asal,tujuan, bantu);

            cout<<"Piringan " << N <<" dari " << asal << " ke " << tujuan<<endl;

            MenaraHanoi(N-1, bantu, asal, tujuan);

        }

}