Towers of Hanoi atau dalam bahasa Indonesia
berarti Menara Hanoi (juga disebut Menara Brahma atau Lucas
Tower, 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.
disk dalam tumpukan rapi dalam urutan dari ukuran pada satu tongkat, yang terkecil di bagian atas, sehingga membuat bentuk kerucut.
Tujuannya adalah untuk mentransfer seluruh
menara ke salah satu pasak lainnya (yang paling kanan di applet bawah),
bergerak hanya satu disk pada suatu waktu dan tidak pernah yang lebih besar ke
kecil atau mematuhi aturan berikut:
- Hanya satu disk dapat dipindahkan pada suatu waktu.
- 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.
- Tidak dapat ditempatkan di atas sebuah disk lebih
kecil.
Dengan tiga disk, teka-teki dapat diselesaikan dalam tujuh
langkah.
Teka-teki ini
terkenal untuk mahasiswa Ilmu Komputer sejak muncul dalam hampir semua teks
pengantar pada struktur data atau algoritma. Its solution touches on two
important topics discussed later on: Solusinya menyentuh pada dua topik penting
yang dibahas di kemudian hari:
- rekursif fungsi dan tumpukan
- kambuh hubungan
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.
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 disk ini 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 ke Dst
- Pindahkan N - 1 disk dari Aux untuk Dst (menggunakan
Src sebagai pasak perantara)
Mentransfer N-1 disk atas dari Sumber ke menara Auxiliary
lagi dapat dianggap sebagai masalah baru dan dapat memecahkan dengan cara yang
sama. Jadi setelah Anda menguasai pemecahan Menara Hanoi dengan tiga disk, Anda
dapat memecahkannya dengan sejumlah disk dengan algoritma di atas.
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
exit
else
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
- Pindah dari
Src untuk DST
- Pindah dari
Src ke Aux
- Pindah dari
Dst ke Aux
- Pindah dari
Src untuk DST
- Pindah dari
Aux untuk Src
- Pindah dari
Aux untuk Dst
- Pindah dari
Src untuk DST
Tentu
saja "Pindah" berarti bergerak disk paling atas. Untuk N = 4 kita
mendapatkan urutan berikut
- Pindah dari
Src ke Aux
- Pindah dari
Src untuk DST
- Pindah dari
Aux untuk Dst
- Pindah dari
Src ke Aux
- Pindah dari
Dst untuk Src
- Aux Pindah
dari Dst ke Aux
- Pindah dari
Src ke Aux
- Pindah dari
Src untuk DST
- Pindah dari
Aux untuk Dst
- Pindah dari
Aux untuk Src
- Pindah dari
Dst untuk Src
- dari Aux
untuk Dst
- Pindah dari
Src ke Aux
- Pindah dari
Src untuk DST
- Pindah dari
Aux untuk Dst
Kekambuhan hubungan
Misalkan T U
adalah jumlah minimum langkah yang diperlukan untuk memecahkan teka-teki dengan
disk N. Dari bagian sebelumnya T 3 = 7 dan T 4 = 15. Satu
dapat dengan mudah meyakinkan diri sendiri bahwa T 2 = 3 dan T 1
= 1 Seorang ahli matematika terlatih juga. Akan mencatat bahwa T 0
= 0 Sekarang mari. Kita mencoba untuk mendapatkan seorang jenderal
formula.
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
T N ≤ T N-1 + 1 + T N-1
= 2T N-1 + 1 T U ≤ T N-1 + 1
+ T N-1 = 2T N-1 + 1
Ketimpangan ini
menunjukkan bahwa ada kemungkinan untuk memindahkan disk U dengan kurang dari
2T N-1 + 1 bergerak. Which is
actually not the case. 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 N-1 langkah T. Karena kita
berusaha untuk digunakan sebagai langkah sesedikit mungkin, kita bisa
mengasumsikan bahwa sebagian dari tugas mengambil persis T N-1
langkah. Hanya diperlukan satu gerakan untuk memindahkan disk terbesar dari Src
untuk Dst . Satu kemudian perlu persis T N-1 langkah lagi untuk
menyelesaikan tugas. Oleh karena itu jumlah minimum langkah yang diperlukan
untuk memecahkan teka-teki dengan disk N sama T N-1 + 1 +
T N-1 = 2T N-1 + 1 bergerak.
Dengan kata lain,
T N = 2T N-1 +
1 T N = 2T N-1 + 1
Dengan demikian kita dapat mendefinisikan kuantitas T N sebagai
T 0 = 0 T 0
= 0
T N = 2T N-1 + 1 for N > 0 T N = N-1 2T + 1 untuk N> 0
Kami dapat menghitung T 1 = 2T 0 + 1 = 1, T 2
= 2T 1 + 1 = 3, T 3 = 2T 2 + 1 = 7
dan seterusnya secara berurutan. T N = 2T N-1 + 1 for N > 0 T N = N-1 2T + 1 untuk N> 0
Ekspresi di atas dikenal sebagai
kambuh hubungan yang, seperti yang mungkin telah menyadari, hanyalah sebuah
fungsi rekursif. T U didefinisikan dalam hal hanya salah satu nilai
yang sebelumnyaHubungan 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 T U, mendefinisikan
S T U = N + 1. Kemudian S 0 = 1 dan S T N
= N + 1 = (2T N-1 + 1) + 1 = 2T N-1
+ 2 = 2 (T N-1 + 1) = 2S N-1. Yang berarti bahwa S N
dapat didefinisikan sebagai
S 0 = 1 S 0
= 1
S N = 2S N-1 for N > 0 S N = 2S N-1 untuk N> 0
Yang terakhir ini diselesaikan dengan mudah dalam tertutup (tidak berulang)
bentuk S N = 2 N. Situlah S N = 2S N-1 for N > 0 S N = 2S N-1 untuk N> 0
T N = 2 N - 1
for N ≥ 0. T N = 2 N - 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 sebuah penjelasan tentang algoritma-nya . Algoritma ini benar-benar
memberikan yang lain, solusi non-rekursif untuk teka-teki.
Catatan 2
Sebagai contoh, Anda mungkin ingin bereksperimen dengan yang bicolor atau
versi 3 warna.
Contoh Source Code :
paket de.vogella.algorithms.towersofhanoi;
/ **
* Towers of Hanoi
* Kutub diberi label 1, 2,3
* Setiap disk juga diberi label
* @ Author Lars Vogel
*
* /
public class TowersOfHanoi {
publik bergerak static void (int n, int startPole, int endPole) {
if (n == 0) {
kembali;
}
int intermediatePole = 6 - startPole - endPole;
bergerak (n-1, startPole, intermediatePole);
System.out.println ("Pindah" + n + "dari" + startPole + "untuk" + endPole);
bergerak (n-1, intermediatePole, endPole);
}
public static void main (String [] args) {
bergerak (5, 1, 3);
}
}
0 komentar:
Posting Komentar