Misez p'tit, Optimisez - N°15 (le jour des fourmis)

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
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Misez p'tit, Optimisez - N°15 (le jour des fourmis)

Message par C.Ret »

Comme cela fait un peu de temps, je propose à nos Pockets et nos calculettes un petit exercice de style misez p'tit - Optimiser sans grande prétention.

Comme à l’accoutumée, le sujet est sans intérêt concret et provient du hasard des lectures de ces dernières semaines (1). Le seul intérêt est peut-être celui de constituer un exercice de niveau fort différent selon la machine ou le Pocket sur lequel il sera porté.

En effet, les séries audioactives peuvent facilement se programmer en utilisant les capacités alphanumériques de certains Pockets, mais vont certainement poser un problème d’optimisation plus ardu sur les Pockets ou les calculatrices dépourvue de chaines de caractères.


L’exercice proposé consiste à écrire le code le plus compact et le plus efficace pour afficher les termes successifs d’une Suites de Robinson. L’utilisateur saisira le premier terme, puis à chaque itération le programme devra afficher le terme suivant et ainsi de suite.

La notion de suites audioactives a été introduite en 1986 le mathématicien John Horton Conway, mais avec la Suite de Conway, le nombre de chiffres augmente trop rapidement pour que cela soit intéressant sur l’affichage limité de nos calculettes.

Nous considérerons donc les Suites de Robinson qui sont du même type que celles de Conway, mais dont le nombre de chiffres ne s’étend pas aussi rapidement, ni à l’infini d’ailleurs.

Définition:
Suites de Robinson est une suite mathématique dont chaque terme se détermine en comptant combien de fois chaque chiffre apparaît dans le terme précédent.

Le premier terme de la suite de Robinson est posé comme égal à 0. Mais, par extension, nous considérerons également les suites dont le premier terme est un nombre entier quelconque.

Chaque terme de la suite se construit ensuite en comptant le nombre d'apparitions des différents chiffres de 9 à 0 (pris dans cet ordre) dans le terme précédent. Si un chiffre n'apparaît pas, il n'est pas pris en compte.

Concrètement :

X0 = 0
Ce terme comporte juste un « 0 ». Par conséquent, le terme suivant est :
X1 = 10
Celui-ci est composé d'un « 1 » et d'un « 0 » :
X2 = 1110
En poursuivant le procédé :
X3 = 3110
X4 = 132110
X5 = 13123110
X6 = 23124110
X7 = 1413223110
X8 = 1423224110
X9 = 2413323110
X10 = 1433223110
X11 = 1433223110
Et ainsi de suite.

Le code proposé devra donc permettre d’afficher les termes successifs de la suite de Robinson, dont le premier terme est zéro, mais aussi toute suite dérivée construite à partir d’un nombre entier positif quelconque pris comme premier terme.
X0 = 523
X1 = 151312
X2 = 15131231
X3 = 15231241
X4 = 1514132231
X5 = 1514232241
X6 = ...


A titre de bonus, les RPL et autres Pockets BASIC pourront étendre la chose en étendant le principe à tout terme initial alphanumérique. Ainsi, on construira une suite alphanumérique de Robinson de premier membre C.Ret de la façon suivante :
A0 = C.RET
A1 = 1T1R1E1C1.
A2 = 1T1R1E1C511.
A3 =1T1R1E1C15611.
A4 = 1T1R1E1C1615711.
Et ainsi de suite…


Voilà, ces suites n’ont rien de bien palpitant, même s’il y a des propriétés intéressantes. Mais leur programmation sur certaines calculatrices (comme les SHARP PC-1211 ou les HP Classique) peuvent, selon la technique utilisée, poser quelques petits problèmes.


----
(1) Le Jour des Fourmis Bernard WEBER. p.209 ed. Le Livre de Poche - ISBN 978-2-253-13724-5
Modifié en dernier par C.Ret le 24 févr. 2012 17:51, 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
pir2
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4641
Enregistré le : 31 oct. 2006 15:08
Localisation : 67310 Westhoffen
Contact :

Re: Misez p'tit, Optimisez - N°15 (le jour des fourmis)

Message par pir2 »

Voilà, j'ai mon devoir de vacances :)
lisp? rpl? rpn? basic? c?, vais devoir en emmener des bécanes ;)
Peut-être mon premier vrai programme sur HP-35S, depuis le temps.
Image
Image
Avatar du membre
badaze
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 8372
Enregistré le : 12 févr. 2007 18:36
Localisation : Pas très loin de Lyon
Contact :

