Combinaisons

[rexacont]

Bonjour à tous,
Je souhaite programmer la formule de combinaisons
n! /(n-r)!
SUR 41 bien entendu.
Cordialement.

[Thomas FR69]

Bonjour,

Je propose :

Code : Tout sélectionner

                 X                 Y             LASTX
                --------------------------------------
                 n                 r
01 LBL "C"          
02 -             r - n                           n
03 LASTX         n                 r - n 
04 FACT          n!                r - n 
05 X<>Y          r - n             n!
06 CHS           n - r             n!
07 FACT          (n - r)!          n!
08 /             n! / (n - r)! 
09 RTN

9 lignes. Qui dit mieux !

[hpmaniac]

Bonjour,

J'ai trois remarques:
1) la formule donnée n!/(n-r)! est celle du calcul des permutations, pas celle du calcul des combinaisons
2) sur les calculatrices HP qui intègrent ce calcul on entre d'abord n puis r, ce qui donne un ordre inverse dans la pile par rapport au programme de Thomas
3) sur la HP-41 le label "C" est un label local, pas globlal (du moins sans programmation synthétique)

Calcul des combinaisons: n!/r!(n-r)!

Code : Tout sélectionner

                 X                 Y                 Z                 T
                ---------------------------------------------------------
                 r                 n                 z                 t
01 LBL "COMB"         
02 RCL Y         n                 r                 n                 z
03 FACT          n!                r                 n                 z
04 X<> Z         n                 r                 n!                z
05 X<>Y          r                 n                 n!                z
06 ST- Y         r                 n - r             n!                z
07 FACT          r!                n - r             n!                z
08 X<>Y          n-r               r!                n!                z
09 FACT          (n-r)!            r!                n!                z
10 *             r!(n-r)!          n!                z                 z
11 /             n!/r!(n-r)!       z                 z                 z
12 RTN

Ce programme préserve Z et s'exécute par: n ENTER r XEQ "COMB"


Calcul des permutations: n!/(n-r)!

En changeant l'ordre des paramètres le programme de Thomas devient:

Code : Tout sélectionner

                 X                 Y             LASTX
                --------------------------------------
                 r                 n
01 LBL "PERM"         
02 X<>Y          n                 r
03 -             r - n                           n
04 LASTX         n                 r - n
05 FACT          n!                r - n
06 X<>Y          r - n             n!
07 CHS           n - r             n!
08 FACT          (n - r)!          n!
09 /             n! / (n - r)!
10 RTN

Ce programme a l'avantage de préserver Z et T.

Il est possible de faire mieux, en 9 lignes, mais en ne préservant que Z:

Code : Tout sélectionner

                 X                 Y                 Z                 T
                ---------------------------------------------------------
                 r                 n                 z                 t
01 LBL "PERM"         
02 RCL Y         n                 r                 n                 z
03 FACT          n!                r                 n                 z
04 X<> Z         n                 r                 n!                z
05 -             r-n               n!                z                 z
06 CHS           n-r               n!                z                 z
07 FACT          (n-r)!            n!                z                 z
08 /             n!/(n-r)!         z                 z                 z
09 RTN 

[Thomas FR69]

Bravo ! Qui propose une ligne de moins ?

[hpmaniac]

Bravo ! Qui propose une ligne de moins ?

Moi ! mais sur HP-42s ...

Le programme "COMB" utilise plusieurs instructions de manipulation de pile spécifiques à la HP-41 (par rapport aux autres machines RPN):
RCL Y : extension des instructions RCL et STO aux registres de la pile - s'obtient par [RCL] [.] [Y]
X<> Z : extension de X<> à tous les registres y compris ceux de la pile - s'obtient par [XEQ] [ALPHA] [X] [Shift][COS] [Shift][TAN] [ALPHA] [.] [Z]
ST- Y : extension aux registres de la pile de l'arithmétique dans les registres avec STO (+,-,*,/) - s'obtient par [STO] [-] [Y]

Par contre il n'y a pas sur la HP-41 d'opération arithmétique dans les registres associée à RCL. On ne trouve ces opérations que sur la HP-42s, ce qui permet de remplacer les lignes 05 X<>Y et 06 ST- Y par un simple 05 RCL- Y.
Voici donc le programme "COMB" sur HP-42s en 11 lignes:

