Pemrograman java Challenge: Mengagumi Menara Hanoi - dummies

Tantangan ini membantu Anda menggunakan bakat pemrograman Anda untuk menulis program Java yang akan mencetak langkah-langkah yang diperlukan untuk memecahkan teka-teki Menara Hanoi mengingat jumlah disk.

Menara Hanoi adalah teka-teki logika klasik yang terdiri dari tiga pasak vertikal dan sejumlah cakram dengan berbagai diameter. Setiap cakram memiliki lubang di tengahnya, sehingga cakramnya tergelincir di pasak.

Teka-teki dimulai dengan semua disk yang ditumpuk di salah satu pasak, dengan disk terbesar di bagian bawah dan yang terkecil di atas. Objek teka-teki ini adalah untuk memindahkan tumpukan disk ke salah satu pegas lainnya, dengan mematuhi dua aturan sederhana: (1) Anda hanya dapat memindahkan satu disk pada satu waktu, dan (2) Anda tidak dapat menempatkan disk yang lebih besar pada atas yang lebih kecil.

Gambar berikut menunjukkan solusi untuk setumpuk tiga disk. Seperti yang Anda lihat, solusinya memerlukan tujuh gerakan:

Pindahkan Disk 1 dari Peg 1 ke Peg 3.
Pindahkan Disk 2 dari Peg 1 ke Peg 2.
Pindahkan Disk 1 dari Peg 3 ke Peg 2.
Pindahkan Disk 3 dari Peg 1 ke Peg 3.
Pindahkan Disk 1 dari Peg 2 ke Peg 1.
Pindahkan Disk 2 dari Peg 2 ke Peg 3.
Pindahkan Disk 1 dari Peg 1 ke Peg 3.

Setelah tujuh langkah ini, tumpukan disk akan berada di Peg 3.

Solusi untuk teka-teki Menara Hanoi dengan tiga disk.

Teka-teki akan menarik saat Anda mulai menambahkan disk ke posisi awal. Dengan tiga disk, teka-teki ini hanya membutuhkan 7 langkah untuk dipecahkan. Dengan empat disk, dibutuhkan 15 gerakan. Dengan lima disk, Anda memerlukan 31 gerakan. Enam disk membutuhkan 64 gerakan.

Jika Anda telah mengikuti matematika, jumlah gerakan yang dibutuhkan untuk menyelesaikan teka-teki meningkat secara eksponensial seiring bertambahnya jumlah disk. Secara khusus, jumlah gerakan yang diperlukan untuk memindahkan disk n adalah 2 ⁿ - 1. Misalnya, tumpukan 20 disk akan memerlukan 2 ²⁰ - 1 bergerak; Itu lebih dari satu juta bergerak!

Legenda yang menarik dikaitkan dengan teka-teki: Di sebuah kuil di Hanoi, para biksu telah mengerjakan teka-teki Towers of Hanoi dengan 64 disk sejak penciptaan bumi. Ketika mereka selesai, dunia akan berakhir. Untungnya, kita memiliki waktu yang lama untuk menunggu: Jika para bhikkhu dapat memindahkan satu disk per detik, maka akan ada 580 miliar tahun lagi sebelum mereka menyelesaikan teka-teki itu.

Tantangan Anda sederhana: Tuliskan program Java yang akan mencetak langkah-langkah yang diperlukan untuk memecahkan teka-teki Menara Hanoi yang diberi jumlah disk. Program pertama harus meminta pengguna untuk jumlah disk. Maka harus menampilkan langkah-langkahnya, satu per baris.Setiap langkah harus menunjukkan pegangan untuk memindahkan disk dari, dan yang pas untuk memindahkan disk ke. Langkah-langkahnya juga harus berurutan bernomor.

Setelah selesai, program harus diulang, meminta pengguna untuk jumlah disk lagi. Program harus berakhir saat pengguna memasuki 0.

Berikut adalah contoh keluaran konsol yang harus dihasilkan program Anda:

Berapa banyak disk? (0 sampai akhir) 3 1: 1 sampai 3 2: 1 sampai 2 3: 3 sampai 2 4: 1 sampai 3 5: 2 sampai 1 6: 2 sampai 3 7: 1 sampai 3 Berapa banyak disk ? (0 sampai akhir) 0

Satu-satunya persyaratan lain untuk memecahkan tantangan ini adalah bahwa solusi Anda harus menggunakan pemrograman rekursif. Dengan kata lain, solusi Anda harus menyertakan metode yang memanggil dirinya sendiri untuk memecahkan teka-teki itu.

Program rekursif bisa jadi tantangan, jadi berikut ini beberapa petunjuk untuk pemecahan teka-teki ini:

Teka-teki terdiri dari tiga pasak. Salah satunya berisi tumpukan awal disk; panggil pasak pasak ini . Salah satu dari dua pasak yang tersisa adalah pasak yang ingin Anda pindahkan setumpuk disk; Panggil ini pasangkan patok target . Pasokan ketiga tersedia untuk Anda gunakan sebagai pegangan perantara untuk menyimpan disk sementara karena Anda memindahkannya. Panggil pas ini pasak pasak .
Metode rekursif Anda harus menerima tiga parameter: jumlah disk bergerak, pasak sumber, dan pasak target. Gunakan nilai integer 1, 2, dan 3 untuk mewakili pasak. Ide dasar pemecahan teka-teki secara rekursif adalah ini: Untuk memindahkan setumpuk disk dari sumber pasak ke pasak target memerlukan tiga langkah:
Pindahkan semua disk di tumpukan kecuali disket bawah ke pasak pasak
1. Pindahkan disk terbesar ke tumpukan semula ke pasak target.
2. Pindahkan tumpukan yang Anda pindahkan pada Langkah 1 dari pasak pasak ke pasak target. Tentu saja, aturan teka-teki memungkinkan Anda memindahkan hanya satu disk pada satu waktu, jadi Anda tidak dapat menyelesaikan Langkah 1 dan 3 dari prosedur yang diberikan di sini hanya dengan mengambil tumpukan dan memindahkannya. Di situlah rekursi masuk. Untuk Langkah 1 dan 3, Anda memanggil metode ini secara rekursif, setiap kali menentukan satu disk yang lebih sedikit untuk dipindahkan, dan setiap kali menggunakan pasak target sebelumnya sebagai pasak cadangan.
3. Bingung mengapa metode rekursif tidak perlu menerima pasak pasak sebagai argumen? Karena Anda bisa dengan mudah menghitungnya, mengingat sumber dan target pasak. Karena hanya ada tiga pasak, diberi nomor 1, 2, dan 3, jumlah tiga pasak adalah 6 (1 + 2 + 3). Dengan adanya sumber dan pasak target, Anda bisa menghitung pasak pasak dengan mengurangkan sumber dan pasak target dari 6. Misalnya, jika sumber pasak 1 dan pasak target adalah 3, pasak pasak harus 2 karena
6 - 3 - 1 = 2.
Untuk solusinya, pergi ke tab Download halaman produk

Java All-in-One For Dummies,