Tours de Hanoi - Page 1

Voila un sujet qui etait pose en meme temps que les 8 reines.
A ma surprise, j'ai pu trouver rapidement une solution incroyable tellement elle est enfantine.
Mais je n'en dis pas plus, je posterai la solution Vendredi, si personne n'a trouve d'ici la.

3 piquets, n rondelles de bois.
On bouge les rondelles une a une. On ne doit jamais poser une rondelle sur une rondelle plus petite.
Toutes les rondelles ont des tailles differents.
Le but est de deplacer toutes les rondelles du premier piquet,
ou elles sont entassees par ordre croissant
(la plus petite en haut), vers le dernier piquet
(disons le plus a droite, par exemple, mais cela n'a pas d'importance)
On prend toujours la rondelle posee en dessus d'un piquet.


Je demande d'ecrire une procedure qui simule les deplacements a effectuer.

Si je lance Hanoi(n : in Positive; piquet1, piquet2, piquet3 : in Character), ou n
n est le nombre de rondelles et les char sont les noms des piquets, la procedure doit m'afficher:

"je deplace la rondelle du piquet A vers le piquet B"
"je deplace la rondelle du piquet A vers le piquet C"
"je deplace la rondelle du piquet ...

Un bon dessin vaut mieux qu'un long discours :


Position de depart :

......|...........|.............|............
......|...........|.............|............
....**|**.........|.............|............
...***|***........|.............|............
.*****|*****......|.............|............
---------------------------------------------
......A...........B.............C............

Position d'arrivee :

......|...........|.............|............
......|...........|.............|............
......|...........|...........**|**..........
......|...........|..........***|***.........
......|...........|........*****|*****.......
---------------------------------------------
......A...........B.............C............

La solution du precedent est :

A --> C
A --> B
C --> B
A --> C
B --> A
B --> C
A --> C

si je ne m'abuse.

c'est 2^n-1 mouvements et c'est du recursif debile

Je demande d'ecrire une procedure qui simule les deplacements a effectuer.

Si je lance Hanoi(n : in Positive; piquet1, piquet2, piquet3 : in Character), ou n
n est le nombre de rondelles et les char sont les noms des piquets, la procedure doit m'afficher:

"je deplace la rondelle du piquet A vers le piquet B"
"je deplace la rondelle du piquet A vers le piquet C"
"je deplace la rondelle du piquet ...


hanoi(n,depart,arrivee)
{
si ( n == 0 ) ecrire("je depace la rondelle du piquet 'depart' vers le piquet 'arrivee'")
sinon
{
hanoi( n-1 , depart , 6-depart-arrivee )
ecrire("je depace la rondelle du piquet 'depart' vers le piquet 'arrivee'")
hanoi(n-1 , 6-depart-arrivee , arrivee)
}
}

et on appelle l'algo avec : hanoi(n,1,3)

y'a pas une solution à ce pb dans le manuel de la TI-92 ?

en plus l'algo est dans le boukin des ti il me semble !

Hanoi !!!!!!!
surement l'un des trucs les plus connus !!!!!!!
et effectivement ya un prog ds le manuel de ma 89 !
smeet t'es trop fort

héhé, mais si vous voulez, on peut peut etre trouver une optimisation du code, ce serait interessant ... koike connu ...

voici un exemple trouvé sur le ouaibe:


#define PR (void)printf(
#define PE (void)fprintf(stderr,

#define ALLO(x) { if((x = (int *)malloc((n+2) * sizeof(int))) == NULL) {
PE #x " allocation failed!n") exit(1); }}


main(int argc, char *argv[]){

int i, *a, *b, *c, *p, *o1, *o2, *e, n, n1;
n = atoi(argv[1]);
n1 = n+1;
ALLO(a)
ALLO(b)
ALLO(c)

a[0] = 1; b[0] = c[0] = n1;
a[n1] = n1; b[n1] = n+2; c[n1] = n+3;
for(i=1; i<n1; i++) {
a[i] = i; b[i] = c[i] = 0;
}

o1 = a;
if(n&1) { o2 = b; e = c; }
else { o2 = c; e = b; }

e[--(*e)] = o1[(*o1)++];
/* (call to) tower visualization code */
p = e; e = o1; o1 = o2; o2 = p;

while(*c>1) {
if(o1[*o1] > e[*e]) o1[--(*o1)] = e[(*e)++];
else e[--(*e)] = o1[(*o1)++];
/* (call to) tower visualization code */
p = e; e = o1; o1 = o2; o2 = p;
e[--(*e)] = o1[(*o1)++];
/* (call to) tower visualization code */
p = e; e = o1; o1 = o2; o2 = p;
}

for(i=1;i<n1;i++) PR"%d ", c[i]);
PR"n")
}
[edit]Edité par nEUrOne le 06-11-2001 à 21:17:47[/edit]

