formule du lote et Combinaisons

Le
Jean-marc
Hello à tous,

la question de la formule du Loto nous a amené
à la question nettement plus intéressante du
calcul général de C(n,p) avec :
p n!
C = -
n (n-p)! . p!

VB ne disposant pas de la fonction factorielle,
on peut exprimer C(n,p) comme :


p n * (n-1) * (n-2) * * (n-p+1)
C = --
n p * (p-1) * (p-2) * * 2


Il est évident que le calcul du nominateur et/ou du
dénominateur va très vite être plus grand qu'un Long.
Exemple : le calcul de C(49,6) =

(49*48*47*46*45*44) / (6*5*4*3*2) entraine un dépassement
de capacité au niveau du numérateur car le résultat est trop
grand pour un Long (ici il vaut 10.068.347.520 alors que la
limite d'un Long est 2.147.483.647).
Pourtant, le résultat (qui vaut 13.983.816) est tout petit
en comparaison et tient sans problème dans un Long.

Il faut donc être un peu malin et essayer de contraindre
le numérateur à être le plus petit possible.

Je vous propose la petite fonction suivante qui permet de calculer
C(n,p) de façon intelligente. En pratique, elle pourra calculer tous
les C(n,p) dont le résultat final tient dans un Long.

Elle utilise la fonction PGCD() dont un exemple d'implémentation
est donné dans la FAQ : http://faq.vb.free.fr/index.php?question2

Voici :

Public Function Cnp(ByVal n As Long, ByVal p As Long) As Long
Dim NumLow As Long
Dim i As Long
Dim j As Long
Dim r As Long
Dim t() As Long
Dim tempNum As Long
Dim Num As Long
Dim pp As Long
Dim must_stop As Boolean

NumLow = n - p + 1

ReDim t(p)
For i = 2 To p
t(i - 1) = i
Next i
Num = 1
For i = n To NumLow Step -1
tempNum = i

Do
must_stop = True
For j = 1 To p - 1
pp = PGCD(tempNum, t(j))
If pp > 1 Then
tempNum = tempNum / pp
t(j) = t(j) / pp
must_stop = False
End If
Next j
Loop While (Not must_stop) And (tempNum <> 1)
Num = Num * tempNum
Next i
For i = 1 To p - 1
Num = Num / t(i)
Next i
Cnp = Num

End Function

Private Function PGCD(ByVal n1 As Long, ByVal n2 As Long) As Long

If n2 = 0 Then
PGCD = n1
Else
PGCD = PGCD(n2, n1 Mod n2)
End If
End Function
' --

Note : Non, utiliser des Double ne serait *PAS* une
bonne(tm) solution, pas plus qu'utiliser un type Currency

Bonne lecture et bonne soirée !

--
Jean-marc Noury (jean_marc_n2)
FAQ VB: http://faq.vb.free.fr/
mailto: remove '_no_spam_' ; _no_spam_jean_marc_n2@yahoo.fr
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
fraction
Le #20490171
Je suis toujours dans mon déducteur technique.
J'ai une propriété finale A que je dois étudier en fonction de n-1
autres propriétés. J'ai donc réalisé un tableau à n dimensions qu i, en
fonction de l'exécution d'un déducteur logique préalable, me donne
comme résultat 0, 1 ou 2 (2 étant la contradiction).
Je dois maintenant étudier la totalité des groupes nécessaires et/ou
suffisants à l'existence de la propriété finale.

Exemple :
J'ai quatre propriétés : A, x, y, z
A étant la propriété finale, dont il faut déduire les propriété s
nécessaires et/ou suffisantes.
Je sais que "x et y créent A" mais je n'ai plus accès à cette formule ,
seulement au tableau. Mon tableau possède dans ses coordonnées T
(A=1,x=1,y=1,z=0)=1
Je veux maintenant que mon déducteur déduise que (x=1 et y=1) est u n
groupe suffisant à l'existence de A.

Le nombre total de groupes possibles est donc 2*(n!/(n-1)! +....+n!/
((n-p)!*p!)+.....+n!/n!), enfin je crois, je verrais bien.

Je n'ai pas compris ce qu'est sensé représenter ta fonction PGCD, ni
ce que signifie Mod. Pour ce qui est du code, j'ai mes habitudes et je
ne ferais sûrement pas comme toi. J'ai juste besoin de connaître mieux
ta méthode, puisque tu dis qu'elle résout les problèmes de dépassem ent
de capacité (cela dit, si je dois étudier 10.000.000.000 de groupes,
ce n'est pas raisonnable, je pense faire une sélection préalable)
fraction
Le #20490231
On 4 nov, 22:23, "Jean-marc"
Hello à tous,

la question de la formule du Loto nous a amené
à la question nettement plus intéressante du
calcul général de C(n,p) avec :
  p           n!
 C   = -------------
  n     (n-p)! . p!



Petit détail
Pour nI et pI on a C(n,p)I!/(0!*49!) donc C(n,p)I!/0, alors
qu'on doit obtenir 1
Question : est-ce que 0!=1 ? Ça m'arrangerait.
Driss HANIB
Le #20491301
Bonjour

Oui 0! = 1 par définition

Driss
"fraction"
On 4 nov, 22:23, "Jean-marc"
Hello à tous,

la question de la formule du Loto nous a amené
à la question nettement plus intéressante du
calcul général de C(n,p) avec :
p n!
C = -------------
n (n-p)! . p!



Petit détail
Pour nI et pI on a C(n,p)I!/(0!*49!) donc C(n,p)I!/0, alors
qu'on doit obtenir 1
Question : est-ce que 0!=1 ? Ça m'arrangerait.
jean-marc
Le #20491291
"fraction" news:
On 4 nov, 22:23, "Jean-marc"
Hello à tous,

la question de la formule du Loto nous a amené
à la question nettement plus intéressante du
calcul général de C(n,p) avec :
p n!
C = -------------
n (n-p)! . p!



Petit détail
Pour nI et pI on a C(n,p)I!/(0!*49!) donc C(n,p)I!/0,





NON.

C(49,49) = 49! / ((49-49)! * 49 !) = 49!/(49! * 0!)
ce qui fait 1.

alors
qu'on doit obtenir 1





OUI.

Question : est-ce que 0!=1 ? Ça m'arrangerait.



Bien sur.

Cordialement,

--
Jean-marc
jean-marc
Le #20491371
"fraction" news:
Je suis toujours dans mon déducteur technique.


<snip>
Exemple :
J'ai quatre propriétés : A, x, y, z
A étant la propriété finale, dont il faut déduire les propriétés
nécessaires et/ou suffisantes.
Je sais que "x et y créent A" mais je n'ai plus accès à cette formule,
seulement au tableau. Mon tableau possède dans ses coordonnées T
(A=1,x=1,y=1,z=0)=1
Je veux maintenant que mon déducteur déduise que (x=1 et y=1) est un
groupe suffisant à l'existence de A.



Le nombre total de groupes possibles est donc 2*(n!/(n-1)! +....+n!/
((n-p)!*p!)+.....+n!/n!), enfin je crois, je verrais bien.



non.

Je n'ai pas compris ce qu'est sensé représenter ta fonction PGCD,



Le Plus Grand Commun Dénominateur. Tu n'as pas lu mon post en
entier, je donne la référence de l'article de la FAQ qui le décrit.
http://faq.vb.free.fr/index.php?question2

ni ce que signifie Mod.



L'opérateur modulo. Cf.:
http://msdn.microsoft.com/en-us/library/se0w9esz(VS.80).aspx
http://fr.wikipedia.org/wiki/Modulo_(informatique)


Pour ce qui est du code, j'ai mes habitudes et je
ne ferais sûrement pas comme toi. J'ai juste besoin de connaître mieux
ta méthode, puisque tu dis qu'elle résout les problèmes de dépassement
de capacité



C'est des maths de niveau seconde; le code me semble limpide ...

(cela dit, si je dois étudier 10.000.000.000 de groupes,
ce n'est pas raisonnable, je pense faire une sélection préalable)



Ca semble en effet sage ...

--
Jean-Marc
Fred
Le #20492711
in news:4af1f0e3$0$2863$, Jean-marc wrote :

Hello à tous,



Salut Jean-Marc,

Pour le PGCD, je te propose cette variante étrange mais qui fonctionne
sans récursivité :
(avec des entiers positifs)

Function PGCD(ByVal a As Integer, ByVal b As Integer) As Integer
While a <> b
If a > b Then
a = a - b
Else
b = b - a
End If
Wend
PGCD = a
End Function


--
Fred

fraction
Le #20492871
> >Le nombre total de groupes possibles est donc 2*(n!/(n-1)! +....+n!/
>((n-p)!*p!)+.....+n!/n!), enfin je crois, je verrais bien.

non.



Tu as raison, comme chaque élément de p a deux valeurs possibles, je
dois multiplier C(n,p) par 2^p.

Le Plus Grand Commun Dénominateur. Tu n'as pas lu mon post en
entier, je donne la référence de l'article de la FAQ qui le décrit. http://faq.vb.free.fr/index.php?question2

> ni ce que signifie Mod.

L'opérateur modulo. Cf.:http://msdn.microsoft.com/en-us/library/se0w9es z(VS.80).aspxhttp://fr.wikipedia.org/wiki/Modulo_(informatique)



J'ai du mal avec Wiki, je trouve qu'il veut trop bien faire, il en dit
trop.


>Pour ce qui est du code, j'ai mes habitudes et je
>ne ferais sûrement pas comme toi. J'ai juste besoin de connaître mie ux
>ta méthode, puisque tu dis qu'elle résout les problèmes de dépas sement
>de capacité

C'est des maths de niveau seconde; le code me semble limpide ...



Mes études m'ont lâchement abandonné. :-) Et ma mémoire a organis é un
grand plan social depuis, pour une meilleure productivité.


>(cela dit, si je dois étudier 10.000.000.000 de groupes,
>ce n'est pas raisonnable, je pense faire une sélection préalable)

Ca semble en effet sage ...



Je vais essayer de trouver le nombre de propriétés maximum que je peux
étudier sans sélection préalable.


--
Jean-Marc


fraction
Le #20493181
On 5 nov, 09:12, "Driss HANIB"
Bonjour

Oui 0! = 1  par définition



En même temps, si tu le sais pas... Ce n'est pas intuitif.
jean-marc
Le #20493371
"Fred" news:
in news:4af1f0e3$0$2863$, Jean-marc wrote :

Hello à tous,



Salut Jean-Marc,



Salut Fred,

Pour le PGCD, je te propose cette variante étrange mais qui fonctionne
sans récursivité :
(avec des entiers positifs)



C'est en faite la méthode classique quand on le fait en itératif.
C'est la meilleure méthode en fait, en tout cas meilleure que
la version récursive que je donne dans la FAQ - Je l'ai mis pour
le plaisir de faire un lien vers l'autre article de la FAQ
traitant de la récursivité :-)

(à l'occasion, je l'ajouterais à la FAQ dans l'article.)

--
jean-Marc
Fred
Le #20496061
"jean-marc" news:4af2ddbc$0$2858$

"Fred" news:
in news:4af1f0e3$0$2863$, Jean-marc wrote :

Hello à tous,



Salut Jean-Marc,



Salut Fred,

Pour le PGCD, je te propose cette variante étrange mais qui
fonctionne sans récursivité :
(avec des entiers positifs)



C'est en faite la méthode classique quand on le fait en itératif.
C'est la meilleure méthode en fait, en tout cas meilleure que
la version récursive que je donne dans la FAQ - Je l'ai mis pour
le plaisir de faire un lien vers l'autre article de la FAQ
traitant de la récursivité :-)



Dans le cas présent, oui, je pense qu'elle est plus rapide, mais pour de
très grands nombres, surtout s'ils sont de même ordre de grandeur, la
méthode récursive est plus rapide.

--
Fred

Publicité
Poster une réponse
Anonyme