Misez p'tit Optimisez n°57 : palindromes

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

caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 434
Enregistré le : 05 juin 2014 22:23
Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau

Re: Misez p'tit Optimisez n°57 : palindromes

Message par caloubugs »

C.Ret a écrit : Je préfère, et de loin, cette seconde version plus rationnelle et qui finit ce qu'elle commence:

Code : Tout sélectionner

10 INPUT "N=";N$: S$=N$: N%=0 
15 DO                                                       : REM ******* Boucle principale
20 :  A$=S$: L%=LEN(A$): C%=0: S$="": P%=N%
25 :  FOR I=1 TO L%                                         : REM    **** Boucle Sommation/Detection Palindrome
30 :  :  A%=VAL(MID$(A$,I,1)): B%=VAL(MID$(A$,1+L%-I,1))
35 :  :  S%=48+C%+A%+B%: C%=0: IF S%>57 THEN S%=S%-10: C%=1 : REM C%=1 si retenue
40 :  :  S$=CHR$(S%)+S$: IF A%<>B% THEN P%=0                : REM P%=0 si A$ n'est pas palidromique  
45 :  NEXT I
50 :  IF P% THEN  EXIT : ELSE N%=N%+1: IF C% THEN S$="1"+S$
55 LOOP 
60 PRINT "Initial   :";N$                                   : REM    * * * Presentation resultat
65 PRINT "Iterations:";N%
70 PRINT "Palindrome:";A$
75 END
Cette petite merveille trouve le palindrome 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544 issu de 10022000904998799523 en environ 10.3 min à l'aide de 255 additions sur mon Commodore C128D.
Joli mais Il y a trop de calculs et d'affectations à des variables => ça coûte beaucoup de temps CPU.

Par exemple pour 140669390 qui nous amène à 98 itérations : mon programme s'exécute en 1'49"5 alors que le tiens (adapté pour le casio Z-1 GR) arrive à 2'14".
J'avoue quand même être surpris de ce résultat car tu arrives quand même à une belle optimisation où tu fais les deux opérations durant la même boucle.
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: Misez p'tit Optimisez n°57 : palindromes

Message par gege »

caloubugs a écrit :Mais ne pas trouver en 100 itérations ne veut pas dire qu'il n'y en a pas un plus loin, ça ne prouve rien... :?

Par contre 100 itérations en 69 secondes, pas mal comparé à 91 secondes pour le Basic de la casio Z-1 GR (mais je pense que ça devrait tourner autour de 50 en C, je vais voir pour faire le prog, quoique me prendre la tête avec les malloc, ça m'enchante moyen).
En fait faire 50 millions d'itérations ne prouve rien non plus.
Je me doutais que l'existence de ces nombres n'était pas démontrée.
En 69 secondes la Casio teste tous les nombres de 1 à 196.
Bonne machine (en OS 1.0 - le 2.0 est deux fois plus lent ;-) )
G.E.
caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 434
Enregistré le : 05 juin 2014 22:23
Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau

Re: Misez p'tit Optimisez n°57 : palindromes

Message par caloubugs »

gege a écrit :
caloubugs a écrit :Mais ne pas trouver en 100 itérations ne veut pas dire qu'il n'y en a pas un plus loin, ça ne prouve rien... :? .
En fait faire 50 millions d'itérations ne prouve rien non plus.
Je n'ai pas dis le contraire : que ce soit en 10 ou 10 milliards : ne pas trouver n'est pas une preuve.
Je me suis mal exprimé : je pense que se limiter à 100 était peut-être un peu juste intuitivement (sauf si on regarde les chiffres en amont). En même temps, l'objectif de ce MPO n'est pas sur ce point.

Il ressemble à quoi le code sur ta bécane ?
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: Misez p'tit Optimisez n°57 : palindromes

Message par gege »

