Analisis bagaimana PHP melaksanakan algoritma Menara Hanoi yang menarik

                                                                                                               

Saya belajar algoritma Menara Hanno selama sehari semalam. Saya rasa IQ saya tidak sehebat orang utan dalam "The Rise of the Gorilla Ball"! ! !

Origin

Dikatakan bahawa orang yang mula-mula mencipta masalah ini ialah ahli matematik Perancis "Edward Lucas".

Di kuil suci Benares (di utara India) di tengah dunia, terdapat tiga jarum permata yang dimasukkan pada pinggan tembaga. Apabila Brahma, tuhan utama agama Hindu, mencipta dunia, dia mengikat 64 keping emas dari besar ke kecil pada salah satu jarum dari bawah ke atas Ini adalah yang dipanggil Menara Hanoi. Tidak kira siang atau malam, sentiasa ada seorang sami yang menggerakkan kepingan emas ini mengikut peraturan berikut: hanya gerakkan satu keping pada satu masa, tidak kira jarum mana yang digunakan, kepingan kecil mesti berada di atas kepingan besar. Para bhikkhu meramalkan bahawa apabila semua kepingan emas dipindahkan dari jarum berulir oleh Brahma ke jarum lain, dunia akan dihapuskan dengan petir, dan Menara Vatican, kuil dan semua makhluk hidup juga akan binasa bersama.

Terdapat banyak variasi lagenda ini dan tidak diketahui siapa dia, tetapi masalah matematik yang ditinggalkan adalah sangat klasik.

Pengetahuan matematik yang ditinggalkan: hubungan antara bilangan keping emas dan bilangan langkah bergerak ialah

. 2^n - 1

Bilangan pergerakan 1 keping emas ialah 2 dinaikkan kepada kuasa 1 tolak 1
• Bilangan pergerakan 2 keping emas 2 dinaikkan kepada kuasa 2 dikurangkan oleh 1
• 3 Bilangan pergerakan sekeping emas ke kuasa ketiga ialah 2 tolak 1
• …
• Bilangan pergerakan sekeping emas ke kuasa ke-n daripada 2 adalah tolak 1

Jika lagenda itu Benar, para bhikkhu memerlukan

langkah untuk menyelesaikan tugas ini; dengan mengandaikan mereka memindahkan satu keping emas sesaat, ia akan mengambil masa 584.9 bilion tahun untuk diselesaikan. Seluruh alam ini hanya berusia 13.7 bilion tahun, jadi masih awal untuk kemusnahan alam semesta ... (Saya bosan, jadi saya benar-benar mengiranya, seperti yang ditunjukkan di bawah) 2^64 - 1

Peraturan asas

Algoritma Menara Hanoi mempunyai dua syarat asas, dengan mengandaikan bahawa plat dialihkan.

1. Hanya satu pinggan boleh dialihkan pada satu masa.

2. Pinggan kecil mesti berada di atas pinggan besar.

Analisis

Andaikan terdapat 3 tunjang dalam permainan ini iaitu A,B, dan C. Sudah ada N plat disusun pada salah satu daripadanya, yang terbesar adalah di bahagian bawah, dan plat semakin kecil dan semakin kecil naik, dan terdapat dua lajur kosong lain.

Keadaan awal adalah seperti yang ditunjukkan di bawah:

Matlamat akhir yang perlu dicapai ialah memindahkan semua plat pada tiang ke tiang lain. [Pembelajaran yang disyorkan:

Tutorial video PHP]

Idea am pelaksanaan:

Ketepikan diri anda memikirkan Bagaimana untuk mengambil setiap langkah adalah sangat rumit Saya rasa kapasiti otak saya tidak cukup saya mahu memikirkan logik penyelesaian yang paling mudah dan paling kasar.
• Untuk memenuhi syarat asas iaitu plat besar berada di bahagian bawah, anda mesti mengosongkan plat terbesar pada A dahulu, dan kemudian meletakkan plat terbesar pada tiang C. Katakan nombor plat terbesar ialah N.
• Disebabkan anda ingin beralih ke C, untuk mencapai langkah pertama, anda pasti perlu memindahkan semua
• plat ke tiang B. Hanya dengan cara ini plat N (iaitu plat terbesar) dipindahkan ke C Pada tiang itu. N-1
Alihkan
• plat ke tiang B. Kerana yang lebih besar mesti berada di bahagian bawah dan yang lebih kecil di atas, plat N-1 juga tertib pada tiang B. N-1
Akhir sekali gerakkan plat N-1 dari tiang B ke tiang C untuk melengkapkan gol terakhir.

Untuk meringkaskan:

Langkah pertama ialah mengalihkan plat N-1 pada A ke B.

Kenapa alihkan N-1 ke B dahulu? Anda lihat, kerana apa yang akhirnya anda capai ialah memindahkan semua plat pada A ke C, susunannya tidak boleh diubah, hanya boleh yang besar berada di bahagian bawah dan yang kecil berada di atas. Kemudian anda pasti perlu memindahkan yang terbesar ke C terlebih dahulu, jika tidak, syarat tidak akan dipenuhi.

Untuk mengalihkan plat terbesar dari A ke C, plat terbesar di A mesti dikosongkan, iaitu semua plat pada plat terbesar mesti dialihkan. Dan anda hanya mempunyai 3 tiang mesti tiada pemegang plat lain pada C, jika tidak, anda tidak akan memenuhi syarat Semua plat N-1 hanya boleh diletakkan di B, dan ia masih teratur. Ia menjadi gambar berikut:

