Misez p'tit, optimisez n°61: Produit de chiffres en séquence
Modérateur : Politburo
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2930
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Misez p'tit, optimisez n°61: Produit de chiffres en séquence
Voici un petit MPO en attendant la prochaine gazette.
Considérons la suite Un+1 = Un + (produit des chiffres non nuls de Un)
Si on commençe avec U1=1 on obtient : 1, 2, 4, 8, 16, 22, 26, 38, 62, 74 ….
Si on commence avec U1=3 on obtient : 3, 6, 12, 14, 18, 26, 38, 62, 74 …
On s’apercoit alors qu'à partir de 26 les deux suites vont être identiques. On peut définir LU(n), la Longueur de U pour U1=n, par le nombre de termes que l’on ne retrouve pas dans la suite commençant par 1. On a donc LU(3)=5.
Touver la valeur de n <=1000 pour laquelle LU(n) est maximale. On optimisera en particulier la rapidité d’obtention de la solution.
( Sommaire des MPO )
Considérons la suite Un+1 = Un + (produit des chiffres non nuls de Un)
Si on commençe avec U1=1 on obtient : 1, 2, 4, 8, 16, 22, 26, 38, 62, 74 ….
Si on commence avec U1=3 on obtient : 3, 6, 12, 14, 18, 26, 38, 62, 74 …
On s’apercoit alors qu'à partir de 26 les deux suites vont être identiques. On peut définir LU(n), la Longueur de U pour U1=n, par le nombre de termes que l’on ne retrouve pas dans la suite commençant par 1. On a donc LU(3)=5.
Touver la valeur de n <=1000 pour laquelle LU(n) est maximale. On optimisera en particulier la rapidité d’obtention de la solution.
( Sommaire des MPO )
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit, optimisez n°61: Produit de chiffres en séqu
Voici, après une mûre réflexion dans les bouchons sur l'autoroute, mon algorithme pour HP-28S.
Il faut dans un premier temps créer la fonction NxtU qui permet de passer de u(n) à u(n+1).
Par exemple, en plaçant 607 au niveau 1: dela pile, la fonction NxtU renvoie 649.
Ensuite, LU(n) peut être calculé à partir du programme LUNE :
L'idée dans la LUNE est de calculer conjointement les suites issues de 1 et de n de telle sorte que l'on sache quel est le terme de la suite issue de 1 immédiatement au-dessus du terme actuel de la suite issue de n. La séquence ROT 1 + ROT ROT permet de compter le nombre de terme de la suite issuée de n.
P.S.: Bien évidemment, il y a moyen de faire plus court et d'optimiser. (Par exemple en inversant l'ordre des suites dans la pile). Je laisse aux lecteurs pratiquant le RPL le soin de découvrir l'astuce.
Par contre, le calcul n'est pas des plus rapide (il faut calculer conjointement deux suites. Peut-être une astuce permet d'accélérer les choses ??
Il faut dans un premier temps créer la fonction NxtU qui permet de passer de u(n) à u(n+1).
Par exemple, en plaçant 607 au niveau 1: dela pile, la fonction NxtU renvoie 649.
Ensuite, LU(n) peut être calculé à partir du programme LUNE :
Code : Tout sélectionner
NxtU:
« 1 OVER @@ Fait une copie de n et prépare le produit de ses chiffres
DO
10 /
LAST MOD @@ Extrait le dernier chiffre de n
1 MAX @@ Evite de prendre en compte les éventuels zéros
ROT * SWAP IP @@ Effectue le produit des chiffres et arrondi n
UNTIL DUP END @@ Boucle jusqu'à épuisement de n
DROP + » @@ Ajoute n et le produit de ses chiffres
LUNE:
« 0 1 ROT @@ 0 est le compteur et 1 l'initial de la série issue de 1
WHILE
WHILE DUP2 < REPEAT SWAP NxtU SWAP END @@ Calcule les éventuels termes de la série issue de 1
DUP2 >
REPEAT @@ Si nécessaire le terme suivant de la série issue de n
NxtU ROT 1 + ROT ROT @@ tout en incrémentant le compteur
END
DROP2 » @@ Efface les termes égaux en laissant le compteur LU(n)
P.S.: Bien évidemment, il y a moyen de faire plus court et d'optimiser. (Par exemple en inversant l'ordre des suites dans la pile). Je laisse aux lecteurs pratiquant le RPL le soin de découvrir l'astuce.
Par contre, le calcul n'est pas des plus rapide (il faut calculer conjointement deux suites. Peut-être une astuce permet d'accélérer 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.
Re: Misez p'tit, optimisez n°61: Produit de chiffres en séqu
Je dois être bouché, mais je ne vois pas la forme de ta suite, je n'arrive pas à savoir ce que tu veux calculer .
- badaze
- Fonctionne à 14400 bauds
- Messages : 8402
- Enregistré le : 12 févr. 2007 18:36
- Localisation : Pas très loin de Lyon
- Contact :
Re: Misez p'tit, optimisez n°61: Produit de chiffres en séqu
+1doum-doum a écrit :Je dois être bouché, mais je ne vois pas la forme de ta suite, je n'arrive pas à savoir ce que tu veux calculer .
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.
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.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit, optimisez n°61: Produit de chiffres en séqu
Eh! Oui pardon , j'ai mal expliqué la suite.badaze &doum-doum a écrit :Je dois être bouché, mais je ne vois pas la forme de ta suite, je n'arrive pas à savoir ce que tu veux calculer .
La fonction NxtU calcule l'élement U(n+1) à partir de U(n).
Ainsi, par pressions sucessives sur la touche [NxtU] j'obtiens les termes de la suite.
Par exemple: 1 [NxtU] affiche 2 puis une pression sur [NxtU] affiche 4 et ainsi de suite ...
La fonction [LUNE] permet d'avoir directement LU(n).
par exemple 3 [LUNE] affiche 5 car 3 -> 6 -> 12 -> 14 -> 18 -> 26 qui est un des termes de la suite issue de 1.
Ce qui fait donc LU(3)=5 termes avant de rejoindre la suite issue de 1.
Désolé, la journée fut longue et les bouchons énervants !!
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.
- babaorhum
- Fonctionne à 1200 bauds
- Messages : 454
- Enregistré le : 13 janv. 2013 19:44
- Localisation : Marseille-est
Re: Misez p'tit, optimisez n°61: Produit de chiffres en séqu
Belle proposition C.Ret sur 28s, j'aime bien ta LUNE ! ... de mon côté je suis parti dans les Listes (sur 28s aussi) pour aller un peu plus vite ... mais côté octets c'est pas économe (33 termes dans la suite U1 jusqu'à 1000) ... mais j'ai peut être moins de bouchons, c'est une excuse qui convient ? ...C.Ret a écrit : Désolé, la journée fut longue et les bouchons énervants !!
BaBaoRhum
HP J728,200LX,1000CX,75C,71B,48GX,42s,41CX,32E,32Sii,28S,22s,21,16C,11C
Sharp PC- E500,1600,1500,1350,1261,1245
Casio FX-502P,602p,850P,3900P,4000P
TI-74,92,95 ; Canon X-07 ; TANDY EC-4026 ; Wp34S
HP J728,200LX,1000CX,75C,71B,48GX,42s,41CX,32E,32Sii,28S,22s,21,16C,11C
Sharp PC- E500,1600,1500,1350,1261,1245
Casio FX-502P,602p,850P,3900P,4000P
TI-74,92,95 ; Canon X-07 ; TANDY EC-4026 ; Wp34S
- gege
- Fonctionne à 14400 bauds
- Messages : 7147
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Misez p'tit, optimisez n°61: Produit de chiffres en séqu
Bonjour,
Marrant, je ne vois pas pourquoi il n'y aurait pas de n pour lequel LU(n) est infini, en fait même il suffit de prendre un des U(n) et changer l'ordre de ses chiffres, non (exemple 38 -> 83) ?
Vite une machine !!!
G.E.
Marrant, je ne vois pas pourquoi il n'y aurait pas de n pour lequel LU(n) est infini, en fait même il suffit de prendre un des U(n) et changer l'ordre de ses chiffres, non (exemple 38 -> 83) ?
Vite une machine !!!
G.E.
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2930
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit, optimisez n°61: Produit de chiffres en séqu
Très bon début ! On ne dira jamais assez l'importance des bouchons dans l'évolution de la science moderneC.Ret a écrit :Voici, après une mûre réflexion dans les bouchons sur l'autoroute, mon algorithme pour HP-28S.
... et pourtant... la suite LU(n) est surprenante, il semblerait qu'elle soit liée aux fractales....gege a écrit : Marrant, je ne vois pas pourquoi il n'y aurait pas de n pour lequel LU(n) est infini,
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit, optimisez n°61: Produit de chiffres en séqu
Je suis actuellemet moi aussi sur des listes pré-calculée en BASIC dans des tableaux de 1000 entiers.babaorhum a écrit : [ ...] de mon côté je suis parti dans les Listes (sur 28s aussi) pour aller un peu plus vite ...[...]
En attendant que cela donne quelque chose de signifiatif, voici une seconde version de LUNE qui économise quelques octets en intervertisssant l'ordre des suites dans la pile. c'est strictement le même algorithme.
Code : Tout sélectionner
LUNE:
« 0 SWAP 1 @@ 0 est le compteur et 1 l'initial de la série issue de 1
WHILE
WHILE DUP2 > REPEAT NxtU END @@ Calcule les éventuels termes de la série issue de 1
DUP2 <
REPEAT @@ Si nécessaire le terme suivant de la série issue de n
ROT 1 + ROT NxtU ROT @@ tout en incrémentant le compteur
END
DROP2 » @@ Efface les termes égaux en laissant le compteur LU(n)
Ce qui me laisse supposer qu'il doit y avoir un moyen de déterminer l'intiale n qui produit le plus grand LU(n) sans avoir à faire des milles et des cents de calculs ou manipuler des listes ou des tableaux kilométriques.
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.
- dprtl
- Fonctionne à 1200 bauds
- Messages : 463
- Enregistré le : 27 janv. 2013 00:26
- Localisation : Strasbourg
- Contact :
Re: Misez p'tit, optimisez n°61: Produit de chiffres en séqu
Entre deux tentatives d'optimisation du "Compte est bon" (défi Gazette 4, affreusement difficile), j'ai testé ma première proposition naïve à ce MPO sur PB-1000 :
Pour fonctionner, ce programme aura besoin de l'extension mémoire RP-32, et de la partition mémoire suivante (par exemple) :
Un résultat sera affiché... au bout d'un certain temps... long long long :
... pour arriver jusqu'à 1000, prévoir des piles neuves.
Edit : un peu moins de 35h de calcul !
Code : Tout sélectionner
10 CLEAR:DIM A(1000):M=1000
20 U=1:FOR I=0 TO M-1:PRINT U;:A(I)=U:GOSUB 110:NEXT
30 X=0:FOR K=2 TO M:U=K
40 FOR I=0 TO M-1:L=0
50 IF A(L)<U THEN L=L+1:GOTO 50
60 IF A(L)>U THEN 90
70 IF X<I THEN X=I
80 PRINT "LU(";K;") =";I;" MAX =";X:GOTO 100
90 GOSUB 110:NEXT I
100 NEXT K:END
110 P=1:V$=STR$(U):FOR J=2 TO LEN(V$)
120 C=ASC(MID$(V$,J,1))-48:IF C>0 THEN P=P*C
130 NEXT J:U=U+P:RETURN
Code : Tout sélectionner
CLEAR 8000,0,25000
Code : Tout sélectionner
[...]
LU( 62 ) = 0 MAX = 17
LU( 63 ) = 322 MAX = 322
LU( 64 ) = 3 MAX = 322
[...]
LU( 999 ) = 15 MAX = 322
LU( 1000 ) = 30 MAX = 322
Edit : un peu moins de 35h de calcul !
Modifié en dernier par dprtl le 19 avr. 2015 09:27, modifié 1 fois.
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2930
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit, optimisez n°61: Produit de chiffres en séqu
Pas mal ! Pour aller plus vite essaye d'optimiser le sous-programme en 110.
Sur ma hp Prime j'ai le résultat en 1mn.
Sur ma hp Prime j'ai le résultat en 1mn.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit, optimisez n°61: Produit de chiffres en séqu
Dans le style qui met du temps à fournr un résultat j'ai aussi progressé.
Un peu moins que dans le style qui prend des kilo d'octets pour gagner un peut de temps.
Une fois les programmes NxtU et LUNE saisis, le programe SCRUN scrute les nombres jusqu'à 1000 pour trouver les plus grands LU().
Inconvénient, ce programme recalcule sans cesse la suite issue de 1. Avantage, il est suffisament court pour être présenté dans un MPO.
Un peu moins que dans le style qui prend des kilo d'octets pour gagner un peut de temps.
Une fois les programmes NxtU et LUNE saisis, le programe SCRUN scrute les nombres jusqu'à 1000 pour trouver les plus grands LU().
Code : Tout sélectionner
CRUN: 3: 2: 1: @@ Commentaires:
« 3 5 r lr @@ Initialise record connu
4 1000 FOR u @@ Recherche les autres
u LUNE r lr lu @@ Calcule lu=LU(n)
IF DUP2 <= THEN @@ Si lr<=lu alors échange r et lr avec n et lu
ROT DROP u lr lu u
SWAP ROT u lu lr
END
DROP r' lr' @@ efface lu ou lr
NEXT
R->C » @@ Returne résultat sous forme (r,lr)
Modifié en dernier par C.Ret le 15 avr. 2015 21:18, 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.
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2930
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit, optimisez n°61: Produit de chiffres en séqu
Il doit être possible de faire plus court que la suite LUNE et SCRUN et aussi plus rapideC.ret a écrit :Inconvénient, ce programme recalcle sans cesse la suite issue de 1. Avantage, il est suffisament court pour être présenté dans un MPO.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit, optimisez n°61: Produit de chiffres en séqu
Eh! Oui il doit y avoir un moyen d'aller vers la plus longue suite sans faire tous ces calculs...
Mais laissons le temps à chacun de trouver une voie...
En attendant, un petit graphe pour observer ce qui se passe :
Mais laissons le temps à chacun de trouver une voie...
En attendant, un petit graphe pour observer ce qui se passe :
Code : Tout sélectionner
0.:°1-2-4-8-16-22---26-----38-62-74-----102---104-108-116----122-----126-----------138--162-174-----202-206-218---234-----258---338-
..: | | | | | | / \ | / | \ | / \ | | | / \ | / \ | / \
1.: 13 20 18 32 52 54 66 101 59 68 84 113 120 77 118 132 152 154 166 200 176 178 186 242 266 317
..: ° | / \ | ° | / \ | ° | ° ° / \ | / | \ | | | / \ \ ° / / \ | ° °
2.: 15 9 14 24 36 39 60 100 53 93 115 70 76 109 114 124 88 136 139 160 191 171 156 172 179
..: ° ° / \ | ° ° | | ° ° ° | ° / / \ | / \ ° ° / \ ° ° | ° °
3.: 7 12 17 44 91 46 67 107 112 117 64 80 97 144 151
..: ° / \ ° / \ ° | / / / \ ° ° / \ ° / \ °
4.: 6 11 28 40 34 61 83 106 111 48 55 128 140
..: | | | ° | ° ° / | ° / \ | |
5.: 3 10 19 31 103 110 43 50 119 95
..: ° | ° ° ° / | \ ° / \ ° |
6.: 5 75 92 105 35 42 65
..: ° | | ° | | |
7.: 47 57 25 33 45
..: | ° ° | |
8.: 29 30 41
..: | ° |
9.: 23 27
..: | °
10: 21
..: °
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.
Re: Misez p'tit, optimisez n°61: Produit de chiffres en séqu
HP50G + GoferList Mode exact
[/size]
Même résultats que dprtl mais lent même avec l'émulateur ...
La liste pour la suite Un commençant par 1 est calculée 1 seule fois, sa "profondeur" augmente au fur et à mesure des besoins (mais la totalité de la liste est en mémoire à partir du calcul de la suite commençant par 63)..
Code : Tout sélectionner
« DUP ->STR Chars « "0" ≠ » Filter STR-> Product + » 'Unext' STO @ Calcul de Un+1
«
0 0 -> m Lu
«
{1} @ La liste Un pour 1 est calculée au fur et à mesure des besoins
2 1000 FOR n n 2. DISP
0 SWAP n
WHILE DUP2 POS NOT REPEAT
IF OVER Last OVER < THEN SWAP DUP Last Unext + SWAP ELSE Unext ROT 1 + UNROT END
END
DROP SWAP IF DUP m > THEN 'm' STO n DUP 1. DISP 'Lu' STO ELSE DROP END
NEXT
m Lu
»
»
Même résultats que dprtl mais lent même avec l'émulateur ...
La liste pour la suite Un commençant par 1 est calculée 1 seule fois, sa "profondeur" augmente au fur et à mesure des besoins (mais la totalité de la liste est en mémoire à partir du calcul de la suite commençant par 63)..
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