Bagaimana untuk menganalisis masalah Menara Hanoi menggunakan Java

1. Sumber masalah Menara Hanoi

Menara Hanoi, juga dikenali sebagai Menara Hanoi, adalah mainan pendidikan yang berasal dari legenda India kuno. Apabila Brahma mencipta dunia, dia membuat tiga tiang berlian Pada satu tiang, 64 cakera emas disusun mengikut saiz dari bawah ke atas. Brahma mengarahkan Brahmin untuk menyusun semula cakera pada tiang lain mengikut saiz dari bawah. Dan ditetapkan bahawa cakera tidak boleh dibesarkan pada cakera kecil, dan hanya satu cakera boleh digerakkan antara tiga tiang pada satu masa

2. Analisis Masalah

Mulakan dengan soalan mudah

Mungkin sukar untuk memikirkan 64 pinggan secara langsung Kita boleh mulakan dengan 1 pinggan, seperti yang ditunjukkan di bawah:

Satu pinggan

A -> C

Apabila hanya ada satu plat, kita boleh terus mengalihkan plat pada tiang A ke tiang C

Perlu bergerak sekali

Dua pinggan

Apabila ada dua pinggan, kita juga boleh mencapainya dengan cara berikut:

A -> ->C B->C

Perlu bergerak 3 kali

1 >

2. A -> C

3. B -> C

Tiga plat

Apabila terdapat tiga plat, langkah bergerak adalah seperti berikut:

A -> B C -> -> C A -> C

Sebanyak 7 pergerakan diperlukan

1. A -> 🎜>

2. A -> B

3. C -> B

4. A -> C

5. B -> >C

7. A -> C

Ini melengkapkan pergerakan 3 plat

Apabila ada 4 plat, masalah ini sebenarnya sangat rumit

Penerbitan peraturan

1 plat digerakkan sekali

2 plat digerakkan 3 kali

3 plat digerakkan 7 kali

......

N plat digerakkan 2^N - 1 kali

Kemudian 64 plat diperlukan Pindahkan 2^64 - 1 kali

3. Selesaikan masalah

Kita boleh menyelesaikan masalah ini melalui rekursi dan mendapatkan cara pergerakan yang betul

Bagaimana jika terdapat N plat Bagaimana pula dengan mudah alih?

Idea keseluruhan

Kita boleh mula-mula mengalihkan N - 1 plat dari lajur A ke lajur B melalui lajur C, kemudian alihkan plat selebihnya dari lajur A ke lajur C, dan kemudian gerakkan N - 1 plat pada tiang B dialihkan ke tiang C dengan bantuan tiang A, sekali gus melengkapkan pergerakan semua tiang (proses pergerakan khusus di tengah tidak akan dibincangkan buat masa ini)

Kod di atas

public static void hanoi(int num, String src, String help, String dest) {
    if (num == 1) {     // 只有一个盘子的时候直接移动
        System.out.print(src + "->" + dest + "  ");  // 将一个盘子从源柱子挪到目标柱子
    } else {
        hanoi(num - 1, src, dest, help);   // 将n - 1个盘子从源柱子借助目标柱子挪到辅助柱子
        System.out.print(src + "->" + dest + "  ");  // 将一个盘子从源柱子挪到目标柱子
        hanoi(num - 1, help, src, dest);  // 将辅助柱子上n - 1个盘子借助源柱子挪到目标柱子
    }
}
public static void main(String[] args) {
    hanoi(3, "A", "B", "C");
}

Perenggan ini Dalam kod, src ialah tiang sumber, bantuan ialah tiang tambahan, dan dest ialah tiang sasaran

Ini ialah rekursi dua hala

Hasil larian :

Ini berjaya menyelesaikan pergerakan plat

4 Bolehkah Brahman menyelesaikan tugas Brahma?

Berapa lama take to move 64 plates

Di sini kita anggap orang Brahmin sangat bijak dan secara langsung boleh tahu cara yang betul untuk bergerak tanpa berfikir mengambil masa satu saat untuk menggerakkan pinggan dan terus bergerak

Menukar 2^64 - 1 saat kepada setahun ialah kira-kira 5849 4241 7355 tahun (584.942 bilion tahun Bumi hanya wujud selama 4.5 bilion tahun, dan jangka hayat sistem suria dikatakan berpuluh bilion). daripada tahun. Ia benar-benar telah 584.942 bilion tahun Belum lagi sistem suria dan Bima Sakti, sekurang-kurangnya semua kehidupan di bumi, termasuk Menara Vatican, kuil, dan lain-lain, telah lama dihapuskan.

Nubuatan yang berkaitan

Ada ramalan bahawa apabila perkara ini selesai, alam semesta akan musnah dalam sekelip mata. Sesetengah orang juga percaya bahawa Brahmin masih menggerakkan cakera sepanjang masa

Berapa lama masa yang diperlukan untuk komputer menggerakkan 64 plat?

Kekerapan teras komputer saya ialah 2.90GHz, iaitu 2.9 bilion operasi sesaat, jadi masa yang diperlukan untuk bergerak 2^64 - 1 kali ialah kira-kira 201 tahun

Atas ialah kandungan terperinci Bagaimana untuk menganalisis masalah Menara Hanoi menggunakan Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!