Tower of Hanoi

 

Menara Hanoi (juga disebut Menara Brahma atau Lucas Tower, [1] dan terkadang pluralised) 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:

   1.  Hanya satu disk dapat dipindahkan pada suatu waktu.
   2.  Setiap langkah terdiri dari mengambil disk atas dari salah satu batang dan menggesernya ke batang yang lain, di atas disk lain yang mungkin sudah ada pada batang itu.
   3.  Disk Tidak dapat ditempatkan di atas sebuah disk lebih kecil.

Asal

Teka-teki ini ditemukan oleh matematikawan Prancis Edouard Lucas pada tahun 1883. Ada sebuah legenda tentang candi Indian yang berisi ruang besar dengan tiga waktu yang dikenakan di posting di dalamnya dikelilingi oleh 64 disk emas. Imam brahmana, dengan memerankan komando ramalan kuno, telah memindahkan disk ini, sesuai dengan aturan teka-teki, sejak saat itu. Teka-teki ini karena itu juga dikenal sebagai Menara puzzle Brahma. Menurut legenda, ketika langkah terakhir dari teka-teki selesai, dunia akan berakhir. Tidak jelas apakah Lucas menemukan legenda ini atau terinspirasi olehnya.

Jika legenda itu benar, dan jika imam mampu memindahkan disk dengan laju satu per detik, dengan menggunakan jumlah terkecil bergerak, itu akan membawa mereka 264-1 detik atau sekitar 585 miliar tahun atau 18.446.744.073.709.551.615 bergantian selesai.

Ada banyak variasi pada legenda ini. Misalnya, dalam beberapa tellings, kuil adalah sebuah biara dan para imam adalah biarawan. Kuil atau biara dapat dikatakan di berbagai belahan dunia - termasuk Hanoi, Vietnam, dan mungkin terkait dengan agama apapun. Dalam beberapa versi, unsur lain diperkenalkan, seperti fakta bahwa menara ini dibuat pada awal dunia, atau bahwa para imam atau biarawan dapat membuat hanya satu langkah per hari.

Larutan
Teka-teki bisa dimainkan dengan jumlah disk, meskipun versi mainan banyak memiliki sekitar tujuh sampai sembilan dari mereka. Permainan ini tampaknya tidak mungkin untuk pemula banyak, namun dipecahkan dengan algoritma sederhana. Jumlah langkah yang diperlukan untuk memecahkan teka-teki Menara Hanoi adalah 2n -1, dimana n adalah jumlah disk.Iteratif solusi
Solusi berikut adalah solusi sederhana untuk teka-teki mainan.
Alternatif bergerak antara bagian terkecil dan sepotong non-terkecil. Ketika memindahkan bagian terkecil, selalu memindahkannya ke posisi berikutnya dalam arah yang sama (ke kanan jika jumlah awal potongan bahkan, ke kiri jika jumlah awal potongan aneh). Jika tidak ada posisi menara ke arah yang dipilih, memindahkan potongan ke ujung, tapi kemudian terus bergerak ke arah yang benar. Misalnya, jika Anda mulai dengan tiga potong, Anda akan memindahkan bagian terkecil ke ujung, lalu lanjutkan ke arah kiri setelah itu. Ketika gilirannya adalah untuk memindahkan bagian non-terkecil, hanya ada satu langkah hukum. Melakukan hal ini akan menyelesaikan teka-teki menggunakan jumlah paling sedikit bergerak untuk melakukannya.
Barangkali perlu dicatat bahwa ini dapat ditulis sebagai satu set mencolok elegan aturan:Pernyataan Simpler solusi iteratif

Bergantian antara yang terkecil dan mendatang terkecil disk, ikuti langkah-langkah untuk kasus yang sesuai:
Untuk bahkan jumlah disk:

    melakukan langkah hukum antara pasak A dan B
    melakukan langkah hukum antara pasak A dan C
    melakukan langkah hukum antara pasak B dan C
    ulangi sampai lengkap
Untuk ganjil disk:

    melakukan langkah hukum antara pasak A dan C
    melakukan langkah hukum antara pasak A dan B
    melakukan langkah hukum antara pasak B dan C
    ulangi sampai lengkap