Langkah kedua ialah mengalihkan plat N pada A (iaitu plat terbesar) ke C.

Ini sangat mudah. ​​Hanya alihkan plat terbesar dari A ke C dalam satu langkah. Seperti yang ditunjukkan di bawah:

Langkah ketiga ialah mengalihkan plat N-1 pada B ke C.

Nota: Untuk mengalihkan plat N-1 ke C, adakah ia bertukar menjadi mencari plat terbesar di antara mereka, dan kemudian mengalihkan plat terbesar terlebih dahulu. Jadi di sini ia sebenarnya menjadi masalah untuk mengulangi langkah 1 dan 2, mencari yang terbesar di antara N-1 ini dan mengalihkannya ke C terlebih dahulu, dan kitaran berulang.

Langkah ketiga sebenarnya bersamaan dengan menukar keperluan.
Terdapat plat K pada tiang B, tiang A kosong, dan tiang C mempunyai plat terbesar, jadi untuk tiang B dengan plat K, ia bersamaan dengan kosong.
Langkah pertama ialah mengalihkan plat K-1 pada B ke A.
Langkah kedua ialah mengalihkan plat Kth pada B ke C.
Langkah ketiga ialah mengalihkan plat K-1 pada A ke C.
…

menjadi gambar di bawah

Mula-mula cari yang terbesar antara plat yang tinggal

dan kemudian gerakkan plat terbesar

Kemudian gelung sehingga hanya tinggal satu pinggan, bergerak terus ke C, dan permainan tamat.

Tiang Bantu

Apakah itu tiang bantu? Andaikan bahawa semua plat yang anda ingin alihkan berada pada A, dan matlamatnya adalah untuk bergerak ke C, maka B ialah tiang tambahan bagi plat N-1. Kerana mereka hanya boleh wujud di sini buat sementara waktu, jika tidak, mereka tidak akan memenuhi peraturan permainan.

Di sini anda perlu mencari tiang tambahan terlebih dahulu. Jangan fikirkan cara untuk melaksanakannya, tetapi jelaskan logiknya terlebih dahulu.

• Untuk bergerak dari A ke B, C ialah tiang bantu
• Untuk bergerak dari A ke C, B ialah tiang tambahan
• Untuk bergerak dari B bergerak kepada C, maka A ialah tiang tambahan

pelaksanaan

Daripada analisis di atas, kita dapat melihat bahawa ini sebenarnya adalah operasi berulang, yang sangat berulang. Sama seperti rekursi, semuanya di sini boleh dilaksanakan menggunakan rekursi.

Untuk menggunakan rekursi, terdapat 2 syarat yang diperlukan

1 Cari formula rekursi
2. Cari keadaan keluar

Keadaan keluar Ia mudah untuk menulis. Ia mesti dipindahkan terus ke tiang C apabila hanya ada satu pinggan.

Jadi apakah formula rekursi? Berdasarkan analisis logik di atas, ia boleh diuraikan kepada 3 langkah.

Langkah pertama ialah mengalihkan plat [N-1] dari A ke B
Langkah kedua ialah mengalihkan plat [N-1] dari A ke C
Langkah ketiga ialah mengalihkan [baki N-1] plat dari B ke C

Berikut ialah kod pseudo yang dilaksanakan dalam PHP:

class HanoiTower
{
    // 计数器
    public $count = 0;
    /**
     * 汉诺塔实现
     * 
     * @param $n 盘子号
     * @param $A 初始柱子
     * @param $B 中转站
     * @param $C 目标柱子
     */
    public function hanoi($n, $A, $B, $C)
    {
        if ($n == 1) {
            // 退出条件 只剩一个盘子的时候直接从A移动到C
            $this->biggestOne($n, $A, $B, $C);
        } else {
            // Analisis bagaimana PHP melaksanakan algoritma Menara Hanoi yang menarik把 【n-1】 个盘子从A移动到B 此时C为中转站
            $this->hanoi($n - 1, $A, $C, $B);
            // Analisis bagaimana PHP melaksanakan algoritma Menara Hanoi yang menarik把 【第n】 个盘子从A移动到C
            $this->biggestOne($n, $A, $B, $C);
            // 第三步把B上 【剩余的n-1个】 盘子从B移动到C 此时A为中转站
            $this->hanoi($n - 1, $B, $A, $C);
        }
    }
    /**
     * 移动最大的盘子
     * 直接从A移动到C
     */
    public function biggestOne($n, $A, $B, $C)
    {
        ++$this->count;
        echo &#39;第&#39;, $this->count, &#39;步 &#39;, &#39;把 &#39;, $n, &#39;从 &#39;, $A, &#39;移动到&#39;, $C, &#39;<br />&#39;;
    }
}
$n = 5;
$hanoiTower = new HanoiTower();
echo &#39;这是一个有 【&#39;, $n, &#39;】 个盘子的汉诺塔：&#39;, &#39;<br />&#39;;
// 调用执行
$hanoiTower->hanoi($n, &#39;A&#39;, &#39;B&#39;, &#39;C&#39;);
echo &#39;总共需要走：【&#39;, $hanoiTower->count, &#39;】 步&#39;;

Keputusannya adalah seperti berikut:

>

Atas ialah kandungan terperinci Analisis bagaimana PHP melaksanakan algoritma Menara Hanoi yang menarik. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!