Misez P'tit, Optimisez - N°32 (factorielle)

[badaze]

Bonjour,

Un petit MPO sur le thème de la factorielle, avec bien sûr interdiction d'utiliser la fonction.

De mémoire j'avais fait un programme pour TI 57 de 5 ou 6 pas (à l'époque je l'avais envoyé à l'OP mais il n'avait pas été publié) et bien entendu je ne l'ai pas retrouvé ni m'en souviens.

[bkg2018]

Oh, franchement...

STO 0
Lbl 0
rcl 0
*
Dsz
Gto 0
=
R/S

Ou un truc comme çà non ?

[zpalm]

WP 34S:

Code : Tout sélectionner

01 LBL A
02 ENTER
03 DSE Y
04 SKIP 001
05 RTN
06 RCLx Y
07 BACK 004

Avec un pas de plus on laisse Y, Z &T intacts:

Code : Tout sélectionner

01 LBL A
02 STO L
03 DSE X
04 SKIP 002
05 x<>L
06 RTN
07 STOx L
08 BACK 005

[zpalm]

Et sur TI 57: 7 pas, comme la WP 34S (mais sans label). Vraiment surprenante cette petite machine, il va m'en falloir une un jour

Code : Tout sélectionner

00 STO 0
01 =
02 INV 2nd DSZ (Decrement & Skip if not Zero)
03 INV SBR     (RTN)
04 *
05 RCL 0
06 RST         (Reset program counter to first step = GTO 00)

Après avoir rentré le programme on tape RST (pour revenir au début de la mémoire programme), le nombre dont on veut calculer la factorielle puis R/S.
Par ex:
RST 5 R/S donne 120
RST 1 R/S donne 1

L'astuce c'est d'utiliser RST au lieu de GTO ce qui évite le LBL, avec cela le STO 0 se retrouve dans la boucle, il faut donc déplacer le '=' pour que lors de l'exécution de la boucle le STO 0 suive le RCL 0 pour ne ne pas modifier le registre 0.
La deuxième astuce c'est le INV 2nd DSZ (Decrement & Skip if not Zero), une instruction qui n'existe pas sur les machines HP et qui évite un saut supplémentaire.

(@badaze, si tu as une solution en 5 ou 6 pas je suis curieux de la voir...)

[C.Ret]

Pour les calculettes biologiques :

Code : Tout sélectionner

« IF DUP 1 >
  THEN
    DUP 1 - F! *
  END
»
'F!' STO

ou

Code : Tout sélectionner

« 1
  DUP ROT FOR f
    f *
  NEXT
»
'FCT!' STO

Et pour les machine moins biologiques:

Code : Tout sélectionner

                        n
001 LBL "FCT    
002 1             n     1
003 x<>Y          1     n
004 Lbl 00      prd     f
005 ST* Y     prd.f     f
006 DSE X     prd.f   f-1
007 GTO 00
                 n!     0
008 Rdn
009 END                n!

Code : Tout sélectionner

 1:"F"AREAD N:F=1:FOR I=1 TO N:F=FI:NEXT I:PRINT N,F:END

[bernouilli92]

Voici ma version en RPL :

Code : Tout sélectionner

« 1 OVER 1 - FOR I I * NEXT »

Et ma version pour hp41, mais elle ne fonctionne pas pour la valeur 0 (et inférieur) :

Code : Tout sélectionner

000 LBL FACTO
001 ENTER
002 LBL 00
003 1 
004 -
005 x=0?
006 GTO 01
007 *
008 LASTx
009 GTO 00
010 LBL 01
011 +

[C.Ret]

Voici ma version en RPL :

Code : Tout sélectionner

« 1 OVER 1 - FOR I I * NEXT »

Le souci provient de 0! qui avec ce code ne fait pas 1 ?

Par ailleurs cela fait une instruction de plus que
« 1 DUP ROT FOR f f * NEXT »
Qui donne bien 0!=1

[bernouilli92]

Voici ma version en RPL :

Code : Tout sélectionner

« 1 OVER 1 - FOR I I * NEXT »

Le souci provient de 0! qui avec ce code ne fait pas 1 ?

Par ailleurs cela fait une instruction de plus que
« 1 DUP ROT FOR f f * NEXT »
Qui donne bien 0!=1

Tu as raison, je n'ai pas testé mon code avec la valeur 0

[badaze]

(@badaze, si tu as une solution en 5 ou 6 pas je suis curieux de la voir...)

C'était il y a plus de 30 ans....

[zpalm]

Et pour les machine moins biologiques:

Code : Tout sélectionner

                        n
001 LBL "FCT    
002 1             n     1
003 x<>Y          1     n
004 Lbl 00      prd     f
005 ST* Y     prd.f     f
006 DSE X     prd.f   f-1
007 GTO 00
                 n!     0
008 Rdn
009 END                 n!

Bien vu le coup du 1 dans la pile! Appliqué à la WP 34S on descend à 6 pas avec:

Code : Tout sélectionner

                        n
001 LBL A    
002 1             n     1
003 RCL* Y        f prd.f
004 DSE Y       f-1 prd.f
005 BACK 002
006 END                n!

[C.Ret]

Bien vu bien vu c'est vite dit !

Car cela n'empêche pas de répondre que 0!=0 au lieu de 1

[zpalm]

Bien vu bien vu c'est vite dit !

Car cela n'empêche pas de répondre que 0!=0 au lieu de 1

Il suffit de rajouter un petit test et c'est bon:

Code : Tout sélectionner

                        n
001 LBL A   
002 1             n     1
003 x<=? Y
004 RCL* Y        f prd.f
005 DSE Y       f-1 prd.f
006 BACK 002
007 END                n!

[Gilles59]

J'ai pas la 602 (ou 502), sous la main mais :

Code : Tout sélectionner

Min00 ISZ
LBL0
MR00 
*
DSZ
GOTO0
=

en 8 pas devrait le faire avec 0! -> 1
Doit y avoir mieux

pas mieux que les solution précédente en RPL

[bkg2018]

J'ai pas la 602 (ou 502), sous la main mais :

Code : Tout sélectionner

Min00 ISZ
LBL0
MR00 
*
DSZ
GOTO0
=

en 8 pas devrait le faire avec 0! -> 1
Doit y avoir mieux

pas mieux que les solution précédente en RPL

MMmmm si ISZ fait ce que je pense, tu ne serais pas en train de calculer factorielle de N+1 ?

[bkg2018]

Sur TI57 avec la contrainte 0!=1 et une utilisation sans préstockage dans les registres je n'ai pas grand chose de dément...

00 Sto 0
01 1
02 Sto 1
03 Lbl 0
04 Inv Dsz
05 Gto 1
06 Rcl 0
07 Prd 1
08 Gto 0
09 Lbl 1
10 Rcl 1
11 R/S

On ne peut plus ruser avec RST à cause de l'initialisation de R0 et R1. Et on ne peut pas trop éviter deux labels : un pour boucler, un pour sortir de la boucle.