Dalam setiap kasus, sebanyak 2n-1 bergerak yang dibuat.Setara Iteratif SolusiCara lain untuk menghasilkan yang optimal unik iteratif solusi, adalah untuk nomor disk 1 sampai n, terbesar ke terkecil. Jika n ganjil, langkah pertama adalah dari Start ke Finish pasak, dan jika n adalah bahkan langkah pertama adalah dari Start untuk pasak Menggunakan.
Sekarang, tambahkan batasan bahwa tidak ada disk yang aneh dapat ditempatkan langsung pada disk aneh, dan tidak ada disk bahkan dapat ditempatkan langsung pada disk bahkan. Dengan kendala ekstra, dan aturan yang jelas tidak pernah melepas langkah terakhir, hanya ada satu gerakan di setiap kesempatan. Urutan langkah yang unik adalah solusi optimal untuk masalah setara dengan iteratif solusi yang dijelaskan di atas.

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

    label pasak A, B, C-label ini dapat bergerak dengan langkah yang berbeda
    mari 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:

    memindahkan n-1 cakram dari A ke B. Ini disk daun n sendirian di pasak A
    memindahkan n piringan dari A ke C
    memindahkan 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 teori pemrograman dinamis, dan sering digunakan sebagai contoh rekursi ketika mengajar pemrograman.analisis logis dari solusi rekursif
Seperti di banyak teka-teki matematika, menemukan solusi menjadi lebih mudah dengan memecahkan masalah yang sedikit lebih umum: bagaimana memindahkan menara h (h = tinggi) disk dari pasak awal A (f = dari) ke tujuan pasak C (t = untuk), B menjadi pasak ketiga tersisa dan dengan asumsi t ≠ f. Pertama, amati bahwa masalahnya adalah simetris untuk permutasi dari nama-nama pasak (simetris kelompok S3). Jika solusi ini dikenal bergerak dari A ke pasak pasak C, maka, dengan mengganti nama pasak, solusi yang sama dapat digunakan untuk setiap pilihan lain untuk memulai dan pasak tujuan. Jika hanya ada satu disk (atau bahkan tidak sama sekali), masalahnya adalah sepele. Jika h = 1, maka cukup memindahkan disk tersebut dari A ke pasak pasak C. Jika h> 1, maka suatu tempat di sepanjang urutan bergerak, disk terbesar harus pindah dari A ke pasak pasak lain, sebaiknya untuk mematok C. hanya situasi yang memungkinkan langkah ini adalah ketika semua h-1 lebih kecil disk berada di pasak B. Oleh karena itu, pertama semua h-1 disk yang lebih kecil harus pergi dari A ke B. Kemudian memindahkan disk terbesar dan akhirnya memindahkan h-1 disk lebih kecil dari pasak B untuk mematok C. Kehadiran disk terbesar tidak menghambat setiap langkah dari h-1 disk lebih kecil dan untuk sementara dapat diabaikan. Sekarang masalahnya berkurang untuk bergerak h-1 disk dari satu wadah ke satu sama lain, pertama dari A B ke B dan kemudian dari ke C, tetapi metode yang sama dapat digunakan dua kali dengan mengganti nama pasak. Strategi yang sama dapat digunakan untuk mengurangi masalah h-1 untuk h-2, h-3, dan seterusnya sampai hanya satu disk yang tersisa. Ini disebut rekursi. Algoritma ini dapat schematized sebagai berikut. Mengidentifikasi disk di urutan ukuran meningkat alam nomor dari 0 sampai dengan tetapi tidak termasuk jam. Oleh karena itu disk 0 adalah yang terkecil dan disk h-1 yang terbesar.
Berikut ini adalah prosedur untuk memindahkan menara disk jam dari pasak A ke C pasak, dengan B menjadi pasak ketiga tersisa:

    Langkah 1: Jika h> 1 maka pertama menggunakan prosedur ini untuk memindahkan h-1 disk lebih kecil dari A ke pasak pasak B.
    Langkah 2: Sekarang disk terbesar, yaitu hard disk h-1 dapat dipindahkan dari pasak pasak A ke C.
    Langkah 3: Jika h> 1 maka lagi menggunakan prosedur ini untuk memindahkan h-1 disk lebih kecil dari B ke pasak pasak C.