Bonjour,
Ca ressemble à ça (j'ai comprimé les lignes) :

Code : Tout sélectionner

+++Prgm LYR+++
?->N
Lbl A:N->M:1->C:Prog "LYRθ"
Lbl B:M+R->M:1e9<M=>Goto D
Prog "LYRθ":R=M=>Goto C
C+1->C:100>C=>Goto B
"SOLUTION":N:Stop
Lbl C:N+1->N:Goto A
Lbl D:ClrGraph:Text 10,10,N:Text 10,30,C
8->K:{Frac (M/10^K)*10^K,Int (M/10^K)}->List 1
Prog "LYRθθ":0->R:For 1->M To Dim List 1
List 1[M]+R->R:Frac (R/10^K)*10^K->List 1[M]:Int (R/10^K)->R
Next
0≠R=>Augment(List 1,{R})->List 1
Prog "LYRθθ":Abs (List 1-List 2)->List 3:0=Max(List 3)=>Goto C
C+1->C:100>C=>Goto E
"SOLUTION":N

+++Prgm LYRθ+++
0->R:M->O:While 0≠O:10Frac (.1O)->Q:10R+Q->R:WhileEnd

+++Prgm LYRθθ+++
0List 1->List 2:Dim List 1->M:Int (log List 1[M])+1-K+KM->M
For 1->O To M
Int ((O-1)/K)->Q:1+Q->P:O-KQ->Q
Int (10Frac (List 1[P]/10^Q))->R
Int ((M-O)/K)->Q:1+Q->P:M-O-KQ->Q
List 2[P]+R10^Q->List 2[P]
Next
Le symbole "10^" est l'inverse du log décimal, "->" l'affectation.
On peut virer les affichages au Label D. Je sais qu'on devrait ne pas avoir besoin de List 3, mais c'est une limitation du Basic Casio.

Bon, ce n'est pas le plus beau code de la planète et l'écriture Casio est parfois pénible, mais on s'habitue...
L'astuce du programme est de n'utiliser la multiprécision que si nécessaire.
Je note que sans Goto le code ne pourrait absolument pas être aussi élégant... :wink:

Il y a un input au début du programme pour démarrer ailleurs qu'à 1.
Si on tape 1, ça affiche "SOLUTION 196" en 69 secondes.
G.E.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°57 : palindromes

Message par C.Ret »

caloubugs a écrit : => ça coûte beaucoup de temps CPU.
Ca c'est vrai. En plus sur le Commodore, un temps non négligeable est perdu si les variables alphanumériques ne sont pas à la fin de la plage mémoire. Pour cela, il faut faire attention à les définir dans le bon ordre.

Dans notre cas, N$ ne varie pas tout au long du programme, il faut la définir en premier, suivi de A$ qui ne "croît" qu'une fois à chaque boucle et enfin S$ qui croît moultes fois dans la boucle FOR/TO/NEXT

Voici donc une version avec laquelle je gagne pas mal de temps sur mon Commodore 8bits de MCMDXXXVII:

Code : Tout sélectionner

 5 A%=0: B%=0: C%=0: L%=0: N%-1: P%=0: I=0                  : REM ******* Initialisation des variables (en début de plage mémoire)  
10 INPUT "N=";N$: A$=N$: S$=N$: L%=LEN(N$)                  : REM ******* Initialisation des chaines de caractère en fin de plage mémoire  
15 DO                                                       : REM ******* Boucle principale
20 :  N%=N%+1: A$=S$: C%=0: S$="": P%=N%
25 :  FOR I=1 TO L%                                         : REM    **** Boucle Sommation/Detection Palindrome
30 :  :  A%=VAL(MID$(A$,I,1)): B%=VAL(MID$(A$,1+L%-I,1))
35 :  :  S%=C%+A%+B%: C%=S%/10: S$=CHR$(48+S%-10*C%)+S$     : REM C%=0 ou 1 si retenue
40 :  :  P%=P% AND (A%=B%)                                  : REM P%=0 si A$ n'est pas palidromique  
45 :  NEXT I
50 :  IF C% THEN S$="1"+S$: L%=L%+1
55 LOOP UNTIL P%
60 PRINT "Initial   :";N$                                   : REM    * * * Presentation resultat
65 PRINT "Iterations:";N%
70 PRINT "Palindrome:";A$
75 END
Je n'ai pas diminuer le nombre de variables, mais surtout le nombre de tests !

J'obtiens le palindrome de 10022000904998799523 en maintenant 9.7 minutes
Celui de 140669390 en 1.6 min

Mais en 'compressant' les p-codes:

Code : Tout sélectionner

1 a%=0:b%=0:c%=0:l%=0:n%-1:p%=0:i=0:input"N=";n$:a$=n$:s$=n$:l%=len(n$):do:n%=n%+1:a$=s$:s$="":p%=n%:fori=1tol%:a%=val(mid$(a$,i,1))
2 b%=val(mid$(a$,1+l%-i,1)):s%=a%+b%+c%:c%=s%/10:s$=chr$(48+s%-10*c%)+s$:p%=p%aand(a%=b%):next:ifc%thens$="1"+s$:l%=l%+1:c%=0
3 loopuntilp%:print"Initial   :";n$:print"Itérations:";n%:print"Palindrome:";A$:end
Mais c'est bien moins lisible !!

Une version pour Hp-41C qui se limite au 10 chiffres de la machine.
Sur une 41C, je ne sais pas comment manipuler caractères par caractères l'affichage alpha.

Code : Tout sélectionner

                      t:      z:      y:      x:      L:                                                                          
                                                                                                                                  
001 LBL "MPO57                             abcde           /abcde/ est le nombre inital (on n'est pas limité à 5 chiffres)
002 0                              abcde       0               Initialise le compteur à t=0
003 X<> Y                              0   abcde
004*LBL 00                             t   abcde           *** Boucle Principale Inversion/Sommation
005 ENTER^                     t   abcde   abcde               Formatage du nombre
006 LOG                        t   abcde  n.nnnn
007 INT                        t   abcde       n
008 ALOG                       t   abcde    10^n
009 /                                  t  a.bcde
010 0                          t  a.bcde       0               Initialisation de l'inversion
011 RCL Y              t  a.bcde       0  a.bcde               x: contient les chiffres à ajouter
012*LBL 01             t  a.bcde     .ba    c.de           *** Boucle Secondaire: inversion du nombre
013 INT                t  a.bcde     .ba       c    c.de
014 ST+ Y              t  a.bcde    c.ba       c    c.de
015 X<> L              t  a.bcde    c.ba    c.de       c
016 FRC                t  a.bcde    c.ba     .de    c.de
017 R^            a.bcde    c.ba     .de       t    c.de
018 X<> L         a.bcde    c.ba     .de    c.de       t       le compteur est sauvegadé dans le registre L:
019 Clx           a.bcde    c.ba     .de       0       t
020 10            a.bcde    c.ba     .de      10       t
021 ST/ Z         a.bcde    .cba     .de      10       t
022 ST* Y         a.bcde    .cba     d.e      10       t
023 X<> L         a.bcde    .cba     d.e       t      10       la valeur 10 du registre L: sera utilisée plus loin
024 RDN                t  a.bcde    .cba     d.e      10
025 x>0 ?                                                   On boucle tant qu'il reste des chiffres à ajouter pour l'inversion
026 GTO 01             t  a.bcde  .edcba       0      10
027 X<> L              t  a.bcde  .edcba      10       0
028 *                          t  a.bcde  e.dcba      10
029 X=Y ?
030 GTO 02                                                  Sortie de la boucle principale si le nombre est un palindrome
031 +                                  t  s.ssss           *** Sommation du nombre et de son inversion
032 ISG Y                            t+1  s.ssss               incrémente le compteur
033 AVIEW
034 GTO 00
035*LBL 02                     t  a.bcba  a.bcba      10   *** Fin du programme
036 RDN                                t  a.bcba               la touche x<>y permet d'afficher alternativemetn le palindrome
037 .END.                                                      final et le compteur
                                       t       p

Soit en version 'condensée' :

Code : Tout sélectionner

001*LBL "MPO57
      0 x<>y 
004*LBL 00
      ENTER^  LOG  INT  10^x  /  0  RCL Y
012*LBL 01
      INT ST+ Y  X<> L  FRC  R^  X<> L  Clx  10
      ST/ Z  ST* Y  X<> L  RDN  x>0 ?  GTO 01
      X<> L  *  X=Y ?  GTO 02
      +  ISG Y  AVIEW  
      GTO 00

035*LBL 02
      RDN
037 .END.
Modifié en dernier par C.Ret le 23 juin 2014 08:21, modifié 2 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
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: Misez p'tit Optimisez n°57 : palindromes

Message par gege »

Bon,
Je vais bricoler mon programme pour qu'il accepte une entrée en multiprécision.
A bientôt !
G.E.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez n°57 : palindromes

Message par Gilles59 »

oups...doublon ! (comment on supprime ?)
Modifié en dernier par Gilles59 le 24 oct. 2014 22:36, modifié 1 fois.
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
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez n°57 : palindromes

Message par Gilles59 »

Une version HP50G manquait ici (c'est l'avantage d'être loin de Silicium pendant un bail, on a des choses à rattraper ensuite :D ). La 50G s'adapte bien à ce genre de chose et les entiers 'infinis' évitent toute bidouille multiprécision.

Pal :

Code : Tout sélectionner

« 0 -> Nb
 «
  DUPDUP 1. DISP
  DO
   DUP ->STR SREV STR-> + 
  UNTIL DUP ->STR DUP SREV == 'Nb' INCR 999 > OR END
  DROP 
  IF 'Nb>999' THEN ">999" ELSE Nb END
  2 ->LIST 
 »
»
148,5 Octets (remplacer -> par la fléche sur la calc ou l'émulateur)

Example
265 Pal retourne {265, 5}
196 Pal retourne {196, ">999"}
140669390 Pal retourne {140669390 , 98} en 5,7 sec.
10022000904998799523 Pal retourne 255 en 15 sec

Code : Tout sélectionner

{ 1000000038990407538, 9000000000255353839, 1000000005577676468, 1060000000523124995, 3000000022999288679, 1000000079994144385, 1003062289999939142, 1186060307891929990, 10022000904998799523, 10000000039395795416, 10200000000065287900 }
1 'Pal' DOSUBS 

retourne

{ { 1000000038990407538 217 } { 9000000000255353839 224 } { 1000000005577676468 225 } { 1060000000523124995 226 } { 3000000022999288679 258 } { 1000000079994144385 259 } { 1003062289999939142 260 } { 1186060307891929990 261 } { 10022000904998799523 255 } { 10000000039395795416 256 } { 10200000000065287900 257 } }
[/size]
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
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez n°57 : palindromes

Message par Gilles59 »

Voilà d'après ma HP50G la liste des 249 nombres suspectés d'être de Lychrel et inférieur à 10.000 :

Code : Tout sélectionner

{ 196 295 394 493 592 689 691 788 790 879 887 978 986 1495 1497 1585 1587 1675 1677 1765 1767 1855 1857 1945 1947 1997 2494 2496 2584 2586 2674 2676 2764 2766 2854 2856 2944 2946 2996 3493 3495 3583 3585 3673 3675 3763 3765 3853 3855 3943 3945 3995 4079 4169 4259 4349 4439 4492 4494 4529 4582 4584 4619 4672 4674 4709 4762 4764 4799 4852 4854 4889 4942 4944 4979 4994 5078 5168 5258 5348 5438 5491 5493 5528 5581 5583 5618 5671 5673 5708 5761 5763 5798 5851 5853 5888 5941 5943 5978 5993 6077 6167 6257 6347 6437 6490 6492 6527 6580 6582 6617 6670 6672 6707 6760 6762 6797 6850 6852 6887 6940 6942 6977 6992 7059 7076 7149 7166 7239 7256 7329 7346 7419 7436 7491 7509 7526 7581 7599 7616 7671 7689 7706 7761 7779 7796 7851 7869 7886 7941 7959 7976 7991 8058 8075 8079 8089 8148 8165 8169 8179 8238 8255 8259 8269 8328 8345 8349 8359 8418 8435 8439 8449 8490 8508 8525 8529 8539 8580 8598 8615 8619 8629 8670 8688 8705 8709 8719 8760 8778 8795 8799 8809 8850 8868 8885 8889 8899 8940 8958 8975 8979 8989 8990 9057 9074 9078 9088 9147 9164 9168 9178 9237 9254 9258 9268 9327 9344 9348 9358 9417 9434 9438 9448 9507 9524 9528 9538 9597 9614 9618 9628 9687 9704 9708 9718 9777 9794 9798 9808 9867 9884 9888 9898 9957 9974 9978 9988 9999 }

Code : Tout sélectionner

Pal :
« 0 -> Nb
 «
  DUPDUP 1 DISP
  DO
   DUP ->STR SREV STR-> + 
  UNTIL  DUP ->STR DUP SREV == 
         'Nb' INCR 262 > 
         OR 
  END
  DROP 
  IF 'Nb<262' THEN DROP END
 »
»

«
 CLEAR
 1 10000 FOR n
  n Pal
 NEXT
 DEPTH ->LIST
»
[/size]

On note que l'écart entre 2 nombres de Lychrel successifs semble avoir une certaine logique

DUP TAIL SWAP 1 248 SUB -

Code : Tout sélectionner

{ 99 99 99 99 97 2 97 2 89 8 91 8 509 2 88 2 88 2 88 2 88 2 88 2 50 497 2 88 2 88 2 88 2 88 2 88 2 50 497 2 88 2 88 2 88 2 88 2 88 2 50 84 90 90 90 90 53 2 35 53 2 35 53 2 35 53 2 35 53 2 35 53 2 35 15 84 90 90 90 90 53 2 35 53 2 35 53 2 35 53 2 35 53 2 35 53 2 35 15 84 90 90 90 90 53 2 35 53 2 35 53 2 35 53 2 35 53 2 35 53 2 35 15 67 17 73 17 73 17 73 17 73 17 55 18 17 55 18 17 55 18 17 55 18 17 55 18 17 55 18 17 15 67 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 41 18 17 4 10 41 18 17 4 10 41 18 17 4 10 41 18 17 4 10 41 18 17 4 10 41 18 17 4 10 1 67 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 11 }
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
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: Misez p'tit Optimisez n°57 : palindromes

Message par gege »

Bonjour,
Ta dernière remarque est à la fois particulièrement judicieuse, intriguante, et difficile à expliquer !!!
(gratte tête)
Week-end foutu ! ;-)
G.E.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez n°57 : palindromes

Message par Gilles59 »

Les "deltas" jusque 20 000. Les séquences de répétitions sont moins nettes....

Code : Tout sélectionner

{ 99 99 99 99 97 2 97 2 89 8 91 8 509 2 88 2 88 2 88 2 88 2 88 2 50 497 2 88 2 88 2 88 2 88 2 88 2 50 497 2 88 2 88 2 88 2 88 2 88 2 50 84 90 90 90 90 53 2 35 53 2 35 53 2 35 53 2 35 53 2 35 53 2 35 15 84 90 90 90 90 53 2 35 53 2 35 53 2 35 53 2 35 53 2 35 53 2 35 15 84 90 90 90 90 53 2 35 53 2 35 53 2 35 53 2 35 53 2 35 53 2 35 15 67 17 73 17 73 17 73 17 73 17 55 18 17 55 18 17 55 18 17 55 18 17 55 18 17 55 18 17 15 67 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 41 18 17 4 10 41 18 17 4 10 41 18 17 4 10 41 18 17 4 10 41 18 17 4 10 41 18 17 4 10 1 67 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 59 17 4 10 11 539 15 10 14 6 2 53 15 10 5 29 18 13 7 11 2 35 2 2 1 33 22 34 6 50 30 2 4 8 6 2 543 15 10 14 6 2 53 15 10 5 29 18 13 7 11 2 35 2 2 1 33 22 34 6 25 25 30 2 4 8 6 2 122 200 96 125 15 10 14 6 2 53 15 10 5 29 31 7 11 2 35 2 2 1 25 4 4 22 34 6 25 10 15 30 2 4 8 6 2 122 10 100 90 96 9 1 4 111 15 10 14 6 2 41 1 11 15 10 5 29 27 11 11 2 35 2 2 1 25 4 26 34 6 25 10 15 30 2 4 8 6 2 42 80 10 9 1 90 10 80 20 76 9 1 4 10 116 10 14 6 2 41 1 26 10 5 29 27 14 8 2 35 2 2 1 25 4 26 34 6 25 10 19 26 2 4 8 6 2 42 8 72 10 9 1 90 10 80 20 10 66 9 1 4 10 6 110 10 14 6 2 41 1 20 6 10 5 29 27 14 45 2 2 1 25 4 60 6 25 10 19 26 2 4 8 6 2 42 8 72 10 9 1 90 10 80 20 10 66 9 1 4 10 6 120 14 6 2 41 1 20 10 6 5 29 27 14 45 2 2 1 25 4 40 20 6 25 10 19 26 2 4 8 6 2 42 8 24 48 10 9 1 90 10 23 57 20 10 15 5 46 9 1 4 10 6 125 9 6 2 41 1 20 10 10 30 27 14 29 16 2 2 1 25 4 40 20 6 25 10 19 30 10 6 2 42 8 24 48 10 9 1 39 1 50 10 23 14 43 20 10 15 5 46 9 1 4 10 6 125 9 6 2 41 1 20 10 10 9 1 1 19 27 14 29 10 6 2 2 1 25 4 40 20 1 5 25 10 19 30 10 6 2 42 8 24 48 10 9 1 39 1 11 39 10 23 14 43 20 10 15 5 46 9 1 4 10 6 44 81 9 8 41 1 20 10 10 9 1 1 3 16 27 14 29 10 36 4 40 20 1 4 1 4 21 10 19 30 10 6 44 8 24 29 }
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
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5631
Enregistré le : 26 mars 2009 13:07
Localisation : Ile de France
Contact :

Re: Misez p'tit Optimisez n°57 : palindromes

Message par ledudu »

Machine : CASIO Pro FX-1
Langage : Fortran Casio

Je me contenterai du programme de détermination du palindrome (quand il existe) et du nombre d'itérations :

Pour calculer le reverse d'un nombre A=abcde, je calcule itérativement, en ST#2, B = A + 10^11 - 10^11 = abcd0 (par arrondi de la machine).
A-B me donne le chiffre des unités que j'utilise pour construire le palindrome.

Code : Tout sélectionner

ST#0 : ENT 0 : 9 = K11 10x : 7 = K0 :                                            'Pas 18 - Initialisations globales
ST#1 : 1=0 : 3 = 8 :                                                             'Pas 29 - Initialisations à chaque itération
ST#2 : 2 = 1 + 9 - 9 :3 = 3 x K10 + 1 - 2 : 1 = 2 / K10 : IF 1 = 8 : 3 : 3 : 2 : 'Pas 71 - Calcul itératif du reverse dans le registre 3
ST#3 : IF 0 = 3 : 5 : 4 : 5 :                                                    'Pas 85 - Test de palindromie
ST#4 : ANS 0 : 7 : GOTO 0 :                                                      'Pas 96 - Test VRAI : Affichage palindrome et nombre d'itérations
ST#5 : 0 = 3 + 0 : 7 = 7 + K1 :GOTO 1 :                                          'Pas 115 - Test FAUX : Poursuite de la recherche du palindrome
D'autres programmes pour PRO Fx-1.
Avatar du membre
Thierry Loiseau
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 823
Enregistré le : 10 avr. 2004 22:23
Localisation : Terrasson (Périgord)
Contact :

Re: Misez p'tit Optimisez n°57 : palindromes

Message par Thierry Loiseau »

Version Casio P-207XF

Code : Tout sélectionner

10 INP "ERBMON ",A:N=0:X=A
20 GSB 40:PRT A;"+";R;"=";B:A=B:N=N+1:GOTO 20
30 PRT "NB FOIS:";N;" POUR";X:END
40 C=INT LOG A+1:B=A:R=0
50 FOR I=1 TO C:
60 B=B/10:D=FRAC(B)*10
70 B=INT(B):
80 R=R*10+D:
90 NEXT I
100 IF N≠0;IF A=R THEN 30
110 B=A+R
120 RET
Pour renverser le nombre, je fais cela :
  1. déterminer le nombre de chiffre : n = INT ( LOG(nombre) ) + 1
  2. n_inverse = 0
  3. Itération : de 1 à n
  4. récupérer l'unité du nombre : unite = FRAC(nombre/10)*10
  5. n_inverse = n_inverse x 10 + unite
  6. nombre = INT ( nombre/10 )
  7. fin itération
Exemple :

143

14.3 :arrow: 3
1.4 :arrow: 30 + 4 :arrow: 34
1 :arrow: 340 + 1 :arrow: 341

10

1.0 :arrow: 0
1 :arrow: 0 + 1 :arrow: 1

Code : Tout sélectionner

637
637 + 736 = 1373
1373 + 3731 = 5104
5104 + 4015 = 9119
NB FOIS: 3 POUR 637
Renverser le nombre avec HP-41C (toujours pareil, il faudra que j'apprenne à n'utiliser que les piles :roll:

Code : Tout sélectionner

01 LBL "PL"
02 STO 03
03 STO 00
04 LOG
05 INT
06 1
07 +
08 STO 01
09 0
10 STO 0
11 LBL 01
12 RCL 02
13 10
14 *
15 STO 02
16 RCL 00
17 10
18 /
19 STO 00
20 FRC
21 10
22 *
23 ST+ 02
24 RCL 00
25 INT
26 STO 00
27 1
28 ST- 01
29 RCL 01
30 x≠0
31 GTO 01
32 LBL 02
33 RLC 03
34 RCL 02
35 +
36 STO 04
37 CLA
38 ARCL 03
39 "[+"
40 ARCL 02
41 "[="
42 ARCL 04
43 AVIEW
44 END

1456
1456+6541=7997
Modifié en dernier par Thierry Loiseau le 19 mars 2017 14:30, modifié 1 fois.
HP-41C, HP-12C ; Casio FX-702P, FX-850P, FX-602P, FX-3900P, FX-4000P, FX-180Pv ;
TI 57 avec adaptation d'une pile LR9 et une originale, accus HS; Newton MP 120FR, MP 2100US, MP 130US...
[***Apple //e, 7100, 8500, Atari Mega ST1 ***], PB-540c, PISMO, [***CPC-6128, MO5***]... et bien d'autres trucs

[--- plus ---]
http://astrophoto.free.fr/
Avatar du membre
Thierry Loiseau
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 823
Enregistré le : 10 avr. 2004 22:23
Localisation : Terrasson (Périgord)
Contact :

Re: Misez p'tit Optimisez n°57 : palindromes

Message par Thierry Loiseau »

Image

195 :arrow: 9339 en 24 secondes seulement... :mrgreen:

Par contre pour 196...

Image

... il est débordé au delà de la 18ème itérations... :oops:

2017 + 7102 = 9119 :)
HP-41C, HP-12C ; Casio FX-702P, FX-850P, FX-602P, FX-3900P, FX-4000P, FX-180Pv ;
TI 57 avec adaptation d'une pile LR9 et une originale, accus HS; Newton MP 120FR, MP 2100US, MP 130US...
[***Apple //e, 7100, 8500, Atari Mega ST1 ***], PB-540c, PISMO, [***CPC-6128, MO5***]... et bien d'autres trucs

[--- plus ---]
http://astrophoto.free.fr/
Avatar du membre
Thierry Loiseau
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 823
Enregistré le : 10 avr. 2004 22:23
Localisation : Terrasson (Périgord)
Contact :

Re: Misez p'tit Optimisez n°57 : palindromes

Message par Thierry Loiseau »

TI-57 (SI ! SI ! ) :mrgreen:

Code : Tout sélectionner

00 32   1   STO 1	Nombre à inverser
01 32   3   STO 3	dupliqué non traité
02 00       0
03 32   7   STO 7	Nombre inversé/test
04 33   1   RCL 1
05 18       LOG
06 49       INT
07 75       +
08 01       1
09 85       =
10 32       STO 0	Nombre de chiffre
11 86   0   LBL 0
12 33   7   RCL 7
13 55       *
14 01       1
15 00       0
16 85       =
17 32   7   STO 7
18 33   1   RCL 1
19 45       ÷
20 01       1
21 00       0
22 85       =
23 32   1   STO 1
24-49       FRAC
25 55       *
26 01       1
27 00       0
28 85       =
29 34   7   SUM 7
30 33   1   RCL 1
31 49       INT
32 85       =
33 32   1   STO 1
34 56       DSZ
35 51   0   GTO 0
36 33   3   RCL 3
37 75       +
38 33   7   RCL 7
39 85       =
40 32   4   STO 4
41 33   4   RCL 4
42 85       =
43 81       R/S
Ça marche !
On tape le nombre puis [RST] [R/S]

Exemple :
195 [RST] [R/S]
786.
[RST] [R/S]
1473
[RST] [R/S]
5214
[RST] [R/S]
9339

mais à vous de vous dire : "Ah, c'est fait !'
Je pensais faire un 1 STO 6 pour indiquer que l'on débutait le test et dès le premier, mettre à 0 STO 6 et si le nombre à inverser = nombre inverser et que STO 6 = 0 alors on bloque sur STO 3... Il faudrait optimiser le code franchement pour gagner des pas de programme... parce que là, avec 6 restant :(
Modifié en dernier par Thierry Loiseau le 19 mars 2017 22:22, modifié 2 fois.
HP-41C, HP-12C ; Casio FX-702P, FX-850P, FX-602P, FX-3900P, FX-4000P, FX-180Pv ;
TI 57 avec adaptation d'une pile LR9 et une originale, accus HS; Newton MP 120FR, MP 2100US, MP 130US...
[***Apple //e, 7100, 8500, Atari Mega ST1 ***], PB-540c, PISMO, [***CPC-6128, MO5***]... et bien d'autres trucs

[--- plus ---]
http://astrophoto.free.fr/
Répondre

Retourner vers « Tous les Pockets »