tower of hanoi

5/11/2018 Tower of hanoi - slidepdf.com

http://slidepdf.com/reader/full/tower-of-hanoi-55a0cbc9b6fb9 1/21

Tower of hanoi

Disusun oleh :

Tyas annisa rahma

Nopia fitriani

Ellin Agni Rinalda

Sartika Dwi N

Alfina Aditya A

Sintia A



Abstrak :Tower of Hanoi. Salah satu puzzle yang unik karena

memiliki berbagai macam variasi yang membutuhkanpenyelesaian yang berbeda untuk tiap variasinya.

Tower of Hanoi ini memiliki asal muasal yang unik karena beasal dari sebuah legenda di India. Puzzle inicukup dikenal oleh para mahasiswa Ilmu Komputer

karena sering muncul pada pengenalan struktur datadan algoritma.

Tower of Hanoi ini dapat dicari solusinya denganmenggunakan berbagai cara, mulai dari Gray Code,Binary Carry Sequence, representasi graf, dan Induksi

Matematik. Tower of Hanoi ini juga isomorfik untuk mendapatkan Jalur Hamilton yang akan diterangkandalam bentuk graf kemudian.



Tower Of Hanoi:

• Sejarah SingkatTower of Hanoi merupakan sebuah teka-teki yang ditemukan oleh seorangmatematikawan Perancis, Edouard Lucaspada tahun 1883. Legenda mengenai

Tower of Hanoi ini berasal dari sebuahkuil India, dimana terdapat sebuahruangan besar dengan tiga buahtonggak raksasa dengan 64 buahpiringan besar yang berbeda satu samalainnya. Ke 64 buah piringan tersebuttersusun sehingga bentuknya menyeupaisebuah piramid.



Model Tower Of Hanoi :



Lanjutan Slide:

• Dikatakan bahwa seorang pendeta Brahma, yangmeyakini sebuah ramalan kuno, telah berusahamemindahkan piringan-pringan tersebut, sesuai denganaturan pemindahannya. Menurut legenda, pada saatpiringan terakhir selesai dipindahkan, dunia akan berakhir.

• Apabila legenda ini benar, dan sang pendeta dapatmemindahkan piringan tersebut dengan kecepatan 1piringan per detik, dengan menggunakan jumlahperpindahan terkecil, paling sedikit membutuhkan waktu264- 1 detik atau kurang lebih setara dengan 584.542

juta tahun. Alam semesta ini kurang lebih telah berumur

13.7 juta tahun. Jadi mungkin saja legenda tersebut benar



Aturan Puzzle:

• Aturan Tower of Hanoi ini adalah bagaimanacara memindahkan semua piringan dari satutonggak ke tonggak lain. Dalam setiap

pemindahan hanya dapat memindahkan 1piringan saja dan tidak boleh menempatkanpiringan yang lebih besar diatas piringan yanglebih kecil.



Implementasi Tower of Hanoi • Tower of Hanoi sering digunakan dalam riset psikologi dalam

pemecahan masalah. Terdapat pula variasi dari Tower ofHanoi, yaitu Tower of London untuk diagnose neuropsikologidan pengerjaan fugsi eksklusif. Tower of Hanoi juga seringdipakai dalam skema Backup Rotation ketika membuatpenggandaan data komputer dimana banyak tape/ mediapenyimpanan termasuk didalamnya.

• Tower of Hanoi dapat dipakai untuk melatih kreativitas anak-anak dalam masa pertumbuhan. Selain itu, Tower of Hanoi juga sering diimplementasikan dalam proses pengajaranalgoritma rekursif dasar. Tower of Hanoi juga digunakan

untuk tes memory oleh para neuropsikolog untuk mengevaluasiamnesia.



•Pemecahan Tower of Hanoi

A. Solusi Rekursif

• Dalam dunia matematik, mencari solusi dari sebuahpermasalahan lebih mudah dengan cara menyelesaikanmasalah yang lebih umum. Bila didefinisikan a (a = asal),t (t = tujuan), s (s = sementara), dan h adalah jumlahpiringan, dibawah ini merupakan prosedur singkat

mengenai cara pemindahan sebuah piringan dari a ket dengan s untuk membantu.

• Langkah 1 : Bila h>1, gunakan prosedur ini untuk memindahkan h – 1 piringan dari a ke s.

• Langkah 2 : Sekarang piringan yang lebih besar. Piringan keh – 1 dipindahkan dari a ke t.

• Langkah 3 : Bila h>1, gunakan prosedur ini untuk memindahkan h – 1 piringan dari s ke t.



Lanjutan Slide :

Asumsikan terdapat sebuah fungsi untuk mencari solusi Tower of Hanoi dengan 4 argumen, yaitujumlah piringan (n) dan 3tonggak (a, t, dan r). Fungsi algoritmiknya sebagai berikut :

Solve (n, a, r, t)if (n = 0)

exitelseSolve (n - 1, a, t, r)Move from a to tSolve (n - 1, r, a, t)

Fungsi diatas merupakan fungsi sederhana Solve.Fungsimerupakan fungsi rekursif karena memanggildirinya sendiridengan nilai n yang terus berkurang hingga nilai n mencapai0. Secara implisit, penulisanfungsi diatas untuk n = 3



