Combinatoire tres difficile

Signaler
Messages postés
26
Date d'inscription
vendredi 8 septembre 2006
Statut
Membre
Dernière intervention
7 août 2008
-
Messages postés
212
Date d'inscription
mardi 17 mai 2005
Statut
Membre
Dernière intervention
23 juin 2011
-
Bonjour a tous .
Voila un probleme que je n'arrive pas a resoudre ( je suis un neophyte ) et pardon pour mon francais je suis etranger .

probleme du loto ( non je ne joue pas car cela n'existe pas dans mon pays ) probleme qui devient une obscetion et faut que j'arrete :-)

j'ai un premier programme qui genere toutes les combinaisons C(x,y) par exemple pour 10 je vais en genrer 210 jusqu'a la c'est facile ensuite j'ai un deuxieme programme qui en fonction des combinaisons que je joue me dit combien j'ai de gagnant a 3 ,4 , 5 , 6 numeros .

le but c'est d'avoir le minimum de combinaisons a jouer pour etre sur d'avoir 5 bon numeros dans au moins une de mes combinaisons si les 6 numeros gagnant sont parmi ma liste par exemple je veux jouer 10 numeros supposons que les 6 numeros gagnants sont parmi mes 10 et bien j'ai trouvé comme mini ( mais on peut descendre plus bas d'ou mon probleme) 18 combinaisons les voici :

1 2 3 4 5 6
1 2 3 4 7 8
1 2 3 4 9 10
1 2 3 5 7 9
1 2 3 5 8 10
1 2 3 6 7 10
1 2 3 6 8 9
1 2 4 5 7 10
1 2 4 5 8 9
1 2 4 6 7 9
1 2 4 6 8 10
1 2 5 6 7 8
1 2 5 6 9 10
1 2 7 8 9 10
3 4 5 6 7 8
3 4 5 6 9 10
3 4 7 8 9 10
5 6 7 8 9 10

vous pouvez verifier que quelque soit la combinaison que vous prenez parmi les 10 j'aurais au moins une de mes 18 combinaisons qui en auras 5 .

ce resultat je l'ai fait a la main avec mon programme verif_combi voila comment je procede je prends d'office la premiere combi soit 1 2 3 4 5 6 que je met dans un fichier ensuite je rajoute la deuxieme et je test dans verif_combi ce que cela donne ( il faut essayer ce programme pour comprendre ) et je continue en essayant toutes les posisibilitées possible le but c'est trouver le minimum de combinaisons qui me donneras comme rsultat combi a 4=0 combi a 3=0 etc... pour que je n'ai que des combi a 5 et a 6 .
mais a la main c'est tres tres long enfin vous imaginez :-)
donc comment faire pour programmer ce genre de chose y a t'il une ame charitable qui pourrais me le faire peut etre avec un algo de type dichtra ( j'ai lu ca quelque part ) car les chemin possible sont enorme .
merci beaucoup de votre aide.
cordialement

PROGRAMME GENERATEUR DE COMBINAISONS:

#include <stdio.h>
// #define nb_boules 8 /* indiquer ici le nombre de numero de votre Loto */
/*
Generer toutes les combinaisons du Loto (Francais, donc avec 49 numeros)
Le programme va generer un fichier texte contenant 13983816 combinaisons.
Compilation :
gcc -o Loto49 Loto49.c
*/

int main(void) {
int i,j,k,m,n,p,nb_boules,nb_combi=0,pause;
printf("NOMBRE DE BOULES --> ");
scanf("%d",&nb_boules);
FILE * fichier; /* pointeur sur le fichier de sauvegarde des resultats */

fichier=fopen("combinaisons_brut.txt","w"); /* resultats.txt est le nom du fichier */

printf("Debut du programme\nPatientez...\n\n");

for(i=1;i<=nb_boules-5;i++)
for(j=i+1;j<=nb_boules-4;j++)
for(k=j+1;k<=nb_boules-3;k++)
for(m=k+1;m<=nb_boules-2;m++)
for(n=m+1;n<=nb_boules-1;n++)
for(p=n+1;p<=nb_boules;p++)
{
nb_combi++;
fprintf(fichier,"%d %d %d %d %d %d\n",i,j,k,m,n,p); /* on ecrit les combinaisons dans le fichier */
}
fprintf(fichier,"nombre de combinaisons %d ", nb_combi);
fclose(fichier);
printf("Le programme a termine. Fin;)\n\n");
printf("nombre de combinaisons %d ", nb_combi);
scanf("%d",&pause);;
return 0;
}


