J'apprends la récursion en C ++ mais j'ai été déconcerté par le code C ++ suivant utilisé pour résoudre le problème de Tower Of Hanoi.
m is equal to: 3 m is equal to: 2 m is equal to: 1 Move Disc from start to end Move disc 2 from start to middle m is equal to: 1 Move Disc from end to middle Move disc 3 from start to end m is equal to: 2 m is equal to: 1 Move Disc from middle to start Move disc 2 from middle to end m is equal to: 1 Move Disc from start to end
la sortie du code est la suivante: p>
void Hanoi(int m, string start, string middle, string end){
cout << "m is equal to: " << m << endl;
if(m == 1){
cout << "Move Disc " << " from " << start << " to " << end << endl;
}
else{
Hanoi(m-1,start,end,middle);
cout << "Move disc " << m << " from " << start << " to " << end << endl;
Hanoi(m-1,middle,start,end);
}
}
int main(){
int discs = 3;
Hanoi(discs, "start","middle","end");
}
Mon problème général est que je ne comprends pas comment fonctionne la récursivité. pourquoi dois-je aller à 1 avant d'exécuter l'instruction "if"? comment vais-je revenir à 2?
4 Réponses :
Si vous l'imprimez sous la forme d'un arbre, vous obtenez quelque chose comme ceci:
hanoi(3, ...)
hanoi(2, ...)
hanoi(1, ...)
hanoi(1, ...)
hanoi(2, ...)
hanoi(1, ...)
hanoi(1, ...)
Pour chaque appel à hanoi (m, ...) , il continuera d'appeler hanoi (m - 1, ...) deux fois à moins que m == 1. Lors du premier appel, il appellera à nouveau appelez hanoi (m - 1, ...) ... jusqu'à ce que m soit 1.
Donc en reculant quand m vaut 2 il appellera hanoi (1, ...) deux fois de suite:
hanoi(2, ...)
hanoi(1, ...)
hanoi(1, ...)
Quand m vaut 3 il appellera hanoi (2, ...) deux fois de suite, d'où:
main |--> hanoi(3, ...) | | | |--> hanoi(2, ...) | | | | | |--> hanoi(1, ...) | | |--> hanoi(1, ...) | |<----| | |--> hanoi(2, ...) | | | | | |--> hanoi(1, ...) | | |--> hanoi(1, ...) | |<----| |<-----| |
Cette trace devrait vous aider, si ce n'est pas le cas, vous pouvez toujours trouver plus de traces en recherchant sur Google "Trace du programme de récursivité de la tour de Hanoi"
Vous pouvez également découvrir comment l'algorithme fonctionne sur https: // javabypatel.blogspot.com/2015/12/tower-of-hanoi.html
Commençons par la première partie de la sortie:
m est égal à: 3
m est égal à: 2
m est égal à: 1
La fonction Hanoi est d'abord appelée comme ceci: Hanoi (3) .
Puisque m! = 1 dans ce cas, nous appellerons à nouveau Hanoi (m-1) . Cela produira la sortie ci-dessus. Nous sommes maintenant à 3 niveaux dans cette fonction.
Depuis m == 1 , nous allons maintenant voir cette sortie:
Déplacer le disque du début à la fin .
Maintenant, nous quittons la fonction la plus profonde et revenons au niveau 2 de notre pile d'appels de fonction. Maintenant, nous sortons:
Déplacez le disque 2 du début au milieu .
Votre objectif est de déplacer tous les disques vers un autre emplacement.
Pour résoudre l'énigme, vous devez déplacer la tour de la position 1 à la position 2.
Pour ce faire, vous devez déplacer le plus grand disque de la position 1 à la position 2.
Pour ce faire, la position 2 doit être vide et tous les autres disques doivent être en position 3 (en tant que tour de taille m-1).
Vous devez donc résoudre le casse-tête de taille m-1 (déplacer la tour de taille m-1 de la position 1 à 3). C'est le premier appel récursif.
Vous pouvez maintenant déplacer le plus grand disque de la position 1 à la position 2. C'est la sortie entre les appels de fonction récursifs.
Vous devez maintenant déplacer la tour de taille m-1 de la position 3 à la position 2.
Vous devez donc résoudre à nouveau le puzzle de la taille m-1 (déplacer la tour de taille m-1 de la position 3 à 2). Il s'agit du deuxième appel de fonction récursive.
Le seul problème de taille que vous pouvez résoudre sans cette récursivité est de déplacer la tour de taille 1 vers un autre endroit, car il ne peut pas y avoir de disque sur le dessus et vous pouvez vous déplacer sur n'importe quel autre disque. C'est la raison pour laquelle m doit être égal à 1 avant de pouvoir exécuter l'instruction if.