Dengan cara induksi matematika, hal ini mudah dibuktikan bahwa prosedur di atas mengharuskan jumlah minimal bergerak mungkin, dan bahwa solusi yang dihasilkan adalah satu-satunya dengan jumlah minimal bergerak. Menggunakan hubungan kambuh, persis jumlah langkah yang membutuhkan solusi ini dapat dihitung dengan: 2 ^ h - 1. Hasil ini diperoleh dengan mencatat bahwa langkah 1 dan 3 mengambil T_ {h-1} bergerak, dan langkah 2 mengambil satu gerakan, memberikan T_h = 2T_ {h-1} + 1.[Sunting] Non-rekursif solusi
Daftar bergerak untuk sebuah menara yang dilakukan dari satu wadah ke yang lain, seperti yang dihasilkan oleh algoritma rekursif memiliki keteraturan banyak. Bila dihitung bergerak mulai dari 1, ordinal disk yang akan dipindahkan selama m bergerak adalah jumlah m kali dapat dibagi dengan 2. Oleh karena itu setiap gerakan aneh melibatkan disk terkecil. Hal ini juga dapat diamati bahwa melintasi disk terkecil f pasak, t, r, f, t, r, dll untuk ketinggian aneh menara dan melintasi f pasak, r, t, f, r, t, dll bahkan untuk ketinggian menara. Ini menyediakan algoritma berikut, yang lebih mudah, dilakukan dengan tangan, daripada algoritma rekursif.
Dalam bergerak alternatif:

    memindahkan disk terkecil ke pasak itu tidak baru datang dari.
    memindahkan disk lain secara hukum (akan ada satu kemungkinan saja)
Untuk langkah pertama, disk terkecil pergi ke pasak t jika h adalah aneh dan untuk mematok r jika h bahkan.
Juga mengamati bahwa:

    Disk yang ordinals memiliki bahkan bergerak paritas dalam arti yang sama seperti disk terkecil.
    Disk yang ordinals memiliki langkah paritas ganjil dalam arti yang berlawanan.
    Jika h adalah bahkan, pasak ketiga tersisa selama bergerak berturut-turut adalah t, r, f, t, r, f, dll
    Jika h adalah aneh, pasak ketiga tersisa selama bergerak berurutan adalah r, t, f, r, t, f, dll
Dengan pengetahuan ini, satu set disk di tengah solusi optimal dapat dipulihkan dengan informasi negara tidak lebih dari posisi setiap disk:

    Panggil bergerak rinci di atas 'alami' bergerak disk.
    Periksa disk atas terkecil yang tidak disk 0, dan perhatikan apa yang satu-satunya (hukum) bergerak akan menjadi: (jika tidak ada disk tersebut, maka kita baik pada langkah pertama atau terakhir).
    Jika langkah yang 'alami' disk yang bergerak, maka disc tidak digerakkan sejak pindah 0 disc terakhir, dan langkah yang harus diambil.
    Jika langkah yang tidak 'alami' disk yang bergerak, kemudian bergerak 0 disk.
