Code des tours de hanoi

**crazyvirus** · 24/01/2009, 18h30

Bonjour ,
SVP y a il quelqu'un pour m'expliquer étape par étape ce code de hanoi, je le trouve vraiment pas mal compliqué.. Si non y a il une autre méthode pour résoudre les tours de hanoi sans avoir recours aux tableau multidimensionnel et aux classes .
MERCI D'AVANCE , Merci du fond de mon coeur!!!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
using namespace std;
 
const unsigned int N = 4; // la taille de la tour de depart
 
// un disque sera represente simplement par sa taille (rayon)
typedef unsigned int Disque;
// 0 signifiant pas de disque
const Disque PAS_DE_DISQUE(0);
 
typedef Disque Pilier[N]; // un pilier est une pile d'au plus N disques
typedef Pilier Jeu[3]; // le jeu est constitue de 3 piliers
 
// les fonctions
void affiche(char c, unsigned int n = 1);
void affiche(Disque d);
void affiche(Jeu jeu);;
void init(Jeu& jeu); /* Note: le passage par reference est ici
                      * facultatif vu que Jeu est un tableau.  Mais je
                      * prefere marquer clairement par ce passage par
                      * reference que l'argument jeu est modifie par
                      * cette fonction */
 
unsigned int sommet(Pilier p);
void deplace(Pilier& origine, Pilier& destination); // meme remarque
unsigned int autre(unsigned int p1, unsigned int p2);
void hanoi(unsigned int n, unsigned int origine,
           unsigned int destination, Jeu jeu);
 
// --------------------------------------------------------------------
int main()
{
  Jeu monjeu;
 
  init(monjeu);
  affiche(monjeu);
  hanoi(N, 0, 2, monjeu);
 
  return 0;
}
 
// --------------------------------------------------------------------
void init(Jeu& jeu)
{
  for (unsigned int i(0); i < N; ++i) {
    jeu[0][i] = i+1;
    jeu[1][i] = PAS_DE_DISQUE;
    jeu[2][i] = PAS_DE_DISQUE;
  }
}
 
// --------------------------------------------------------------------
void affiche(char c, unsigned int n)
{
  for (unsigned int i(0); i < n; ++i) cout << c;
}
 
// --------------------------------------------------------------------
void affiche(Disque d)
{
  if (d == PAS_DE_DISQUE) {
    affiche(' ', N-1);
    cout << '|';
    affiche(' ', N);
  }
  else {
    affiche(' ', N-d);
    affiche('-', 2*d-1);
    affiche(' ', N-d+1);
  }
}
 
// --------------------------------------------------------------------
void affiche(Jeu jeu)
{
  for (unsigned int i(0); i < N; ++i) {
    affiche(jeu[0][i]);
    affiche(jeu[1][i]);
    affiche(jeu[2][i]);
    cout << endl;
  }
  // le socle
  affiche('#', 6*N-1); // 3*(2*N-1)+2 = 6*N-1
  cout << endl << endl;
}
 
// --------------------------------------------------------------------
unsigned int sommet(Pilier p)
{
  unsigned int top;
  for (top = 0; (top < N) && (p[top] == PAS_DE_DISQUE); ++top);
  return top;
}
 
// --------------------------------------------------------------------
void deplace(Pilier& origine, Pilier& destination)
{
  unsigned int top1(sommet(origine));
  if (top1 < N) { // si la tour d'origine existe bien
 
    unsigned int top2(sommet(destination));
    if ((top2 < N) && (destination[top2] < origine[top1])) {
      /* on essaye de mettre un disque plus gros (origine[top1])
       * sur un disque plus petit (destination[top2]) : ce n'est pas
       * un deplacement autorise !
       */
      cerr << "ERREUR : on ne peut pas deplacer une disque de taille "
           << origine[top1] << " sur un disque de taille "
           << destination[top2] << " !" << endl;
      return;
    }
 
    // effectue le mouvement
    destination[top2-1] = origine[top1];
    origine[top1] = PAS_DE_DISQUE;
  }
}
 
// --------------------------------------------------------------------
unsigned int autre(unsigned int p1, unsigned int p2)
{
  return 3 - p1 -p2;
}
 
// --------------------------------------------------------------------
void hanoi(unsigned int n, unsigned int origine,
           unsigned int destination, Jeu jeu)
{
  if (n != 0) {
    unsigned int auxiliaire(autre(origine, destination));
    hanoi(n-1, origine, auxiliaire, jeu);
    deplace(jeu[origine], jeu[destination]);
    affiche(jeu);
    hanoi(n-1, auxiliaire, destination, jeu);
  }
}

**Senji** · 24/01/2009, 18h46

salut,

il serait mieux de comprendre l'algorithme des tours de hanoi que de comprendre ce code. car Il existe un algorithme récursif très classique pour résoudre ce problème. Imprégnez vous du principe du jeu, vérifiez que vous comprenez l'algorithme récursif, et réfléchissez à une modélisation, ainsi vous pourrez le coder tout seul et dans n'importe quel langage

