Analysez comment PHP implémente l'intéressant algorithme de la Tour de Hanoï

                                                                                                            天 Hier, j'ai étudié l'algorithme de Hanno Tower pendant une journée. J'ai senti que mon QI était écrasé. Ce n'était pas aussi bon que l'orang-outan dans Rise of the Gorilla Ball ! ! !

OrigineOn dit que la personne qui a inventé ce problème pour la première fois était le mathématicien français "Edward Lucas".

Dans le temple sacré de Bénarès (au nord de l'Inde) au centre du monde, se trouvent trois aiguilles de pierres précieuses insérées sur une plaque de laiton. Lorsque Brahma, le dieu principal de l'hindouisme, a créé le monde, il a enfilé 64 pièces d'or de grande à petite sur l'une des aiguilles, de bas en haut. C'est ce qu'on appelle la Tour de Hanoï. Peu importe le jour ou la nuit, il y a toujours un moine qui déplace ces pièces d'or selon les règles suivantes : ne déplacez qu'une pièce à la fois, quelle que soit l'aiguille sur laquelle elle se trouve, la petite pièce doit être au-dessus de la grande pièce. Les moines ont prédit que lorsque toutes les pièces d'or seraient déplacées de l'aiguille enfilée par Brahma vers une autre aiguille, le monde serait anéanti par la foudre et la tour du Vatican, les temples et tous les êtres vivants périraient également ensemble.

Il existe de nombreuses variantes de cette légende et on ne sait pas de qui il s'agit, mais les problèmes mathématiques laissés derrière sont très classiques.

Les connaissances mathématiques qu'il a laissées : la relation entre le nombre de pièces d'or et le nombre de pas en mouvement est

.

2^n - 1

Le nombre de mouvement de 1 pièce d'or est 2 à la puissance 1 moins 1

• Le nombre de mouvement de 2 pièces d'or est 2 à la puissance 2 moins 1
• Le nombre de mouvement de 3 pièces d'or est 2 à la troisième puissance moins 1
• …
• Le nombre de mouvements de 2 pièces d'or à la nième puissance moins 1
• Si la légende est vraie, les moines ont besoin de

étapes pour accomplir cette tâche ; morceau chaque seconde, il faudra 584,9 milliards d'années pour le terminer. L'univers entier n'a que 13,7 milliards d'années, il est donc encore tôt pour que l'univers soit détruit... (Je m'ennuyais, alors je l'ai calculé, comme indiqué ci-dessous)

2^64 - 1

Règles de base

L'algorithme de la Tour de Hanoï a deux conditions de base, en supposant que la plaque soit déplacée.

1. Une seule assiette peut être déplacée à la fois.

2. La petite assiette doit être au-dessus de la grande assiette.

AnalyseSupposons qu'il y ait 3 piliers dans ce jeu, à savoir A, B et C. Il y a déjà N plaques triées sur l'une d'elles, la plus grande est en bas, les plaques sont de plus en plus petites en montant, et il y a deux autres colonnes vides.

L'état initial est le suivant :

Le but ultime à atteindre est de déplacer toutes les plaques d'un pilier vers un autre pilier. [Apprentissage recommandé :

Tutoriel vidéo PHP

]

Idée générale de mise en œuvre :

Mettez de côté les pensées dans votre esprit sur la façon de franchir chaque étape. Ce n'est pas très compliqué. avoir suffisamment de capacité cérébrale. Pensez d'abord à la logique de solution la plus simple et la plus grossière.

