Misez p'tit, Optimisez - N°16 (Fibonacci)
Modérateur : Politburo
- Hobiecat
- Fonctionne à 9600 bauds
- Messages : 3644
- Enregistré le : 06 sept. 2011 14:57
- Localisation : Normandie
Misez p'tit, Optimisez - N°16 (Fibonacci)
L'exemple de C.Ret sur le fil 39GII m'a rappelé que nous n'avons pas fait de MPO depuis longtemps !
L'objectif de ce MPO : avec comme donnée d'entrée le rang n, calculer le nombre de Fibonacci de rang n, F(n)
Points particuliers :
- le programme devra traiter les cas particuliers F(0)=0 et F(1)=1
- vous calculez avec la méthode qui vous convient : soit en récursif, soit avec le calcul direct (voir la page wikipedia pour ceux qui ont des trous de mémoire)
Comme d'habitude, l'économie de pas de programme est la règle !
L'objectif de ce MPO : avec comme donnée d'entrée le rang n, calculer le nombre de Fibonacci de rang n, F(n)
Points particuliers :
- le programme devra traiter les cas particuliers F(0)=0 et F(1)=1
- vous calculez avec la méthode qui vous convient : soit en récursif, soit avec le calcul direct (voir la page wikipedia pour ceux qui ont des trous de mémoire)
Comme d'habitude, l'économie de pas de programme est la règle !
- pir2
- Fonctionne à 9600 bauds
- Messages : 4647
- Enregistré le : 31 oct. 2006 15:08
- Localisation : 67310 Westhoffen
- Contact :
Re: Misez p'tit, Optimisez - N°16 (Fibonacci)
Tiens, marrant, je me suis fait çà sur ma 15C pour voir si je n'étais pas trop rouillé
(pas optimisé par contre)
Allez, çà va me faire un exercice de lecture des codes programmes de la 15C LE
Edith me dit que c'est draft, pas tout à fait juste, mais c'est un début (pas de traitement de f(0) et f(1), pas sûr que f(2) soit juste etc..)
Edith2 m'a nettoyé tout çà
(pas optimisé par contre)
Allez, çà va me faire un exercice de lecture des codes programmes de la 15C LE
Code : Tout sélectionner
001 - 42.21.11 LBL A
002 - 1 1
003 - 43.30. 9 TEST 9 (x>=y?)
004 - 22 1 GTO 1
005 - 30 -
006 - 44 0 STO 0
007 - 1 1
008 - 36 ENTER
009 - 42.21. 0 LBL 0
010 - 40 +
011 - 43 36 LSTx
012 - 34 x<>y
013 - 42. 5. 0 DSE 0
014 - 22 0 GTO 0
015 - 42.21. 1 LBL 1
Edith2 m'a nettoyé tout çà
- pir2
- Fonctionne à 9600 bauds
- Messages : 4647
- Enregistré le : 31 oct. 2006 15:08
- Localisation : 67310 Westhoffen
- Contact :
Re: Misez p'tit, Optimisez - N°16 (Fibonacci)
Et le même (ou presque) pour HP-41
Pas de X>=Y? sur 41 (4 pas de perdus)
Code : Tout sélectionner
01 LBL^FIBO
02 1
03 X>Y?
04 GTO 01
05 -
06 X=0?
07 GTO 02
08 1
09 ENTER^
10 LBL 00
11 +
12 LASTX
13 X<>Y
14 DSE Z
15 GTO 00
16 LBL 02
17 1
18 LBL 01
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2936
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit, Optimisez - N°16 (Fibonacci)
Un peu plus court sur 15C:
Et l'équivalent sur 41C et 42s en n'utilisant que la pile:
Sur WP 34S, trop facile:
Code : Tout sélectionner
001 - 42,22,11 LBL A
002 - 43 20 x=0?
003 - 43 32 RTN
004 - 44 0 STO 0
005 - 1 1
006 - 36 ENTER
007 - 0 0
008 - 42.21. 0 LBL 0
009 - 40 +
010 - 43 36 LSTx
011 - 34 x<>y
012 - 42. 5. 0 DSE 0
013 - 22 0 GTO 0
Code : Tout sélectionner
HP-41C HP-42S
00 { 22-Byte Prgm}
01 LBL 'FIB# 01 LBL"FIB#"
02 X=0? 02 X=0? * cas particulier F(0) => on retourne 0
03 RTN 03 RTN
04 1 04 1 * x:1, y:N
05 0 05 0 * x:0, y:1, z:N qui va servir de compteur de boucles
06 LBL 00 06 LBL 00
07 + 07 + * calcul F(n+1)=F(n)+F(n-1)
08 LASTX 08 LASTX * on rappelle F(n)
09 X<>Y 09 X<>Y * x: F(n+1), y: F(n), z:compteur de boucle
10 DSE Z 10 DSE ST Z * on décrémente z et on teste si on est arrivé à 0
11 GTO 00 11 GTO 00
12 END 12 END * après N boucles on sort
Code : Tout sélectionner
FIB
- Hobiecat
- Fonctionne à 9600 bauds
- Messages : 3644
- Enregistré le : 06 sept. 2011 14:57
- Localisation : Normandie
Re: Misez p'tit, Optimisez - N°16 (Fibonacci)
Bien, mais y'a un petit bug : F(4) donne 5 alors que normalement c'est F(5) qui donne 5. Un petit décalage quoi !pir2 a écrit :Tiens, marrant, je me suis fait çà sur ma 15C pour voir si je n'étais pas trop rouillé
(pas optimisé par contre)
Allez, çà va me faire un exercice de lecture des codes programmes de la 15C LE
Edith me dit que c'est draft, pas tout à fait juste, mais c'est un début (pas de traitement de f(0) et f(1), pas sûr que f(2) soit juste etc..)
Edith2 m'a nettoyé tout çà
- Hobiecat
- Fonctionne à 9600 bauds
- Messages : 3644
- Enregistré le : 06 sept. 2011 14:57
- Localisation : Normandie
Re: Misez p'tit, Optimisez - N°16 (Fibonacci)
Il ne marche pas celui-ci : F(5) donne 34 ??zpalm a écrit :Un peu plus court sur 15C:
Petit rappel pour les tests :
F(0)=0
F(1)=1
F(2)=1
F(3)=2
F(4)=3
F(5)=5
F(6)=8
F(7)=13
F(8)=21
F(9)=34
Je n'ai pas trouvé la fonction ! Dommage qu'on ne puisse pas faire XEQ "FIB" d'ailleurs sur la 34S...(ou alors je n'ai pas trouvé, la seule solution que j'ai trouvée est h/x.fcn puis de faire défiler)zpalm a écrit :Sur WP 34S, trop facile:Code : Tout sélectionner
FIB
Modifié en dernier par Hobiecat le 23 mai 2012 17:00, modifié 1 fois.
- pir2
- Fonctionne à 9600 bauds
- Messages : 4647
- Enregistré le : 31 oct. 2006 15:08
- Localisation : 67310 Westhoffen
- Contact :
Re: Misez p'tit, Optimisez - N°16 (Fibonacci)
Voilà, c'est fait
Code : Tout sélectionner
001 - 42.21.11 LBL A
002 - 43.20 x=0
003 - 31 R/S
004 - 1 1
005 - 43.30. 5 TEST 5 (x=y)
006 - 31 R/S
007 - 30 -
008 - 44 0 STO 0
009 - 0 0
010 - 36 ENTER
009 - 1 1
011 - 42.21. 0 LBL 0
012 - 40 +
013 - 43 36 LSTx
014 - 34 x<>y
015 - 42. 5. 0 DSE 0
016 - 22 0 GTO 0
Modifié en dernier par pir2 le 23 mai 2012 17:34, modifié 2 fois.
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2936
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit, Optimisez - N°16 (Fibonacci)
C'est exactement ce que j’obtiens sur ma 15C LE. Il faut peut être ajouter un "R/S" à la fin pour ne pas exécuter du code qui traînerai en mémoire...Hobiecat a écrit :Il ne marche pas celui-ci : F(5) donne 34 ??zpalm a écrit :Un peu plus court sur 15C:
Petit rappel pour les tests :
F(0)=0
F(1)=1
F(2)=1
F(3)=2
F(4)=3
F(5)=5
F(6)=8
F(7)=13
F(8)=21
F(9)=34
Une version améliorée pour la 42s:
Code : Tout sélectionner
00 { 20-Byte Prgm}
01 LBL"FIB#"
02 X=0? * cas particulier F(0) => on retourne 0
03 RTN
04 1 * X:1, Y:n
05 LOG * L:1 X:0, Y:n qui va servir de compteur de boucles
06 LBL 00 * L:F(n-1) X:F(n) Y:n
07 RCL+ ST L * calcul F(n+1)=F(n)+F(n-1) => L:F(n) X:F(n+1) Y:n
08 DSE ST Y * on décrémente Y et on teste si on est arrivé à 0
09 GTO 00
10 END * après N boucles on sort
- pir2
- Fonctionne à 9600 bauds
- Messages : 4647
- Enregistré le : 31 oct. 2006 15:08
- Localisation : 67310 Westhoffen
- Contact :
Re: Misez p'tit, Optimisez - N°16 (Fibonacci)
Et pour 41
Code : Tout sélectionner
01 LBL^FIBO
02 X=0?
03 STOP
04 1
05 X=Y?
06 STOP
07 -
08 0
09 1
10 LBL 00
11 +
12 LASTX
13 X<>Y
14 DSE Z
15 GTO 00
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2936
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit, Optimisez - N°16 (Fibonacci)
Sur la WP 34S Il faut effectivement passer par le catalogue x.fcn, mais pour se positionner dans le catalogue tu peux taper les lettres de la fonction, par h x.fcn F te positionne sur la première fonction commençant par FHobiecat a écrit :(ou alors je n'ai pas trouvé, la seule solution que j'ai trouvée est h/x.fcn puis de faire défiler)
- Hobiecat
- Fonctionne à 9600 bauds
- Messages : 3644
- Enregistré le : 06 sept. 2011 14:57
- Localisation : Normandie
Re: Misez p'tit, Optimisez - N°16 (Fibonacci)
Oups, effectivement, j'avais oublié le "Clear PRGM" avant d'entrer ta version sur 15C....zpalm a écrit :C'est exactement ce que j’obtiens sur ma 15C LE. Il faut peut être ajouter un "R/S" à la fin pour ne pas exécuter du code qui traînerai en mémoire...
C'est mieux, mais pas idéal quand même...quand on veut atteindre les fonctions commençant par des lettres grecques ou des symboles, il faut tout faire défiler (certes, on peut faire défiler "à l'envers" pour être tout de suite à la fin). L'avantage quand même est que la machine garde en mémoire la dernière fonction.zpalm a écrit :Sur la WP 34S Il faut effectivement passer par le catalogue x.fcn, mais pour se positionner dans le catalogue tu peux taper les lettres de la fonction, par h x.fcn F te positionne sur la première fonction commençant par F
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit, Optimisez - N°16 (Fibonacci)
Wouah ! Ce Misez P'tit démarre très fort.
Je peine à trouver mieux que les codes déjà listés ci-dessus.
Donc, je vais proposer quelque chose pour HP28S, ce qui sera pour un temps seulement le mieux puisque rien n'a encore été posté ici pour cette machine :
Bon d'accord, ce n'est pas très original. Mais cela fonctionne (mal car très long et très gourmant en mémoire à cause du nombre incroyable de calculs qu'engendre les appels récursifs !).
En tout cas c'est plus lisible que le code suivant, qui lui par contre est efficace :
Comme vous ne l'avais certainement pas remarqué (car le RPL c'est assez illisible), ce code rempli la pile avec les termes successifs de la série de Fibonacci jusqu'à celui spécifié. Le résultat est donc celui au niveau 1: à la fin de son execution.
Bon allez, j'ai pitié, je poste la version structurée et commentée.
Je peine à trouver mieux que les codes déjà listés ci-dessus.
Donc, je vais proposer quelque chose pour HP28S, ce qui sera pour un temps seulement le mieux puisque rien n'a encore été posté ici pour cette machine :
Code : Tout sélectionner
'F(n)=IFTE( n<2 , n , F(n-1)+F(n-2) )' DEF
En tout cas c'est plus lisible que le code suivant, qui lui par contre est efficace :
Code : Tout sélectionner
« 0 OVER SIGN 2 4 ROLL START DUP2 + NEXT » 'FIB' STO
Bon allez, j'ai pitié, je poste la version structurée et commentée.
Code : Tout sélectionner
« "Calcul des termes de la suite de Fibonacci" DROP
-> n
« "Initialise la suite avec F0=0 et F1=1" DROP
0 n SIGN
"^--- une astuce pour le cas où n=0, la somme fera quoi qu'il arrive toujours 0" DROP
"Boucle principale de 2 à n (si n=0 ou n=1 on fait une fois la boucle" DROP
"Par chance le résultat avec n=1 est alors valide. Et celui avec n=0 " DROP
"est garanti par la fonction SIGN" DROP
2 n START
DUP2 + "Additionne les deux derniers termes tout en en laissant une copie dans la pile" DROP
NEXT
"Fin du programme " DROP "C'est chouette ces commentaires en RPL ! Non ?" DROP
»
»
'FIB' ST'FIB' ST
Modifié en dernier par C.Ret le 01 mars 2022 18:11, 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.
- badaze
- Fonctionne à 14400 bauds
- Messages : 8412
- Enregistré le : 12 févr. 2007 18:36
- Localisation : Pas très loin de Lyon
- Contact :
Re: Misez p'tit, Optimisez - N°16 (Fibonacci)
Ouais, tu enlèves un commentaire tout en oubliant le DROP et t'as un programme qui ne marche plus.C.Ret a écrit :Wouah ! Ce Misez P'tit démarre très fort.
Je peine à trouver mieux que les codes déjà listé ci-dessus.
Donc, je vais proposer quelque chose pour HP28S, ce qui sera pour un temps seulement le mieux puisque rien n'a encore été posté ici pour cette machine :
Bon d'accord, ce n'est pas très original. Mais cela fonctionne (mal car très long et très gourmant en mémoire à cause du nombre incroyable de calculs qu'engendre les appels récursifs !).Code : Tout sélectionner
'F(n)=IFTE( n<2 , n , F(n-1)+F(n-2) )' DEF
En tout cas c'est plus lisible que le code suivant, qui lui par contre est efficace :Comme vous ne l'avais certainemetn pas remarqué (car le RPL c'est assez illisible), ce code rempli la pile avec les termes successifs de la série de Fibonacci jusqu'à celui spécifié. Le résultat est donc celui au niveau 1: à la fin de son execution.Code : Tout sélectionner
« 0 OVER SIGN 2 4 ROLL START DUP2 + NEXT » 'FIB' STO
Bon allez, j'ai pitié, je poste la version structurée et commentée.Code : Tout sélectionner
« "Calcul des termes de la suite de Fibonacci" DROP -> n « "Initialise la suite avec F0=0 et F1=1" DROP 0 n SIGN "^--- une astuce pour le cas où n=0, la somme fera quoi qu'il arrive toujours 0" DROP "Boucle principale de 2 à n (si n=0 ou n=1 on fait une fois la boucle" DROP "Par chance le résultat avec n=1 est alors valide. Et celui avec n=0 " DROP "est garanti par la fonction SIGN" DROP 2 n START DUP2 + "Additionne les deux derniers termes totu en en laissant une copie dans la pile" DROP NEXT "Fin du programme " DROP "C'est chouette ces commantaires en RPL ! Non ?" DROP » » 'FIB' ST'FIB' ST
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.
- gege
- Fonctionne à 14400 bauds
- Messages : 7148
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Misez p'tit, Optimisez - N°16 (Fibonacci)
Bonjour,
Pour sauver l'honneur de Casio, une version qui consomme une place incroyable (60 octets !) mais qui est rapide. Pour Graph 85 :
FIBONACC
?->N:RndFix(((1+¥5)/2)^N/¥5,0)->F:F
(¥ etant le signe de la racine carree).
Ca calcule F(49)=7778742049 en un temps non mesurable (mais une bete boucle est indecelable de l'instantane aussi).
On a aussi F(68) calcule comme 72723460248157, alors que les deux derniers chiffres devraient etre 41. Pas anormal cependant.
G.E.
Pour sauver l'honneur de Casio, une version qui consomme une place incroyable (60 octets !) mais qui est rapide. Pour Graph 85 :
FIBONACC
?->N:RndFix(((1+¥5)/2)^N/¥5,0)->F:F
(¥ etant le signe de la racine carree).
Ca calcule F(49)=7778742049 en un temps non mesurable (mais une bete boucle est indecelable de l'instantane aussi).
On a aussi F(68) calcule comme 72723460248157, alors que les deux derniers chiffres devraient etre 41. Pas anormal cependant.
G.E.