SOS algorithme

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

46 réponses

KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
Remarque : 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;
}
0
le père
 
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.
0
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
J'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...
0
le père
 
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.
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
Bon alors j'explique l'algorithme, j'essaierai de le mettre en C quand j'aurais un peu de temps...

On part du cas N=1, avec la solution triviale 1

Puis pour le cas N+1, on considère chaque solution du cas N (qui utilise M urnes)
On complète la solution N en rajoutant la boule N+1 à chacune des urnes possibles (entre 1 et M+1)

Exemple : en partant de la solution 1,4/2/3 (N=4, M=3)
On rajoute la boule N+1=5 aux urnes allant de 1 à M+1=4

On rajoute la boule 5 à l'urne 1 : 1,4,5/2/3 (N=5, M=3)
On rajoute la boule 5 à l'urne 2 : 1,4/2,5/3 (N=5, M=3)
On rajoute la boule 5 à l'urne 3 : 1,4/2/3,5 (N=5, M=3)
On rajoute la boule 5 à l'urne 4 : 1,4/2/3/5 (N=5, M=4)

Est-ce plus clair ?

D'un point de vue programmation on voit bien se profiler l'utilisation d'une récursivité dont le cas terminal sera (N=1, M=1) et dont chaque appel récursif fera appel à la solution précédente et au couple (N, M)...
0
le père
 
Merci beaucoup pour ta réponse, je la regarderai à tête reposée. Mais en première lecture, j'ai l'impression que tu ne présentes que l'ébauche de l'algorithme, qui me fait la même impression que ma propre idée. On 'voit bien', mais je ne serai satisfait que quand j'aurai un véritable algorithme noir sur blanc. Si j'y consacre le temps nécessaire et que j'y arrive, je reviendrai le mettre ici.
Je ne sais pas si ça intéresse toujours coco ?
0
coco
 
slt
alors la tu crois pas c bien dire ,bein sur ke s m'interse moi uassi je vait voir de mon cote ,j fait une petite recherche ca me semble que le nombre de cas suit le nombre de BELL
http://mathforum.org/advanced/robertd/bell.html
0
le père
 
Bonjour coco

le nombre de cas suit le nombre de BELL
C'est bien ce que disait le lien de mon message n°2.

Mais je vois que dans ton lien à toi, il y a le programme, YAPUKA traduire en C... ton problème est résolu ;)
0
coco
 
slt
comme le programme ne voulait pas s 'executer sur le dev a cause de type booleen j ai changer ca declaration

#include <stdio.h>
#include <stdlib.h>

const int nMax=3;//Remarque nMax doit être > 1
const int nbUrne=3;
const int nbBoule=3;
typedef enum {true,false} Bool; ----------------> ici


typedef Bool solution[3][3];





est voila le resultat je VOIS AFFICHER

Urne 1: en principe ici il va avoir 1 2 3

Urne1: 3
Urne2 : 1 2

Urne1: 2
Urne 2: 1 3

Urne1: 2 3
Urne 2: 1

Urne1: 2 3 Urne 1: 1
Urne2 : 1 3 ici Urne 2: 2
Urne3: 1 2 Urne 3: 3

alors si je me trompe pas pour l afichage des autre cas ca depond de le boule enregistrer, ou c cas que je voit sont ceux uniquement calculer par l'algorithme .parce que j eesyer avec 4 cas ,je voit bien que la meme boule peut etre dans deux urne different exatement dans 7/15 cas ce que fait ke les vrai cas il ne reste que 7 (exemple dans l exemple precedent la boule 1 revient deux fois (23,13,12);
0
coco
 
juste pour expliquer apres excution on voit afficher les truc a gauche alors que il faut les trucs a droit

Urne1: 2 3 ---------------------------------->Urne 1: 1
Urne2 : 1 3 -----------------------------------> Urne 2: 2
Urne3: 1 2 ------------------------------------>Urne 3: 3
0
coco
 
1001 merci pour votre aide ,et tt vous effort ca ma bien aidé
l'algorithme fonction tres bien ,
0
togodo Messages postés 148 Date d'inscription   Statut Membre Dernière intervention   8
 
Na tu pas penser a insérer du prolog dans ton code c?
0
coco
 
slt ,je connais pas ce language tu pourrai pas me dire un peu plus ,peut etre il est intressent .
j ai vue sur google mais je comprend pas comme le rendre compatible avec le C
0
togodo Messages postés 148 Date d'inscription   Statut Membre Dernière intervention   8
 
Prolog est un langage de programmation logique donc n'est pas un langage impératif ( comme la plupart de ceux qu'on utilise couramment java,C,c#, vb, cobol, etc....).

En gros, les langage impératifs sont des programmes ou des ordres sont données (des instructions).

Or en prolog (et dans les autres langages de programmation logique), on établies des prédicats et le but d'un programme est donc de satisfaire au prédicats (l'ordinateur te balance toutes les variables possibles (dans un ordre quand même) jusqu'au moment ou il établit que le prédicat principal est satisfait (="méthode" principale) ou irréalisable (après avoir énuméré tout les solutions qu'il a testé donc toutes les combinaisons de variables possibles)).