• Pour remplir la condition de base selon laquelle la grande assiette est en bas, vous devez d'abord vider la plus grande assiette sur A, puis poser la plus grande assiette sur le pilier C. Supposons que le plus grand numéro de plaque soit N.
• Parce que pour passer au C, pour réaliser la première étape, vous devez absolument déplacer
toutes les assiettes vers le pilier B. Ce n'est qu'ainsi que la Nième assiette (c'est-à-dire la plus grande assiette) peut être déplacée vers le pilier C.
• N-1Déplacez les
assiettes sur le pilier B. Parce que les conditions doivent être remplies, les plus grandes sont en bas et les plus petites sont en haut, donc ces
• assiettes sont également en ordre sur le pilier B. N-1N-1Déplacez enfin ces plaques N-1 du pilier B vers le pilier C pour compléter l'objectif final.
• Pour résumer :

La première étape consiste à déplacer les plaques N-1 de A vers B.

Pourquoi devons-nous d'abord déplacer N-1 vers B ? Vous voyez, parce que ce que vous réalisez finalement est de déplacer toutes les plaques de A vers C, l'ordre ne peut pas être modifié, il se peut seulement que les grandes soient en bas et les petites en haut. Ensuite, vous devez d'abord déplacer le plus grand vers C, sinon les conditions ne seront pas remplies.

Pour déplacer la plus grande assiette de A à C, la plus grande assiette de A doit être libérée, c'est-à-dire que toutes les assiettes de la plus grande assiette doivent être déplacées. Et vous n'avez que 3 piliers. Il ne doit y avoir aucune autre poignée de plaque sur C, sinon vous ne remplirez plus les conditions. Toutes ces plaques N-1 ne peuvent être placées que sur B, et elles sont toujours en ordre. Cela devient l'image ci-dessous :

La deuxième étape consiste à déplacer la Nième plaque de A (c'est-à-dire la plus grande plaque) vers C.

C'est très simple. Déplacez simplement la plus grande assiette de A à C en une seule étape. Comme indiqué ci-dessous :

La troisième étape consiste à déplacer les plaques N-1 de B vers C.

Remarque : Pour déplacer N-1 plaques vers C, cela revient-il à trouver la plus grande plaque parmi elles, puis à déplacer la plus grande plaque en premier ? Il s'agit donc ici de répéter les étapes 1 et 2, de trouver la plus grande parmi ces N-1 et de la déplacer en premier vers C, et le cycle se répète.

La troisième étape équivaut en fait à modifier les exigences. Supposons que K = N - 1.
Il y a K assiettes sur le pilier B, le pilier A est vide, et le pilier C a la plus grande assiette, donc pour le pilier B avec K assiettes, cela équivaut à être vide.
La première étape consiste à déplacer les plaques K-1 de B vers A.
La deuxième étape consiste à déplacer la Kième plaque de B vers C.
La troisième étape consiste à déplacer les plaques K-1 de A vers C.
...

devient l'image ci-dessous

Trouvez d'abord la plus grande parmi les assiettes restantes

puis déplacez la plus grande assiette

Ensuite, faites une boucle jusqu'à ce qu'il ne reste qu'une seule assiette, passez directement à C, le jeu est terminé.

Piliers auxiliaires

Que sont les piliers auxiliaires ? Supposons que toutes les assiettes que vous souhaitez déplacer se trouvent sur A et que le but est de se déplacer vers C, alors B est le pilier auxiliaire de N-1 assiettes. Parce qu’ils ne peuvent exister ici que temporairement, sinon ils ne respecteront pas les règles du jeu.

Ici, vous devez d'abord découvrir les piliers auxiliaires, ne réfléchissez pas à la manière de les mettre en œuvre, mais clarifiez d'abord la logique.

• Pour passer de A à B, alors C est le pilier auxiliaire
• Pour passer de A à C, alors B est le pilier auxiliaire
• Pour passer de B à C, alors A est le pilier auxiliaire

Implémentation

Grâce à l'analyse ci-dessus, nous pouvons voir qu'il s'agit en fait d'une opération répétitive dans un cycle, très similaire à la récursivité, donc la récursivité peut être utilisée pour l'implémenter.

Pour utiliser la récursion, il y a deux conditions nécessaires

1. Trouver la formule de récursion
2 Trouver la condition de sortie

La condition de sortie est facile à écrire. Elle doit être déplacée directement vers le pilier C lorsqu'il n'y en a que. une assiette.

Alors c'est quoi la formule de récidive ? Sur la base de l’analyse logique ci-dessus, elle peut être décomposée en 3 étapes.

La première étape consiste à déplacer les [N-1] plaques de A à B
La deuxième étape consiste à déplacer la [Nième] plaque de A à C
La troisième étape consiste à déplacer la [Nième] plaque restant] -1 pièce] La plaque est déplacée de B vers C

Voici le pseudo-code implémenté en 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 {
            // Analysez comment PHP implémente lintéressant algorithme de la Tour de Hanoï把 【n-1】 个盘子从A移动到B 此时C为中转站
            $this->hanoi($n - 1, $A, $C, $B);
            // Analysez comment PHP implémente lintéressant algorithme de la Tour de Hanoï把 【第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;;

Les résultats sont les suivants:

                                                       

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!