Calcule d'une combinaison

Version imprimable

24/03/2006, 19h54
ccensam

Calcule d'une combinaison

Salut ça fais 1 semaine que j'essaye d'ecrire un programme qui calcule http://upload.wikimedia.org/math/2/0...9dd8b726ea.png
exactement et cela pour des nombres un peu grands sans depasser la limite de unsigned int.
Quelqu'un à une bonne idée.!
24/03/2006, 21h28
Graffito

Bonjour,

Pour gérer de grands entiers tels que peuvent en donner des factoriels,
Il faut se faire son propre code ou utiliser une bibli non standard pour gérer des entiers super-longs.

Un petit code (en dephi) qui pourrait t'interesser :
http://www.delphiforfun.org/Programs/big_factorials.htm

Ca te donnera les algo pour les fonctions de multiplication et division
24/03/2006, 21h38
pcaboche

Sauf erreur de ma part (n'hésitez pas à me corriger):

1) Si n/2 =< k =< n, on a:
1 =< n-k+1 =< k =< n

au numérateur: n-k+1 --> n
au dénominateur: 1 --> k

Les nombres qui sont entre n-k+1 et k apparaissent donc à la fois au numérateur et au dénominateur, donc on peut les éliminer.

On a alors:
au numérateur: k --> n
au dénominateur: 1 --> n-k+1

Maintenant, pour éviter les dépassement de capacité, on prend un élément du numérateur, un élément du dénominateur, on en fait le quotient et ainsi de suite:
R = k/1 * (k+1)/2 * ... * n/(n-k+1)

2) Si 0 < k < n/2, on a:
1 =< k =< n-k+1 =< n

On a alors:
au numérateur: n-k+1 --> n
au dénominateur: 1 --> k

Aucun élément n'apparait à la fois au numérateur et au dénominateur, mais comme toute à l'heure, on prend un élément du numérateur, un élément du dénominateur, on en fait le quotient et ainsi de suite:
R = (n-k+1)/1 * (n-k+2)/2 * ... * n/k

***
Maintenant, y a-t'il un mathématicien dans l'assemblée pour vérifier mes dires? (ça m'arrive de faire des erreurs en maths, donc j'aimerais confirmation/infirmation)
25/03/2006, 10h26
ToTo13

Bonjour,

on n'utilise jamais la formule du C(n,p)!!!
Il faut plutot utiliser le triangle de pascal. En revanche celui ci dépasse les int_max pour une valeur de n=35. Il te faut donc trouver une lib qui gère ce genre de soucis.

Au fait, pour quelle type d'utilisation est ce ????
27/03/2006, 10h17
random

outre les simplifications déja proposées
on peut remplacer un produit par une addition de logs
sans entrer dans des bibliothèques sur les nombres longs
c'est facile à mettre en oeuvre

Ma solution

Voila ce que j'ai reussit à faire.
Ce petit code en C permet de calculer la combinaison à condition qu'elle ne dépasse pas la capacité de long int. Et elle n'utilise que des variables entières :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
#include <stdlib.h>
 
void nodiv(unsigned long * , unsigned long *);
int compar(int , int); //
unsigned long calcul(int , int);
 
int main(int argc , char **argv)
{
    int n,k;
    char *ptr;
 
    printf("Ce programme calcul une combinaison k de n.\n\n");
    printf("\tDonnez n = ");
    scanf("%d",&n);
    printf("\tDonnez k = ");
    scanf("%d",&k);
    printf("La combinaison K de n = %u ",calcul(n,k));
    system("PAUSE");
    return EXIT_SUCCESS;
}
 
unsigned long calcul(int n , int k)
{
    unsigned long p=1,ddv=1;
    int i;
 
    if(n==0 || k==0) return 1;
    for(i=1;i<=compar(n-k,k);i++) // avancement jusqu'à le min de (n-k) e k
    {
                     if(p%i==0)
                     {
                               p=(p/i)*(n-i+1);
                               nodiv(&p,&ddv);
                     }
                     else if ((n-i+1)%i==0)
                     {
                               p*=((n-i+1)/i);
                               nodiv(&p,&ddv);
                     }
                     else
                     {
                               p*=(n-i+1);
                               ddv *=i;
                   /* On garde la valeur de i dans ddv parce qu'il ne divise ni p
                                  ni (n+1-i).
                  La division sur ddv se fait dans la fonction nodiv(int *,int *)
                               */
 
                     }
    }
    return p;
}
 
int compar(int a , int b)
{
     return (a<b? a:b);
     /* renvoie  le min entre (n-k) et k
        Cela pour diminuer le nombres de calculs parcequ'on a une symetrie.
        par exemple les deux couples (50,48) et (50,2) donnent le meme resultat.
     */
}
 
void nodiv(unsigned long *p , unsigned long *ddv)
{
     if(*p%*ddv==0)
     {
                   *p/=*ddv;
                   *ddv = 1;
     }
}

Vous pouvez poser des questions. :wink: