nombre de combinaisons

Bonjour,

Je voulais stocker le résultat dans un tableau pour l'utiliser après donc ce tableau qui sera allouer dynamiquement mais le problème est combien on doit réserver des cases pour ce tableau car le résultat ne contient pas toutes les combinaisons sauf de taille 2 jusqu'à taille N?
Si on N=4 alors le nombre de toutes les combinaisons sont :

Code:

---

1 2 3

int nombre; nombre=pow(2,N);

---

Mais en réalité la taille de tableau est inférieur que 'nombre' alors pour la libération après de ce tableau est ce que je fais jusqu'à la taille 'nombre' ou bien jusqu'à le nombre des cases réellement remplies?

Est ce que on peut déterminer par une formule ou autre ? :
- les combinaisons de taille 2: ici on a 6 si N=4
- les combinaisons de taille 3: ici on a 4 si N=4
- les combinaisons de taille 4: ici on a 1 si N=4

Quel l'équivalent de cette formule en C ?

Merci.

C'est a toi de determiner le nombre de case que tu veux avoir.

Je n'ai pas compris comment tu determine le nombre de case que tu veux, mais si tu as une formule pour connaitre cette taille, alors fais ceci :

Code:

---

1 2 3 4 5 6

int nombreDeCase;   /* Ton traitement pour savoir ton nombre de case */   Tableau = malloc (sizeof(/* Type */ * nombreDeCase));

---

Si je n'ai pas repondu a ta question, reformule la correctement s'il te plait.

Citation:

---

Mais en réalité la taille de tableau est inférieur que 'nombre' alors pour la libération après de ce tableau est ce que je fais jusqu'à la taille 'nombre' ou bien jusqu'à le nombre des cases réellement remplies?

---

Tu dois désallouer tout ce que tu as alloué : Si tu as alloué par p = malloc(....), tu désalloues par free(p);

Citation:

---

Est ce que on peut déterminer par une formule ou autre ? :
- les combinaisons de taille 2: ici on a 6 si N=4
- les combinaisons de taille 3: ici on a 4 si N=4
- les combinaisons de taille 4: ici on a 1 si N=4

---

Le nombre de combinaisons de taille p est N!/p!/(N-p)!

Citation:

---

Le nombre de combinaisons de taille p est N!/p!/(N-p)!

---

Oui.
Quelle est l'équivalent de cette formule en C ?

Il y a des fonctions prédéfinies en C pour cette formule?

Citation:

---

Envoyé par siempre

Il y a des fonctions prédéfinies en C pour cette formule?

---

Non il faut que tu les crées toi-même ...

Je ne sais plus comment on appel '!', mais elle n'est pas presente dans math.h.
Cependant, refaire cette fonction est tres facile:

Code:

---

1 2 3 4 5 6 7 8 9 10 11

int FonctionMystere (int nombre) { int resultat = nombre; int i;   for (i=2, i<nombre ; i++) resultat *= i;   return resultat; }

---

et ensuite, il ne reste plu qu'a l'appliquer :

Code:

---

1 2	N!/p!/(N-p)!

---

Code:

---

1 2	FonctionMystere (N) / FonctionMystere (p) / FonctionMystere (N-p);

---

Ps : vous etes sur que la formule est bonne ?
Il me semblait que c'etait :

Code:

---

1 2 3 4

N! Combinaison = ----------- p!(N-p)!

---

C'est la factorielle :ccool:
Mais bon je trouve que l'utilisation de la factorielle est assez limitée en C parce qu'on dépasse vite la capacité d'une variable :roll:

Ahhhhhhhhhhhh

pitin je l'aurai longtemps chercher celle la !!

Sinon, il y a la librairie GMP pour les depassement de capacité memoire ou l'utilisation des doubles. Apres, c'est a voir quelle va etre la plage de valeur prise par le nombre mis a la factorielle

Citation:

---

Ps : vous etes sur que la formule est bonne ?
Il me semblait que c'etait :

Code:

---

1 2 3

N! Combinaison = ----------- p!(N-p)!

---

---

C'est bien cette formule que j'ai écrite (avec les conventions d'évaluation du C)
C(N,p) == N!/p!/(N-p)! == (N!/p!)/(N-p)!

Citation:

---

Sinon, il y a la librairie GMP pour les depassement de capacité memoire ou l'utilisation des doubles. Apres, c'est a voir quelle va etre la plage de valeur prise par le nombre mis a la factorielle

---

Il ne faut pas partir du calcul des factorielles mais des relations du genre :
C(N,p) = N/(N-p) * C(N-1,p) = N/p *C(N-1,p-1)

Arf, effectivement, ca marche.

apres, ce sont des simplification mathematique qu'il faut connaitre, c'est un peu dur de les deviner si on a pas l'habitude

C'est mieux d'utiliser une version récursive ou itérative de cette solution au niveau moins consommation de mémoire ?

Pour remplacer un entier en long, on remplace 'int' par 'long' et dans l'affichage '%d' par '%ld" ?

Merci.

Citation:

---

C'est mieux d'utiliser une version récursive ou itérative de cette solution au niveau moins consommation de mémoire ?

---

Les versions itératives sont en général plus rapides et présentent beaucoup moins de risques de saturer la pile mémoire. Mais elles sont parfois moins esthétiques.

Citation:

---

Pour remplacer un entier en long, on remplace 'int' par 'long' et dans l'affichage '%d' par '%ld" ?

---

Oui