SOS algorithme
slt tt le monde ca fait un moment que cherche a touver un algorithme mais je arrive pas ,je sais po pourkoi ,a premier vue il doit pas etre tres dur mais moi je bogue completement ,alors c vous pourraier m'aider ou me donner juste une aide commet faire,
voila le probleme :
suppose que tu as n urnes (sac..) identique et n balles differentes et tu veut avoir tt les cas possible de distribution de ces balle sur ses urnes , exemple
c tu as 2 urnes alors tu as 2 balles ----> 2 cas :
1 cas : urnes 1 contient la balle 1 et l 'urne 2 contient la balle 2 (ou contrire )
2 cas :urne 1 contient les deux balle (c pareil que urne 2 contient les 2 balle puisque identique )
pour 3 urnes et 3 balles on a 5 cas
pour 4 on a 15 cas
pour 5 on a 40 cas
je cherche a le codé en C
pour la prtie calcul de nombre de cas j ai fait deja ca ,
moi je cherche a affecter pour chaque cas les balle et suvgarder tt les cas ,pour pour pouvoir les afficher c-a-d si je veut verifier les belle de 1 er cas il doit m afficher que j ai la belle 1 dans l 'urnes 1 et la belle 2 dans l urne 2;
pour 3 urnes et 3 balle c 5 cas •
cas 1 • U1=(balle1), U2=(balle 2), U3=(belle 3),
cas 2• U1=(1,2), U2=(3),
cas 3• U1=(1,3), U2=(2),
cas4• U1=(2,3), U2=(1),
cas 5• U1=(1,2,3),
pour ma part moi j ai consederé les cas comme des sequence alors j essyer de le faire sous forme de structure avec des place pour mettre les balles
juste pour rappel llaffecation U1=(1,2) ,U2=( ) ,U3=(3) , et pariel que U1 =( ) , S2=(1,2) ,U3=(3)
j espere ke c clair maintenant
merci d'avance pour votre aide
Configuration: Windows XP Firefox 1.5.0.9
46 réponses
Le problème consiste à énumérer les partitions d'un ensemble de n balles distinctes dans des urnes identiques, et le comptage évoqué n'est pas le bon pour n=5, qui est 52. Plusieurs réponses proposent d'identifier ce problème comme l'énumération des partitions d'un ensemble et d'implémenter en C soit une approche récursive, soit une méthode fondée sur une base numérique. Des codes partagés dans la discussion montrent des solutions variées, notamment une approche avec boucles et structures pour enregistrer chaque cas, et une autre basée sur une énumération en base U^B. En outre, la discussion précise que pour n=5 le nombre exact est 52 et que certaines propositions visent à réduire la complexité, passant d'exponentielle à des méthodes plus efficaces.
-
ModérateurComme ça je dirais que c'est une imbrication de boucles for... (même s'il faudra surement le traiter autrement)
for(Balle1=0; Balle1<nombreDUrnes; Balle1++)
for(Balle2=0; Balle2<nombreDUrnes; Balle2++)
for(Balle3=0; Balle3<nombreDUrnes; Balle3++)
(...)
for(BalleMax=0; BalleMax<nombreDUrnes; BalleMax++)
Masi ce genre d'algorithme va faire exploser ta complexité O(n!) -
Bonjour
Si j'ai bien compris, tes balles sont différentes mais tes urnes identiques.
Ce que tu cherches à faire, c'est donc à énumérer toutes les partitions d'un ensemble à N éléments . Il y en a 52 et non pas 40 pour 5 éléments ( D'après Wikipédia, je n'ai pas vérifié)
http://fr.wikipedia.org/wiki/Partition_(math%C3%A9matiques)
Malheureusement, ça ne répond pas à ta question sur l'algorithme. Laisse tomber les boucles imbriquées, il faut écrire un programme différent pour chaque valeur de N
Je n'ai pas la bonne réponse, mais elle passe sûrement par la récursivité -
ModérateurJ'ai réussi à faire ça avec des boucles virtuellement imbriquées par des appels récursifs...
Mais j'ai quelques cas en trop...#include <stdio.h> #include <stdlib.h> const int nbUrne=2; const int nbBoule=3; void Boucle(bool g[nbUrne][nbBoule], int numBoule) { int numUrne; if (numBoule<=nbBoule) { for (numUrne=1; numUrne<=nbUrne; numUrne++) { g[numUrne][numBoule]=false; Boucle(g,numBoule+1); g[numUrne][numBoule]=true; Boucle(g,numBoule+1); } } else { for (numUrne=1; numUrne<=nbUrne; numUrne++) { printf("Urne %ld : ",numUrne); for (numBoule=1; numBoule<=nbBoule; numBoule++) if (g[numUrne][numBoule]) printf("%ld ",numBoule); printf("\n"); } printf("\n"); } } int main(void) { bool g[nbUrne][nbBoule]; Boucle(g,0); system("PAUSE"); return 0; } -
slt , je suis en train de verifer l'algo mais juste pour le nombre de boulle et d'urne tu as donnee les chiffre 2 et 3 au hasard ? parceque dans mon cas le nombre de boule doit etre agale au nombre d'urne,
si j bien compris ton algorithme peut etre generalisé sur tt les cas possible. -
ModérateurEffectivement j'ai pris 2 et 3 au hasard, mais si ils sont égaux ça changerait rien...
La seule chose que je n'ai pas faite, c'est éliminé les cas absurde (très nombreux) où la boule apparait dans plusieurs urnes en même temps...
Tu voulais une idée pour savoir comment faire, je t'ai apporté l'idée, à toi de voir ce que ça peux donner... -
et pour toi le pere le nombre de cas pour 5 et bien 40 et pas 52
le nombre de cas et calculer comme suit
A=1+ somme(j=2-->j=m) somme (i=0--> i=max(0,m-j-i) (m-i)!/j!(m-i-j)!
int i,j,sum,x,y;
sum=1;
for(j=2;j<=m;j++){
y=j+1;
x=fdim(m,y);
for (i=0;i<=x;i++)
sum=sum+fact(m-i)/(fact(j)*fact(m-j-i)); -
slt
KX juste pour ta boucle
for (numUrne=1; numUrne<=nbUrne; numUrne++)
{
g[numUrne][numBoule]=false;
Boucle(g,numBoule+1);
g[numUrne][numBoule]=true;
Boucle(g,numBoule+1);
tu n'est pa en train de marquer par false et puis de le refaire par true , je comprend pas bien l utilite des deux boucle ensemble ; -
pour toi la matrice g represent koi exatctement ,et je pense que toi tu suvgarde pas les etats ,alors que moi j ai besoin de suvgarder les etats pour un autre traitement ,parce que ca c que une partie de l esemble de l algo,mais dans ton programme je voit bien ou est le resultat finale (cad ,les urnes et les boule dedans )
pour la 2 eme partie de la fonction le if c normal que il ce retrouve seul sans test logique -
ModérateurLa grille g contient toutes les possibilités, et il faut la comprendre comme ça :
g[numUrne][numBoule] est vrai si la boule numBoule est dans l'urne numUrne
Et c'est pour ca qu'il faut vérifier (ce que je n'ai pas fait) qu'il y ait une seule fois la valeur true pour une même boule numBoule, sinon ça voudrait dire qu'une boule est dans plusieurs urnes en même temps...
En ce qui concerne ton enregistrement des cas tu peux (tu dois) modifier cette partie là du code :printf("Urne %ld : ",numUrne); for (numBoule=1; numBoule<=nbBoule; numBoule++) if (g[numUrne][numBoule]) printf("%ld ",numBoule); printf("\n");C'est aussi dans ce morceau de code qu'il faut que tu fasses la vérification que j'ai expliquée... -
ModérateurJe ne sais pas comment tu veux faire ta procédure d'enregistrement mais voici un complément de code :
#include <stdio.h> #include <stdlib.h> const int nbUrne=3; const int nbBoule=3; bool CasFavorable(bool g[nbUrne][nbBoule], int numBoule) { int cpt=0; // compte le nombre d'urne où est la boule numBoule int numUrne; for (numUrne=1; numUrne<=nbUrne; numUrne++) if (g[numUrne][numBoule]) cpt++; return (cpt==1); // la boule est dans une urne (et une seule) } bool GrilleCorrecte(bool g[nbUrne][nbBoule]) // toutes les boules sont une fois et une seule dans l'urne { int numBoule; for (numBoule=1; numBoule<=nbBoule; numBoule++) if (!CasFavorable(g,numBoule)) return false; return true; } void Boucle(bool g[nbUrne][nbBoule], int numBoule) { int numUrne; if (numBoule<=nbBoule) { for (numUrne=1; numUrne<=nbUrne; numUrne++) { g[numUrne][numBoule]=false; Boucle(g,numBoule+1); g[numUrne][numBoule]=true; Boucle(g,numBoule+1); } } else if (GrilleCorrecte(g)) { // Enregistrer(g); for (numUrne=1; numUrne<=nbUrne; numUrne++) { printf("Urne %ld : ",numUrne); for (numBoule=1; numBoule<=nbBoule; numBoule++) if (g[numUrne][numBoule]) printf("%ld ",numBoule); printf("\n"); } printf("\n"); } } int main(void) { bool g[nbUrne][nbBoule]; Boucle(g,0); system("PAUSE"); return 0; }Pour ton enregistrement : à chaque grille correcte tu as un nouveau cas à enregistrer, et tu peux savoir si une boule "b" est dans une urne "u" si g[u,b] est vrai...
PS. j'ai pas compilé voir si ça marchait, mais ça devrait pas loin d'être bon... -
merci pour les effort que t as fait pour le programme je vait voir ca pour le principe ,et pour l enregistrement je doit cree un tableau pour chaque cas avec les num de boules dedans parce que comme j t avait ditt j ai besoin de ca .
-
ModérateurJe vais regarder moi aussi de mon côté... Par contre ATTENTION grosse erreur de ma part, à chaque fois j'ai fais des boucles de 1 à N au lieu de les faire de 0 à N-1, il faudra donc faire une correction dans ce sens
-
ModérateurAlors j'ai remis en place toutes mes idées, et après avoir réalisé que j'avais fait plusieurs boulettes, il m'était impossible de ne pas apporter un correctif ^^
#include <stdio.h> #include <stdlib.h> const int nbUrne=2; const int nbBoule=2; typedef bool grille[nbUrne][nbBoule]; void Enregistrer(grille g) // ici un simple affichage { int numBoule,numUrne; for (numUrne=0; numUrne<nbUrne; numUrne++) { printf("Urne %ld : ",numUrne); for (numBoule=0; numBoule<nbBoule; numBoule++) if (g[numUrne][numBoule]) printf("%ld ",numBoule); printf("\n"); } printf("\n"); } bool CasFavorable(grille g, int numBoule) { int cpt=0; // compte le nombre d'urne où est la boule numBoule int numUrne; for (numUrne=0; numUrne<nbUrne; numUrne++) if (g[numUrne][numBoule]) cpt++; return (cpt==1); // la boule est dans une urne (et une seule) } bool GrilleCorrecte(grille g) // toutes les boules sont une fois et une seule dans l'urne { int numBoule; for (numBoule=0; numBoule<nbBoule; numBoule++) if (!CasFavorable(g,numBoule)) return false; return true; } void Boucle(grille g, int numUrne, int numBoule) { if (numUrne<nbUrne) { if (numBoule<nbBoule) { g[numUrne][numBoule]=false; Boucle(g,numUrne,numBoule+1); g[numUrne][numBoule]=true; Boucle(g,numUrne,numBoule+1); } else // numBoule=nbBoule : on saute à la ligne suivante { g[numUrne][numBoule]=false; Boucle(g,numUrne+1,0); g[numUrne][numBoule]=true; Boucle(g,numUrne+1,0); } } else // numUrne=nbUrne { if (numBoule<nbBoule) { g[numUrne][numBoule]=false; Boucle(g,numUrne,numBoule+1); g[numUrne][numBoule]=true; Boucle(g,numUrne,numBoule+1); } else // numBoule=nbBoule : fin du tableau { g[numUrne][numBoule]=false; if (GrilleCorrecte(g)) Enregistrer(g); g[numUrne][numBoule]=true; if (GrilleCorrecte(g)) Enregistrer(g); } } } int main(void) { grille g; int numBoule,numUrne; for (numUrne=0; numUrne<nbUrne; numUrne++) for (numBoule=0; numBoule<nbBoule; numBoule++) g[numUrne][numBoule]=false; Boucle(g,0,0); system("PAUSE"); return 0; }PS. Il doit y avoir tous les cas mais il y a surtout beaucoup de doublons, il faudrait que dans ton enregistrement tu vérifies à chaque fois que l'élément inséré n'existe pas déjà...
D'un point de vue de la complexité c'est très moche...
Calcul rapide je dirai O(2^(nbUrne*nbBoule)) -
ModérateurRemarque : la plupart des doublons sont consécutifs, en se souvenant de la dernière grille traitée on peut donc supprimer la majorité des doublons...
Pour nbUrne=3 et nbBoule=3 j'avais 3456 résultats et en utilisant cette méthode pour enlever les doublons je n'en garde plus que 53 (certes il y a encore des doublons mais nettement moins)
Voici ce que ça change au début :#include <stdio.h> #include <stdlib.h> const int nbUrne=3; const int nbBoule=3; typedef bool grille[nbUrne][nbBoule]; grille mem; bool Egal(grille g) { int numBoule,numUrne; for (numUrne=0; numUrne<nbUrne; numUrne++) for (numBoule=0; numBoule<nbBoule; numBoule++) if (g[numUrne][numBoule]!=mem[numUrne][numBoule]) return false; return true; } void Memoriser(grille g) { int numBoule,numUrne; for (numUrne=0; numUrne<nbUrne; numUrne++) for (numBoule=0; numBoule<nbBoule; numBoule++) mem[numUrne][numBoule]=g[numUrne][numBoule]; } void Enregistrer(grille g) // ici un simple affichage { if (Egal(g)) return; // on ne traite pas 2 fois consécutives la même grille else Memoriser(g); int numBoule,numUrne; for (numUrne=0; numUrne<nbUrne; numUrne++) { printf("Urne %ld : ",numUrne); for (numBoule=0; numBoule<nbBoule; numBoule++) if (g[numUrne][numBoule]) printf("%ld ",numBoule); printf("\n"); } printf("\n"); }Et à la fin :int main(void) { grille g; Memoriser(g); int numBoule,numUrne; for (numUrne=0; numUrne<nbUrne; numUrne++) for (numBoule=0; numBoule<nbBoule; numBoule++) g[numUrne][numBoule]=false; Boucle(g,0,0); system("PAUSE"); return 0; } -
Si j'ai compris quelque chose au problème, il y a bien 52 solutions pour n=5 (mais je n'ai peut-être pas compris le problème)
1 solution (5) 12345 5 solutions 4+1 1234 5 1235 4 1245 3 1345 2 2345 1 10 solutions 3+2 123 45 124 35 125 34 134 25 135 24 145 23 234 15 235 14 245 13 345 12 10 solutions 3+1+1 (les mêmes que ci-dessus, en séparant le groupe de 2) 15 solutions 2+2+1 (il y en a 3 pour chaque solution de 4+1) 1234 5 -> 12 34 5 13 24 5 14 23 5 1235 4 -> 12 35 4 13 25 4 15 23 4 1245 3 -> 12 45 3 14 25 3 15 24 3 1345 2 -> 13 45 2 14 35 2 15 34 2 2345 1 -> 23 45 1 24 35 1 25 34 1 10 solutions 2+1+1+1 12 3 4 5 13 2 4 5 14 2 3 5 15 2 3 4 23 1 4 5 24 1 3 5 25 1 3 4 34 1 2 5 35 1 2 4 45 1 2 3 1 solution 1+1+1+1+1 1 2 3 4 5
-
ModérateurMoi je ne me suis pas du tout occupé de la théorie...
Et d'ailleurs je vais essayer de trouver un autre algorithme parce que celui que j'ai fait est de complexité exponentielle O(2^n²) alors qu'on peut faire mieux
Par contre je ne vois pas pourquoi [ 1 _ | 2 _ ] et [ 2 _ | 1 _ ] seraient 2 cas identiques, ils ont la même probabilité d'exister mais c'est tout...
pour n=3 tu as n^n=27 cas :123|...|... 12.|..3|... 12.|...|..3 1.3|.2.|... 1..|.23|... 1..|.2.|..3 1.3|...|.2. 1..|..3|.2. 1..|...|.23 .23|1..|... .2.|1.3|... .2.|1..|..3 ..3|12.|... ...|123|... ...|12.|..3 ..3|1..|.2. ...|1.3|.2. ...|1..|.23 .23|...|1.. .2.|..3|1.. .2.|...|1.3 ..3|.2.|1.. ...|.23|1.. ...|.2.|1.3 ..3|...|12. ...|..3|12. ...|...|123
Si tu considères que 123|...|... , ...|123|... et ...|...|123 sont la même chose tu dis qu'ils ont la même chance d'arriver or en les cumulant on a 1/27+1/27+1/27 = 3/27
Mais si tu considères que 12.|..3|... , 12.|...|..3 , ..3|12.|... , ...|12.|..3 , ..3|...|12. et ...|..3|12. sont la même chose ça donne une probabilité cumulé de 6/27 !
Il faudrait donc bien que tu distingue les cas !!!
PS. j'essaye dans la journée de faire un algorithme un peu plus efficace qui donne les n^n résultats (hier j'étais parti sur une mauvaise idée), si tu veux absolument dire que c'est la même chose , tu feras le trin dans mes résultats... -
ModérateurVoici un algorithme nettement plus efficace que celui que j'avais proposé avant
L'algorithme repose sur une énumération de tous les nombres à nbBoule chiffres dans la base nbUrne.
Le Nème chiffre ainsi obtenu correspond à la Nième boule dont la valeur correspond à l'urne dans laquelle elle est...
Il ne restera plus qu'à modifier la procédure Enregistrer qui n'est chez moi qu'un simple affichage des solutions.
Si B=numBoule et U=numUrne, la complexité du programme est en (2U+1).B.U^B = O( B.U^B )
Hier elle était en O( 2^(B.U) ).
#include <stdio.h> #include <stdlib.h> const int nbUrne=3; const int nbBoule=2; typedef bool solution[nbUrne][nbBoule]; int diviseur[nbBoule]; int InitDiviseur() { int numBoule; int facteur=1; for (numBoule=nbBoule-1; numBoule>=0; numBoule--) { diviseur[numBoule]=facteur; facteur*=nbUrne; } return facteur; } void Enregistrer(solution s) // ici un simple affichage, modifiable à volonté { int numBoule,numUrne; for (numUrne=0; numUrne<nbUrne; numUrne++) { printf("Urne %ld : ",numUrne+1); for (numBoule=0; numBoule<nbBoule; numBoule++) if (s[numUrne][numBoule]) printf("%ld ",numBoule+1); printf("\n"); } printf("\n"); } void Boucle() { int i,j,numUrne,numBoule,facteur; solution s; facteur=InitDiviseur(); for (i=0; i<facteur; i++) { // on "efface" s for (numUrne=0; numUrne<nbUrne; numUrne++) for (numBoule=0; numBoule<nbBoule; numBoule++) s[numUrne][numBoule]=false; j=i; // calcul en base "numUrne" for (numBoule=0; numBoule<nbBoule; numBoule++) { numUrne=j/diviseur[numBoule]; s[numUrne][numBoule]=true; j=j%diviseur[numBoule]; } Enregistrer(s); } } int main(void) { Boucle(); system("PAUSE"); return 0; } -
Bonjour,
Si tu considères que 123|...|... , ...|123|... et ...|...|123 sont la même chose tu dis qu'ils ont la même chance d'arriver or en les cumulant on a 1/27+1/27+1/27 = 3/27 Non, personne d'autre que toi ne dit ça. Personne n'a jamais dit que toutes les solutions avaient la même probabilité. En fait, il n'est absolument pas question de probabilités dans ce problème.
je ne vois pas pourquoi [ 1 _ | 2 _ ] et [ 2 _ | 1 _ ] seraient 2 cas identiques parce que l'énoncé dit :
tu as n urnes (sac..) identique. Si tu considères qu'inverser le contenu de deux urnes donne une solution distincte, ça veut dire quoi que les urnes sont identiques ?
Si tu distingues les urnes, les nombres de solutions n'a plus aucun rapport avec ceux que donne coco.
Je reste persuadé que le problème soumis est celui du nombre de partitions d'un ensemble fini, c'est pour ça que l'énoncé précise des nombres égaux de boules et d'urnes.
Il faudrait éliminer tous les doublons générés par ton programme du message 18, mais c'est un sacré boulot. Par exemple, pour N=6, il faudrait générer 46656 solutions pour n'en garder que 203. J'imagine que quand N augmente, on va très vite bloquer à cause du N^N alors que le nombre de solutions réel est encore raisonnable. -
ModérateurJ'ai trouvé un algorithme qui répond au problème et qui devrait je pense pouvoir se mettre en C ensuite...
Normalement les 52 solutions que j'ai doivent être le même que celles du post 16 de le père mais ici elles sont mises "dans l'ordre" conformément à mon algorithme (récursif)1 1,2 1,2,3 1,2,3,4 1,2,3,4,5 1,2,3,4/5 1,2,3/4 1,2,3,5/4 1,2,3/4,5 1,2,3/4/5 1,2/3 1,2,4/3 1,2,4,5/3 1,2,4/3,5 1,2,4/3/5 1,2/3,4 1,2,5/3,4 1,2/3,4,5 1,2/3,4/5 1,2/3/4 1,2,5/3/4 1,2/3,5/4 1,2/3/4,5 1,2/3/4/5 1/2 1,3/2 1,3,4/2 1,2,4,5/2 1,2,4/2,5 1,2,4/2/5 1,3/2,4 1,3,5/2,4 1,3/2,4,5 1,3/2,4/5 1,3/2/4 1,3,5/2/4 1,3/2,5/4 1,3/2/4,5 1,3/2/4/5 1/2,3 1,4/2,3 1,4,5/2,3 1,4/2,3,5 1,4/2,3/5 1/2,3,4 1,5/2,3,4 1/2,3,4,5 1/2,3,4/5 1/2,3/4 1,5/2,3/4 1/2,3,5/4 1/2,3/4,5 1/2,3/4/5 1/2/3 1,4/2/3 1,4,5/2/3 1,4/2,5/3 1,4/2/3,5 1,4/2/3/5 1/2,4/3 1,5/2,4/3 1/2,4,5/3 1/2,4/3,5 1/2,4/3/5 1/2/3,4 1,5/2/3,4 1/2,5/3,4 1/2/3,4,5 1/2/3,4/5 1/2/3/4 1,5/2/3/4 1/2,5/3/4 1/2/3,5/4 1/2/3/4,5 1/2/3/4/5
Je pense que l'algorithme se comprend facilement grâce à l'exemple... -
l'algorithme se comprend facilement grâce à l'exemple
Malheureusement non pour moi. Depuis cet après-midi (pendant mon footing ... ), je suis dans la situation irritante où je 'vois bien' ce qu'il faut faire et ça correspond bien à ton exemple, mais quand j'essaye de le mettre noir sur blanc je n'y arrive pas. Mes idées ne sont pas encore assez claires.
- 1
- 2
- 3