gege a écrit :Bonjour,
il me semble que ce problème est bien étudié (le nombre de coups est 2^N pour N disques), par contre si la configuration de départ est "libre", ça semble plus ouvert...
Exemple on démarre avec :
1> 86531
2> 974
3> 2
et il faut aboutir à tout mettre sur le poteau 1> ...
Je vais tenter un algo (pas la moindre idée pour l'instant, génial !)
A+
G.E.
Pour être compatible avec l'énoncé, le plus simple est de finir par tout mettre sur la tour n°3.
Bon voici ma réponse aux questions 1 & 2 pour un SHARP PC-1211
Les trois tours sont nommées A B et C dans ce programme qui ne fait qu'environ 428 octets et n'utilise aucune variable au-delà de la zone mémoire préétablie aux registres A-Z. Il est donc compatible pour le SHARP PC-1210.
Il répond à la question n°1 car il permet de gérer les déplacements entre les trois tours. Ceci est réalisé à l'aide des trois touches [ A ] [ B ] et [ C ] en mode DEF afin de lancer respectivement les mouvements A<===>B , A<===>C et B<==>C. Le sens du mouvement s'effectuant en fonction de la configuration des deux tours. A savoir depuis la tour remplie vers la tour vide (si les deux tours sont vide un BEEP retenti pour indiquer le mouvement impossible), Si les deux tours sont remplies, le sens utilisé permettra de déplacer le disque le plus petit vers la tour contenant le disque le plus grand.
Ainsi:
def-[ A ] ( A<--->B ) permet le déplacement d'un disque entre les tours A et B. C'est à dire soit de la tour A vers la tour B, soit dans l'autre sens de la tour B vers la tour A.
En effet, s'il y a au moins un disque dans chacune des tours, seul le disque le plus petit est déplacé. Il n'y a donc pas d'ambiguïté, A<===>B correspond à A-->B ou B-->A selon la position du plus grand disque ou que l'une des deux tour soit vide. C'est d'ailleurs une astuce qui facilite l'algorithme de résolution. Et moins de déplacements à programmer dans le code MPO.
De même def-[ B ] et def-[ C ] déclenchent les mouvements A<===>C et B<===>C qui correspondent selon les circonstances aux déplacements du disque de A-->C ou C-->A et respectivement B-->C ou C-->B
En cas de déplacement impossible (les deux tours vides), le pocket sonne et revient à l'affichage de l'étape en cours.
Les lignes 1: et 2: permettent de saisir trois tours initiales quelconques comme le suggère notre am
gégé.
Comme pour les TI-57, le contenu des trois tours initiales n'est pas vérifié.
Pour spécifier un nouveau contenus pour les trois tours, il suffit d'utiliser le raccourci def-[SPC] (comme DEFinir SPéCifier !) ou de relancer le programme par RUN[ENTER]
Le pocket demande alors la composition des tours A, B et C. Un simple appuis sur ENTER permet de passer à la tour suivante et revient à saisir 0 (qui signifie tour vide).
En fonction de la parité du nombre de disque, le pocket élabore une stratégie de résolution qui utilise des choses compliquées comme des logarithmes décimaux, deux variables (G et P comme Coup Gagnant et Parité) et un test de division par deux (cf. ligne 3:) ! Il en résulte un algorithme de résolution automatique que l'utilisateur pourra déclencher pas à, pas à chaque étape.
Pour lancer la configuration initiale proposée par
Marge, il suffit de n'entrer aucune composition, le code étant par défaut programmé avec cette configuration (cf. ligne 1:).
La réponse à la question n°2 est réalisée par la seconde partie de la ligne 4: qui déroule l'algorithme de résolution automatique grâce à un astucieux GOTO 6+G. Celle-ci est automatiquement lancée en pressant [ENTER]à chaque étape lors de l'affichage du contenu des trois tours. L'utilisateur peut donc après chaque coup tenter d'avancer dans la résolution ou laisser faire son pocket.
J'utilise un algorithme itératif qui revient à déplacer le disque le plus petit toujours dans le même sens en alternance avec le déplacement d'un des autres disques.
A chaque étape, l'affichage du SHARP-PC1211 se compose des informations suivantes :
- nombre de déplacement depuis le début de la partie, (variable N)
- rappel du dernier mouvement (taille du disque, tour d'origine et destination) (resp. variable X E$ et F$)
- contenu de la tour A (variable A) ou 0. si celle-ci est vide
- contenu de la tour B (variable B) ou 0. si celle-ci est vide
- contenu de la tour C (variable C) ou 0. si celle-ci est vide
Exemple affichage initial:
Code : Tout sélectionner
Affichage Keystrocke Commentaires
------------------------ -------------- ----------------------------------------------------------
> MODE Mettre en mode DEF
RUN_ RUN[ENTER] Lance le programme
? _ [ENTER] Demande composition Tour A - Aucune saisie (configuration de Marge)
? _ [ENTER] Demande composition Tour B - idem
? _ [ENTER] Demande composioton Tour C - idem
0.1 A987654321.B0.C0. Affichage de l'état initial - En cas d'erreur relancer par def-SPC
La tour A contient l'empilement des 9 disques
B et C sont vides.
Code : Tout sélectionner
shft-A Déplacement entre A et B.
1.1AB A98765432.B1.C0. 1. coup
1AB indique que le disque 1 a été déplacé de A vers B
A contient maintenant 98765432, B contient 1 et C est vide.
shft-B Déplacement entre A et C.
2.2AC A9876543.B1.C2. shft-C Déplacement entre B et C, comme 2 ne peut-être posé sur le 1
c'est ce dernier qui sera déplacé de C-->B.
3.1BC A9876543.B0.C21. La tour B est à nouveau vide.
shft-A Déplacement entre A et B.
4.3AB A987654.B3.C21. shft-B Déplacement entre A et C,ici aussi c'est 1 qui sera déplacé.
5.1CA A9876541.B3.C2. shft-B Répétition du dernier déplacement pour annuler son effet
6.1AC A987654.B3.C21. On retrouve la configuration de l'étape 4.
Code : Tout sélectionner
shft-SPC Ré-initialisation des tours
? 321_ 321[ENTER] Saisie de la configuration simple pour exemple de résolution
? 0_ 0[ENTER]
? _ [ENTER]
0.1 A321. B0. C0. [ENTER] Petit exemple pour tester l'algorithme de résolution.
1.1AC A32. B0. C1. [ENTER]
2.2AB A3. B2. C1. [ENTER]
3.1CB A3. B21. C0. [ENTER]
4.3AC A0. B21. C3. [ENTER]
5.1BA A1. B2. C3. [ENTER]
6.2BC A1. B0. C32. [ENTER]
* * beep * beep * beep * *
7.1AC A0.B0.C321. Résolu en 7 mouvements
PROGRAMME ====================================================================================================
Code : Tout sélectionner
1:" " CLEAR :USING :A=987654321,D=.1,M=1:FOR I=1 TO 3:INPUT A(I) (43)
2:IF A(I)>0 GOSUB 5:N=1+N+INT LOG A(I):IF X<M LET M=X,J=I (38)
3:NEXT I:P=1-2*(N/2<>INT .5N),N=0,G=2J+P (34)
4:"=" Y=A+B=0:BEEP 3Y:PRINT N+X,E$,F$," A";A;"B";B;"C";C:G=G-3*INT (G/3):GOTO 6+G (63)
5:X=DA(I),X=X-INT X:RETURN (18)
6:"A" I=1,E$="A",J=2,F$="B":GOTO 9 (30)
7:"B" I=1,E$="A",J=3,F$="C":GOTO 9 (30)
8:"C" I=2,E$="B",J=3,F$="C" (27)
9:GOSUB 5:Y=DA(J),Y=Y-INT Y:IF Y IF Y*SGN X<=X LET X=I,I=J,J=X,X$=E$,E$=F$,F$=X$:GOTO 9 (63)
10:G=G+P,Y=1:IF A+B IF X LET N=N+1,A(J)=(A(J)+X)/D,A(I)=INT DA(I),Y=0:IF X<M LET M=X,G=2J+P (74)
11:BEEP Y:GOTO 4 ( 8)
(428 octets)
LIGNES :==================================================================================================
Code : Tout sélectionner
1:2:3: def-SPC Initialisation des trois tours et de la stratégie gagnante GP
4: def- = Affichage du dernier coup et configuration des trois tours
[ENTER] et résolution automatique pas à pas
6: def- A Mouvement n°1 A<===>B déplaçant soit de A-->B soit de B-->A selon le contenu des tours
7: def- B Mouvement n°2 A<===>C déplaçant un disque de A-->C ou C-->A
8: def- C Mouvement n°3 B<===>C déplaçant un disque de B-->C ou C-->B
Sous-Programme :==================================================================================================
Code : Tout sélectionner
5: Appels depuis ligen 2: et 9: pour extraction du disque X de la tour I
9:10:11: Tronc commun du transfert du disque X avec éventuel échange par le disque Y de la tour j si celui-ci est plus ptit (ligne 9:)
La ligne 10: effectue le mouvement du disque et ajoute la stratégie gagnante GP si le disque minium M est manipulé
CODES SONNORES: :==============================================================================================
Code : Tout sélectionner
1 BEEP est émis en cas d'erreur (mouvement impossible)
3 BEEP retentissent lorsque la configuration finale est atteinte (tous les disques sur la tour C)
VARIABLES ::==================================================================================================
Code : Tout sélectionner
B - Contenu Tour B
C - Contenu Tour C M - Valeur du plus petit disque
N - Nombre de disque/Nombre de mouvements
D - .1 Constante décimale
P - Parité/ Sens du mouvement
E$ - Label tour origine du mouvement
F$ - Label tour destination du dernier mouvement X - Valeur disque tour i
Y - Valeur disque tour j
G - Prochain coup "gagnant"
I - Indice tour i
J - Indice tour j
Etant donné la structure des ligne 6: 7: et 8:, il est évident que ce programme peut encore être MPO-iser, mais je préfère présenter cette version plus lisible et plus compacte, même si quelques octets sont perdus dans cette zone.
J'oubliais !!!
Bonne Année à toutes et tous !!
je vais faire du béton pendant 3 jours, alors... ça peut attendre. 
(j'édite car c'est repoussé à la semaine prochaine, il pleut depuis deux mois tous les jours ici. Mais ça peut toujours attendre !)
)