Voilà donc j'ai un projet info à faire sur le jeu "les tours de Hanoï" en C.
 
Ceux qui ont déjà fait un pg sur ce jeu serait sympa de m'éclairer sur le sujet. Merci
 
Ceux qui ne connaissent pas le jeu. Faites le moi savoir je vous expliquerais brièvement.
 
Merci d'avance

Tu veux quoi exactement ? Si c'est un truc tout fait tout cuit je pense pas que tu obtiennes quelque chose...

Non pas forcément.
 
Mais si on pouvait m'aider par ex sur les types de fonctions à utiliser etc...

à question vague, lassitude de répondre.
 
à question spécifique, réponse spécifique.

1 seule fonction récursive et basta.

Ah le bon vieux classique des tours de Hanoï.
 
Bon quelques pistes de travail:
 
A) L'approche à utiliser c'est "diviser pour résoudre" (ie: penser récursivité)
 
B) Décompose en 3 sous pbs:
tu dispose de 3 batons qu'on va appeler: G, M et D et de n disques initialement sur G et que tu veux mettre sur D.
pb1: deplacer (n-1) disques de G sur M
pb2: deplacer le disque restant de G sur D
pb3: deplacer les (n-1) disques de M sur D
 
C) les pb1 et pb3 sont recursifs !
 
D) La complexité de l'algo. est gigantesque: c'est du O(2^n). En clair, t'étonne pas qu'il y ait 10 minutes de calcul avec ton super bi-P4 2GHz pour n=30. Et ne pense même pas à essayer de résoudre le problème pour n>50.
Et non, il n'y a pas d'algo. plus performant pour résoudre le pb. des tours de Hanoï.

 
n'est ce pas ? surtout qu'a mon avis, un tour sur google et c bon........

effectiment, on peut trouver des sources toutes faites a pas mal d'endroits..

En gros il suffit de faire ça (n'oublie pas de remplacer les cout par les manipulations de stack décrites ...
 

Pompé sur le manuel de ma TI-92 :
 
deplace(n,a,b)
Prgm
 
If n = 1 then
  Pause string(a)&" -> "&string(b)
Else
  deplace(n-1,a,6-a-b)
  deplace(1,a,b)
  deplace(n-1,6-a-b,b)
EndIf
EnPrgm
 
 
Voilà, c'est tout!

Bizarre ton programme.  
Normalement la fonction Hanoï prend 4 paramètres: le nombre n de disques et les 3 piles.
Et je ne comprend pas très bien ta formule: 6-a-b
Ca correspond à quoi exactement ?

Les paramétres sont :
n = le nombres de disques à déplacer
a = le premier piquet
b = le dernier piquet
 
On déplace les n disques du piquet a au piquet b
Par exemple, seplace(3,1,3) va déplacer 3 anneaux du piquet 1 vers le piquet 3

Effectivement, ça fonctionne.  
Mais ça fait vraiment un peu magique cette formule (6-a-b).  
Par contre, ça implique que les piquets soient appelés 1, 2 et 3.

ouais, mais au moins, ca marche avec autant de piquets qu'on veut!

Bon pour le peu de prog que je fais, on va dire que j'ai l'habitude du java, et la je dois résoudre le problème des tours de hanoi en C. Je ne sais pas quoi utiliser pour représenter les tours : une structure ?? en effet je ne vois pas quoi prendre à part les objets :|  (mais y a pas d objet en c sniff )
 
Pour l'algo je pense qu'il y a un bon aiguillage ici, mais quel type utiliser pour représenter les tours ? les palets qui sont dessus ?
 
Merci pour tout )

C'est marrant j'ai fait le même exercice il y a 2 ans à l'INSA de Lyon (dép Télécom !).
 
Va fouiller http://www.dio.fr.st pour le code source (c pas mon site mais celui d'un pote)

 
à bas la récursivité ! Vive les algos itératifs qui déchirent leur môman !
 
 
 
(edit : ajustement de l'indentation du code)
 
C'est pas de moi ! C'est dispo là : http://remus.rutgers.edu/~rhoads/Code/code.html
 
Je précise que l'algo est complet (collez-le dans un fichier .c et il marche avec affichage et tout !)

 
IOCCC roulaize

 
Surtout que dans le cas des tours de Hanoi y'a pas de différence de complexité entre la version itérative et la version récursive...

 
par complexité, je supposes que tu entends temps de calcul nécessaire par itération ... Parce que l'algo en lui même est assez 'complexe' !

salut, j'ai le meme projet que toi à faire Rast@rthur,
j'avé pensé faire un tableau à 2 dimension pour ça, mais j'arrive pa à le coder...
donc question... comment on déclare un tableau à 2 dimensions??? (malloc, etc.???)
 
edit :
j'ai roué un truc sympa pour ça:
char **tab;
 
/* METHODE 1 */
/* Allocation de la 1er dimension */
tab = (char **) malloc ( sizeof (char *) * taille);  
 
/* Allocation des tableaux */
for (i=0; i<taille; i++) {
    tab[i] = (char *) malloc ( sizeof (char ) * taille2);
     
}  
 
mais bon allez savoir si c 'est possible de résoudre cet algo avec un tablo à 2 dim      

 
il te plait pas mon algo ?
 

je ne suis pas sur que ce soit la meilleure solution de passer par des tableaux de taille fixe ...
 
En fait, ca dépend des libertés de ton projet. Mais avec une petite recherche sur google, j'avais trouvé des algos qui permettaient de résoudre le pb des tours de Hanoi quel que soit le nb de piliers et de pièces (si plus de trois piliers, on précise le pilier dest ...)
 
Mais l'algo que j'ai donné plus haut possède des avantages par rapport aux autres algos :
1 - il est très rapide (travail sur les bits principalement et pas d'appel de fonction successifs comme pour les fonctions récursives)
2 - il n'alloue pas de mem inutile.
3 - ne s'embourbe jamais dans un chemin faux qu'il serait obligé de backtracker : l'algo converge directement vers la bonne solution ...
 
Juste un petit bug : suivant si le nb de pièces est pair ou impair, le pilier de destination sera le 2eme ou le 3eme ... Mais c'est un problème facile à contourner ...

 
Oui, bien sur, je parle du temps de calcul... Apres, il est vrai que la version itérative est un peu plus compliquée que celle récursive, mais bon... ca reste relativement simple comme algo.
 
edit : a condition de pas l'écrire comme tu nous l'a montré

 
C'est déjà un peu mieux !
 
Voila la version tip top !

 
Voilàààà ...
 
 
Edit : Je ne l'ai pas précisé, mais le n est le nombre de pièces sur la tour de départ ...