bye

**jfouche** · 24/01/2009, 18h52

Bonjour

Que trouves tu compliqué dans ce code (pour savoir quoi t'expliquer dans le code proposé) ?

A la question :
Si non y a il une autre méthode pour résoudre les tours de hanoi sans avoir recours aux tableau multidimensionnel et aux classes, la réponses est oui, bien entendu... (Tout est possible, tout est réalisable, c'est le jeu de ... l'informatique).

Pour commenser, tu peux essayer de mettres des classes conformement a ce que l'auteur utilise déjà (Disque, Pilier, Jeu), avec leurs méthodes.
Si tu veux être (plus) c++, tu peux utiliser std::vector à la place des tableaux.
Fais un essais, et je pourrais t'aider
--
Jérémie

**Obsidian** · 25/01/2009, 02h13

Envoyé par crazyvirus

Bonjour ,
SVP y a il quelqu'un pour m'expliquer étape par étape ce code de hanoi, je le trouve vraiment pas mal compliqué..

Hello,

Toute l'âme du jeu réside dans l'unique fonction « hanoï », soit dans les dix dernières lignes de ton code. Le reste n'est là que pour gérer l'affichage du jeu à l'écran.

Il y a deux manières de résoudre le jeu, une méthode récursive et une méthode non récursive. Si tu abordes ce jeu dans le cadre d'un cours, il y a fort à parier que c'est pour mettre en évidence l'approche récursive.

Si non y a il une autre méthode pour résoudre les tours de hanoi sans avoir recours aux tableau multidimensionnel et aux classes .

Je n'ai pas vu de tableau multi-dimensionnel dans ton code. Tu n'es pas obligé d'utiliser non plus la programmation orientée objet. Ce jeu a été implémenté très souvent en C, et certains ici-même essaient même de le coder en assembleur MIPS. C'est un problème purement algorithmique.

**crazyvirus** · 25/01/2009, 03h00

Merci a tous ! Je vais essayer de coder un et vous donner de mes nouvelles

Envoyé par Obsidian

Je n'ai pas vu de tableau multi-dimensionnel dans ton code. Tu n'es pas obligé d'utiliser non plus la programmation orientée objet. Ce jeu a été implémenté très souvent en C, et certains ici-même essaient même de le coder en assembleur MIPS. C'est un problème purement algorithmique.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
 jeu[0][i] = i+1;
    jeu[1][i] = PAS_DE_DISQUE;
    jeu[2][i] = PAS_DE_DISQUE;

**Obsidian** · 25/01/2009, 15h43

Envoyé par crazyvirus

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
 jeu[0][i] = i+1;
    jeu[1][i] = PAS_DE_DISQUE;
    jeu[2][i] = PAS_DE_DISQUE;

Effectivement, j'ai lu ton code un peu trop vite ...

**crazyvirus** · 02/02/2009, 01h51

Enfin , voila mon code

!!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
using namespace std;
void hanoi (int,char,char,char);
int main()
{
    int n;
    cout<<"Entrer le nombre de disques : "<<endl;
    cin>>n;
    hanoi(n,'A','B','C');
    cout<<endl;
    system("pause");
    return 0;
}
 
void  hanoi( int ndisque,char source,char intermediaire,char destination)
{
      if ( ndisque == 1)
      cout<<"Deplacer le disque de la tour"<<" "<<source<<" "<<"a la tour"<<" "<<destination<<endl;
      else
      {
          hanoi ( ndisque - 1 , source , destination , intermediaire);
          hanoi( 1 , source , intermediaire , destination );
          hanoi ( ndisque - 1 ,intermediaire , source , destination );
      }
}

**Obsidian** · 02/02/2009, 02h29

Tout de suite, c'est nettement plus simple, tu ne trouves pas ? :-)

À bientôt.

**crazyvirus** · 02/02/2009, 04h31

Oui biensur

!! mais aprés un bon temps passé XD!!

**ram-0000** · 02/02/2009, 08h28

Juste une remarque concernant la fonction hanoi()

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

void  hanoi( int ndisque,char source,char intermediaire,char destination)

Comme cela se joue toujours avec 3 tours, le paramètre "intermédiaire" n'est pas nécessaire car il peut se déduire de "source" et "destination". Cela fait un risque d'incohérence en moins et aussi un paramètre de moins à passer.

Mon avis à 0,01€

**droggo** · 02/02/2009, 14h26

Beo,

Envoyé par ram-0000

Juste une remarque concernant la fonction hanoi()

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

void  hanoi( int ndisque,char source,char intermediaire,char destination)

Comme cela se joue toujours avec 3 tours, le paramètre "intermédiaire" n'est pas nécessaire car il peut se déduire de "source" et "destination". Cela fait un risque d'incohérence en moins et aussi un paramètre de moins à passer.

Mon avis à 0,01€

Mais il rend le code plus compréhensible pour un lecteur.