*******************************************************************************************

PROGRAMME VERIFICATION DES COMBINAISONS :

#include<fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <dos.h>
#include <time.h>


main()
{
FILE *fichier ;
int w=0,z=0,f=0,y=0,u=0,max=0,v=0,numscommuns,cptc=0;
float cpt0=0,cpt1=0,cpt2=0,cpt3=0,cpt4=0,cpt5=0,cpt6=0;
int i=0,j=0,k=0,l=0,m=0,n=0,zz=0,a=0,nt=0,xx=0,c=0;
int x[250][6];
int tab[6];
int tc[6];
int line;
float temp_reel=0,temp_ecoule=0;
time_t deb_total,fin_total,deb_reel,fin_reel;
bool stop;

//PARCOUR FICHIER ET CHARGEMENT TABLEAU ***************************************
if (fichier =fopen ("Combinaisons.txt", "r")) { //Si ouverture réussie : note le if pour fopen (alors true soit false)
while (!feof(fichier)) {
for (u=0 ; u<6 ; u++) {
if (fscanf (fichier, "%d", &y)==1) { x[w][u] = y; }
}//End for u...
w++;//Compteur de combinaisons contenues dans le fichier
}//End while...
fclose (fichier); // fermeture du fichier
if (w>0) { printf("Le fichier contient %d ligne(s)\n", w); }//Vérif lignes lues
}//End if...
else { //Si échec d'ouverture : if fopen retourne false et alors on arrive ici
printf("Echec a l'ouverture du fichier.\n");
printf("Appuyez sur n'importe quelle touche pour quitter.");
getchar();
exit(0); }
// FIN PARCOUR FICHIER ET CHARGEMENT TABLEAU **********************************

printf("Entrez votre nombre de numeros : ");
scanf("%d",&nt);
//nt=10;
printf("\n");
deb_reel=time(NULL);
a=nt-5;

for(i=1;i<=a;i++)
for(j=i+1;j<=a+1;j++)
for(k=j+1;k<=a+2;k++)
for(l=k+1;l<=a+3;l++)
for(m=l+1;m<=a+4;m++)
for(n=m+1;n<=a+5;n++)
{
tc[0]=i;tc[1]=j;tc[2]=k;tc[3]=l;tc[4]=m;tc[5]=n;
cptc++;

for (z=0, max=0; z<w ;z++) {

for (u=0, numscommuns=0; u<6 ; u++) //Comparaison
for(xx=0; xx<6; xx++)
if(x[z][u]==tc[xx]) { numscommuns++; }

if (numscommuns > max) { max = numscommuns; } //Stocker le max trouvé
}//End z...

if(max==6) { cpt6++; }
if(max==5) { cpt5++; }
if(max==4) { cpt4++; }
if(max==3) { cpt3++; }
if(max==2) { cpt2++; }
if(max==1) { cpt1++; }
if(max==0) { cpt0++; }
// printf("progression : %d\r",cptc);//Vérifie la progression en test
// getchar();
}//End boucle imbriquée i..n

fin_reel=time(NULL);
temp_reel=difftime(fin_reel,deb_reel);
printf("\r");//Effacer la ligne "progression"
printf(" 6 numeros = %g fois\n",cpt6);
printf(" 5 numeros = %g fois\n",cpt5);
printf(" 4 numeros = %g fois\n",cpt4);
printf(" 3 numeros = %g fois\n",cpt3);
printf(" 2 numeros = %g fois\n",cpt2);
printf(" 1 numeros = %g fois\n",cpt1);
printf(" 0 numeros = %g fois\n",cpt0);
printf(" TOTAL = %g\n",cpt6+cpt5+cpt4+cpt3+cpt2+cpt1+cpt0);
printf("\n");
printf("duree reelle de calcul : %g seconde(s)\n",temp_reel);
scanf(" %d ",nt);
getchar();
}

***************************************************************************************

6 réponses

Messages postés
212
Date d'inscription
mardi 17 mai 2005
Statut
Membre
Dernière intervention
23 juin 2011

Salut,

Si j'ai bien compris, tu veux faire un programme qui génère toutes les combinaisons possible à 5 ou 6 digit ?

Cordialement,
Sébastien.
Messages postés
26
Date d'inscription
vendredi 8 septembre 2006
Statut
Membre
Dernière intervention
7 août 2008

