Construire le triangle de pascal d'apres la formule des C(n, p) [Résolu]

[BStylene]

Bonjour, le programme construit et affiche le triangle de pascal selon la formule C(n, p) = n!/p!(n-p)! . Mon code source compile très bien et affiche le triangle pour n = 1 à 12, a partir de n >= 13, le programme affiche le triangle mais avec de faux coefficient.
Voici mon code source

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
int main(int argc, char *argv[])
{
    unsigned long exposant, nbre, r, i;
    printf("Entrez un exposant : ");
    scanf("%lu", &exposant);
    for(i = 0; i <= exposant; i++)
    {
        for(nbre = 0; nbre <= i; nbre++)
        {
            r = combinaison(i, nbre);
            printf("%4.lu", r);
        }
        printf("\n");
    }
    return 0;
}
 
unsigned long factorielle(unsigned long nbre)
{
    unsigned long resultat = 1;
        while(nbre)
        {
            if(nbre == 0)
            resultat = 1;
            else
            {
                resultat *= nbre;
                nbre--;
            }
        }
    return resultat;
}
 
unsigned long combinaison(long p, long q)
{
    unsigned long resultat = 0;
    if(q == 0 && p == 0)
    resultat = 1;
    else
    resultat = factorielle(p)/(factorielle(q)*factorielle(p-q));
    return resultat;
}

Merci d'avance.

[_-Slash-_]

Chez moi (FreeBSD, testé avec clang et gcc) cela fonctionne très bien si ce n'est 5 warnings :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
triangle.c:15:29: warning: implicit conversion changes signedness: 'unsigned long' to 'long' [-Wsign-conversion]
            r = combinaison(i, nbre);
                ~~~~~~~~~~~ ^
triangle.c:15:32: warning: implicit conversion changes signedness: 'unsigned long' to 'long' [-Wsign-conversion]
            r = combinaison(i, nbre);
                ~~~~~~~~~~~    ^~~~
triangle.c:45:28: warning: implicit conversion changes signedness: 'long' to 'unsigned long' [-Wsign-conversion]
    resultat = factorielle(p)/(factorielle(q)*factorielle(p-q));
               ~~~~~~~~~~~ ^
triangle.c:45:44: warning: implicit conversion changes signedness: 'long' to 'unsigned long' [-Wsign-conversion]
    resultat = factorielle(p)/(factorielle(q)*factorielle(p-q));
                               ~~~~~~~~~~~ ^
triangle.c:45:60: warning: implicit conversion changes signedness: 'long' to 'unsigned long' [-Wsign-conversion]
    resultat = factorielle(p)/(factorielle(q)*factorielle(p-q));
                                              ~~~~~~~~~~~ ~^~
5 warnings generated.

[Winjerome]

Bonjour,

Dans un premier temps corrige les avertissements montrés par _-Slash-_, puis je t'invite à regarder le résultat de ceci :

Code :

1
2
3
unsigned long i, exposant = 16;
for(i= 0 ; i<=exposant ; i++)
    printf("%2lu => %lu\n" , i , factorielle(i));

et à te souvenir de la valeur maximale que peut prendre un unsigned long sur ta machine

[BStylene]

Envoyé par _-Slash-_

Chez moi (FreeBSD, testé avec clang et gcc) cela fonctionne très bien si ce n'est 5 warnings :

Code :

Chez moi ça compile sans erreur, j'utilise codeblock sous windows
le programme fonctionne très bien pour n <=12, pour n = 13 ou plus ça affiche le triangle mais pas avec les bons coefficients a partir de n = 13
Merci.

[BStylene]

Envoyé par Winjerome

Bonjour,

Dans un premier temps corrige les avertissements montrés par _-Slash-_, puis je t'invite à regarder le résultat de ceci :

Code :

et à te souvenir de la valeur maximale que peut prendre un unsigned long sur ta machine

En comparant les valeurs des n! données dans votre code avec celle de la calculatrice de windows, j'ai remarqué qu'a partir de n = 13, les valeurs ne concordaient plus, et comme vous me l'avez signalé je crois que c'est unsigned long qui ne peut pas prendre la valeur des des factorielles pour n >=13, c'est de la que vient l'erreur.
Est-ce-qu'il y a une façon d'y remedié?
Merci.

[_-Slash-_]

Envoyé par BStylene

Chez moi ça compile sans erreur, j'utilise codeblock sous windows
le programme fonctionne très bien pour n <=12, pour n = 13 ou plus ça affiche le triangle mais pas avec les bons coefficients a partir de n = 13
Merci.

Il faut voir comment est configuré le compilateur. Chez moi j'ai ces options :

Code :

1
2
 
-O2 -Wchar-subscripts -Wcomment -Wformat=2 -Wimplicit-int -Werror-implicit-function-declaration -Wmain -Wparentheses -Wsequence-point -Wreturn-type -Wswitch -Wtrigraphs -Wunused -Wuninitialized -Wunknown-pragmas -Wfloat-equal -Wundef -Wshadow -Wpointer-arith -Wbad-function-cast -Wwrite-strings -Wconversion -Wsign-compare -Waggregate-return -Wstrict-prototypes -Wmissing-prototypes -Wmissing-declarations -Wmissing-noreturn -Wformat -Wmissing-format-attribute -Wno-deprecated-declarations -Wpacked -Wredundant-decls -Wnested-externs -Winline -Wlong-long -fstack-protector-all

[diogene]

Il ne faut pas procéder de cette façon : Pour calculer C(n,p) tu passes par le calcul de n! qui est rapidement très grand devant la valeur de C(n,p) et qui va dépasser la capacité de l'entier utilisé et donc fausser le résultat.

