Tugas Resume Towers of Hanoi

     Towers of Hanoi ( menara Hanoi ) adalah permainan atau teka teki matematika yang diperkenalkan oleh matematikawan Prancis yaitu Edouard Lucas pada tahun 1883. teka teki tersebut tersebut terdiri dari tiga buah menara ( pasak ), dan sejumlah disk ( piringan ) dengan ukuran yang berbeda, dan piringan tersebut dapat dipindahkan pada tiap pasaknya. teka teki tersebut dimulai dengan tumpukan piringan yang tersusun rapi dari atas ke bawah mulai dari piringan terkecil hingga yang terbesar sehingga membentuk sebuah kerucut.

     Tujuan dari permainan ini adalah untuk memindahkan seluruh tumpukkan piringan dari pasak awal ke pasak yang lain dengan memenuhi aturan sebagai berikut :

• Hanya satu piringan yang dapat dipindahkan pada satu waktu
• Hanya piringan yang paling atas yang dapat dipindahkan pada satu waktu, dan
• Piringan yang kecil harus terletak pada posisi paling atas atau dengan kata lain, piringan yang besar tidak dapat ditempatkan diatas piringan yang kecil

Algoritma Towers of Hanoi

     Dalam matematika, mencari solusi dari sebuah permasalahan dapat dicari dengan menyelesaikan masalah yang lebih umum. begitu juga dalam menyelesaikan masalah puzzle tower of Hanoi, akan dicari solusi dari sebuah permasalahan dengan menyelesaikan masalah dari yang lebih umum.

     Sebelum menyelesaikan masalah yang umum, biasanya masalah diinisialisasi terlebih dahulu dengan menggunakan contoh yang sederhana, kemudian baru menginisialisasi masalahnya secara umum.

     Untuk mencari solusi yang umum dari masalah ini tidaklah mudah, karena terdapat aturan yang membatasi masalah tersebut. jika tidak terdapat aturan, kita mungkin akan lebih mudah menyelesaikannya.

Legenda Menara Hanoi
(oleh Edouard Lucas abad 19)

·Seorang biarawan memiliki 3 menara.

·Diharuskan memindahkan 64 piringan emas.

·Diameter piringan tersebut tersusun dari ukuran kecil ke besar.

·Biarawan berusaha memindahkan semua piringan dari menara pertama ke menara ketiga tetapi harus melalui menara kedua sebagai menara tampungan.

•Kondisi:

§

• Piringan tersebut hanya bisa dipindahkan satu-satu. 
• Piringan yang besar tidak bisa diletakkan di atas piringan yang lebih kecil.

·Ternyata : mungkin akan memakan waktu sangat lama (sampai dunia kiamat).

·Secara teori, diperlukan 264-1 perpindahan. Jika kita salah memindahkan, maka jumlah perpindahan akan lebih banyak lagi.

•Jika satu perpindahan butuh 1 detik, maka total waktu yang dibutuhkan lebih dari 500 juta tahun !!.

•

•Algoritma:

•Jika n==1, pindahkan pringan dari A ke C

•Jika tidak:

•Pindahkan n-1 piringan dari A ke B menggunakan C sebagai tampungan

•Pindahkan n-1 piringan dari B ke C menggunakan A sebagai tampungan

Program

#include <stdio.h>

void towers(int n, char awal, char akhir, char antara)

{

 if(n==1)

printf("Pindahkan piringan 1 dari %c ke %c\n", awal,akhir);

 else{

towers(n-1, awal, antara, akhir);

printf("Pindahkan piringan %d dari %c ke %c\n", n, awal, akhir);

towers(n-1, antara, akhir, awal);

}

}

void main()

{

int n;

printf("Berapa piringan ? ");scanf("%d", &n);

towers(n, 'A', 'C', 'B');

}

Capture Tower of Hanoi

Ilustrasi Tower of Hanoi

Proses Kerja

Pemangkatan

int power2(int m,int n){

int p=1;

for(int i=1;i<=n;i++)

 p*=m;

return p;

}

•

•

int power(int m,int n){

if(n==1||n==0) return m;

else return m*power(m,n-1);

}

Analisis Algoritma

•Faktor-faktor yang menyulitkan analisis disebabkan oleh:

•

• Implementasi instruksi oleh bahasa pemrograman yang berbeda 
• Ketergantungan algoritma terhadap jenis data 
• Ketidakjelasan algoritma yang diimplementasikan 

•Langkah-langkah analisis algoritma

•

• Menentukan jenis/sifat data input. 
• Mengidentifikasi abstract operation dari data input. 

Analisis Algoritma

•

•Penilaian algoritma didasarkan pada:

•

• Waktu eksekusi (paling utama) 
• Penggunaan memori/sumber daya 
• Kesederhanaan dan kejelasan algoritma 

•Analisis algoritma tidak mudah dilakukan secara pasti, maka hanya diambil:

•

• Kondisi rata-rata (average case) 
• Kondisi terburuk (worst case) 

•Waktu eksekusi dipengaruhi oleh:

•

• Jenis data input 
• Jumlah data input 
• Pemilihan instruksi bahasa pemrograman

Daftar pustaka :

http://repository.upi.edu/operator/upload/s_mat_055400_chapter3.pdf

http://lecturer.ukdw.ac.id/anton/download/TIstrukdat9.ppt