Towers of hanoi (Menara Hanoi), teka-teki ini ditemukan
oleh matematikawan Prancis yaitu Edouard Lucas pada 1883. Kita
diberi sebuah
menara delapan disk (awalnya empat di
applet bawah), awalnya ditumpuk dalam ukuran peningkatan
pada salah satu dari tiga pasak. Tujuannya adalah untuk
mentransfer seluruh menara ke salah
satu pasak lainnya (yang paling kanan di applet bawah), bergerak hanya satu disk pada suatu
waktu dari yang lebih besar ke kecil.
Teka-teki ini terkenal untuk mahasiswa Ilmu Komputer sejak muncul
dalam hampir semua teks pengantar pada struktur data
atau algoritma. Solusinya menyentuh pada dua
topik penting yang dibahas di kemudian hari :
Rekursif fungsi dan tumpukan
Applet memiliki beberapa kontrol yang memungkinkan
seseorang untuk memilih jumlah disk dan
mengamati solusi dengan cara Cepat atau Lambat. Untuk
memecahkan teka-teki disk drag dari satu wadah ke
wadah lainnya mengikuti aturan. Anda dapat menjatuhkan sebuah
disk ke pasak ketika pusatnya cukup dekat dengan
pusat dari pasak. Applet mengharapkan Anda untuk
memindahkan disk dari pasak paling kiri ke paling
kanan pasak.
Bagaimana jika applet tidak berjalan?
Rekursif solusi
Mari memanggil tiga pasak Src (Sumber), Aux (Auxiliary) dan Dst (Tujuan). Untuk lebih memahami dan menghargai solusi berikut Anda harus mencoba
memecahkan teka-teki untuk sejumlah kecil disk, katakanlah, 2,3, dan, mungkin,
4. Namun satu memecahkan masalah, cepat atau lambat disk
bawah harus dipindahkan dari Src untuk DST. Pada titik waktu ini
semua disk yang tersisa harus ditumpuk dalam urutan menurun ukuran tentang Aux. Setelah pindah disk bawah dari Src untuk DST ini disjs harus dipindahkan
dari Aux untuk Dst. Oleh karena itu, untuk N jumlah tertentu
disk, masalah tampaknya dipecahkan jika kita tahu bagaimana menyelesaikan
tugas-tugas berikut:
Pindahkan N atas - 1 disk dari Src ke Aux (menggunakan Dst sebagai pasak
perantara)
Pindahkan disk bawah dari Src Dst untuk
Pindahkan N - 1 disk dari Aux untuk Dst (menggunakan Src sebagai pasak
perantara)
Asumsikan ada fungsi Memecahkan dengan empat argumen - jumlah disk dan tiga
pasak (sumber, perantara dan tujuan - dalam urutan ini). Kemudian tubuh fungsi akan terlihat seperti
Memecahkan (N, Src, Aux, Dst)
jika N adalah 0
keluar
lain
Memecahkan (N - 1, Src, Dst, Aux)
Pindah dari Src untuk DST
Memecahkan (N - 1, Aux, Src, Dst)
Ini benar-benar berfungsi sebagai definisi fungsi Memecahkan. Fungsinya adalah rekursif dalam hal itu berulang kali menyebut dirinya
dengan penurunan nilai dari N sampai kondisi mengakhiri (dalam kasus kami N =
0) telah dipenuhi. Bagi saya kesederhanaan belaka dari solusi
adalah hati. Untuk N = 3 itu diterjemahkan menjadi
Move from Src to Dst
Move from Src to Aux
Move from Dst to Aux
Move from Src to Dst
Move from Aux to Src
Move from Aux to Dst
Move from Src to Dst
Tentu saja "Move" berarti bergerak disk
paling atas. Untuk N = 4 kita mendapatkan urutan
berikut
Move from Src to Aux
Move from Src to Dst
Move from Aux to Dst
Move from Src to Aux
Move from Dst to Src
Move from Dst to Aux
Move from Src to Aux
Move from Src to Dst
Move from Aux to Dst,o:p>
Move from Aux to Src
Move from Dst to Src
Move from Aux to Dst
Move from Src to Aux
Move from Src to Dst
Move from Aux to Dst
Kekambuhan hubungan
TN adalah jumlah minimum langkah yang diperlukan untuk memecahkan teka-teki
dengan disk N. Dari bagian sebelumnya T3 dan T4 = 7 = 15. Satu dapat dengan mudah meyakinkan diri sendiri bahwa T2 = T1 = 3 dan 1. Seorang ahli matematika yang terlatih juga akan mencatat bahwa T0 = 0. Sekarang mari kita mencoba untuk menurunkan rumus umum.
Solusi rekursif di atas melibatkan bergerak dua kali (N - 1) disk dari satu
wadah ke wadah lainnya dan membuat satu gerakan tambahan di antaranya. Kemudian berikut bahwa
TN ≤ TN-1 + 1 + TN-1 = 2TN-1 + 1
Ketimpangan ini menunjukkan bahwa ada kemungkinan untuk memindahkan disk U
dengan kurang dari 2TN-1 + 1 bergerak. Yang sebenarnya tidak
terjadi.Memang, ketika saatnya tiba untuk memindahkan disk bawah, (N - 1) disk
lebih kecil akan telah pindah dari Src ke Aux dalam setidaknya-1 TN bergerak. Karena kita berusaha untuk digunakan sebagai langkah sesedikit mungkin,
kita bisa mengasumsikan bahwa sebagian dari tugas mengambil persis TN-1
bergerak.Hanya diperlukan satu gerakan untuk memindahkan disk terbesar dari Src
Dst untuk. Satu kemudian perlu langkah-langkah persis
TN-1 lebih untuk menyelesaikan tugas. Oleh karena itu jumlah
minimum langkah yang diperlukan untuk memecahkan teka-teki dengan disk N sama
dengan TN-1 + 1 + TN-1 = 2TN-1 + 1 bergerak.
Dengan kata lain,
TN = 2TN-1 + 1
Dengan demikian kita dapat mendefinisikan TN kuantitas
T0 = 0
TN = 2TN-1 + 1 untuk N> 0
Kita dapat menghitung T1 = 2T0 + 1 = 1, T2 = 2T1 + 1 = 3, T3 = 2T2 + 1 = 7 dan
seterusnya secara berurutan.
Ekspresi di atas dikenal sebagai relasi rekursi yang, seperti yang mungkin
telah menyadari, hanyalah sebuah fungsi rekursif. TN didefinisikan dalam hal hanya salah satu nilai yang sebelumnya. Hubungan kambuh lain mungkin lebih rumit, misalnya, f (N) = 2f (N - 1) + 3f
(N - 2). Hubungan kambuh muncul di bawah berbagai
samaran dalam banyak cabang Matematika dan aplikasi.
Kembali ke definisi TN, mendefinisikan SN = TN + 1. Kemudian S0 = 1 dan SN = TN + 1 = (2TN-1 + 1) + 1 = 2TN-1 + 2 = 2 (TN-1 +
1) = 2SN-1. Yang mengatakan bahwa SN dapat
didefinisikan sebagai
S0 = 1
SN = 2SN-1 untuk N> 0
Yang terakhir ini diselesaikan dengan mudah dalam bentuk tertutup (tidak
berulang) SN = 2N. Situlah
TN = 2N - 1 untuk N ≥ 0.
Catatan 1
Pelaksanaan terbaru applet olahraga "Sarankan bergerak" tombol yang
memanfaatkan algoritma yang dibuat oleh Romek Zylla yang anggun memasang di Web
penjelasan tentang algoritma-nya. Algoritma ini
benar-benar memberikan yang lain, solusi non-rekursif untuk teka-teki.
Catatan 2
Ada cukup beberapa variasi pada teka-teki. Sebagai contoh, Anda
mungkin ingin bereksperimen dengan yang bicolor atau 3 warna versi.
Referensi
A. Beck, MN Bleicher, DW Crowe, Excursions ke Matematika, AK Peters, 2000
Menara Hanoi
Menara Hanoi, Jalan Keras
Bicolor Towers of Hanoi
Bicolor Towers of Hanoi, Solusi
3-Warna Menara Hanoi
3-Warna Menara Hanoi (Algoritma)
Hanoing
Sierpinski Garket dan Menara Hanoi
Di Internet
Kombinatorial Obyek Server
Menara Hanoi di Web, Miroslav Kolar
Baru cepat berulang algoritma komputer untuk teka-teki Menara Hanoi, M. Kolar
Sebuah implementasi JavaScript yang menampilkan tombol Bantuan. Salah satu jenis yang. Dengan Romek Zylla. Versi ini menggunakan bingkai, yang lain adalah tanpa bingkai.
Sebuah varian multi-pasak oleh Robert J. Swartz.
Source 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;
$3B 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;
$3B BufferedReader
in = new BufferedReader (new InputStreamReader(System.in));
System.out.print(question);
theNumber
= in.readLine();
System.out.println();
number
= Integer.parseInt(theNumber);
return
number;
}
}
Sumber Pustaka :
- www.cut-the-knot.org
- www.proglogic.com
- www.youtube.com
.