Binary solusi
Posisi Disk dapat ditentukan lebih langsung dari biner (basis 2) representasi dari jumlah bergerak (keadaan awal yang bergerak # 0, dengan semua digit 0, dan makhluk keadaan akhir # 2n-1, dengan semua angka 1), menggunakan berikut aturan:

    Ada satu digit biner (bit) untuk setiap disk
    Bit (paling kiri) merupakan yang paling signifikan disk terbesar. Nilai 0 menunjukkan bahwa disk terbesar adalah pada pasak awal, sementara 1 menunjukkan bahwa itu ada di pasak akhir.
    Bitstring itu dibaca dari kiri ke kanan, dan tiap bit dapat digunakan untuk menentukan lokasi disk yang sesuai.
    Sebuah bit dengan nilai yang sama dengan yang sebelumnya berarti bahwa disk yang bersangkutan akan ditumpuk di atas disk sebelumnya pada pasak yang sama.
        (Artinya: urutan lurus dari 1 atau 0 berarti bahwa disk yang sesuai semua pada pasak yang sama).
    Sebuah bit dengan nilai yang berbeda dengan yang sebelumnya berarti bahwa disk yang sesuai adalah satu posisi ke kiri atau kanan yang sebelumnya. Apakah itu kiri atau kanan ditentukan oleh aturan ini:
        Asumsikan bahwa pasak awal adalah di sebelah kiri dan pasak terakhir adalah di sebelah kanan.
        Juga menganggap "membungkus" - sehingga jumlah pasak yang tepat sebagai salah satu pasak "kiri" dari pasak kiri, dan sebaliknya.
        Misalkan n jumlah disk yang lebih besar yang terletak di pasak yang sama seperti disk pertama mereka yang lebih besar dan tambahkan 1 jika disk terbesar adalah pada pasak kiri. Jika n adalah bahkan, disk terletak satu pasak ke kiri, jika n adalah ganjil, disk terletak satu pasak ke kanan.
Sebagai contoh, dalam sebuah 8-disk Hanoi:

    Pindahkan 0
        Disk terbesar adalah 0, sehingga pada pasak (awal) kiri.
        Semua disk lainnya adalah 0 juga, sehingga mereka ditumpuk di atasnya. Oleh karena itu semua disk berada di pasak awal.
    Pindahkan 28-1
        Disk terbesar adalah 1, sehingga pada pasak (akhir) benar.
        Semua disk lainnya 1 juga, sehingga mereka ditumpuk di atasnya. Oleh karena itu semua disk berada di pasak akhir dan teka-teki selesai.
    Pindah 011011000 = 21610
        Disk terbesar adalah 1, sehingga pada pasak (akhir) benar.
        Disk kedua adalah juga 1, sehingga ditumpuk di atasnya, di pasak yang tepat.
        Disk tiga adalah 0, sehingga pada pasak yang lain. Sejak n adalah ganjil (n = 3), adalah salah satu pasak ke kanan, yaitu pada pasak kiri.
        Disk empat adalah 1, sehingga pada pasak yang lain. Sejak n genap (n = 2), adalah salah satu pasak ke kiri, yaitu pada pasak yang tepat.
        Disk lima adalah juga 1, sehingga ditumpuk di atasnya, di pasak yang tepat.
        Disk enam adalah 0, sehingga pada pasak yang lain. Sejak n adalah ganjil (n = 5), disk adalah salah satu pasak ke kanan, yaitu pada pasak kiri.
        Disk tujuh dan delapan juga 0, sehingga mereka ditumpuk di atasnya, pada pasak kiri.
Sumber dan pasak tujuan untuk bergerak mth juga dapat ditemukan elegan dari representasi biner dari m menggunakan operasi bitwise. Untuk menggunakan sintaks bahasa pemrograman C, memindahkan m adalah dari pasak (m & m-1) 3% untuk mematok ((m | m-1) +1)% 3, jika disk dimulai pada pasak 0 dan selesai pada pasak 1 atau 2 menurut seperti apakah jumlah disk adalah genap atau ganjil. Formulasi lain adalah dari pasak (m-(m & m))% 3 untuk mematok (m + (m & m))% 3.
Selanjutnya disk untuk dipindahkan ditentukan oleh berapa kali hitungan bergerak (m) dapat dibagi oleh 2 (yaitu jumlah bit nol di bagian kanan), menghitung langkah pertama sebagai 1 dan mengidentifikasi disk dengan angka 0 , 1, 2 dll dalam rangka ukuran meningkat. Hal ini memungkinkan implementasi non-rekursif komputer yang sangat cepat untuk menemukan posisi disk setelah bergerak m tanpa referensi untuk setiap langkah sebelumnya atau distribusi disk.
Hitungannya nol tertinggal (ctz) operasi, yang menghitung jumlah angka nol berturut-turut pada akhir bilangan biner, memberikan solusi sederhana untuk masalah: disk diberi nomor dari nol, dan pada m bergerak, disk jumlah ctz (m) dipindahkan jarak minimum yang mungkin ke kanan (berputar-putar kembali sekitar ke kiri sesuai kebutuhan).

 

Source code Tower Of Hanoi

/**
 * 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...");
   }
  FileOutputStream fos = new FileOutputStream("TowersOfHanoiSolution.txt");
  PrintStream ps = new PrintStream(fos);
  solveHanoi(disks, fromPole, toPole, withPole, ps);
  ps.close();
  System.out.println();
  System.out.println("\nAmount of moves: " + moves + "\n");
  System.out.print("You can now access the TowersOfHanoiSolution.txt file");
  System.out.println(" which is in the same directory as the .class file of this program.");
  }
 
 static void solveHanoi(int disks, char fromPole, char toPole, char withPole, PrintStream ps) {
  if (disks >= 1) {
   solveHanoi(disks-1, fromPole, withPole, toPole, ps);
   moveDisk(fromPole, toPole, ps);
   solveHanoi(disks-1, withPole, toPole, fromPole, ps);
   }
  }
  
 static void moveDisk(char fromPole, char toPole, PrintStream ps) {
  moves++;
  if(totalDisks <= 10){
   System.out.print("Move from " + fromPole + " to " + toPole + ". ");
   ps.print("Move from " + fromPole + " to " + toPole + ". ");
   if (moves%4 == 0){
    System.out.println();
    ps.println();
    }
   }
   else {
   ps.print("Move from " + fromPole + " to " + toPole + ". ");
   if (moves%4 == 0){
    ps.println();
    }
   }
  }
 
 static int getNumber(String question) throws java.io.IOException {
  String theNumber;
  int number = 0;
  BufferedReader in = new BufferedReader (new InputStreamReader(System.in));
  System.out.print(question);
  theNumber = in.readLine();
  System.out.println();
  number = Integer.parseInt(theNumber);
  return number;
  }
 }

Posted in: