Aditya chandra_1135010020

Menara 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:

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.

Beli applet ini
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 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

Misalkan T _U adalah jumlah minimum langkah yang diperlukan untuk memecahkan teka-teki dengan disk N. Dari bagian sebelumnya T ₃ = 7 dan T ₄ = 15. Satu dapat dengan mudah meyakinkan diri sendiri bahwa T ₂ = 3 dan T ₁ = 1. Seorang ahli matematika yang terlatih juga akan mencatat bahwa T ₀ = 0.Sekarang marilah 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 _U ≤ T _N-1 + 1 + T _N-1 = 2T _N-1 + 1

Ketimpangan ini menunjukkan bahwa ada kemungkinan untuk memindahkan disk U dengan kurang dari2T _N-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 T _N-1 langkah.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 Dst untuk. 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

Dengan demikian kita dapat mendefinisikan kuantitas T _U sebagai

T ₀ = 0
T _U = 2T _N-1 + 1 untuk N> 0

Kami dapat menghitung T ₁ = 2T ₀ + 1 = 1, T ₂ = 2T ₁ + 1 = 3, T ₃ = 2T ₂ + 1 = 7 dan seterusnya secara berurutan.

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 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 T _U , mendefinisikan S _N = T _U + 1. Kemudian S ₀ = 1 dan S _N = T _U + 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 ₀ = 1
S _N = 2S _N-1 untuk N> 0

Yang terakhir ini diselesaikan dengan mudah dalam tertutup (tidak berulang) bentuk S _N = 2 ^N . Situlah

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.