THE TOWER OF HANOI [ menara hanoi ]

THE TOWER OF HANOI [ menara hanoi ]

Artikel ini aku buat sebagai tugas dari dosen Struktur Data saya, Pak Cahyo Wibowo. Beliau yang telah memberi tugas sekaligus memotivasi kami untuk belajar tentang menara Hanoi kemudian men-share nya di blog masing-masing . Terimaksih untuk Pak Cahyo karena selalu mengingatkan aku untuk berbagi …. :) :) 

APA SIH ‘THE TOWER OF HANOI’ ITU?

Yang pertamakali ada dibenakku tentang the tower of Hanoi atau menara Hanoi , adalah gambaran sebuah menara di Hanoi. Haha :D , langsung aja deh .. simak selengakpnya yuuk ..   J

M E N A R A   H A N O I  Sebuah permainan dimana sejumlah piringan dipindahkan dari tonggak satu ke tonggak lainnya dan dapat menggunakan tonggak bantuan . Menara Hanoi merupakan Salah satu puzzle yang unik karena memiliki berbagai macam variasi yang membutuhkan penyelesaian yang berbeda untuk tiap variasinya.

TUJUAN MEMPELAJARI THE TOER OF HANOI

Kenapa sih harus mempelajari menera Hanoi ini ??????

Hmm , di dalam ilmu computer,permasalahan seperti pada menara Hanoi ini seringkali muncul, terutama pada pengenalan kuliah Struktur data dan juga Algoritma.

Tujuan dari teka-teki ini sendiri adalah untuk memindahkan seluruh tumpukan ke tiang yang lain

SEJARAH THE TOWER OF HANOI

Tower of Hanoi ini memiliki asal muasal yang unik karena berasal dari sebuah legenda di Ind

Teka-teki ini ditemukan É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.

Permasalahan yang muncul saat itu ….

• 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 2⁶⁴-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 !

Karena permasalahan diatas yang muncul , maka muncullah penyeesaian seperti berikut  :

Aturan :

1. Hanya satu cakram yang boleh dipindahkan dalam satu waktu.  
2. 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. 
3. Tidak boleh meletakkan cakram di atas cakram lain yang lebih kecil.

Contoh , penyelesaian permasalahan yang muncul saat itu …

 

Untuk memindahkan n piringan dari tiang 1 ke tiang 3:

1. Pindahkan (n-1) piringan dari tiang 1 ke tiang 2
2. Pindahkan 1 piringan (terbesar) dari tiang 1 ke tian 3
3. Pindahkan (n-1) piringan dari tiang 2 ke tiang 3

H(n) : untuk memindahkan n piringan

1. H(n-1) pemindahan
2. 1 pemindahan             total ada  2H(n-1) + 1

H(n-1) pemindahan

RUMUS :

•         Rumus : H(n) = 2 H(n – 1) + 1

•         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

Keterangan   :  N = banyaknya piringan

ILUSTRASI GAMBAR

 

CONTOH PROGRAM

SOURCE CODE ..

#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 TAMPILAN [HASIL OUTPUT] ..

 

CONTOH SOURCE CODE LAIN

JAVA CODE

/**

 * TowersOfHanoi.java

 * Created by Stijn Strickx on Aug. 12 2006

 * Copyright 2006 Stijn Strickx, All rights reserved

 */

import java.io.*;

public class TowersOfHanoi {

               static int moves = 0;

               static int totalDisks = 0;

              

               public static void main(String[] arguments) throws java.io.IOException {

                               int disks;

                               char fromPole = 'A';

                               char withPole = 'B';

                               char toPole = 'C';

                               disks = getNumber("\nHow many disks are there on the tower? ");

                               totalDisks = disks;

                               if(totalDisks > 10){

                                              System.out.println("Working...")