MPO n°68 : les tours de Hanoï

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Avatar du membre
Marge
Fonctionne à 14400 bauds
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ï

Message par Marge »

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.
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é.
billaj
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 383
Enregistré le : 09 avr. 2005 17:48
Localisation : Brest
Contact :

Re: MPO n°68 : les tours de Hanoï

Message par billaj »

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 :

Code : Tout sélectionner

Prog 0 (35 pas) :

9->A:
-1->B:
1->C:
0->D:
1.23456789->E:
0->F:
0->G:
et Prog 1 :

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:
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 !
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.
Avatar du membre
Marge
Fonctionne à 14400 bauds
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ï

Message par Marge »

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 :
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.
Je pense à transformer ce principe en :
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.
Le déplacement se fait de droite à gauche puisque le nombre initial de disques est 9.

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é.
Avatar du membre
Pocket
Administrateur
Administrateur
Messages : 5944
Enregistré le : 24 mai 2002 16:55
Localisation : Toulouse
Contact :

Re: MPO n°68 : les tours de Hanoï

Message par Pocket »

Salut,

Il y a un article sur ce sujet dans "Pour La Science" de décembre, ils y donnent les algos ...

A+
Pocket, voit tout, sait tout, lit l'avenir dans les entrailles d'une base phpBB ...
Image
Avatar du membre
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5235
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

Re: MPO n°68 : les tours de Hanoï

Message par bernouilli92 »

De quelle année? Pas trouvé dans celui de décembre 2015.
HP, Casio, Sharp, Psion, quelques TI et divers autres
Avatar du membre
Pocket
Administrateur
Administrateur
Messages : 5944
Enregistré le : 24 mai 2002 16:55
Localisation : Toulouse
Contact :

Re: MPO n°68 : les tours de Hanoï

Message par Pocket »

Salut,

Oops, erreur de ma part : Numéro spécial 457 de Novembre sur un certain Albert Einstein, page 108.

A+
Pocket, voit tout, sait tout, lit l'avenir dans les entrailles d'une base phpBB ...
Image
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
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ï

Message par C.Ret »

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)
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.
Avatar du membre
Pocket
Administrateur
Administrateur
Messages : 5944
Enregistré le : 24 mai 2002 16:55
Localisation : Toulouse
Contact :

Re: MPO n°68 : les tours de Hanoï

Message par Pocket »

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+
Pocket, voit tout, sait tout, lit l'avenir dans les entrailles d'une base phpBB ...
Image
Avatar du membre
jvernet
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7958
Enregistré le : 24 mai 2002 09:57
Localisation : France 69
Contact :

Re: MPO n°68 : les tours de Hanoï

Message par jvernet »

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

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."
Avatar du membre
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5235
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

Re: MPO n°68 : les tours de Hanoï

Message par bernouilli92 »

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)
Si quelqu'un est intéressé qu'il m’envoie un MP, je pourrai lui transmettre l'article en question.
Je doute qu'il soit correct de poster un lien de téléchargement ici.
HP, Casio, Sharp, Psion, quelques TI et divers autres
Avatar du membre
Marge
Fonctionne à 14400 bauds
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ï

Message par Marge »

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) :

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.
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... :lol: 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)
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é.
Avatar du membre
Marge
Fonctionne à 14400 bauds
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ï

Message par Marge »

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.

Image

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

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é.
Avatar du membre
Marge
Fonctionne à 14400 bauds
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ï

Message par Marge »

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...
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é.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2920
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: MPO n°68 : les tours de Hanoï

Message par zpalm »

XEQ ALPHA X shift COS shift TAN ALPHA
Avatar du membre
Marge
Fonctionne à 14400 bauds
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ï

Message par Marge »

zpalm a écrit : 23 oct. 2017 22:01 XEQ ALPHA X shift COS shift TAN ALPHA
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'

8O

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é.
Répondre

Retourner vers « Tous les Pockets »