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
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.
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
0 komentar :
Posting Komentar