Re: Misez p'tit, Optimisez - N°15 (le jour des fourmis)

Message par badaze »

En Basic pour PC-1500. J'utilise un tableau A au lieu de @ car PC1500FOREVER ne charge pas ce caractère.

Code : Tout sélectionner

110 DIM ST$(0) * 80
120 DIM A(9)
130 INPUT ST$(0)
140 "A" FOR Z=0 TO 9
150 A(Z)=0
160 NEXT Z 
170 FOR Z=1 TO LEN(ST$(0))
180 Y=VAL(MID$(ST$(0),Z,1))
190 A(Y)=A(Y)+1
200 NEXT Z
210 ST$(0) = ""
220 FOR Z=9 TO 0 STEP -1
230 IF A(Z) = 0 THEN "B"
240 A$=STR$(A(Z))+STR$(Z)
250 ST$(0)=A$+ST$(0) 
260 "B" NEXT Z
270 PRINT ST$(0)
290 GOTO "A"
Tout est bon dans le pocket.
Moi j'aime tout.... Casio, HP, Sharp, TI et les autres sauf que les TI semblent ne pas m'aimer :(
http://www.emmella.fr
Mes Casio - HP - Sharp - TI
Homme invisible.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit, Optimisez - N°15 (le jour des fourmis)

Message par C.Ret »

Merci Badaze j'aime bien ce code, il utilise la même stratégie que celle que j'utilise sur mes Commodres 8 bits.

En fait, un tableau de dix valeurs est utilisé pour mémoriser le nombre de chacun des chiffres. En effet dans chaque terme, il y a deux type de chiffres; eux des compteurs et les chiffres qui indiquent justemetn de quel chiffre il s'agit (ceux entre < > dans le tableau ci-dessous:

Code : Tout sélectionner

X0 =                     0
X1 =                  1<0>
X2 =              1<1>1<0>
X3 =              3<1>1<0>
X4 =      1<3>    2<1>1<0>
X5 =      1<3>1<2>3<1>1<0>
X6 =      2<3>1<2>4<1>1<0>
X7 =  1<4>1<3>2<2>3<1>1<0>
X8 =  1<4>2<3>2<2>4<1>1<0>
X9 =  2<4>1<3>3<2>3<1>1<0>
X10 = 1<4>3<3>2<2>3<1>1<0>
X11 = 1<4>3<3>2<2>3<1>1<0>
Et ainsi de suite.


A chaque cycle, le tableau est remis à zéro. Puis on parcours la chaine de caractère qui contient le terme précèdent (ou le terme inital) pour en compter le nombre de chaque chiffre justemetn dans ce tableau.
Une fois la chaine de caractère parcourrue, on utilise le tableau pour constuire le terme suivant sous forme de chaine de caractère en omettant les chiffre absents qui correspondent au valeur nulle restante dans le tableau.

Voici donc ma version du problème :

Code : Tout sélectionner

10 : DIM N%(9)                                                                                                  :rem  N( 0 to 9 ) entier
15 : INPUT "SUITE DE ROBINSON: X0=";T$:IF VAL(T$)<0 THEN END         :rem seuls les positifs sont acceptés

20 : FOR I=0 TO 9:A(I)=0:NEXT I                                                                      :rem Etape 1: raz du tableau
25 : FOR I=1 TO LEN(T$)
30 :        C%=VAL(MID$(T$,I,1)) : N%(C%)=N%(C%)+1                                   :rem Etape 2: comptage des chiffres
35 : NEXT I
40 : T$="":FOR I=9 TO 0 STEP -1
45 :        IF N%(I)>0 THEN T$=T$+MID$(STR$(N%(I)),2)+CHR$(48+I)           :rem Etape 3: construction terme suivant
50 : NEXT I
60 : PRINT T$                                                                                                    :rem et affichage              
70 : GOTO 20   
Le piège est que certains BASIC ajoutent un espace en début de chaine avec la fonction STR$. Il faut donc, comme dans le code ci-dessus utiliser MID$ pour ne pas inclure cet espace de signe dans la chaine.
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
Hobiecat
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3625
Enregistré le : 06 sept. 2011 14:57
Localisation : Normandie

Re: Misez p'tit, Optimisez - N°15 (le jour des fourmis)

Message par Hobiecat »

J'ai essayé sur ma HP41 cet après-midi... et j'ai laissé tomber : avec les (maigres) possibilités du registre alpha, on tombe tout de suite dans l'usine à gaz pour programmer cette suite !
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit, Optimisez - N°15 (le jour des fourmis)

Message par C.Ret »

J'ai moi aussi une 41-C, est c'est vrai que l'on ne peut pas utiliser le registre alpha numérique aussi efficacement qu'avec les chaines alpahnumérique en BASIC.

Mais, c'est là qu'est le challenge, comment programmer cette suite sans l'avantage de l'alpha numérique.

Les HP-41, ont au moins pour elle la possibilité d'afficher plus facilement les termes de la suite.


Pour siplifier, on peut dans un premier temps ne considérer uniquement la suite de Robinson originale, c'est à dire celle qui commence par x0 = 0.
Si on se débrouille bien, cela va éviter d'avoir à analyser lenombre saisi par l'utilisateur du programme. Selon l'algorithme que l'on utilisera, cela peut permettre de mieux contrôler les choses !
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.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit, Optimisez - N°15 (le jour des fourmis)

Message par Gilles59 »

1er version HP49/50. Une autre façon plus générique est d'utiliser des listes

Code : Tout sélectionner

«   
  ""
  58 48 FOR n
    OVER n CHR DUP SREPL NIP
    DUP { R->I  n CHR + + } { DROP } IFTE
  -1 STEP
  NIP
»
'Robin' STO
Avec la bib GoferList (permet de résoudre "C.RET" ou toute chaine de caractères

Code : Tout sélectionner

« -> t
  «  
   t Chars « > » Sort Nub 
      1 « DUP t SWAP DUP SREPL NIP R->I SWAP + » DOLIST
   Strcat  
  »
»
'Robi2' STO
http://www.musikwissenschaft.uni-mainz. ... GoferLists

Si on ne considère que les chiffres c'est faisable sur une 602P (mais longueur <=12 pour garder un code raisonnable)
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit, Optimisez - N°15 (le jour des fourmis)

Message par C.Ret »

Merci Gilles.


Bon trois choses :

La première, il va me falloir un peu de temps pour digérer les codes pur la HP-50. Il faut que je ré-installe l'émulateur (j'ai dû changer d'ordinateur !).


La seconde, mon imprimante thermique infra-rouge HP 82240A est maintenant reliée à mon HP-41C.


La troisième, j'ai pu composer un code qui permet de calculer les suites numérique (limité à 10 chiffres pour les mêmes raisons que les 12 chiffre de la Fx-602).
C'est tout à fait normal, c'est pour cela que j'ai choisi les suite de robinson, à cause justemetn du nombre limite de chiffres nécessaires.


Donc, pour une première fois, je présenterais le code en scannant le listing. Ce qui m'évite toute faute de frappe !
robinx.png
robinx.png (40.84 Kio) Vu 7134 fois
Sinon deux mots quand à son fonctionnement :

Le programme est en deux parties.
La première (ligne 01 à 19) est un codeur qui prend le terme de la suite dans la pile (niveau x:) et compte chaque chiffre et mémorise le résultat des comptage en un seul nombre de dix chiffres. Ce qui évite d'utiliser un tableau de valeur - j'économise les registres, d'ailleurs ce code n'utilise aucun registre de l'HP-41C - tout se fait dans la pile et le registre L = lastX

La seconde (ligne 20 à 50) est un décodeur qui à partir du nombre contenant le résultat des comptages, construit le terme suivant.
Comme la première partie, c'est essentiellement une boucle (de 9 à 0) qui ajoute les codes de chaque chiffre compté.

Les résultats de ce code sont correct, tant que l'on se limite à un maximum de 10 chiffres et pas plus de 9 chiffres identiques.
Il n'utilise aucun registre mémoire, ni le registre alphanumérique. Tout est fait par arithmétique, chiffre par chiffre en utilisant la pile (et le registre Lastx = L dans les listings) et le drapeau (Flag - 01 ).


Et même si ce n'est pas tout à fait l'usine à gaz dont parlait très justement Hobicat, if fait tout de même 54 pas.
robin2.png
robin2.png (29.26 Kio) Vu 7134 fois
Modifié en dernier par C.Ret le 05 janv. 2021 20:08, modifié 4 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
badaze
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 8372
Enregistré le : 12 févr. 2007 18:36
Localisation : Pas très loin de Lyon
Contact :

Re: Misez p'tit, Optimisez - N°15 (le jour des fourmis)

Message par badaze »

54 pas c'est pas beaucoup. Chapeau.
Tout est bon dans le pocket.
Moi j'aime tout.... Casio, HP, Sharp, TI et les autres sauf que les TI semblent ne pas m'aimer :(
http://www.emmella.fr
Mes Casio - HP - Sharp - TI
Homme invisible.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit, Optimisez - N°15 (le jour des fourmis)

Message par Gilles59 »

badaze a écrit :54 pas c'est pas beaucoup. Chapeau.
+1
102,5 octets pour la 50G

Je vois la logique du prog. Même idée pour la 602 mais çà fera quelques octets de plus sauf astuces, mode algébrique et absence de qqes instrctions oblige....
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Avatar du membre
Hobiecat
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3625
Enregistré le : 06 sept. 2011 14:57
Localisation : Normandie

Re: Misez p'tit, Optimisez - N°15 (le jour des fourmis)

Message par Hobiecat »

Superbe la version 41C !
J'avais parlé d'usine à gaz parce que j'étais parti en utilisant le registre ALPHA et ça devenait vraiment une usine à gaz, mais là en 54 pas, chapeau !!

PS : la version 49/50G a aussi l'air très sympa, mais il faudrait vraiment que je me plonge sur le RPL. En l'état, je ne comprends pas grand chose...
Modifié en dernier par Hobiecat le 26 févr. 2012 23:28, modifié 1 fois.
Avatar du membre
badaze
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 8372
Enregistré le : 12 févr. 2007 18:36
Localisation : Pas très loin de Lyon
Contact :

Re: Misez p'tit, Optimisez - N°15 (le jour des fourmis)

Message par badaze »

Et avec le module X-Functions ou une 41CX ?
Tout est bon dans le pocket.
Moi j'aime tout.... Casio, HP, Sharp, TI et les autres sauf que les TI semblent ne pas m'aimer :(
http://www.emmella.fr
Mes Casio - HP - Sharp - TI
Homme invisible.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit, Optimisez - N°15 (le jour des fourmis)

Message par C.Ret »

Oui, c'est le principe du code qui fait gagner des pas.

Car, l'idée de base est que losque l'on compte un 9, on ajoute 10^9 au compteur, pour un 5 on ajoutera 10^5, un zéro compte donc pour 10^0 (soit l'unité), etc.
Tout ce passe bien tant qu'il y a moins de 9 chiffres identiques. Mais comme l'HP-41 n'utilise que dix chiffres, c'est pas trop grave.

En pratique, j'ai décalé la positon des comptages de façon à ce que le compteur soit un nombre décimal "9.876543210", ce qui facile la boucle de décodage, car j'utilise INT et FRAC pour "avancer" dans le nombre. Ce qui fait que les 0 sont comptés au niveau des 1/10^9, les 1 au niveau des 1/10^8, .... les 8 des dixièmes et les 9 comme unité. Mais c'est le même principe, juste un petit décalage pour me faciliter l'extraction.


Concernant l'HP-41CX ce doit être plus facile, si je me souviens bien il y a moyen d'extraire des codes caractères (ATOX ???) depuis le registre alpha. On doit donc pouvoir faire quelque code qui tolère les lettres, ou en tout cas qui permette d'aller au-delà de dix chiffres (l'apha peut contenir jusqu'à 24 caractères) et plus de 9 fois le même 'chiffre'.
Par contre, la structure codeur --> compteur unique --> décodeur sera difficile à réaliser, il n'y a qu'un seul registre alpha !
Mais bon, il ne doit pas être difficile d'utiliser un tableau de registres (plusieurs dizaines pour avoir chiffres et lettres).


Je suis en train d'adapter à mon HP-28S et pour la version en cours utilise une structure diffèrente. Plutôt basée sur la récurrenceb(en quelque sorte).
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
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit, Optimisez - N°15 (le jour des fourmis)

Message par C.Ret »

Hobiecat a écrit :En l'état, je ne comprends pas grand chose...
Je ne suis donc pas seul.
Ce qui m'inquiète, c'est que du RPL, j'en fais tous les jours (mais du que je comprends).

Donc, les gens qui disent que le RPL est un "write only langage" n'ont peut-être pas tord !
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
badaze
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 8372
Enregistré le : 12 févr. 2007 18:36
Localisation : Pas très loin de Lyon
Contact :

Re: Misez p'tit, Optimisez - N°15 (le jour des fourmis)

Message par badaze »

C'est quand même beaucoup plus compréhensible en Basic. Pour moi le RPL c'est de l'Aldébaranais !!!
Tout est bon dans le pocket.
Moi j'aime tout.... Casio, HP, Sharp, TI et les autres sauf que les TI semblent ne pas m'aimer :(
http://www.emmella.fr
Mes Casio - HP - Sharp - TI
Homme invisible.
Répondre

Retourner vers « Tous les Pockets »