Code : Tout sélectionner

                 X                 Y                 Z                 T
                ---------------------------------------------------------
                 r                 n                 z                 t
00 { 22-Byte Prgm}
01 LBL "COMB"         
02 RCL ST Y      n                 r                 n                 z
03 N!            n!                r                 n                 z
04 X<> ST Z      n                 r                 n!                z
05 RCL- ST Y     n-r               r                 n!                z
06 N!            (n-r)!            r                 n!                z
07 X<>Y          r                 (n-r)!            n!                z
08 N!            r!                (n-r)!            n!                z
09 *             r!(n-r)!          n!                z                 z
10 /             n!/r!(n-r)!       z                 z                 z
11 RTN

Si l'on regarde la formule de calcul des combinaisons n!/r!(n-r)! on voit qu'elle comporte 6 opérations: 3 factorielles, une soustraction, une multiplication et une division. Si l'on ajoute le label de début et le retour de fin cela fait un minimum de 8 lignes de programme. Le programme ci-dessus avec 11 lignes n'ajoute au minimum requis que 3 opérations de manipulation de pile RCL ST Y, X<> ST Z et X<>Y.
Qui fait mieux?

Notes:
sur la 42s les registres de la pile sont précédés de ST pour stack pour les différentier d'une variable qui aurait le même nom.
la 42s offre d'origine les fonctions COMB et PERM dans le menu PROB, le programme ci-dessus est donc superflu sur cette machine.

[hpmaniac]

Voici une version pour HP-41 également en 11 lignes, aussi bien que sur la 42s:

Code : Tout sélectionner

                 X                 Y                 Z                 T
                ---------------------------------------------------------
                 r                 n                 z                 t
01 LBL "COMB"         
02 RCL Y         n                 r                 n                 z
03 FACT          n!                r                 n                 z
04 X<>Y          r                 n!                n                 z
05 ST- Z         r                 n!                n-r               z
06 FACT          r!                n!                n-r               z
07 /             n!/r!             n-r               z                 z
08 X<>Y          n-r               n!/r!             z                 z
09 FACT          (n-r)!            n!/r!             z                 z
10 /             n!/r!(n-r)!       z                 z                 z
11 RTN

[hpmaniac]

Et voici une version du calcul de permutations en 9 lignes, préservant Z et T, soit une ligne de moins que le programme initial de Thomas car on commence avec r et n dans X et Y et non l'inverse:

Code : Tout sélectionner

                 X             Y             Z             T      LASTX
                -----------------------------------------------------------
                 r             n             z             t
01 LBL "PERM"         
02 X<>Y          n             r             z             t
03 FACT          n!            r             z             t        n
04 X<>Y          r             n!            z             t        n
05 ST- L         r             n!            z             t        n-r
06 X<> L         n-r           n!            z             t        r
07 FACT          (n-r)!        n!/r!         z             t        n-r
08 /             n!/(n-r)!     z             t             t        (n-r)!
09 RTN

[Thomas FR69]

Magnifique cette dernière version !
J'étais certain que l'on pouvait mieux faire...
J'avais envisagé le ST- L mais c'est le X<> L que j'avais oublié qui débloque l'optimisation ! Bravo !
Je crois maintenant que cela va être difficile de faire plus court...

[hpmaniac]

[noel]

C'est à peu près ce que propose Jean-Jacques Dhénin dans son bouquin Programme HP-41

01 LBL "CB"
02 X<>Y
03 FACT
04 X<>Y
05 ST-L
06 LAST X
07 FACT
08 X<>Y
09 FACT
10 *
11 /
12 .END.

[Thomas FR69]

C'est à peu près ce que propose Jean-Jacques Dhénin dans son bouquin Programme HP-41

"À peu près" ou une ligne de plus ? Car attention, ce n'est pas du tout la même chose !

[noel]

D'accord, une combinaison n'est pas une permutation. Je teste ta vigilance.

Par contre dans le manuel du PPC-ROM le PRGM correspondant est :
80*LBL C
81*LBL "PM"
82 CHS
83 X<>Y
84 SIGN
85 X<>L
86 ST+Y
87*LBL 06
88 X=Y?
89 GTO 07
90 ST*L
91 DSE X
92 GTO 06
93*LBL 07
94 RDN
95 X<>L
96 RTN

Curieux non ! J'ai aussi été étonné de ne pas trouver cette fonction pourtant très utile dans le module STAT :?