Bonjour sebastien .
humm je sais pas je suis neophite ;-)

ce que je veux c'est essayer de trouver ( dans mon exemple pour une selection de 10 chiffres) le minimum de grilles qui reponds a cette contrainte :

SI les 6 numeros sortis sont dans ma selection de 10 ALORS je suis sur qu'une de mes combinaisons parmi les 18 ( ou moins si cela est possible) a au moins 5 bons numeros .

donc le probleme est complexe du moins pour moi ;-)
j'avais pensé aussi que peut etre on pourrais faire un programmme qui me sorte tous les groupes possible de 18 ,20,etc... bref au choix et ensuite les verifier directement dans mon petit programme verif le probleme c'est que je sais pas comment programmer ce genre de chose , generer des combinaisons je sais faire mais des groupe de combinaisons je sais pas et ensuite il faut les passer dans mon programme verif bref j'ai vraiment besoin d'aide mais c'est dommage car en realité une fois que quelqu'un a trouver comment on fait pour generer des groupes il suffit de rajouter dans ce programme mon code de verification :-)

cordialement
Messages postés
212
Date d'inscription
mardi 17 mai 2005
Statut
Membre
Dernière intervention
23 juin 2011

Salut Zaho77,

Tu veux trouver un nombre minimum de combinaisons à 5 ou 6 digit
qui appartiennent au tirage du loto (6 digit parmi 49)...
Ça me fait penser à quelqu'un qui veux un Algorithme pour gagner au loto (lol).

On parle donc ici de Combinaison sans répétition:
on utilise donc les coefficient binomiaux , noté C(n k), avec C(n k) = n! / k!(n - k)!
soit dans notre cas C(6 49) =  (44 * 45 * 46 * 47 * 48 * 49) / ( 1* 2 * 3 * 4 * 5 * 6) = 13983816;
jusque là on est d'accord.

Après je ne te suis plus:
"Si les 6 numéros sortis sont dans ma sélection de 10 ALORS je suis sur
qu'une de mes combinaisons parmi les 18 ( ou moins si cela est
possible) a au moins 5 bons numéros."
Si tu tires 6 chiffres entre 1 et 10 tous tes tirages correspondent...

En revanche si tu veux connaitre le nombre minimum de combinaisons de 5 chiffres sur une population de 10,il faut calculer C(5 10) (10 * 9 * 8 * 7 * 6) / ( 1 * 2 * 3 * 4 * 5) 252 possibilités

Donc si tu veux connaître le nombre de combinaisons de 6 digit dont 5 appartiennent au 6 tiré sur 49,
ça va être dur à tester, mais encore plus dure à générer...

Peut être que j'ai encore mal compris, si c'est le cas reformule ta question, sinon  je ne voit pas bien l'intéret.

Cordialement,
Sébastien.
Messages postés
26
Date d'inscription
vendredi 8 septembre 2006
Statut
Membre
Dernière intervention
7 août 2008

Bonjour Sébastien .
j'ai pris 10 car plus simple a comprendre.

supposons que le LOTO n'as pas 49 numeros mais 10 .

si je veux etre sur de gagner le gros lot pas le choix je suis obliger de jouer 210 combinaisons .

maintenant supposons que je me contente de gagner que 5 numeros .
je vais essayer de jouer un minimum de grilles qui me permette de gagner a coup sur 5 numeros A LA CONDITION que les 6 bon numeros soit dans ma selection la pas de probleme car je joue tout les chiffres du loto ( 10 au lieu de 49 )
maintenant prends n'importe laquelle des 210 combinaisons et tu est sur de trouver dans mes 18 combi gardées au moins une combinaison qui a 5 numeros en commun avec n'importe laquelle de ses 210 combinaisons voila je ne peut etre plus simple .
cordialement
Messages postés
1
Date d'inscription
jeudi 2 juillet 2009
Statut
Membre
Dernière intervention
2 juillet 2009

Bonjour,
Je crois que tes combinaisons sont bonnes !
Il m'arrive de jouer mais pas au loto et j'aimerais savoir ce que donnerait ton approche pour plus de numéros ?
Messages postés
212
Date d'inscription
mardi 17 mai 2005
Statut
Membre
Dernière intervention
23 juin 2011

Bonsoir,

avec le temps, je crois que je viens de comprendre... (lol)

Cordialement,
Sébastien.