Donc en gros le principe est de justement de ne jamais trouvé de solution (il te balancera tout les valeurs possible mais en te disant qu'il a rien trouvé) et d' écrire chaque combinaison qu'il trouve.

Alors pour le rendre compatible sur c je sais que c'est faisable mais pas comment (car g vu un cours d' université à liege (je pense)où ils intègrent du prolog dans du code c).
J'essaierais de trouver le moyen.
0
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
Insérer du Prolog en C n'a aucun intérêt si on est pas capable de faire du Prolog alors qu'on est capable de faire du C...
D'autant que le C s'est tout de suite imposé dans la résolution du problème puisque c'est le langage qu'utilise Coco !
0
togodo Messages postés 148 Date d'inscription   Statut Membre Dernière intervention   8
 
Ok pas de soucis.
C'étais juste une question à la base.
Et puis le programme est fini de toute façon.
0
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
Alors juste pour répondre à ta question, oui on peux mettre du Prolog en C !

Après une recherche rapide il semble que l'on puisse utiliser ce genre de code :
     #include <sicstus/sicstus.h>
     
     SP_pred_ref
     SP_predicate(char *name_string,
     	     long arity,
     	     char *module_string);
À condition bien sûr de posséder la librairie SICStus

Il y a surement d'autres méthodes qui le permettent (voir aussi SWI-Prolog C++)
0
coco
 
slt
merci pour les infos
je crois je vait rest encore sur le C .
une question :
Est t'il possible en C d' introduire une structure dans une fonction ???
0
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
Que veux tu dire par là ?

Une structure définit un nouveau type, tu peux utiliser les éléments de ce nouveau type n'importe où dans ton programme y compris dans une fonction !

Si c'est pas ça explique un peu plus ce que tu voudrais faire...
0
coco
 
la je suis sur la 2 eme partie de mon probleme qui consite a a considérer que chaque cas genere je doit sauvgarder chaque cas avec les num boul et la num urne ou elle se trouve
exemple de ma structure
tabcas[*g].taburne[numurne].tabboule [k].numboul
c-a-d
pour 3urne et 3 boulle
le cas 1 avec l’urne 1 dedans les boule 1 ,boule 2 ,boule 3
le cas 2 avec urne 1 dedans la boule 1 ,boule 3
le cas 2 avec urne 2 dedans la boule 3
…..
.
.
.
.
. ect ….
c''est une structure ou chaque cas a ces urnes ou chaque urne a ces plalace pour placer les boules
0
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
Ne serait-il pas plus simple de repartir de mon type solution ?
typedef bool solution[nbUrne][nbBoule];

Ensuite si tu veux l'enregistrer tu ouvres un fichier binaire, et à chaque fois qu'un cas arrive dans la procédure enregistrer tu l'enregistre dans le fichier... À la fin du programme tu fermes le fichier et c'est fini !

En plus le type bool ne prend qu'un bit (du moins en C++, en C il n'existe pas donc j'en sais rien)
Ça veut dire que par exemple pour N=5, tu as 5*5=25 bits par cas
Et donc avec 52 cas ça te donne 1300 bits=163 octets !!!

L'avantage de mon type solution c'est que chaque cas a la même taille, la façon dont tu veux le faire paraît plus dur et moins efficace...
0
muco45 Messages postés 441 Date d'inscription   Statut Membre Dernière intervention   65
 
0
coco
 
re slt KX tu pourrai pas me donner une idee comme pouvoir renvoyer les valeur de num boule et num urne et le numero de cas a MAIN pour les traiter (evidament a fur et a mesure ),pour les traiter chaquen a part
merci d avance
0
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
Peux-tu donner un exemple de ce que tu veux faire ?
0
coco
 
Enregistrer(solution s, int M, int *g ) // ici un simple affichage, modifiable ‡ volontÈ
{




int numtache,numachine,k;
k=0;




printf("seq=%ld \n ",*g);
return (*g); --------------------------------> ici vers main
for (numachine=0; numachine<M; numachine++)
{
printf("Machine %ld : ",numachine );
for (numtache=0; numtache<nbtache; numtache++)
if (s[numachine][numtache]==true){
printf("%ld ",numtache);

return (numtache); --------> comme ici vers main
}
printf("\n");
return (numachine); -----------> comme ici vers main
}
*g=*g+1;
printf("\n" );
}



main()
{


int g=0;

Recherche( &g);
sequene =*g;
urne =num urne ;
balle =num boule ;
////pour povoir construir a fur et a mesure mes sequences avec les urnes et le num de belle dedans ,
si je peut le faire aussi dans la fonction enregitrer aussi c era bien bien mais dans ce derner cas je sais pas comme faire pour declaer une structure dans une fonction
system("PAUSE");

}
0