récursivité: Hanoi Résolu/Fermé

Question

Bonjour,
J'ai un algorithme qui marche pour résoudre le pb des tours de Hanoi mais le problème c'est que je ne le comprends pas. 

#include <stdio.h>
#define N 4

void Hanoi(int n, char depart, char arrivee, char libre) {
    if (n>0) {
        Hanoi(n-1,depart,libre,arrivee);
        printf("Bouger disque de %c à %c
", depart, arrivee);
        Hanoi(n-1,libre,arrivee,depart);
    }
}

int main() {
    printf("Tour avec %d disques:
", N);
    Hanoi(N,'A','C','B');
    return 0;
}


Merci de m'aider à éclaircir un peu ce code.

lami20j · Accepted Answer

Re,

En bref, ça donne le principe suivant :

Un disque arrive sur la tour d'arrivé en passant par la tour intermediaire

Premier passe
Depuis la tour départ on passe par la tour intermediaire pour arrivée à la tour d'arrivée

Deuxième passe
Ayant besoin de faire plusieurs mouvements la tour intermediaire est considerée la tour départ, la tour d'arrivée est considerée la tour intermediaire et la tour départ est considerée la tour d'arrivée.

et ainsi de suite.

KX · Answer

Qu'est-ce que tu ne comprends pas ?
Regarde Wikipédia

bibabobu · Answer

Merci pour les explications mais je ne comprends tjs pas qqchose. J'ai essayé de mettre des printf un peu partout pour voir exactement comment fonctionne le code. Ce qui donne:

#include <stdio.h>
#define N 4

void Hanoi(int n, char depart, char arrivee, char libre) {
    if (n>0) {
        printf("%c %c %c 
", depart, arrivee, libre);
        Hanoi(n-1,depart,libre,arrivee);
        printf("%c %c %c 
", depart, arrivee, libre);
        printf("Bouger disque de %c à %c
", depart, arrivee);
        printf("%c %c %c 
", depart, arrivee, libre);
        Hanoi(n-1,libre,arrivee,depart);
        printf("%c %c %c 
", depart, arrivee, libre);
    }
}

int main() {
    printf("Tour avec %d disques:
", N);
    Hanoi(N,'A','C','B');
    return 0;
}


j'ai ensuite compilé et exécuté et j'obtiens:

Tour avec 4 disques:
A C B
A B C
A C B
A B C
A B C
Bouger disque de A Ó B
A B C
A B C /* pourquoi ce résultat et non C B A ? Suite à quelle instruction on obtient ça? */
A C B
Bouger disque de A Ó C
A C B
B C A
B C A
Bouger disque de B Ó C
B C A
B C A
A C B
A B C
Bouger disque de A Ó B
A B C
C B A
C A B
C A B
Bouger disque de C Ó A
C A B
C A B
C B A
Bouger disque de C Ó B
C B A
A B C
A B C
Bouger disque de A Ó B
A B C
A B C
C B A
A B C
A C B
Bouger disque de A Ó C
A C B
B C A
B A C
B C A
B C A
Bouger disque de B Ó C
B C A
B C A
B A C
Bouger disque de B Ó A
B A C
C A B
C A B
Bouger disque de C Ó A
C A B
C A B
B A C
B C A
Bouger disque de B Ó C
B C A
A C B
A B C
A B C
Bouger disque de A Ó B
A B C
A B C
A C B
Bouger disque de A Ó C
A C B
B C A
B C A
Bouger disque de B Ó C
B C A
B C A
A C B
B C A
A C B

Les 5 1ères lignes je comprends (enfin je crois),
le 1er printf donne A C B (là, ça va)
ensuite, d'après ce que je comprends, on appelle la fonction Hanoi (n-1, depart, libre, arrivee); jusqu'à ce qu'on ait n-3 ce qui nous donne:
A B C
A C B
A B C
puis l'autre printf:
A B C
et ensuite: Bouger disque de A à B
le printf en-dessous donne A B C
mais ensuite je ne comprends pas pourquoi on obtient encore A B C alors que pour moi, si on appelle  Hanoi(n-1,libre,arrivee,depart); , on devrait avoir  C B A.


J'espère m'être fait comprendre.
Si ça se trouve c'est tout bête, mais je ne vois pas la logique...
Merci d'avance pour vos réponses.

KX · Answer

Je pense que ton problème vient de l'ordre dans lequel s'effectue les affichages.
En effet les imbrications de récursivité rende peu lisible le phénomène.
Essaye d'analyser le programme avec un affichage qui t'informe plus sur la position dans la récursivité, que sur l'effet sur la tour en lui même, par exemple comme ceci :int cpt=0;

void Hanoi(int n, char depart, char arrivee, char libre)
{
    if (n>0)
    {
         printf("---------------------------
");
         
         printf("%d : %d - 1
", ++cpt, n );
         Hanoi(n-1,depart,libre,arrivee);
         printf("%d : %d - 2
", ++cpt, n );

         printf("
%d : Bouger disque de %c a %c

", ++cpt, depart, arrivee);

         printf("%d : %d - 3
", ++cpt, n );
         Hanoi(n-1,libre,arrivee,depart);
         printf("%d : %d - 4
", ++cpt, n );
         
         printf("---------------------------
");
    }
    else if (n==0) printf("
%d : ------> n==0

",++cpt);
}Les affichages de catégorie 1 sont lancés

bibabobu · Answer

Ton programme est vraiment pas mal. Ca m'aide à y voir plus clair. Je crois en effet que c'est l'ordre dans lequel s'effectue le programme que je n'ai pas compris. 

Mais pourquoi il passe de l'étape 10 : 1 - 4  à l'étape 11 : 2 - 2 ?
Je ne vois vraiment pas pourquoi il "remonte" dans le programme, sans boucles, rien...

Désolé d'abuser de ta gentillesse, mais ça m'intrigue.

KX · Answer

C'est la magie de la récursivité ;-)

Au départ tu appelles Hanoi(4,...) à l'étape 1
Puisque 4>0, il appelle Hanoi(3,...) à l'étape 2
Ainsi de suite jusqu'à l'appel à Hanoi(0,...) à l'étape 5
Dans ce cas on termine la fonction Hanoi(0,...)
Donc on remonte à la fonction Hanoi(1,...) qui n'était pas terminée
Et on se retrouve à faire les étapes 6, 7, et 8
L'étape 9 appelle encore la fonction Hanoi(0,...) puis en sort
Et finalement à l'étape 10, on termine la fonction Hanoi(1,...)
Et on passe dès l'étape 11, à la fin de la fonction Hanoi(2,...)

bibabobu · Answer

puisque n=1, je ne vois pas pourquoi on peut remonter n à 2.
Et pourquoi dès l'étape 11 on passe à la fin de la fonction Hanoi(2,...).

lami20j · Answer

Re,

Un exemple tu avais ici https://forums.commentcamarche.net/forum/affich-11040015-algorithme-de-jeux-tour-de-hanoi#1
Le nombre de déplacements est aussi compté.

je ne vois vraiment pas pourquoi il "remonte" dans le programme, sans boucles, rien... 
Un peu plus tard je vais t'expliquer un peu ce qui se passe sous le capot ;-)

KX · Answer

Parce qu'à l'intérieur de la fonction n=2, tu appelles la fonction n=1, mais à ce moment là tu n'as pas finie la fonction n=2 pour autant.
Du coup lorsque la fonction n=1 est terminée, il reste des instructions à effectuer de la fonction n=2, et c'est pour ça que l'on y "remonte" pour terminer.

Plus précisément, à l'étape 11 ce n'est pas le début de la fonction n=2, mais la suite, la preuve : c'est un 2-2 qui s'affiche et non un 2-1 !

lami20j · Answer

Re,

La manière dont les fonctions sont exécutées en C est utile pour comprendre la récursivité.
Pour cela il faut comprendre comme est est organisé un programme C en mémoire.

A l'exécution un programme C est formé de 4 zones :
- la zone pour le code (les instructions qui s'exécutent au long de programme)
- la zone pour les données statiques (contient les données disponibles tout au long du programme - variables globales et locales statiques)
- un tas (contient les emplacement attribués dynamiquement - malloc)
- une pile ( les informations sur les appels des fonctions)

Le tas progresse du bas de la mémoire du programme vers haut, et la pile en sens inverse (ce n'est qu'une convention, en réalité cela peut varier)


Quand une fonction est appelé, sur la pile un bloc mémoire est alloué pour conserver les informations.

Exemple : la fonction factoriel

      | 1  si x =0 ou x=1
F(x)= |
      |  xF(x-1) si x>1

Voyons ce qui se passe pour 3!

F(3)=3*F(2)             - phase de descente
       F(2)=2*F(1)
              F(1)=1    - condition de fin 
       F(2)=(2)*(1)     - phase de remonté
F(3)=(3)*(2)
6                       - résultat

Le 1er appel de la fonction est placé sur la pile pour x=3
La condition terminale (x=0 ou x=1) n'est pas réalisée
En ce moment la fonction F est appelé à nouveau avec x=2
La condition n'est toujours pas réalisée.
Le fonction F sera appelé à nouveau avec x=1 qui est une condition terminale.
En ce moment l'expression qui correspond à x=2 est évalué comme 2 * 1 donc elle se termine avec la valeur 2
L'expression qui correspond à x=3 est évalué comme 3 * 2 * 1 = 6 et la récursivité est terminée.

Dans le cas des tours de Hanoï

Considérons les emplacements
D - départ
B - base
I - intermédiaire

Cas 1 - déplacement d'un disque

Pour déplacer un disque de D vers B l'emplacement intermédiaire est inutile

 ------------
_|____1_____|___   ______________  ____________


                     ------------
_________________   _|____1_____|_  ____________

         D                B              I


Cas 2 - déplacement de deux disques

Dans ce cas il faut transférer le disque du sommet sur l'emplacement Intermédiaire.
Ensuite le disque qui reste sur la position Départ il faut le mettre sur l'emplacement d'arrivée Base
Il reste a ramener le disque depuis l'emplacement Intermédiaire sur l'emplacement Base

  ----------
  |   2    |
 ------------
_|____1_____|_  ____________  ______________


 ------------                   -----------
_|____1_____|_  _____________ __|____2____|__

                 -----------    -----------
______________  _|____1____|_ __|____2____|__


                  ---------
                  |   2   |
                 -----------
______________ __|____1____|__ _____________

      D               B              I

Cas 3 - déplacement de trois disques

Dans ce cas il faut déplacer 2 disques du somment du D vers I en utilisant B comme emplacement intermédiaire.
Le disque depuis D vers B.
Les deux disques de I vers B en utilisant D comme intermédiaire.
Bref, pour déplacer les 3 disques on utilise deux fois la méthode qui permet de déplacer deux disques, ce qui explique la récursivité.



   --------
   |  3   |
  ----------
  |   2    |
 ------------
_|____1_____|_  _____________  ______________


                                  --------
                                  |  3   |
 ------------                    ----------
_|____1_____|_ ______________  __|___2____|___



                                    -------
                                    |  3  |
		 ------------      ----------
______________  _|____1_____|_   __|___2____|____


                   --------
                   |  3   |
                  ----------
                  |   2    |
                 ------------
______________  _|____1_____|__ ________________

          D           B                 I

bibabobu · Answer

Merci, j'ai enfin compris comment le programme fonctionne. (Mais avant de pouvoir refaire des programmes comme celui-là par moi-même, je pense qu'il va falloir un peu de temps.) 
J'ai juste une question à propos des fonctions qu'on reprend. Par exemple, quand on arrive à 1-4 (dans le programme de KX) ou plus galement à la fin d'1 fonction Hanoi et qu'on rappelle la fonction Hanoi(2,...) non finie, pourquoi ne rappelle-t-on pas la fonction Hanoi(3,...) non finie non plus, avant Hanoi(2,...)? Je pense qu'on doit prendre la dernière fonction en mémoire, mais je préfère être sûre. 

Merci d'avance pour les réponses.

KX · Answer

En fait, c'est parce que Hanoi(3,...) inclus Hanoi(2,...) qui inclus Hanoi(1,...)

On ne peux repasser à 2, qu'une fois le 1-4 atteint, de même on ne repassera au 3, qu'une fois le 2-4 atteint

Récursivité: Hanoi

12 réponses

Discussions similaires