Tujuan dari teka-teki ini adalah untuk memindahkan seluruh tumpukan ke tiang yang lain, mengikuti aturan berikut:
- Hanya satu cakram yang boleh dipindahkan dalam satu waktu.
- Setiap perpindahan berupa pengambilan cakram teratas dari satu tiang dan memasukkannya ke tiang lain, di atas cakram lain yang mungkin sudah ada di tiang tersebut.
- Tidak boleh meletakkan cakram di atas cakram lain yang lebih kecil.
- CONTOH Gambar/teka_teki towers of hanoi :
-Menara Hanoi teka-teki ini ditemukan oleh matematikawan Prancis 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 dan tidak pernah 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:
1. rekursif fungsi dan tumpukan
2. 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 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
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
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
Pindah dari Aux untuk Dst
Pindah dari Src ke Aux
Pindah dari Src untuk DST
Pindah dari Aux untuk Dst
Kekambuhan hubungan
Mari 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
Kami 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.
- A. Beck, MN Bleicher, DW Crowe, Excursions ke Matematika, AK Peters, 2000
Sumber Pustaka : http://www.cut-the-knot.org/recurrence/hanoi.shtml
0 komentar:
Posting Komentar