SOS algorithme
coco
-
coco -
coco -
Bonjour,
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
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
- 1
- 2
- 3
Suivant
Résumé de la discussion
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.
-
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é -
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
-
Moi 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... -
Voici 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; } -
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question -
J'ai pas trouvé d'algorithme dans le lien, mais de toute façon je viens de finir le programme en C...
Donc ce coup-ci effectivement on peut dire que le problème est résolu :#include <stdio.h> #include <stdlib.h> const int nMax=5; // Remarque nMax doit être > 1 const int nbUrne=nMax; const int nbBoule=nMax; typedef bool solution[nbUrne][nbBoule]; //la boule numBoule est dans l'urne numUrne si s[numBoule-1][numUrne-1] est vrai void Enregistrer(solution s, int M) // ici un simple affichage, modifiable à volonté { int numBoule,numUrne; for (numUrne=0; numUrne<M; 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(solution s,int N,int M) // N : nombre de boules, M : nombres d'urnes remplies (on a toujours M<=N) { int numUrne; for (numUrne=0; numUrne<M; numUrne++) { s[numUrne][N-1]=true; if (N==nbUrne) Enregistrer(s,M); else Boucle(s,N+1,M); s[numUrne][N-1]=false; } s[M][N-1]=true; if (N==nbUrne) Enregistrer(s,M+1); else Boucle(s,N+1,M+1); s[M][N-1]=false; } void Recherche() { solution s; int numUrne,numBoule; for (numUrne=0; numUrne<nbUrne; numUrne++) for (numBoule=0; numBoule<nbBoule; numBoule++) s[numUrne][numBoule]=false; s[0][0]=true; // la boule 1 est dans l'urne 1 Boucle(s,2,1); // dans "s" on va insérer la boule "2", on a "1" urne remplie } int main(void) { Recherche(); system("PAUSE"); return 0; } -
J'ai pas trouvé d'algorithme dans le lien
Pas l'algorithme, le programme. En Mathematica 3. Mais tu as du sauter par dessus, il ne fait que 6 lignes. Comme quoi certains langages sont plus ou moins bien adaptés à certains types de problèmes :D
En tous cas, bravo KX, ça n'était pas gagné d'avance. -
ton type Bool ne correspond pas vraiment au boolean, il faut modifier dans Enregistrer:
if (s[numUrne][numBoule]==true) printf("%ld ",numBoule+1); -
Ton utilisation de g* me parait compliqué, si j'ai bien compris à quoi il sert, ça doit être un compteur qui te donne le numéro de ton cas... Pourquoi ne pas utiliser une variable globale int g=0; ?
De plus je ne comprends pas la signification du mot clé struct dans ce code :
void Enregistrer(solution s, int M, int *g,struct squence *tabsquence ) // ici un simple affichage, modifiable à volonté
De même qu'avec g, n'est-il pas possible de définir ta structure au début du code, et son instance tabsquence en variable globale ?int g=0; // variable globale struct squence={ ... }; squence tabsequence; // structure globale void Enregistrer(solution s, int M) { int numtache,numachine,k,machinit; k=0; machinit=0; for (numachine=0; numachine<M; numachine++) { printf("Machine %d : ",numachine ); for (numtache=0; numtache<nbtache; numtache++) { if (s[numachine][numtache]==true) { printf(" %d ",numtache); if (numachine==machinit) { tabsquence[g].tabmachine[numachine].tabordo[k].numjob=numtache; k++ ; } else machinit=numachine; // à quoi sert cette ligne ? elle parait suspecte ^^ tabsquence[g].tabmachine[numachine].tabordo[0].numjob=numtache; // cette instruction ne devrait-elle pas être dans le else ??? k=1; // es-tu sûr que c'est bien 1 ici ??? } } printf("\n"); } g++; printf("\n"); } -
Comme ç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!) -
J'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. -
Effectivement 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 -
La 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... -
Je 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 .
-
Je 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
-
Alors 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))
- 1
- 2
- 3
Suivant