si quelqu'un trouve une solution non exponentielle, il devrait pouvoir avoir le Prix Nobel de mathématiques...
Deux solutions existent à ce problème. La solution récursive et une itérative un peu batarde...

c clair ... sachant que c en 2^n - 2 ..

Miles ... tu serais pas a SupElec par hasard ?

beuh...personne ne connait CamL???? hanoi est en exemple dessus, et en plus il est tout beau tout bien fait, trop facile a retranscrir, meme si c le bordel, avec toutes les données inutiles... genre les affichages des tours

Billy-Bob : tu dis ça au hasard ou tu as regardé sous mon post ?

CamL est de la merde pour des gens qui ne savent pas programmer. Objectiv CamL est mieux mais pas encore top, mais pratique pour tout ce qui est fonctionnel - le problème est que les vrais compilateurs n'existent pas vraiment, la théorie n'étant pas assez aboutie -.

la chui pas trop d'accord...ocaml est hyper bien(enfin il est bien quoi ) et c'est pas un truc pour les PD non plus.

Le problème est qu'il est encore interprété - comme VB - et donc il est lent. Ce qui est bien, c'est qu'il auto-optimise - passe par ex de n^3 à n^2*ln(n) -

N'empeche que tu fais ca en deux sec en CaML.
Justement je me posais la question il y a 1 mois (insomnies) et je l'ai refait en CaML en 15min. Très facile à programmer en CaML, beaucoup plus qu"en TI-Basic!

C'est normal, c'est fonctionnel, comme nous

Desole, je n'ai aucun manuel ti.
Bill bob : ta premiere reponse n'est pas bonne : les "piquets" sont juste des noms. Ils n'interviennt pas dans le calcul.

Enfin bref, je vais tout de meme donner ma solution _ simple ? oui, c'est dit dans l'enonce _ En ada, car c'est le langage que je connais le mieux :


procedure Hanoi(n : in Positive ; depart, aux, arrivee : in Character) is
begin
if n=1 then
Put("Je deplace la rondelle du piquet "&depart&" au piquet "&arrivee);
else
Hanoi(n-1,depart,arrivee,aux);
Put("Je deplace la rondelle du piquet "&depart&" au piquet "&arrivee);
Hanoi(n-1,aux,depart,arrivee);
end if;
end Hanoi;


En plus, c'est facile a lire.









[edit]Edité par smeet le 08-11-2001 à 14:26:29[/edit]

oué, mais ma solution est plus rapide ...

Comment ca elle est pas bonne ma soluce ? ... n'importe koi !

t1 ... chuis véxé !

pas bô smeet

Bill Bob : relis l'enonce. Si j'appelle Hanoi(n, 36, 150, ageDuCapitaine()), ca ne marche plus chez toi ...

neurone >> peut etre, mais trouvee sur le wouaibe... et elle ne repond pas non plus a l'enonce.

oué, mais ce n'etait pas pour ton truc que j'ai sorti ca c'est que qq jours auparavant, je m'etais rensigné sur ca et cete algo etait le plus effficace que j'avais trouvé ...

sinon, les algo classiques sont tous les mm, recursion

CAML EST COMPILE !!!!!!!!!!!!!!!!!


PAS INTERPRETE !!!!!!!!

et oui, wamlwin c tellement bien que ca compile en "simulant" des entrées/sorties, ca les rajouute la ou il faut, masi putain c'est du compilé !

Pourquoi alors des gars m'ont dit qu'il était interprété, parc que la théorie n'est pas assez abouti ?? Comprend pas. Tu as peut-être raison, mais je suis sceptique.

Smeet, c'est mieux comme ca :

Position de depart : 

......|...........|.............|............ 
......|...........|.............|............ 
....**|**.........|.............|............ 
...***|***........|.............|............ 
.*****|*****......|.............|............ 
--------------------------------------------- 
......A...........B.............C............ 

Position d'arrivee : 

......|...........|.............|............ 
......|...........|.............|............ 
......|...........|...........**|**.......... 
......|...........|..........***|***......... 
......|...........|........*****|*****....... 
--------------------------------------------- 
......A...........B.............C............ 

Sinon c'etait juste pour dire que HANOI, c'est trop simple une fois que tu as pige le truc

Eeehhhhhh les gaziers un detail - pour Miles surtout - y a pas de Nobel de Maths, povnaze

normal, les maths ne sont pas une science