Cabaran Pengaturcaraan java: Mengulangi Menara Hanoi - patung

Cabaran ini membantu anda menggunakan bakat pengaturcaraan anda untuk menulis program Java yang akan mencetak langkah-langkah yang diperlukan untuk menyelesaikan teka-teki Towers of Hanoi memandangkan jumlah cakera.

Menara Hanoi adalah teka-teki logik klasik yang terdiri daripada tiga pasak menegak dan beberapa cakera dari pelbagai diameter. Setiap cakera mempunyai lubang di tengah, yang membolehkan cakera-cakera itu diselubungi pasak.

Teka-teki itu bermula dengan semua cakera yang disusun di salah satu pasak, dengan cakera terbesar di bahagian bawah dan terkecil di bahagian atas. Objek teka-teki adalah untuk memindahkan tumpukan cakera ke salah satu pasak lain, mematuhi hanya dua peraturan mudah: (1) anda boleh memindahkan hanya satu cakera pada satu masa, dan (2) anda tidak boleh meletakkan cakera yang lebih besar pada atas yang lebih kecil.

Angka berikut menunjukkan penyelesaian untuk timbunan tiga cakera. Seperti yang anda dapat lihat, penyelesaian memerlukan tujuh langkah:

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

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

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

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

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

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

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

Selepas tujuh langkah ini, timbunan cakera akan berada di Peg 3.

Penyelesaian untuk teka-teki Towers of Hanoi dengan tiga cakera.

Teka-teki menjadi menarik apabila anda mula menambahkan cakera ke kedudukan permulaan. Dengan tiga cakera, teka-teki memerlukan hanya 7 langkah untuk menyelesaikannya. Dengan empat cakera, 15 langkah diperlukan. Dengan lima cakera, anda memerlukan 31 langkah. Enam cakera memerlukan 64 langkah.

Jika anda telah mengikuti matematik, bilangan langkah yang diperlukan untuk menyelesaikan teka-teki meningkat secara eksponen apabila bilangan cakera meningkat. Secara spesifik, bilangan langkah yang diperlukan untuk memindahkan cakera n ialah 2 ⁿ - 1. Sebagai contoh, timbunan 20 cakera memerlukan 2 ²⁰ - 1 bergerak; itu lebih daripada satu juta bergerak!

Satu legenda yang menarik dikaitkan dengan teka-teki: Di ​​sebuah kuil di Hanoi, para biku telah bekerja di Towers of Hanoi puzzle dengan 64 cakera sejak penciptaan bumi. Apabila mereka selesai, dunia akan berakhir. Mujurlah, kita mempunyai masa yang lama untuk menunggu: Jika sami dapat bergerak satu cakera sesaat, ia akan menjadi 580 bilion tahun lagi sebelum mereka menyelesaikan teka-teki.

Cabaran anda mudah: Tulis program Java yang akan mencetak langkah-langkah yang diperlukan untuk menyelesaikan teka-teki Towers of Hanoi memandangkan jumlah cakera. Program ini harus terlebih dahulu menggesa pengguna untuk jumlah cakera. Kemudian ia harus memaparkan langkah-langkah, satu per baris.Setiap langkah harus menunjukkan kepak untuk memindahkan cakera dari, dan kepak untuk memindahkan cakera ke. Langkah-langkah juga perlu diberi nombor berurutan.

Setelah selesai, program harus ulangi, meminta pengguna untuk jumlah cakera lagi. Program ini harus berakhir apabila pengguna memasuki 0.

Berikut adalah contoh output konsol program anda harus menghasilkan:

Berapa banyak cakera? (0 hingga akhir) 3 1: 1 hingga 3 2: 1 hingga 2 3: 3 hingga 2 4: 1 hingga 3 5: 2 hingga 1 6: 2 hingga 3 7: 1 hingga 3 Berapa cakera ? (0 hingga tamat) 0

Satu-satunya keperluan lain untuk menyelesaikan cabaran ini ialah penyelesaian anda mesti menggunakan pengaturcaraan rekursif. Dengan kata lain, penyelesaian anda mesti termasuk kaedah yang memanggil dirinya untuk menyelesaikan teka-teki.

Pengaturcaraan rekursif boleh mencabar, jadi berikut adalah beberapa petunjuk untuk penyelesaian teka-teki ini:

• Teka-teki terdiri daripada tiga pasak. Salah satunya mengandungi tumpuan cakera permulaan; panggil peg ini pancang sumber . Salah satu daripada dua pasak yang lain adalah tiang yang anda hendak alihkan tumpukan cakera; panggil peg ini pegat sasaran . Palang ketiga tersedia untuk digunakan sebagai pancang pertengahan untuk menyimpan cakera pada sementara ketika anda memindahkannya. Panggil peg ini pegat ganti .

• Kaedah rekursif anda harus menerima tiga parameter: bilangan cakera untuk bergerak, pasak sumber, dan pasang sasaran. Gunakan nilai integer 1, 2, dan 3 untuk mewakili pasak.

• Idea asas menyelesaikan teka-teki secara rekursif adalah ini: Untuk memindahkan timbunan cakera dari pasak sumber ke pasak sasaran memerlukan tiga langkah:

  1. Pindahkan semua cakera dalam timbunan kecuali cakera bawah ke pegangan ganti.

  2. Pindahkan cakera terbesar dalam timbunan asal kepada pasak sasaran.

  3. Pindahkan timbunan yang anda bergerak di Langkah 1 dari pasak ganti ke pasak sasaran.

• Sudah tentu, peraturan teka-teki membolehkan anda untuk memindahkan hanya satu cakera pada satu masa, jadi anda tidak dapat mencapai Langkah 1 dan 3 prosedur yang diberikan di sini dengan hanya mengambil stack dan memindahkannya. Di sinilah rekursi masuk Untuk Langkah 1 dan 3, anda memanggil kaedah secara rekursif, setiap kali menentukan satu cakera yang lebih sedikit untuk dipindahkan, dan setiap kali menggunakan pasak sasaran sebelumnya sebagai pasang ganti.

• Tertanya-tanya mengapa kaedah rekursif tidak perlu menerima pegangan ganti sebagai hujah? Kerana anda dengan mudah boleh mengira, memandangkan pasak sumber dan target. Oleh kerana terdapat hanya tiga pasak, berjumlah 1, 2, dan 3, jumlah tiga pasak adalah 6 (1 + 2 + 3). Memandangkan sumber dan pasak sasaran, anda boleh mengira pasang ganti dengan menolak sumber dan sasaran tiang dari 6. Sebagai contoh, jika pasak sumber adalah 1 dan pasak sasaran adalah 3, pasang ganti mestilah 2 kerana

  6 - 3 - 1 = 2.

Untuk penyelesaiannya, pergi ke tab Muat Turun pada halaman produk Java All-in-One Untuk Dummies, Edisi ke-4.

Nasib baik!