C++

Tour de Hanoï..

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Tour de Hanoï..

Rast@rthur

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

Publicité

antp

Super Administrateur
Champion des excuses bidons

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

---------------
mes programmes ·· les voitures dans les films ·· apprenez à écrire

Rast@rthur

Non pas forcément.

Mais si on pouvait m'aider par ex sur les types de fonctions à utiliser etc...

youdontcare

à question vague, lassitude de répondre.

à question spécifique, réponse spécifique.

gizmo

1 seule fonction récursive et basta.

kizkoool

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ï.

chrisbk

youdontcare a écrit a écrit :

à question vague, lassitude de répondre.

à question spécifique, réponse spécifique.

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

kjus

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

yaisseloulou

Elle m'éneeeeeeerve !

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

Code :

void Hanoi (unsigned n, char src, char dst, char tmp) {
if (n) {
Hanoi(n-1, src, tmp, dst);
cout << "Déplacer le disque " << n;
cout << " du piquet " << src;
cout << " au piquet " << dst << endl;
Hanoi(n-1, tmp, dst, src);
}
}

ITM

Avatar peint à la main

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!

---------------
iteme.free.fr | Mon feedback

Publicité

kizkoool

ITM a écrit a écrit :

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

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 ?

ITM

Avatar peint à la main

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

---------------
iteme.free.fr | Mon feedback

kizkoool

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.

ITM

Avatar peint à la main

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

---------------
iteme.free.fr | Mon feedback

fraga

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 )

---------------
Life is short, Take it easy :)

Lex

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)

theshockwave

I work at a firm named Koslow

Code :

main(
){int
z,y,n
;scanf("%d",&n);
for(y=1;(1<<n)-y
;y<<=z-1,printf(
"disk %i from %i to %i.\n"/**/
,z,(y&y-1)%3,((y|y-1)+1)%3),y
++)for(z=1;!(y&1);z++,y>>=1);}

à 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 !)

Message édité par theshockwave le 07-04-2003 à 19:12:19

kadreg

profil: Utilisateur

theShOcKwAvE a écrit :

IOCCC roulaize

---------------
brisez les rêves des gens, il en restera toujours quelque chose... -- laissez moi troller sur discu !

Ace17

theShOcKwAvE a écrit :

à bas la récursivité ! Vive les algos itératifs qui déchirent leur môman !

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...

theshockwave

I work at a firm named Koslow

Ace17 a écrit :

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' !

vandekerput

hooohhi'm'bohéé !!!!

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.???)
:hello:
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 :??: :??: :??:

Message édité par vandekerput le 09-04-2003 à 15:43:50

theshockwave

I work at a firm named Koslow

Vandekerput a écrit :

il te plait pas mon algo ? :heink:

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 ...

Ace17

theShOcKwAvE a écrit :

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' !

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é

Message édité par Ace17 le 09-04-2003 à 18:26:29