1. Move from a to t2. Move from a to r 3. Move from t to r 4. Move from a to t5. Move from r to a6. Move from r to t7. Move from a to t

Dalam hal ini perintah “Move” merupakan instruksi

untuk memindahkan piringan teratas suatu tonggak ketonggak yang dituju. Untuk n = 4 kita dapatkan

1. Move from a to r 2. Move from a to t3. Move from r to t4. Move from a to r 5. Move from t to a6. Move from t to r 7. Move from a to r 8. Move from a to t9. Move from r to t10. Move from r to a11. Move from t to a12. Move from r to t13. Move from a to r 14. Move from a to t

15. Move from r to t



Selanjutnya dalam induksi matematik.

Asumsikan n adalah jumlah total piringan. Pertama-tama, lihat sekuens

S1 = {ak}, jumlah piringan (i = 1 ~ n) yang harus dipindahkan dalamlangkah ke-k direpresentasikan dalam sebuah prosedur rekursifsederhana yang dimulai dari list S1 = {1} untuk tiap piringan, dansecara rekursif menjadi Sn ={Sn – 1, n, Sn – 1} (1)

Untuk beberapa nilai awal dari n akan diperlihatkan pada tabeldibawah ini.n Urutan perpindahan piringan

1 12 1,2,13 1,2,1,3,1,2,14 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1

• Tabel 1: Urutan Perpindahan Tower of Hanoi

Dari tabel diatas dapat terlihat bahwa proses rekurens terjadi setiappenambahan jumlah piringan. Urutan perpindahan piringan akan terusberulang dengan basis n = 1.Untuk ilustrasi perpindahan piringan n = 4 dapat dilihat dibawah ini.



Ilustrasi Tower Of Hanoi

• Untuk n

= 3



Penjelasan :

Setiap pertambahan nilai n, sebuah penambah sekuens terjadi. Uniknya, inimerupakan sekuens car biner ditambah dengan 1. Dan hebatnya, jumlahpiringan yang telah dipindahkan setelah perpindah ke-k sama dengan jumlahelemen yang perlu ditamb atau dikurangi pada addend k dalam fungsi Ryser.

Sebagai hasil dari prosedur diatas, jumlah perpindah hn yang dibutuhkan untuk menyelesaikan n buahpiringan dengan 3 tonggak didapatkan dari relasi rekurens

hn = 2 hn- 1 + 1 (2)

Kita dapat mendefinisikan jumlah hn dengan

h0 = 0hn = 2 hn - 1 + 1 untuk n > 0



Lanjutan Slide:

Kemudian kita dapatkan h1 = 2 h0 + 1 = 1, h2 = 2 h1 + 1 = 3, h3 = 2 h3

+ 1 = 7, dan seterusnya.

Fungsi diatas merupakan fungsi rekursif. Bila kita asumsikanTn = hn +1, maka akan didapatkan T0 = 1 dTn = hn + 1 = (2 hn- 1 + 1) + 1 = 2 hn- 1 + 2 = 2Tn –

Sehingga Tn dapat didefinisikan

Tn = 0 (3)Tn = 2Tn - 1 untuk n > 0 (4)

Dari persamaan diatas, didapatkan

Tn = 2n – 1 untuk n 0 (5)



b.Solusi Biner

Posisi piringan dapat ditentukan langsung dari jumlah pergerakan denganrepresentasi biner (bilangan basis 2).Pergerakan awal adalah #0, dengansemua digit 0, dan pergerakan akhir #2n – 1, dengan semua digit 1,dengan aturan :

1. Terdapat sebuah digit biner (bit) untuk tiap piringan.

2. Bit paling kiri merepresentasikan piringan terbesar. Nilai 0

mengindikasikan bahwa piringan terbesar terdapat pada tonggak awal,dan 1 mengindikasikan bahwa piringan terbesar terdapat pada tonggak tujuan.

3. Pembacaan bit dibaca dari kiri ke kanan, dan tiap bit dapat digunakanuntuk menentukan lokasi dari piringan yang bersangkutan.

4. Bit yang sama dengan bit sebelumnya menunjukkan bahwa piringanyang ukurannya berurutan berada tepat diatas piringan sebelumnya.



Lanjutan Solusi Biner :

5. Bit yang berbeda dengan bit sebelumnya berarti piringanyang ukurannya berurutan berada pada tonggak sebelah kiri

atau kanannya. Penentuan kiri atau kanan didapat dari aturan :

• a. asumsikan tonggak awal berada di sebelah kiri dan tonggak tujuan di sebelah kanan.

• b. asumsikan pula di sebelah tonggak kiri adalah tonggak kanan,

begitu pula sebaliknya.

• c. n adalah jumlah piringan yang ada pada tonggak yangsama dengan piringan yang lebih besar, dan tambahkan 1 bilapiringan terbesar berada pada tonggak kiri. Bila n genap, piringanberada pada 1 tonggak lebih kiri, dan bila n ganjil, piringan beradapada 1 tonggak lebih kanan.



Solusi Menggunakan Grey Code

