Skip to content
17 November 2008 / Jeffrey Hermanto Halimsetiawan

Implementasi Rekursi Menara Hanoi – Bahasa C


Permainan Tower of Hanoi atau Menara Hanoi merupakan permainan klasik yang sudah sangat sering digunakan sebagai contoh permasalahan yang dapat diselesaikan dengan cara rekursi.

Secara singkat Menara Hanoi adalah permainan untuk memindahkan n piringan dari tiang A ke tiang C dengan tiang bantu B, dimana kepingan yang lebih besar harus berada di bawah kepingan yang lebih kecil.

Gambaran Menara Hanoi

Gambaran Menara Hanoi

Ini adalah cara penyelesaian Menara Hanoi atau Tower of Hanoi secara rekursif beserta animasi tiap pergerakannya :

#include <stdio.h>      //definisi printf,scanf
#include <conio.h>      //definisi getch
#include <stdlib.h>     //definisi system
#include <windows.h>    //definisi Sleep

int initialize(int arr1[],int x[]);
void print(int arr1[],int arr2[],int arr3[],int x[]);
void Hanoi(int arr1[],int arr2[],int arr3[],int x[],int n,char asal,char bantu,char tujuan);

int main()
{
    int n;
    int arr1[100],
        arr2[100],
        arr3[100],
        x[3] = {0,0,0};

    n = initialize(arr1,x);
    print(arr1,arr2,arr3,x);
    Hanoi(arr1,arr2,arr3,x,n,'A','B','C');
    getch();
    return 0;
}

int initialize(int arr1[],int x[]){
     int n;
     while (true){
         system("cls");
         printf("= = = = | T O W E R   O F   H A N O I - tutorialpemrograman.wordpress.com | = = = =\n\n");
         printf("Jumlah Kepingan :  ");
         if (scanf("%d",&n) == 1 ) break;
         fflush(stdin);
     }
     puts("");
     for (int i=n;i>=1;i--){
        arr1[x[0]++] = i;
     }
     return n;
}

void print(int arr1[],int arr2[],int arr3[],int x[]){
     int i,
         j = 0;
     for (j=0;j<3;j++){
         if (j == 0)printf("A : ");
         if (j == 1)printf("B : ");
         if (j == 2)printf("C : ");
         for (i=0;i<x[j];i++){
             if (j == 0) printf("%3d",arr1[i]);
             if (j == 1) printf("%3d",arr2[i]);
             if (j == 2) printf("%3d",arr3[i]);
         }
         printf("\n");
     }
     printf("\n");
}

// pindahkan piringan ke n dari asal menuju tujuan melalui bantu
void Hanoi(int arr1[],int arr2[],int arr3[],int x[],int n,char asal,char bantu,char tujuan)
{ 

    if (n == 0) return;
    //pindahkan piringan ke n-1 dari asal ke bantu melalui tonggak tujuan
    Hanoi(arr1,arr2,arr3,x,n-1,asal,tujuan,bantu); 

    printf("... Memindahkan kepingan ke-%d dari %c ke %c ...\n\n",n,asal,tujuan);
    x[asal-65] -= 1;
    switch (tujuan){
           case 'A' :
                arr1[x[0]++] = n;
                break;
           case 'B' :
                arr2[x[1]++] = n;
                break;
           case 'C' :
                arr3[x[2]++] = n;
                break;
    }
    print(arr1,arr2,arr3,x);
    Sleep(1000);
    //pindahkan piringan ke n – 1 dari bantu menuju tujuan melalui asal
    Hanoi(arr1,arr2,arr3,x,n-1,bantu,asal,tujuan);
}

Langkah-langkah pemanggilan fungsi rekursinya adalah sebagai berikut :

3 A B C
	2 A C B
		1 A B C
			0 A C B
		1 A B C
		Pindahkan piringan ke 1 ke dari A ke C
			0 C A B
		1 A B C
	2 A C B
	Pindahkan piringan ke 2 ke dari A ke B
		1 C A B
			0 C B A
		1 C A B
		Pindahkan piringan ke 1 dari C ke B
			0 A C B
		1 C A B
	2 A C B
3 A B C
Pindahkan piringan ke 3 ke dari A ke C
	2 B A C
		1 B C A
			0 B A C
		1 B C A
		Pindahkan piringan ke 1 ke dari B ke A
			0 C B A
		1 B C A
	2 B A C
	Pindahkan piringan ke 2 ke dari B ke C
		1 A B C
			0 A C B
		1 A B C
		Pindahkan piringan ke 1 dari A ke C
			0 B A C
		1 A B C
	2 B A C
3 A B C
About these ads
  1. Alex Lee / Apr 2 2010 19:56

    om….. jelasin caranya traccing donk

    • Jeffrey Hermanto / Apr 5 2010 23:46

      Tracing apa? Tracing rekursi?

      Sempet saya singgung di tulisan :
      Implementasi Rekursi Menara Hanoi

      Semoga bermanfaat :D

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Logout / Ubah )

Twitter picture

You are commenting using your Twitter account. Logout / Ubah )

Facebook photo

You are commenting using your Facebook account. Logout / Ubah )

Google+ photo

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

Ikuti

Get every new post delivered to your Inbox.

Bergabunglah dengan 52 pengikut lainnya.

%d bloggers like this: