Combinaisons

Questions et discussions autour de la programmation du HP-41.
Répondre
rexacont
Apprenti
Messages : 16
Inscription : ven. 13 nov. 2009 14:27

Combinaisons

Message par rexacont »

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

Avatar de l’utilisateur
Thomas FR69
Administrateur
Messages : 582
Inscription : ven. 15 avr. 2005 15:47
Localisation : Lyon, FRANCE
Contact :

Re: Combinaisons

Message par 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 ! :D

Avatar de l’utilisateur
hpmaniac
Expert
Messages : 213
Inscription : mar. 16 sept. 2008 15:18
Localisation : Grenoble

Re: Combinaisons

Message par 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 

Avatar de l’utilisateur
Thomas FR69
Administrateur
Messages : 582
Inscription : ven. 15 avr. 2005 15:47
Localisation : Lyon, FRANCE
Contact :

Re: Combinaisons

Message par Thomas FR69 »

Bravo ! Qui propose une ligne de moins ? :lol:

Avatar de l’utilisateur
hpmaniac
Expert
Messages : 213
Inscription : mar. 16 sept. 2008 15:18
Localisation : Grenoble

Re: Combinaisons

Message par hpmaniac »

Thomas FR69 a écrit :Bravo ! Qui propose une ligne de moins ? :lol:
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.

Avatar de l’utilisateur
hpmaniac
Expert
Messages : 213
Inscription : mar. 16 sept. 2008 15:18
Localisation : Grenoble

Re: Combinaisons

Message par 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

Avatar de l’utilisateur
hpmaniac
Expert
Messages : 213
Inscription : mar. 16 sept. 2008 15:18
Localisation : Grenoble

Re: Combinaisons

Message par 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

Avatar de l’utilisateur
Thomas FR69
Administrateur
Messages : 582
Inscription : ven. 15 avr. 2005 15:47
Localisation : Lyon, FRANCE
Contact :

Re: Combinaisons

Message par Thomas FR69 »

Magnifique cette dernière version ! :D
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...

Avatar de l’utilisateur
hpmaniac
Expert
Messages : 213
Inscription : mar. 16 sept. 2008 15:18
Localisation : Grenoble

Re: Combinaisons

Message par hpmaniac »

:D :D

Avatar de l’utilisateur
noel
Expert
Messages : 327
Inscription : jeu. 28 sept. 2006 08:53
Localisation : Toulouse
Contact :

Re: Combinaisons

Message par 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.
HP 41C, CV et CX fullnut

Avatar de l’utilisateur
Thomas FR69
Administrateur
Messages : 582
Inscription : ven. 15 avr. 2005 15:47
Localisation : Lyon, FRANCE
Contact :

Re: Combinaisons

Message par Thomas FR69 »

noel a écrit :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 :lol: !

Avatar de l’utilisateur
noel
Expert
Messages : 327
Inscription : jeu. 28 sept. 2006 08:53
Localisation : Toulouse
Contact :

Re: Combinaisons

Message par 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 :?
HP 41C, CV et CX fullnut

Répondre