Towers Of Hanoi

Kamis, 15 Maret 2012


Menara Hanoi disebut juga Menara Brahma atau Lucas Tower. Adalah permainan matematika atau teka-teki .Ini terdiri dari tiga batang dan sejumlah disk dengan ukuran yang berbeda yang dapat meluncur ke batang apapun. Teka-teki ini dimulai dengan disk dalam tumpukan rapi dalam urutan dari ukuran pada satu tongkat, yang terkecil di bagian atas, sehingga membuat bentuk kerucut.

Tujuan dari teka-teki adalah untuk memindahkan seluruh tumpukan ke batang lain, mematuhi aturan berikut:
Hanya satu disk dapat dipindahkan pada suatu waktu.



Asal Usul

Teka-teki ini ditemukan oleh Edouard Lucas pada tahun 1883. Ada legenda tentang India candi yang berisi sebuah ruangan besar dengan tiga waktu yang dikenakan di posting di dalamnya dikelilingi oleh 64 disk emas. Brahmana imam, dengan memerankan komando ramalan kuno, telah memindahkan disk ini, sesuai dengan aturan dari teka-teki. Sejak saat itu, teka-teki ini dikenal sebagai Menara Brahma. Menurut legenda, ketika langkah terakhir dari teka-teki selesai, dunia akan berakhir. Tidak jelas apakah Lucas menemukan legenda ini atau terinspirasi olehnya.
Ada banyak variasi pada legenda ini. Misalnya, dalam beberapa tellings, candi adalah biara dan para imam adalah biarawan . Kuil atau biara dapat dikatakan di berbagai belahan dunia - termasuk Hanoi, Vietnam , dan mungkin terkait dengan agama . Unsur lain diperkenalkan dalam beberapa versi, seperti fakta bahwa menara ini dibuat pada awal dunia, atau bahwa para imam atau biarawan dapat membuat hanya satu langkah per hari.

Solusi Rekursif




Sebuah kunci untuk memecahkan teka-teki ini adalah mengakui bahwa hal itu dapat diatasi dengan memecah masalah ke kumpulan masalah yang lebih kecil dan jauh lebih melanggar masalah tersebut ke dalam masalah yang lebih kecil sampai solusi tercapai. Berikut prosedur pendekatannya.

label pasak A, B, C-label ini dapat bergerak dengan langkah yang berbeda
n menjadi jumlah cakram
nomor cakram dari 1 (terkecil, paling atas) dengan n (terbesar, paling bawah)
Untuk memindahkan cakram n dari A ke pasak pasak C:
bergerak n -1 cakram dari A ke B. Ini disk daun n sendirian di pasak A
memindahkan n piringan dari A ke C
bergerak n -1 cakram dari B ke C sehingga mereka duduk di disc n

Di atas adalah algoritma rekursif : untuk melakukan langkah 1 dan 3, menerapkan algoritma yang sama lagi untuk n -1. Seluruh prosedur adalah jumlah terbatas langkah-langkah, karena di beberapa titik algoritma akan diminta untuk n = 1. Langkah ini, bergerak dari satu disk pasak pasak A ke B, adalah sepele. Pendekatan ini dapat diberikan formalisme matematika yang ketat dengan teoripemrograman dinamis , dan sering digunakan sebagai contoh rekursi ketika mengajar pemrograman.


Contoh program menara hanoi

package menara_hanoi;
import javax.swing.JOptionPane;
/**
 *
 * @author COMPAQ
 */
public class Main {
    static int move = 1;

    public static void main(String[] args) {
 
        String input=JOptionPane.showInputDialog("masukkan jumlah piringan:");
        int n=Integer.parseInt(input);
        hanoi (n, 'A', 'B', 'C');}

static void hanoi (int n, char awal, char bantu, char tujuan){

if (n>=1) { hanoi (n-1, awal, tujuan, bantu);
move(n, awal, tujuan);
hanoi (n-1, bantu, awal, tujuan);}}
static void move (int n, char awal, char tujuan){
System.out.print("Langkah "+move+"\n");
move++;
System.out.print("Pindahkan piringan "+n);
System.out.print(" dari "+awal);
System.out.print(" ke "+tujuan+"\n");
    }

}

Learning Recursion with the Towers of Hanoi



Aplikasi
Menara Hanoi sering digunakan dalam penelitian psikologis pada pemecahan masalah . Ada juga ada varian dari tugas ini disebut Menara London untuk diagnosis neuropsikologi dan pengobatan fungsi eksekutif.
Menara Hanoi juga digunakan sebagai skema rotasi Backup data komputer saat melakukan Backup di mana beberapa kaset / media yang terlibat.
Sebagaimana disebutkan di atas, Menara Hanoi adalah populer untuk mengajar algoritma rekursif untuk siswa pemrograman dimulai. Sebuah versi bergambar dari teka-teki ini diprogram ke dalamemacs editor, diakses dengan mengetik Mx hanoi. Ada juga algoritma sampel ditulis dalam Prolog .
Menara Hanoi juga digunakan sebagai ujian oleh neuropsychologists mencoba untuk mengevaluasi lobus frontal defisit

0 komentar:

Posting Komentar

 
Copyright © -2012 share knowledge :) All Rights Reserved | Template Design by Favorite Blogger Templates | Blogger Tips and Tricks