La meilleure solution, et la plus rapide, est de calculer C(n,p+1) à partir du calcul de C(n,p) par la relation

C(n,p+1)=C(n,p)*(n-p)/(p+1)

Code :

1
2
3
4
5
6
7
8
9
10
11
12
...
    for(i = 0; i <= exposant; i++)
    {
        r = 1;
        for(nbre = 0; nbre <= i; nbre++)
        {
            printf("%4lu", r);
            r = r*(i-nbre)/(nbre+1);
        }
        printf("\n");
    }
...

[BStylene]

Envoyé par _-Slash-_

Il faut voir comment est configuré le compilateur. Chez moi j'ai ces options :

Code :

Je ne sais pas ou configuré le compilateur, on utilise pas le même OS peut-être c'est pour cela que nous avons pas les mêmes configurations et erreur de compilation

[BStylene]

Envoyé par diogene

Il ne faut pas procéder de cette façon : Pour calculer C(n,p) tu passes par le calcul de n! qui est rapidement très grand devant la valeur de C(n,p) et qui va dépasser la capacité de l'entier utilisé et donc fausser le résultat.

La meilleure solution, et la plus rapide, est de calculer C(n,p+1) à partir du calcul de C(n,p) par la relation

C(n,p+1)=C(n,p)*(n-p)/(p+1)

Code :

Merci ça résout bien le problème de capacité de unsigned long

[Sve@r]

Envoyé par diogene

La meilleure solution, et la plus rapide, est de calculer C(n,p+1) à partir du calcul de C(n,p) par la relation

C(n,p+1)=C(n,p)*(n-p)/(p+1)

Bonjour
Moi j'ai une solution que je pense encore meilleure et encore plus rapide
Si on se souvient que C(n, p) et C(p-n, p) sont identiques et peuvent se calculer en bouclant de n à p
Exemple: C(3, 8) = C(5, 8) = 6 x 7 x 8 / 1 x 2 x 3

Et si en plus on prend en compte les valeurs particulières C(1, p)=1; C(2, p) = 2; C(p-2, p)=2 et C(p-1, p)=1 on peut encore optimiser un peu plus

Ce qui donnerait

Code c :

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
// Calcul de la combinaison C(x, y) par simplification de la fraction
unsigned long comb(
	unsigned short col,			// Colonne
	unsigned short lig)			// Ligne
{
	// Déclaration des variables
	unsigned short i;				// Indice de boucle
	unsigned short j;				// Indice de boucle
	unsigned short pivot;			// Pivot de départ de la multiplication
	unsigned long res;			// Résultat de la combinaison
 
	// Si on est en première ou dernière colonne (facultatif mais optimise la fonction)
	if (col == 0 || col == lig)
		return 1;				// Valeur du triangle connue
 
	// Si on est en seconde ou avant-dernière colonne (facultatif mais optimise la fonction)
	if (col == 1 || col == (lig - 1))
		return lig;				// Valeur du triangle connue
 
	// Recherche du pivot (point à partir duquel on commencera à multiplier)
	pivot=(lig - col) > col ?(lig - col) :col;
 
	// Calcul de la combinaison par multiplication et division simultanée
	res=1;
	for (i=pivot + 1, j=1; i <= lig; i++, j++)
		res=res * i / j;
 
	// Renvoi du résultat
	return res;
}

La multiplication et division simultanée dans le calcul du résultat lui évite de monter trop haut par rapport à sa capacité (dans laquelle on gagne encore une puissance de 2 par l'utilisation du unsigned)...

[diogene]

@Sve@r
Je crois que tu as inversé dans ta notation c(x,y) celle utilisée par l'auteur du post qui est C(n,p) = n!/p!/(n-p)! et (je crois) que tu notes C(p,n) = n!/p!/(n-p)!

Et si en plus on prend en compte les valeurs particulières C(1, p)=1; C(2, p) = 2; C(p-2, p)=2 et C(p-1, p)=1

?? Ces valeurs particulières sont erronées.

Compte tenu du programme proposé, qui n'est pas de calculer les C(n,p) dans un ordre aléatoire, mais dans un ordre bien particulier, la formule de récurrence permet de calculer un élément par cette unique opération : C(n,p+1)=C(n,p)*(n-p)/(p+1).

[Sve@r]

Envoyé par diogene

@Sve@r
Je crois que tu as inversé dans ta notation c(x,y) celle utilisée par l'auteur du post qui est C(n,p) = n!/p!/(n-p)! et (je crois) que tu notes C(p,n) = n!/p!/(n-p)!

Moui probable. J'ai utilisé "lig" et "col" sensées représenter une ligne et colonne particulière du triangle de Pascal...

Envoyé par diogene

?? Ces valeurs particulières sont erronées.

Exact, pas tiptop de poster les yeux encore embrumés de sommeil...
C(0, p)=1, C(1, p)=p, C(p-1, p)=p et C(p, p)=1

Envoyé par diogene

Compte tenu du programme proposé, qui n'est pas de calculer les C(n,p) dans un ordre aléatoire, mais dans un ordre bien particulier, la formule de récurrence permet de calculer un élément par cette unique opération : C(n,p+1)=C(n,p)*(n-p)/(p+1).

Mais n'est-ce pas mieux d'avoir une fonction pouvant calculer directement et facilement n'importe quel C(n, p) sans avoir à calculer ou mémoriser les C(n, p) précédents ??? Une fonction plus générale et elle non plus pas gourmande en termes de grandeur de nombres pourra s'adapter à ce cas particulier tout en restant utilisable pour d'autres problèmes utilisant C(n, p)...