Discussion :

[ccensam]

Salut ça fais 1 semaine que j'essaye d'ecrire un programme qui calcule
exactement et cela pour des nombres un peu grands sans depasser la limite de unsigned int.
Quelqu'un à une bonne idée.!

[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

[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)

[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 ????

[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

[ccensam]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.