|
|
|
|
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\n", depart, arrivee);
Hanoi(n-1,libre,arrivee,depart);
}
}
int main() {
printf("Tour avec %d disques:\n", N);
Hanoi(N,'A','C','B');
return 0;
}
Merci de m'aider à éclaircir un peu ce code.
Configuration: Windows XP Firefox 3.0.13
Qu'est-ce que tu ne comprends pas ?
|
Re,
|
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:
|
Je pense que ton problème vient de l'ordre dans lequel s'effectue les affichages.
int cpt=0;
void Hanoi(int n, char depart, char arrivee, char libre)
{
if (n>0)
{
printf("---------------------------\n");
printf("%d : %d - 1\n", ++cpt, n );
Hanoi(n-1,depart,libre,arrivee);
printf("%d : %d - 2\n", ++cpt, n );
printf("\n%d : Bouger disque de %c a %c\n\n", ++cpt, depart, arrivee);
printf("%d : %d - 3\n", ++cpt, n );
Hanoi(n-1,libre,arrivee,depart);
printf("%d : %d - 4\n", ++cpt, n );
printf("---------------------------\n");
}
else if (n==0) printf("\n%d : ------> n==0\n\n",++cpt);
}Les affichages de catégorie 1 sont lancés
La confiance n'exclut pas le contrôle |
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.
|
C'est la magie de la récursivité ;-)
|
Re,
|
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.
|
Re,
| 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
106485010510997108 |
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.)
|
Algorithme informatique de la tour de hanoi Exercice récursivité Exercices corriges simples de recursivité informatiques Procedure oracle récursivité Programmation c récursivité Recursivité fonction php Recursivité java pour arbre genealogique Récursivité avec les tableaux Récursivité en sql Récursivité vers itération Solution tour d hanoi Tour de hanoi langage c
