Combinaisons

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

Combinaisons

Messagepar rexacont » lun. 18 juil. 2011 13:57

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 : 579
Inscription : ven. 15 avr. 2005 15:47
Localisation : Lyon
Contact :

Re: Combinaisons

Messagepar Thomas FR69 » lun. 18 juil. 2011 23:33

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 : 205
Inscription : mar. 16 sept. 2008 15:18
Localisation : Grenoble

Re: Combinaisons

Messagepar hpmaniac » mar. 19 juil. 2011 07:51

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 : 579
Inscription : ven. 15 avr. 2005 15:47
Localisation : Lyon
Contact :

Re: Combinaisons

Messagepar Thomas FR69 » mar. 19 juil. 2011 10:06

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

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

Re: Combinaisons

Messagepar hpmaniac » mer. 20 juil. 2011 10:54

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 : 205
Inscription : mar. 16 sept. 2008 15:18
Localisation : Grenoble

Re: Combinaisons

Messagepar hpmaniac » lun. 25 juil. 2011 11:14

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 : 205
Inscription : mar. 16 sept. 2008 15:18
Localisation : Grenoble

Re: Combinaisons

Messagepar hpmaniac » mer. 27 juil. 2011 06:29

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 : 579
Inscription : ven. 15 avr. 2005 15:47
Localisation : Lyon
Contact :

Re: Combinaisons

Messagepar Thomas FR69 » mer. 27 juil. 2011 08:56

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 : 205
Inscription : mar. 16 sept. 2008 15:18
Localisation : Grenoble

Re: Combinaisons

Messagepar hpmaniac » mer. 27 juil. 2011 13:55

:D :D

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

Re: Combinaisons

Messagepar noel » ven. 19 août 2011 13:25

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 : 579
Inscription : ven. 15 avr. 2005 15:47
Localisation : Lyon
Contact :

Re: Combinaisons

Messagepar Thomas FR69 » ven. 19 août 2011 14:26

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 : 326
Inscription : jeu. 28 sept. 2006 08:53
Localisation : Toulouse
Contact :

Re: Combinaisons

Messagepar noel » ven. 19 août 2011 15:03

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


Revenir vers « Programmation »

Qui est en ligne ?

Utilisateurs parcourant ce forum : Aucun utilisateur inscrit et 2 invités