MPO n°68 : les tours de Hanoï
Modérateur : Politburo
- Marge
- Fonctionne à 14400 bauds
- Messages : 6174
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: MPO n°68 : les tours de Hanoï
Bonsoir,
Je viens de regarder d'assez près le programme de C.Ret... c'est une merveille
Il est complet (respecte le mode Joueur et le mode Démo), et même davantage si l'on ajoute la proposition de gege et, ce qui ne gâte rien, comme toujours C.Ret nous régale d'une mine d'explications fournies avec ce magnifique bestiau de 428 octets. Bravo !
Un seul regret, je n'ai pas trouvé le PC-1211 chez PockEmul, je crois que Rémi y travaille encore. Cela dit, il ne semble pas trop compliqué à adapter à une autre machine, je tenterai ça un de ces jours. Merci pour ce bon moment, et j'espère que tu pourras résoudre tes petits problèmes de résolution.
Je viens également de lire les explications de billaj et son programme, j'ai bien suivi les premières, mais je ne suis pas du tout dans le monde Casio et j'ai du mal à comprendre leur application à la Casio graphique (qui, soit dit en passant, devrait permettre de belles choses pour un MPO plus esthétique). Bravo à billaj, on attend le prochain épisode avec impatience !
Quant à moi, j'y retourne. En piètre mathématicien, je n'en suis qu'à la version (petit) Joueur pour HP-34C... mais je m'amuse bien ! à bientôt.
Je viens de regarder d'assez près le programme de C.Ret... c'est une merveille
Il est complet (respecte le mode Joueur et le mode Démo), et même davantage si l'on ajoute la proposition de gege et, ce qui ne gâte rien, comme toujours C.Ret nous régale d'une mine d'explications fournies avec ce magnifique bestiau de 428 octets. Bravo !
Un seul regret, je n'ai pas trouvé le PC-1211 chez PockEmul, je crois que Rémi y travaille encore. Cela dit, il ne semble pas trop compliqué à adapter à une autre machine, je tenterai ça un de ces jours. Merci pour ce bon moment, et j'espère que tu pourras résoudre tes petits problèmes de résolution.
Je viens également de lire les explications de billaj et son programme, j'ai bien suivi les premières, mais je ne suis pas du tout dans le monde Casio et j'ai du mal à comprendre leur application à la Casio graphique (qui, soit dit en passant, devrait permettre de belles choses pour un MPO plus esthétique). Bravo à billaj, on attend le prochain épisode avec impatience !
Quant à moi, j'y retourne. En piètre mathématicien, je n'en suis qu'à la version (petit) Joueur pour HP-34C... mais je m'amuse bien ! à bientôt.
3 hommes, 3 demis, un 3a... Magnéto, Serge !
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
-
- Fonctionne à 1200 bauds
- Messages : 383
- Enregistré le : 09 avr. 2005 17:48
- Localisation : Brest
- Contact :
Re: MPO n°68 : les tours de Hanoï
E, F et G contiennent les indices de 3 colonnes différentes : 0, 1 ou 2. Si seulement ça pouvait nous être utile pour déduire un des indices de la valeur des 2 autres...
Pour 0, 1, 2, peut-être pas, mais si les valeurs sont -1, 0 et 1, j'ai trouvé une astuce :
B = -(C+D)
Pour C et D valant 1 et -1, -(C+D)=0
Pour C et D valant 0 et 1, -(C+D)=-1 (idem pour l'opposé)
Et ça tombe bien, puisqu'avec ces Casio on peut utliser des index négatifs !
Prog 0 devient donc :
et Prog 1 :
Le programme de C. Ret m'a l'air superbe, je ne l'ai pas encre regardé de près...mais il y a sans doute déjà des idées à piocher pour la conversion en itératif, pour l'instant je n'ai pas trouvé tout seul comment on fait !
Déjà, l'utilisation du logarithme décimal est une excellente idée pour avoir la hauteur de chaque pile , ça me sera utile pour faire une version graphique !
Pour 0, 1, 2, peut-être pas, mais si les valeurs sont -1, 0 et 1, j'ai trouvé une astuce :
B = -(C+D)
Pour C et D valant 1 et -1, -(C+D)=0
Pour C et D valant 0 et 1, -(C+D)=-1 (idem pour l'opposé)
Et ça tombe bien, puisqu'avec ces Casio on peut utliser des index négatifs !
Prog 0 devient donc :
Code : Tout sélectionner
Prog 0 (35 pas) :
9->A:
-1->B:
1->C:
0->D:
1.23456789->E:
0->F:
0->G:
Code : Tout sélectionner
Prog 1 (148 pas) :
A=0=>Goto 9:
A-1->A:
D->C:
-B-C->D:
Prog1:
F[D]/10+D+2◢ destination, mais on a inversé C et D pour le sous-appel
F[D]/10+Int(F[B])->F[D]:
F[D]/10+D+2◢
F[B]/10+B+2◢
10Frac(F[B])->F[B]:
F[B]/10+B+2◢
C->B:
D->C:
-B-C->D:
Prog1:
D->B:
-B-C->D:
A+1->A:
Lbl 9:
Déjà, l'utilisation du logarithme décimal est une excellente idée pour avoir la hauteur de chaque pile , ça me sera utile pour faire une version graphique !
Quand Chuck Norris joue à Nintendogs, il a automatiquement armes et munitions infinies.
Chuck Norris peut revenir en arrière dans Super Mario Land.
Chuck Norris utilise exclusiment des calculatrices Texas Instruments.
Chuck Norris peut revenir en arrière dans Super Mario Land.
Chuck Norris utilise exclusiment des calculatrices Texas Instruments.
- Marge
- Fonctionne à 14400 bauds
- Messages : 6174
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: MPO n°68 : les tours de Hanoï
Bonjour,
Non, je ne laisserai pas tomber ce MPO !
J'avance, mais je dois reconnaître que c'est un poil compliqué.
J'ai naturellement bougé du bois, déplacé les neuf disques devant mon fils estomaqué par le beuglement que j'ai poussé à la fin, assez bestial, je dois dire, c'était le cerveau primaire qui parlait. Ce n'est pas simple pour un cerveau humain de résoudre cela sans y perdre son latin.
J'avoue qu'après beaucoup de tentatives désespérantes, je suis allé chez Wikipedia pour voir ce qu'on disait de la résolution de ce problème. On y présente trois algorithmes (si ma mémoire est bonne), mais j'en ai trouvé un qui doit fonctionner (peut-être) mieux. Voici :
Le principe tiré de Wikipedia est itératif, on déplace les disques de gauche à droite si le nombre de disques initial est pair, et de droite à gauche s'il est impair. Ce principe initial est :
Je vous fais grâce du laïus et des essais réalisés sur HP-34C où je tente de profiter du registre I pour n'afficher que les disques (et non les zéros). J'espère trouver quelque chose d'intéressant après la parution de la Gazette 7, car je compte me consacrer à présent à la rédaction des articles promis (surtout en ce qui concerne le jeu de cartes, il faut que j'avance).
À bientôt, donc !
Non, je ne laisserai pas tomber ce MPO !
J'avance, mais je dois reconnaître que c'est un poil compliqué.
J'ai naturellement bougé du bois, déplacé les neuf disques devant mon fils estomaqué par le beuglement que j'ai poussé à la fin, assez bestial, je dois dire, c'était le cerveau primaire qui parlait. Ce n'est pas simple pour un cerveau humain de résoudre cela sans y perdre son latin.
J'avoue qu'après beaucoup de tentatives désespérantes, je suis allé chez Wikipedia pour voir ce qu'on disait de la résolution de ce problème. On y présente trois algorithmes (si ma mémoire est bonne), mais j'en ai trouvé un qui doit fonctionner (peut-être) mieux. Voici :
Le principe tiré de Wikipedia est itératif, on déplace les disques de gauche à droite si le nombre de disques initial est pair, et de droite à gauche s'il est impair. Ce principe initial est :
Je pense à transformer ce principe en :1. déplacer le plus petit disque d'un emplacement à l'emplacement suivant (de A vers B, de B vers C, de C vers A, par exemple) ;
2. déplacer un autre disque.
Le déplacement se fait de droite à gauche puisque le nombre initial de disques est 9.1. Déplacer le 1 d'une tour ;
2. Déplacer le plus petit disque suivant :
- s'il est impair, d'une tour ;
- s'il est pair, de deux tours ;
3. Recommencer en 1.
Je vous fais grâce du laïus et des essais réalisés sur HP-34C où je tente de profiter du registre I pour n'afficher que les disques (et non les zéros). J'espère trouver quelque chose d'intéressant après la parution de la Gazette 7, car je compte me consacrer à présent à la rédaction des articles promis (surtout en ce qui concerne le jeu de cartes, il faut que j'avance).
À bientôt, donc !
3 hommes, 3 demis, un 3a... Magnéto, Serge !
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
- Administrateur
- Messages : 5944
- Enregistré le : 24 mai 2002 16:55
- Localisation : Toulouse
- Contact :
Re: MPO n°68 : les tours de Hanoï
Salut,
Il y a un article sur ce sujet dans "Pour La Science" de décembre, ils y donnent les algos ...
A+
Il y a un article sur ce sujet dans "Pour La Science" de décembre, ils y donnent les algos ...
A+
- bernouilli92
- Fonctionne à 14400 bauds
- Messages : 5235
- Enregistré le : 21 nov. 2012 13:03
- Localisation : Ile de France
Re: MPO n°68 : les tours de Hanoï
De quelle année? Pas trouvé dans celui de décembre 2015.
HP, Casio, Sharp, Psion, quelques TI et divers autres
- Administrateur
- Messages : 5944
- Enregistré le : 24 mai 2002 16:55
- Localisation : Toulouse
- Contact :
Re: MPO n°68 : les tours de Hanoï
Salut,
Oops, erreur de ma part : Numéro spécial 457 de Novembre sur un certain Albert Einstein, page 108.
A+
Oops, erreur de ma part : Numéro spécial 457 de Novembre sur un certain Albert Einstein, page 108.
A+
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3405
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: MPO n°68 : les tours de Hanoï
Je suis moi aussi toujours sur le coup. J'essaye d'améliorer l'algorithme de résolution.
Les info et documentations trouvés pour l'instant ne traitent en général que du cas particulier où tous les disques sont dans l'ordre et sur une seule pile de départ.
Rare sont les auteurs d'articles qui envisagent le cas initial quelconque. Et encore moins le cas où les disques seraient mal mis (pas dans l'ordre) au départ.
Dans le meilleurs des cas ces deux derniers cas sont évoqués, mais très rarement, voir jamais, traités dans le détails. Les seuls algorithmes que j'ai trouvé ne sont pour la majorités valables que dans le cas particulier des disques bien ordonnés sur une seule pile initiale.
Je vais tacher de trouver l'article indiqué par Pocket afin de voir si le schmilblick peut avancer (dans le cas général)
Les info et documentations trouvés pour l'instant ne traitent en général que du cas particulier où tous les disques sont dans l'ordre et sur une seule pile de départ.
Rare sont les auteurs d'articles qui envisagent le cas initial quelconque. Et encore moins le cas où les disques seraient mal mis (pas dans l'ordre) au départ.
Dans le meilleurs des cas ces deux derniers cas sont évoqués, mais très rarement, voir jamais, traités dans le détails. Les seuls algorithmes que j'ai trouvé ne sont pour la majorités valables que dans le cas particulier des disques bien ordonnés sur une seule pile initiale.
Je vais tacher de trouver l'article indiqué par Pocket afin de voir si le schmilblick peut avancer (dans le cas général)
Modifié en dernier par C.Ret le 18 janv. 2016 22:12, modifié 1 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
- Administrateur
- Messages : 5944
- Enregistré le : 24 mai 2002 16:55
- Localisation : Toulouse
- Contact :
Re: MPO n°68 : les tours de Hanoï
Salut,
De mémoire, l'article ne traite que le cas ou les N disques sont dans l'ordre sur la première des trois tiges et étend ensuite le problème à M tiges.
A+
De mémoire, l'article ne traite que le cas ou les N disques sont dans l'ordre sur la première des trois tiges et étend ensuite le problème à M tiges.
A+
- jvernet
- Fonctionne à 14400 bauds
- Messages : 7958
- Enregistré le : 24 mai 2002 09:57
- Localisation : France 69
- Contact :
Re: MPO n°68 : les tours de Hanoï
Oui, c'est un grand classique des TP de Pascal. Au millénaire dernier, je me souviens avoir fait ça en licence info. mais plus du tout comment.badaze a écrit :J'avais fait un algo il n'y a pas si longtemps que ça mais impossible de me souvenir pourquoi ?
Le seul truc dont je me souvienne c'est que c'était récursif.
Le programme permettait de positionner les disques (en respectant la règle) librement puis résolvait le problème, le plus rapidement possible et en un minimum de coups.
Je n'aurais plus les capacités intellectuelles de faire ça aujourd’hui .
"l'ordinateur et l'homme sont les deux opposés les plus intégraux qui existent. L'homme est lent, peu rigoureux et très intuitif. L'ordinateur est super rapide, très rigoureux et complètement con."
- bernouilli92
- Fonctionne à 14400 bauds
- Messages : 5235
- Enregistré le : 21 nov. 2012 13:03
- Localisation : Ile de France
Re: MPO n°68 : les tours de Hanoï
Si quelqu'un est intéressé qu'il m’envoie un MP, je pourrai lui transmettre l'article en question.C.Ret a écrit : Je vais tacher de trouver l'article indiqué par Pocket afin de voir si le schmilblick peut avancer (dans le cas général)
Je doute qu'il soit correct de poster un lien de téléchargement ici.
HP, Casio, Sharp, Psion, quelques TI et divers autres
- Marge
- Fonctionne à 14400 bauds
- Messages : 6174
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: MPO n°68 : les tours de Hanoï
Bonjour,
Je me suis mis en congé de mes programmations en OPL pour passer la semaine dernière sur la résolution automatique du problème sur HP-34c, ma caltoche de la semaine.
J'ai préféré utiliser mon algorithme :
1. Décaler le 1 d'une tour à gauche ;
2. Décaler la plus petite décimale suivante :
2a. d'une tour à gauche si elle est impaire ;
2b. de deux tours à gauche si elle est paire ;
3. Recommencer en 1.
On pourrait très bien décaler alternativement à droite et à gauche, mais mon programme fonctionne avec énormément de sous-programmes et j'ai opté pour deux décalages à gauche... soit le même sous-programme répété.
J'ai essayé de trouver une régularité dans le choix de la tour initiale pour chaque déplacement, mais en vain... il y en a certainement une, mais sur une trop longue période pour qu'elle soit intéressante à algorithmiser (oui, je néologise, et alors ? c'est toujours mieux que de parler globish !).
J'éditerai pour quelques commentaires additionnels, mais voici déjà le programme (à optimiser, notamment dans la partie test) :
Notez que le temps d'exécution est très long : près de 3 heures ! beaucoup plus lente qu'un être humain, mais au moins, la 34c ne se plante pas... Je comptais réaliser une petite vidéo, mais là, 3 heures...
À la décharge de la machine, signalons que les pauses (visualisation de la tour de départ, de la décimale retirée, de la tour d'arrivée), à raison d'une seconde d'arrêt (environ), coûtent (3*511) 1 533 secondes, soit 25 minutes et 33 secondes - mais il faut bien montrer les déplacements, n'est-ce pas ?
Il reste 18 pas pour ajouter la version B (Mode Joueur ou Manuel) actionnée par la touche de la 34c ("B" pour : Bon ben y'a plus qu'à !).
Ce sera pour un autre épisode !
(1ère édition : correction de deux erreurs de syntaxe et d'une d'orthographe)
Je me suis mis en congé de mes programmations en OPL pour passer la semaine dernière sur la résolution automatique du problème sur HP-34c, ma caltoche de la semaine.
J'ai préféré utiliser mon algorithme :
1. Décaler le 1 d'une tour à gauche ;
2. Décaler la plus petite décimale suivante :
2a. d'une tour à gauche si elle est impaire ;
2b. de deux tours à gauche si elle est paire ;
3. Recommencer en 1.
On pourrait très bien décaler alternativement à droite et à gauche, mais mon programme fonctionne avec énormément de sous-programmes et j'ai opté pour deux décalages à gauche... soit le même sous-programme répété.
J'ai essayé de trouver une régularité dans le choix de la tour initiale pour chaque déplacement, mais en vain... il y en a certainement une, mais sur une trop longue période pour qu'elle soit intéressante à algorithmiser (oui, je néologise, et alors ? c'est toujours mieux que de parler globish !).
J'éditerai pour quelques commentaires additionnels, mais voici déjà le programme (à optimiser, notamment dans la partie test) :
Code : Tout sélectionner
001 LBL A // "A" pour Automatique, le mode DEMO.
002 CL. Reg. // Efface les registres.
003 8
004 1
005 1/x
006 STO-1
007 1
008 0
009 STO+1 // R1=9,987654321 (l'entier correspond au nombre de décimales)
010 1
011 STO I
012 GSB 0 // La routine 0 affiche R1, R2 ou R3 avec l'entier correspondant au numéro de registre (ou tour).
013 GSB 1 // La routine 1 décale la tour de référence d'un vers la gauche, avec saut à 3 si nécessaire.
014 LBL 8 // Début de la grande boucle : recherche de la décimale 1 (le disque le plus petit).
015 GSB 5 // La routine 5 extrait la dernière décimale de la tour de référence.
016 .
017 1
018 x=y? // Comparaison. Si 1 (le plus petit disque) a été trouvé, on sort de la boucle.
019 GTO 9 // Saute quelques pas ; l'étiquette LBL 9 revient souvent, permettant ainsi ce que j'appelle le saute-mouton.
020 GSB 1 // Décalage.
021 GTO 8 // Si le pgm n'a pas trouvé 1, on recommence.
022 LBL 9
023 Rd // Roll Down (décale la pile d'un niveau vers le bas).
024 GSB 6 // La routine 6 exécute la décapitation de la tour et montre sa tête au peuple ("elle en vaut la peine !")
025 GSB 1 // Décalage (toujours d'une seule tour pour 1).
026 GSB 2 // La routine 2 assure la réception de la décimale sur la tour d'accueil.
027 GSB 0 // Visualisation du nouvel emplacement.
028 RCL 3 // Le registre (la tour) 3 est rappelé(e) pour savoir si le jeu est fini.
029 9
030 x<=y?
031 GTO 4 // La routine 4 affichera le score.
032 GSB 1 // On cherche à présent la deuxième décimale la plus petite.
033 GSB 5 // Extraction de décimale...
034 RCL 0 // La partie décimale va mémoriser la première décimale trouvée.
035 INT
036 +
037 STO 0
038 GSB 1 // Décalage...
039 GSB 5 // Extraction de la deuxième décimale (il ne peut y avoir que 2 tours concernées, la dernière est occupée par le 1).
040 RCL 0 // Comparaison avec la première...
041 FRAC
042 x=0? // ... mais si la tour est vide, il n'y a plus de comparaison !
043 GTO 9
044 x>y?
045 GTO 9 // Comparaison de la 1ère et la 2ème. Si la deuxième est plus petite, c'est la bonne (comme lors du test à 0 précédent).
046 x<->y // Sinon, on positionne correctement la 1ère décimale pour qu'elle soit remise en x en LBL 9 (on doit pouvoir améliorer ça).
047 GSB 1
048 GSB 1 // Double décalage, car on se réfère alors à la tour de droite.
049 LBL 9
050 x<->y
051 X#0? // Si la deuxième décimale extraite est égale à 0, on veut l'autre !
052 GTO 9 // Référence à une étiquette à venir plus bas...
053 x<->y
054 GSB 1
055 GSB 1 // Double décalage.
056 LBL 9
057 GSB 5 // Extraction réelle de la décimale.
058 GSB 6 // Affichage de la tour décapitée et la tête d'icelle.
059 RCL 0
060 INT
061 +
062 STO 0 // Stockage de la décimale pour usage ultérieur.
063 FRAC // Test de parité.
064 5
065 * // Eh oui : multiplier par 5 équivaut à multiplier par 10 et diviser par 2 pour savoir si la décimale est paire ou non.
066 FRAC
067 x=0?
068 GSB 1
069 GSB 1 // Si la décimale est paire, en effet, il faut décaler 2 fois à gauche ; si elle est impaire, une seule fois.
070 RCL 0
071 FRAC // Récupération de la décimale (perdue au-delà de la pile si on ne procède pas à cette occupation de registre)
072 GSB 2 // Positionnement de la décimale sur la nouvelle tour.
073 GSB 0 // Visualisation de la tour.
074 GTO 8 // Fin de la grande boucle, on repart à la recherche du 1.
075 LBL 6 // Décapitation de la tour initiale.
076 -
077 x<->y
078 /
079 1
080 -
081 STO (i)
082 GSB 0 // Visualisation.
083 Ru // Roll Up : Rotation de la pile vers le haut.
084 1
085 x<->I // Procédure nécessaire pour visualiser la seule décimale nécessaire (voir aussi LBL 0).
086 DSP I
087 x<->y
088 PSE // Affichage de la décimale.
089 x<->y
090 x<->I // On rétablit le registre I comme il était auparavant.
091 1
092 STO+0 // Comptage du nombre de coups.
093 Rd
094 Rd
095 RTN // Fin de la routine de décapitation.
096 LBL 5 // Routine d'extraction de la décimale.
097 RCL (i)
098 ENTER
099 INT
100 1
101 -
102 10^x
103 *
104 Lst X
105 x<->y
106 FRAC
107 Lst X
108 x<->y
109 RTN // Fin de la routine d'extraction.
110 LBL 4 // Routine de fin avec affichage du score.
111 RCL 0
112 FIX 0
113 RTN // Fin de la routine de fin.
114 LBL 2 // Routine de réception de décimale sur la nouvelle tour.
115 1
116 STO+(i) // Augmentation du nombre de décimales noté dans la partie entière.
117 Rd
118 RCL (i)
119 INT
120 1
121 -
122 10^x
123 ENTER
124 Rd
125 /
126 x<->y
127 Rd
128 +
129 x<->y
130 /
131 STO (i)
132 RTN // Fin de la routine de réception de décimale.
133 LBL 1 // Routine de décalage de la tour de référence.
134 DSE // Le test "Decremente & Skip if Equal (to zero)" est préférable à "Incremente and skip if greater" parce qu'il évite de remplir la condition du test en I.
135 GTO 9
136 3
137 STO I // Si I=0, alors I=3.
138 Rd
139 LBL 9
140 RTN // Fin de la routine de décalage.
141 LBL 0 // Routine de visualisation de tour (il faut indiquer le numéro de registre dans la partie entière).
142 RCL I
143 RCL (i)
144 FRAC
145 +
146 RCL (i) // Il faut aussi n'afficher que les décimales nécessaires.
147 INT
148 x<->I
149 Rd
150 DSP I
151 PSE
152 Ru
153 x<->I
154 RTN // Fin de la routine de visualisation de tour.
VARIABLES :
Registre I : Numéro de tour (1, 2 ou 3) OU Nombre de décimales à afficher (1 à 9).
Registre 0 : Nombre de coups joués en partie entière ; décimale autre que 1 en partie décimale.
Registres 1, 2 et 3 : Tours 1, 2 et 3 avec le nombre de décimales de chacune en partie entière.
4*7+154=182 octets.
À la décharge de la machine, signalons que les pauses (visualisation de la tour de départ, de la décimale retirée, de la tour d'arrivée), à raison d'une seconde d'arrêt (environ), coûtent (3*511) 1 533 secondes, soit 25 minutes et 33 secondes - mais il faut bien montrer les déplacements, n'est-ce pas ?
Il reste 18 pas pour ajouter la version B (Mode Joueur ou Manuel) actionnée par la touche de la 34c ("B" pour : Bon ben y'a plus qu'à !).
Ce sera pour un autre épisode !
(1ère édition : correction de deux erreurs de syntaxe et d'une d'orthographe)
3 hommes, 3 demis, un 3a... Magnéto, Serge !
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
- Marge
- Fonctionne à 14400 bauds
- Messages : 6174
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: MPO n°68 : les tours de Hanoï
Parfois, je me demande si je ne vis pas dans un monde parallèle...
J'ai voulu reprendre le programme des Tours de Hanoi afin d'y ajouter, un an après, la possibilité pour un joueur de déplacer lui-même les disques.
J'ai d'abord cherché sur ma machine Psion (voir ci-dessous) le programme nommé HANOI34D.
Peine perdue : je ne l'ai pas retrouvé (malgré l'excellent utilitaire Ferret écrit en C++ qui permet des recherches complexes très rapides), ce qui est déjà surprenant puisque je conserve tout sur la même carte depuis de nombreuses années...
J'ai donc commencé à entrer le programme du message précédent : il a provoqué une erreur au premier déplacement de disque antérieurement déplacé (donc, après 1->3, 1->2, quand il s'est agi de déplacer à nouveau le disque le plus petit de la tour 3 à la tour 2 : 3->2).
Après quelques vérifications qui ont pris plusieurs heures, je suis parvenu à le refaire fonctionner correctement : en fait, il y a de nombreuses lignes redondantes (ou plutôt : inutiles, voire stupides) dans la sous-routine 2 (pas 114). Le plus étrange est que le programme modifié est vraiment beaucoup plus rapide que le précédent qui fonctionnait (mais dans quel trou noir est-il donc passé ?) : 2 heures 32 minutes et 25 secondes (contre près de trois heures pour le précédent).
Mais comment ai-je fait pour transcrire sur le forum un programme qui ne fonctionne pas alors qu'il fonctionnait quelques minutes auparavant ? Mystère...
Voici donc le code modifié ; si vous ne possédez pas d'HP-34c, vous pourrez vérifier la validité de ce code sur PC, sur Android ou peut-être sur Iphone (mais je n'ai pas trouvé l'appli. depuis le mien) ; sinon, le code doit normalement fonctionner pour les HP-15C et 15CLE (et leurs émulateurs) sans modification :
VARIABLES :
Registre I : Numéro de tour (1, 2 ou 3) OU Nombre de décimales à afficher (1 à 9).
Registre 0 : Nombre de coups joués en partie entière ; décimale autre que 1 en partie décimale.
Registres 1, 2 et 3 : Tours 1, 2 et 3 avec le nombre de décimales de chacune en partie entière.
5*7+144=179 octets.
Moralité : il n'est jamais trop tard pour bien faire.
Correction du nombre d'octets total en comptant le registre I.
J'ai voulu reprendre le programme des Tours de Hanoi afin d'y ajouter, un an après, la possibilité pour un joueur de déplacer lui-même les disques.
J'ai d'abord cherché sur ma machine Psion (voir ci-dessous) le programme nommé HANOI34D.
Peine perdue : je ne l'ai pas retrouvé (malgré l'excellent utilitaire Ferret écrit en C++ qui permet des recherches complexes très rapides), ce qui est déjà surprenant puisque je conserve tout sur la même carte depuis de nombreuses années...
J'ai donc commencé à entrer le programme du message précédent : il a provoqué une erreur au premier déplacement de disque antérieurement déplacé (donc, après 1->3, 1->2, quand il s'est agi de déplacer à nouveau le disque le plus petit de la tour 3 à la tour 2 : 3->2).
Après quelques vérifications qui ont pris plusieurs heures, je suis parvenu à le refaire fonctionner correctement : en fait, il y a de nombreuses lignes redondantes (ou plutôt : inutiles, voire stupides) dans la sous-routine 2 (pas 114). Le plus étrange est que le programme modifié est vraiment beaucoup plus rapide que le précédent qui fonctionnait (mais dans quel trou noir est-il donc passé ?) : 2 heures 32 minutes et 25 secondes (contre près de trois heures pour le précédent).
Mais comment ai-je fait pour transcrire sur le forum un programme qui ne fonctionne pas alors qu'il fonctionnait quelques minutes auparavant ? Mystère...
Voici donc le code modifié ; si vous ne possédez pas d'HP-34c, vous pourrez vérifier la validité de ce code sur PC, sur Android ou peut-être sur Iphone (mais je n'ai pas trouvé l'appli. depuis le mien) ; sinon, le code doit normalement fonctionner pour les HP-15C et 15CLE (et leurs émulateurs) sans modification :
Code : Tout sélectionner
001 LBL A // "A" pour Automatique, le mode DEMO.
002 CL. Reg. // Efface les registres.
003 8
004 1
005 1/x
006 STO-1
007 1
008 0
009 STO+1 // R1=9,987654321 (l'entier correspond au nombre de décimales)
010 1
011 STO I
012 GSB 0 // La routine 0 affiche R1, R2 ou R3 avec l'entier correspondant au numéro de registre (ou tour).
013 GSB 1 // La routine 1 décale la tour de référence d'un vers la gauche, avec saut à 3 si nécessaire.
014 LBL 8 // Début de la grande boucle : recherche de la décimale 1 (le disque le plus petit).
015 GSB 5 // La routine 5 extrait la dernière décimale de la tour de référence.
016 .
017 1
018 x=y? // Comparaison. Si 1 (le plus petit disque) a été trouvé, on sort de la boucle.
019 GTO 9 // Saute quelques pas ; l'étiquette LBL 9 revient souvent, permettant ainsi ce que j'appelle le saute-mouton.
020 GSB 1 // Décalage.
021 GTO 8 // Si le pgm n'a pas trouvé 1, on recommence.
022 LBL 9
023 Rd // Roll Down (décale la pile d'un niveau vers le bas).
024 GSB 6 // La routine 6 exécute la décapitation de la tour et montre sa tête au peuple ("elle en vaut la peine !")
025 GSB 1 // Décalage (toujours d'une seule tour pour 1).
026 GSB 2 // La routine 2 assure la réception de la décimale sur la tour d'accueil.
027 GSB 0 // Visualisation du nouvel emplacement.
028 RCL 3 // Le registre (la tour) 3 est rappelé(e) pour savoir si le jeu est fini.
029 9
030 x<=y?
031 GTO 4 // La routine 4 affichera le score.
032 GSB 1 // On cherche à présent la deuxième décimale la plus petite.
033 GSB 5 // Extraction de décimale...
034 RCL 0 // La partie décimale va mémoriser la première décimale trouvée.
035 INT
036 +
037 STO 0
038 GSB 1 // Décalage...
039 GSB 5 // Extraction de la deuxième décimale (il ne peut y avoir que 2 tours concernées, la dernière est occupée par le 1).
040 RCL 0 // Comparaison avec la première...
041 FRAC
042 x=0? // ... mais si la tour est vide, il n'y a plus de comparaison !
043 GTO 9
044 x>y?
045 GTO 9 // Comparaison de la 1ère et la 2ème. Si la deuxième est plus petite, c'est la bonne (comme lors du test à 0 précédent).
046 x<->y // Sinon, on positionne correctement la 1ère décimale pour qu'elle soit remise en x en LBL 9 (on doit pouvoir améliorer ça).
047 GSB 1
048 GSB 1 // Double décalage, car on se réfère alors à la tour de droite.
049 LBL 9
050 x<->y
051 X#0? // Si la deuxième décimale extraite est égale à 0, on veut l'autre !
052 GTO 9 // Référence à une étiquette à venir plus bas...
053 x<->y
054 GSB 1
055 GSB 1 // Double décalage.
056 LBL 9
057 GSB 5 // Extraction réelle de la décimale.
058 GSB 6 // Affichage de la tour décapitée et la tête d'icelle.
059 RCL 0
060 INT
061 +
062 STO 0 // Stockage de la décimale pour usage ultérieur.
063 FRAC // Test de parité.
064 5
065 * // Eh oui : multiplier par 5 équivaut à multiplier par 10 et diviser par 2 pour savoir si la décimale est paire ou non.
066 FRAC
067 x=0?
068 GSB 1
069 GSB 1 // Si la décimale est paire, en effet, il faut décaler 2 fois à gauche ; si elle est impaire, une seule fois.
070 RCL 0
071 FRAC // Récupération de la décimale (perdue au-delà de la pile si on ne procède pas à cette occupation de registre)
072 GSB 2 // Positionnement de la décimale sur la nouvelle tour.
073 GSB 0 // Visualisation de la tour.
074 GTO 8 // Fin de la grande boucle, on repart à la recherche du 1.
075 LBL 6 // Décapitation de la tour initiale.
076 -
077 x<->y
078 /
079 1
080 -
081 STO (i)
082 GSB 0 // Visualisation.
083 Ru // Roll Up : Rotation de la pile vers le haut.
084 1
085 x<->I // Procédure nécessaire pour visualiser la seule décimale nécessaire (voir aussi LBL 0).
086 DSP I
087 x<->y
088 PSE // Affichage de la décimale.
089 x<->y
090 x<->I // On rétablit le registre I comme il était auparavant.
091 1
092 STO+0 // Comptage du nombre de coups.
093 Rd
094 Rd
095 RTN // Fin de la routine de décapitation.
096 LBL 5 // Routine d'extraction de la décimale.
097 RCL (i)
098 ENTER
099 INT
100 1
101 -
102 10^x
103 *
104 Lst X
105 x<->y
106 FRAC
107 Lst X
108 x<->y
109 RTN // Fin de la routine d'extraction.
110 LBL 4 // Routine de fin avec affichage du score.
111 RCL 0
112 FIX 0
113 RTN // Fin de la routine de fin.
114 LBL 2 // Routine MODIFIÉE de réception de décimale sur la nouvelle tour.
115 RCL (i)
116 INT
117 10^x
118 /
119 STO + (i)
120 1
121 STO + (i)
122 RTN // Fin de la routine MODIFIÉE de réception de décimale ; GAIN de 10 pas !
123 LBL 1 // Routine de décalage de la tour de référence.
124 DSE // Le test "Decremente & Skip if Equal (to zero)" est préférable à "Incremente and skip if greater" parce qu'il évite de remplir la condition du test en I.
125 GTO 9
126 3
127 STO I // Si I=0, alors I=3.
128 Rd
129 LBL 9
130 RTN // Fin de la routine de décalage.
131 LBL 0 // Routine de visualisation de tour (il faut indiquer le numéro de registre dans la partie entière).
132 RCL I
133 RCL (i)
134 FRAC
135 +
136 RCL (i) // Il faut aussi n'afficher que les décimales nécessaires.
137 INT
138 x<->I
139 Rd
140 DSP I
141 PSE
142 Ru
143 x<->I
144 RTN // Fin de la routine de visualisation de tour.
Registre I : Numéro de tour (1, 2 ou 3) OU Nombre de décimales à afficher (1 à 9).
Registre 0 : Nombre de coups joués en partie entière ; décimale autre que 1 en partie décimale.
Registres 1, 2 et 3 : Tours 1, 2 et 3 avec le nombre de décimales de chacune en partie entière.
5*7+144=179 octets.
Moralité : il n'est jamais trop tard pour bien faire.
Correction du nombre d'octets total en comptant le registre I.
Modifié en dernier par Marge le 25 oct. 2017 21:07, modifié 1 fois.
3 hommes, 3 demis, un 3a... Magnéto, Serge !
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
- Marge
- Fonctionne à 14400 bauds
- Messages : 6174
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: MPO n°68 : les tours de Hanoï
Les copains, j'ai un problème.
Déçu par l'adaptation de ce programme à ma 15c LE (pour cause de pause défaillante), j'ai tenté une adaptation à cette bonne vieille HP-41c ; mais voilà : comment faire pour demander dans le programme un échange entre le registre X et un registre numéroté quelconque ? Le manuel est très succint (en gros, y'a qu'à faire X<> et entrer le numéro) et les signes "inférieur à" et "supérieur à" ne fonctionnent pas...
Un avis ? je suis sûr que j'ai déjà rencontré ce problème, en plus, c'est agaçant...
Déçu par l'adaptation de ce programme à ma 15c LE (pour cause de pause défaillante), j'ai tenté une adaptation à cette bonne vieille HP-41c ; mais voilà : comment faire pour demander dans le programme un échange entre le registre X et un registre numéroté quelconque ? Le manuel est très succint (en gros, y'a qu'à faire X<> et entrer le numéro) et les signes "inférieur à" et "supérieur à" ne fonctionnent pas...
Un avis ? je suis sûr que j'ai déjà rencontré ce problème, en plus, c'est agaçant...
3 hommes, 3 demis, un 3a... Magnéto, Serge !
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
- Marge
- Fonctionne à 14400 bauds
- Messages : 6174
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: MPO n°68 : les tours de Hanoï
Merci z., mais c'est exactement ce que j'ai fait, suivi du n° de registre, et la machine m'a affiché : xeq 'x<>04'
M'enfin, elle m'a aussi rendu un programme "PRIVATE"... avec un test de drapeau ! (elle est sur une batterie rechargeable un peu vieille...)
J'essaierai avec des piles plus tard...
3 hommes, 3 demis, un 3a... Magnéto, Serge !
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