Sisitem numerik binary dari Gray Code memberikan alternatif

pemecahan selain yang telah dijelaskan di atas. Sistem GrayCode, setiap angka di representasikan dalam bilangankombinasi binary dari 0s dan 1s, dan hal ini menjadi standard darisistem penomoran angka. Gray code beroperasi dengan premisbahwa setiap nilai berbeda dari nilai-nilai yang telah di berikansebelumnya dengan perbedaan hanya tepat satu bit saja.Nomor dari bits yang ada di dalam gray code sangat penting,

dan menggunakan kosong bukan hanya optional saja, tidak seperti di dalam sistem penentuan posisi.

Jika penghitungan dari ukuran bit di dalam gray code samadengan nomer dari piringan tertentu yang ada di Towers ofHanoi, mulai dengan kosong , dan bertambah secara teratur, lalubit berubah setiap perpindahan sesuai dengan perpindahan

piringan, di mana nilai signifikan bit terkecil adalah piringanterkecil dan nilai signifikan bit terbesar adalah piringan terbesar.



Lanjutan Gray Code :

Menghitung perpindahan dari 1 dan memberikan identitas kepadapiringan dimulai dari 0 dan bertambah nilai identitasnya sesuai

dengan pertambahan ukuran piringan, piringan yang utamadipindahkan selama memindahkan m adalah nomer dimana mdapat dibagi oleh dua.

Teknik identifikasi diatas disebabkan ileh perpindahan piringan,bukan karena kemana piringan tersebut dipindahkan. Untuk piringan paling kecil, selalu ada dua kemungkina pemindahan.Untuk piringan yang lainnya selalu ada satu kemungkinan yangmungkin, kecuali ketika semua piringan ada di dalam tiang yangsama , tetapi dalam kasus tersebut bukan hanya piringan yangkecil yang harus di pindahkan atau tujaunnya telah tercapai.Untungnya, di dalam gray code terdapat aturan yangmengatakan kemana harus memindahkan piringan terkecil.Asumsikan a menjadi tiang awal, b menjadi tiang tujuan, dan c

menjadi tiang yang ketiga yang tersisa. Jika nomor dari piringanganjul maka perputaran piringan yang terkecil selama di dalamperpindahan tiang adalah a-b-c-a-b-c,dan seterusnya . jika nomor dari piringan genap, maka ini perputaran piringan terkecil harusterbalik: a-c-b-a-c-b, dan seterusnya.



Aplikasi :• Dalam Neurologi :

Towers Of Hanoi biasanya digunakan di dalam penelitian-peneliltian untuk meneyelesaikan masalah-masalah yang berkaitan dengan memoriseseorang. Towers Of Hanoi di buat untuk mengecek apakah ia amnesiaatau tidak dengan dasar apakah ia dapat mengingat memori yangsebelum-sebelumnya yang terdapat di dalam Towers Of Hanoi.

• Dalam Backup DataDalam dunia informasi, Backup adalah membuat salinan dari data yangtelah di olah oleh user dan akan menyimpannya di sebuah mediapenyimpanan.

Hal ini di gunakan di karenakan dalam dunia informasi terdapat berbagaimacam aktivitas yang dapat menghilangkan data, seperti virus, kelalaianmanusia, media penyimpanan jatuh, terbakar,dll. Towers Of Hanoidigunakan di dalam backup data didalam skema rotasi backup. Skema

rotasi dalam backup memiliki beberapa teknik yang telah di teliti dandiaplikasikan. Diantaranya yaitu:a. Grandfather, father, and sonb. Towers Of Hanoic. Incremented Media Method



Lanjutan Aplikasi :

Skema backup rotasi itu ialah metode untuk membuatsalinan ketika menggunakan banyak media penyimpanan.Skema ini menentukan bagaimana dan kapan waktu yangtepat ketika akan menggunakan atau madia penyimpananyang tersedia. Selain itu, skema ini menentukan media

penyimpanan mana yang akan di gunakan dan berapalama proses penyimpanan itu berlangsung.

Kita hanya akan membahas skema rotasi backup denganteknik Towers Of Hanoi sesuai dengan topik yang sedangdibicarakan. Pembahasan skema teknik Grandfather, father,and son, serta teknik Incremental Media Method penulisserahkan kepada pembaca.



Implementasi Rekrusi Tower Of Hanoi – c ++

#include "stdio.h"#include "math.h"#include "conio.h"int n;char awal='A';char akhir='C';char mid='B';void menara(char awal,char akhir,char mid,int n){if (n==1)printf("pindahkan balok ke-%d dari %c ke %c\n",n,awal,akhir);else

{menara(awal,mid,akhir,n-1);printf("pindahkan balok ke-%d dari %c ke %c\n",n,awal,akhir);menara(awal,mid,akhir,n-1);}}

void main(){

int jum;printf ("Masukkan banyak balok n : ");scanf ("%d",&n);fflush (stdin);menara(awal,akhir,mid,n);

jum=pow(2,n)-1;printf("\n>>jumlah perpindahannya adalah : %d", jum);printf("\n\n\n");getchar ();}

tower of hanoi

Documents