Discussion :

[zhao]

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:

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
    #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 :

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
 
#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();
}

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

[KindPlayer]

je suis pas sur de bien comprendre ce que tu veux faire. Compter le nombre de combinaisons parmis toutes celles possibles contenant au moins 5 (ou 6) numéros gagnant? C'est ça? Heu sinon pour calculer les combinaisons c'est pas plus simple de le faire par récurrence?

[zhao]

non je crois pas , si tu suis mon exemple je joue 10 numeros supposons que le tirage du loto les chiffres suivant sortent :
1 4 5 8 9 10 maintenant tu prends mes 18 combinaisons et tu est sur et certain de trouver AU MOINS une combinaisons ayant 5 numeros gagnant , mais on peut reduire encore ce chiffre de 18 a 15 par exemple mais il faut pour cela faire enormement de tests en verifiant avec mon prog verif combi et je le fais a la main donc comment faire voila je pense que c'est plus clair .
en definitive le probleme est COMMENT trouver le minimum de combinaisons a jouer pour etre sur d'avoir au moins 5 bons numeros gagnants si les 6 du tirage sont parmi ma liste de 10 ?

:-)

je suis pas sur de bien comprendre ce que tu veux faire. Compter le nombre de combinaisons parmis toutes celles possibles contenant au moins 5 (ou 6) numéros gagnant? C'est ça? Heu sinon pour calculer les combinaisons c'est pas plus simple de le faire par récurrence?

[pseudocode]

(Réouverture de la discussion)

Suite à la demande du PO, voici une implémentation Java d'un système réducteur. J'ai essayé de commenter au maximum le programme mais n'hésitez par à poster si ce n'est pas clair.

Une classe qui retourne la liste des tirages possibles (combinaisons C(n,p))

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
/**
 * Enumération des Cnp (stockage sous forme binaire dans un "int") 
 * par exemple
 * 
 * (int)75 = (binaire) 01001011 = (tirage) 1,2,4,7  
 * 
 * @author Xavier Philippeau
 *
 */
public class Cnp {
	private int n,p;
 
	// liste des solutions  
	public int[] results;
 
	// pointeur sur l'element courant de la liste
	private int ptr=0;
 
	public Cnp(int n,int p) {
		this.n=n;
		this.p=p;
 
		// calcul de la taille de la liste des solutions
		// = nombre de combinaisons (n,p) = A(n,p)/!p
		int arrangement = 1, factorielle=1;
		for(int i=0;i<p;i++) {arrangement*=(n-i);factorielle*=(i+1);}
		int combinaison=arrangement/factorielle;
 
		results = new int[combinaison];
 
		build(0,0,0);
	}
 
	// construction recursive des combinaisons possibles
	private void build(int value, int index, int count) {
 
		// impossible de construire une solution
		if ((n-index)<(p-count)) return;
 
		// la combinaison est construite -> ajout a la liste des solutions 
		if (count==p) {
			results[ptr++]=value;
			return;
		}
 
		// explore les 2 chemins possibles pour poursuivre la constuction
 
		// 1. on ne choisit pas l'element numero "index"
		build(value,index+1,count);
 
		// 2. on choisit l'element numero "index"
		build(value+(1<<index),index+1,count+1);
	}
 
	/**
         * Affiche d'une valeur sous forme de chaine texte
         * 
         * @param value valeur sous forme binaire
         * @return la valeur sous forme de chaine texte
         */
	public static String asTicket(int value) {
		StringBuffer sb = new StringBuffer();
		sb.append("[");
		int i=0;
		while(value!=0) {
			i++;
			if ((value & 1)==1) sb.append(i).append(" "); 
			value=value>>1;
		}
		sb.append("]";);
		return sb.toString();
	}
}

La classe du système réducteur avec une heuristique simple, et un methode de monté-carlo pour construire une à une les solutions.

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
import java.util.Arrays;

/**
 * Systeme Reducteur (wheeling system) 
 * 
 * @author Xavier Philippeau
 *
 */
public class SystemeReducteur {

	private final int N,P,K;
	
	/**
	 * @param n,p,k Tirage de P elements parmis N, avec au moins K gagnants
	 */
	public SystemeReducteur(int n, int p, int k) {
		this.N=n;
		this.P=p;
		this.K=k;
	}
	
	/**
	 * Compte le nombre d'elements en commun entre 2 tirages
	 * 
	 * @param value1, value2 2 tirages  
	 * @return le nombre d'elements en commun
	 */
	private int match(int value1,int value2) {
		int and = value1 & value2;
		int bitcount = Integer.bitCount(and);
		return bitcount;
	}
	
	/**
	 * Heuristique pour la recherche des candidats
	 * 
	 * @param value un tirage
	 * @param liste la liste des tirages possibles restants
	 * @return le nombre de fois que ce tirage est gagnant
	 */
	private int score(int value,int[] liste) {
		int score = 0;
		for(int item:liste) {
			if (item==0) continue; // a été supprimé
			int d=match(value,item);
			if (d>=K) score++;
		}
		return score;
	}
	
	/**
	 * retourne la liste des meilleurs tirages
	 * au sens de l'heuristique "score()"
	 * 
	 * @param list la liste des tirages possibles restants 
	 * @return la liste des meilleurs tirages
	 */
	public int[] findCandidats(int[] list) {
		int[] candidats = new int[list.length];
		int count=0;
		
		// recherche exhaustive des meilleures tirages 
		int maxscore=-1;
		for(int item:list) {
			if (item==0) continue; // a été supprimé
			int score = score(item,list);
			if (score>maxscore) {count=0; maxscore=score;}
			if (score==maxscore) candidats[count++]=item;
		}
		return Arrays.copyOf(candidats,count);
	}
	
	/**
	 * Supprime (=mise à zéro) tous les tirages gagnants 
	 * de la liste des tirages possibles
	 * 
	 * @param tirage le tirage de reference
	 * @param list la liste des tirages possibles restants
	 * @return le nombre de tirages possibles restants après suppression
	 */
	public int removeMatching(int tirage, int[] list) {
		int count=0;
		for(int i=0;i<list.length;i++) {
			if (list[i]==0) continue; // a déjà été supprimé
			int match = match(tirage,list[i]);
			if (match>=K) list[i]=0; else count++;
		}
		return count;
	}
	
	/**
	 * retourne une liste des solutions du système de réduction
	 * 
	 * @return la liste des tirages après réduction
	 */
	public int[] computeSolutions() {
		// calcul de la liste de tous les tirages possibles
		int[] tirages = new Cnp(N,P).results;
		int tiragescount=tirages.length;
		
		// allocation de la liste des solutions
		int[] solutions = new int[tirages.length];
		int solutionscount=0;

		// tant qu'il reste des tirages possibles
		while(tiragescount>0) {
			
			// recherche des meilleurs candidats
			int[] candidats = findCandidats(tirages);
			
			// on prend un des candidats, au hasard
			int random = (int)(Math.random()*candidats.length);
			int grille = candidats[random];

			// on ajoute le candidat a la liste des solutions
			solutions[solutionscount++]=grille;

			// on supprime les tirages gagnants de la liste des tirages possibles
			tiragescount=removeMatching(grille, tirages);
		}
		
		// on retourne la liste des solutions 
		return Arrays.copyOf(solutions, solutionscount);
	}
	
	// ------------------------------------------------------------------------
	
	/**
	 * Main: Test du systeme reducteur  
	 */
	public static void main(String[] args) {
		// creation du Systeme Reducteur 10/6/5
		SystemeReducteur tf = new SystemeReducteur(10,6,5);
		
		// calcul des solutions et conserve la meilleure
		int[] bestsolution = null;
		for(int loop=0;loop<100;loop++) {
			int[] solutions = tf.computeSolutions();
			if (bestsolution==null || solutions.length<bestsolution.length) { 
				System.out.println("found a solution of size:"+solutions.length);
				bestsolution=solutions;
			}
		}

		// affiche la meilleure solution
		for(int solution:bestsolution)
			System.out.println(Cnp.asTicket(solution));
	}
}

Résultat pour un systeme 10/6/5

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
found a solution of size:16
found a solution of size:15
found a solution of size:14
[2 3 4 7 9 10 ]
[1 2 5 6 7 10 ]
[1 4 6 8 9 10 ]
[3 4 5 6 7 8 ]
[1 2 3 5 8 9 ]
[1 4 5 7 8 9 ]
[3 4 5 6 9 10 ]
[1 2 3 4 6 7 ]
[2 6 7 8 9 10 ]
[1 2 4 5 8 10 ]
[1 3 5 7 8 10 ]
[1 3 6 7 9 10 ]
[2 3 4 6 8 10 ]
[2 4 5 6 7 9 ]

[zhao]

Bonjour
Pseudocode un seul mot MILLES MERCIS :-)

bon maintenant la question bete ( avant de m'attaquer a ton source:-) ) je voudrais savoir quel sont les etapes a faire pour executer ce programme car je ne connais que le C

autre question je trouve que ton programme est court si je compare avec du C est ce normal ou as tu optimiser ton programme ?

cordialement

je crois comprendre "en gros" ton algo c'est tres beau :-) petites questions :
pourrais tu m'expliquer cette ligne :

* (int)75 = (binaire) 01001011 = (tirage) 1,2,4,7


et celle ci :

@param value valeur sous forme binaire
@return la valeur sous forme de chaine texte

cordialement

[pseudocode]

@param et @return sont dans une zone de commentaire /*...*/ donc ils ne servent a rien d'utile pour le programme.

* (int)75 = (binaire) 01001011 = (tirage) 1,2,4,7

C'est une atuce pour le stockage. Par exemple, pour le tirage 1,2,4,7 on pourrait utiliser un talbeau de 4 int:

int tirage[4];
tirage[0]=1; tirage[1]=2; tirage[2]=4; tirage[3]=7;

Mais ca prend beacoup de place et ce n'est pas facile a manipuler (copier, comparer, ...). La technique que j'utilise permet de représenter un tirage sur un seul "int".

J'utilise le fait qu'un entier a une représentation en binaire en mémoire:
(int)0 = (binaire) 00000000
(int)1 = (binaire) 00000001
(int)2 = (binaire) 00000010
(int)3 = (binaire) 00000011
etc.

Je fais chaque correspondre chaque bit avec un numero de boule. Si le bit=1, alors la boule fait partie du tirage, sinon elle n'en fait pas partie:

(binaire) 00000001 = boule #1 sélectionnée
(binaire) 00000010 = boule #2 sélectionnée
(binaire) 00000100 = boule #3 sélectionnée
(binaire) 00001000 = boule #4 sélectionnée
etc...

donc la combinaison:
(binaire) 01001011 = boules #1 + #2 + #4 + #7 sélectionnées

et ce nombre (binaire) 01001011 est equivalent a l'entier (int)75.

[zhao]

ok je "comprends" un peu mieux mais que fais tu de ce 75 c'est ça que je comprends pas ?

ensuite quelles sont les etapes pour que je puisse executer ton programme ?

tres beau cette maniere de stocker pour gagner de la place , de plus vu que tu travaille avec du binaire je suppose que c'est plus rapide au niveau des tests ?

[pseudocode]

ok je "comprends" un peu mieux mais que fais tu de ce 75 c'est ça que je comprends pas ?

La valeur "75" je n'en fait rien. C'est juste qu'en Java (et en C aussi) il n'y a pas de type "binaire", donc je dois utiliser un type "int".

C'est juste qu'i ne faut donc pas être surpris si on affiche la "valeur" d'un tirage avec un "printf()" car ca affichera 75.

C'est pour ca que j'ai fait une fonction "asTicket()" qui renvoie une représentation humainement compréhensible de ce "int".

ensuite quelles sont les etapes pour que je puisse executer ton programme ?

Il y a une methode "main()" dans la classe "SystemeReducteur". C'est cette methode qui est appelée lorsqu'on lance le programme (comme en C). A partir de la, le programme se déroule entierement.

tres beau cette maniere de stocker pour gagner de la place , de plus vu que tu travaille avec du binaire je suppose que c'est plus rapide au niveau des tests ?

Oui, il y a des fonctions spéciales pour les nombres binaires.

Par exemple, on va devoir comparer 2 tirages pour trouver le nombre de boules en commun. Sous la forme binaire, ca veut dire trouver le nombre de "1" en commun dans les 2 valeurs:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
tirage 1: #1,#2,#4,#7 --> (binaire) 01001011
tirage 2: #2,#6,#7,#8 --> (binaire) 11100010
boules en commun : #2 et #7

L'operation "x AND y" permet de calculer un nouveau binaire qui aura un bit a "1" seulement si les bits correspondants de x et y etaient tous les 2 à "1". C'est une opération tres rapide pour un processeur.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
tirage 1: (binaire) 01001011
tirage 2: (binaire) 11100010
----------------------------
   AND  : (binaire) 01000010

Voila, on sait que le "tirage" commun est (binaire) 01000010 = boules #2 et #7. Pour compter le nombre de boules dans ce tirage, on compte le nombre de bits a "1". Ca tient en quelques lignes dans la methode "match()"

[zhao]

ok maintenant comment j'execute ce programme que j'ai hate de voir fonctionner la bete comment je fais mon executable ? ( question bete je sais mais je sais pas ) en C pas de probleme je compile et hop j'ai un point exe mais quelque chose me dit qu'en java c'est different :-)
j'ai l'impression que ce language Java est tres interessant je ne connaissais pas mais cela semble tres puissant .

merci pour ta patience

[pseudocode]

ok maintenant comment j'execute ce programme que j'ai hate de voir fonctionner la bete comment je fais mon executable ? ( question bete je sais mais je sais pas ) en C pas de probleme je compile et hop j'ai un point exe mais quelque chose me dit qu'en java c'est different :-)
j'ai l'impression que ce language Java est tres interessant je ne connaissais pas mais cela semble tres puissant .

merci pour ta patience

en gros, c'est pareil qu'en C: on compile et on execute. Mais pourquoi tu veux executer ce programme ? Je pensais que tu voulais le traduire en C.

[zhao]

POURQUOI ? ah si tu savais cela fait au moins un an que j'essaie de trouver comment faire ce gennre de programme je vais prendre un grand plaisir a le voire tourner je sais pas si tu me comprends ,de plus je suis curieux de voir le temps qu'il met etc...
le transcrire en C oh la soit en sur meme si je doit apprendre les base du java pour ça :-)

bref c'est une sorte de revanche sur mon incapacité a resoudre ce probleme :-)

on compile les 2 fichiers avec un compilateur specifique ?

cordialement

[pseudocode]

POURQUOI ? ah si tu savais cela fait au moins un an que j'essaie de trouver comment faire ce gennre de programme je vais prendre un grand plaisir a le voire tourner je sais pas si tu me comprends ,de plus je suis curieux de voir le temps qu'il met etc...

Tu va etre déçu. Ce programme utilise une approche monté-carlo, c'est a dire une partie "aléatoire" dans l'algo. Donc tu obtiens des solutions differentes a chaque fois que tu le lances. Rien ne dit que tu trouveras a chaque fois la "meilleur" réduction. Il me trouve une réduction à 14, en moyenne 3 fois sur 4.

on compile les 2 fichiers avec un compilateur specifique ?

hum. C'est pas le forum ideal pour apprendre les bases de Java. Il faudrait que tu lises les tutos, par exemple celui la (au moins la page 2) .

[zhao]

deçu ? certainement pas :-) 3 sur 4 be il suffit de le lancer disons 5 fois et le minimum seras celui le plus bas dans les 5 fois :-)

je vais lire ce tuto ( ou plutot le devorer )

petite question la methode de monte carlo si je comprends bien c'est pour eviter de faire trop de test ?

si tu n'utilisais pas cette methode cela donnerais quoi ?

autre question JAVA semble etre un fabuleux language de programmation peut t'on faire avec java tout ce qu'un programme en language C peut faire ?

[pseudocode]

deçu ? certainement pas :-) 3 sur 4 be il suffit de le lancer disons 5 fois et le minimum seras celui le plus bas dans les 5 fois :-)

Heu... non, ca serait trop simple. Ce n'est pas parce que tu as 1 chance sur 4 de tirer un "coeur", que tu auras toujours un "coeur" au bout de 4 tirages.

petite question la methode de monte carlo si je comprends bien c'est pour eviter de faire trop de test ?

Tout a fait. Quand tu as N choix possibles, tu en prends un au hasard et tu continues.

si tu n'utilisais pas cette methode cela donnerais quoi ?

Tu veux dire tester TOUTES les possibiltés ? Et bien ca serait très, très long.

autre question JAVA semble etre un fabuleux language de programmation peut t'on faire avec java tout ce qu'un programme en language C peut faire ?

Ah. Vaste débat . En fait oui et non.
- Le C est plus performant que Java (en terme de vitesse). Il permet aussi de faire des choses plus "bas niveau" (accès direct a la mémoire, au hardware, ...).
- Java permet de faire les choses en moins de lignes de code (grace a sa grosse bibliotheque de fonctions existante). C'est aussi un langage "orienté-objet", tu verras ce que ca signifie dans les tutos.

Sinon il a aussi les langages fonctionnels (OCaml, Haskell) qui sont particulierement adaptés a ton problème. Bref tout un monde a découvrir.

[zhao]

ok je comprends , je vais telecharger le j2se ( trouver dans ton manuel pour les gosses :-) )et je pense te contacter demain car la il commence a etre tard 22h06 :-)

quand au probleme des cartes "Ce n'est pas parce que tu as 1 chance sur 4 de tirer un "coeur", que tu auras toujours un "coeur" au bout de 4 tirages"

oui mais je sais que j'ai quand meme 25% de chance d'avoir un coeur et plus je fais de tirage sans avoir de coeur et plus j'ai de chance que mon coeur apparaisse au prochain tirage :-) ( enfin je crois :-) )

merci pour tout vraiment merci .
cordialement

[zhao]

escuse je vais rester encore un peu car je viens de penser a un truc :
cela serais difficile pour toi de changer ton programme et rajouter un test ?

on se fixe le minimum que l'on veut trouver et si ce minimum n'est pas trouver on recommence la boucle .
par exemple on sait que pour 10 le minimum c'est 14 tant qu'il ne trouve pas 14 il recommence cela est t'il difficile comme modif ?

merci

[pseudocode]

on se fixe le minimum que l'on veut trouver et si ce minimum n'est pas trouver on recommence la boucle.

cela est t'il difficile comme modif ?

Non, c'est très simple tant qu'on sait quelle valeur on cherche. Il suffit de changer le main()

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
public static void main(String[] args) {
	// creation du Systeme Reducteur 10/6/5
	SystemeReducteur tf = new SystemeReducteur(10,6,5);
 
	// recherche une solution de longueur 14 (ou moins)
	int[] solutions = null;
	do {
		solutions = tf.computeSolutions();			
	} while(solutions.length>14);
 
	// affiche la solution
	for(int solution:solutions)
		System.out.println(Cnp.asTicket(solution));
}

[zhao]

ok oui effectivement c'est pas compliqué .
mais on ne peut pas comme en C au lieu de mettre en dur 10 ,6,5 et 14 grace a un scanf de pouvoir choisir au lancement du programme les valeurs souhaité en java on est obliger de le mettre directement dans le programme ?

autre question ton programme contient 2 sources quand je compile ( car j'ai essayé mais j'ai 100 erreurs :-) ) j'ai tout mis dans un meme fichier bon je sais c'est probablement null mais j'apprends :-)

donc on compile les 2 sources separemment ou il y a aute chose a faire ?

[pseudocode]

ok oui effectivement c'est pas compliqué .
mais on ne peut pas comme en C au lieu de mettre en dur 10 ,6,5 et 14 grace a un scanf de pouvoir choisir au lancement du programme les valeurs souhaité en java on est obliger de le mettre directement dans le programme ?

C'est comme en C. Le main() a un parametre "string[]" qui sont les arguments passés a la ligne de commande. Tu peux les scanner et les utiliser a la place des constantes.

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
public static void main(String[] args) {
	int N=0,P=0,K=0,MAXLENGTH=0;
 
	// lecture des arguments
	if (args.length>=4) {
		N=Integer.parseInt(args[0]);
		P=Integer.parseInt(args[1]);
		K=Integer.parseInt(args[2]);
		MAXLENGTH=Integer.parseInt(args[3]);
	} else {
		System.out.println("besoin des 4 arguments: N P K MAXLENGTH");
		System.exit(1);
	}
 
	// creation du Systeme Reducteur
	SystemeReducteur tf = new SystemeReducteur(N,P,K);
 
	// recherche une solution de la bonne longueur
	int[] solutions = null;
	do {
		solutions = tf.computeSolutions();			
	} while(solutions.length>MAXLENGTH);
 
 
	// affiche la solution
	for(int solution:solutions)
		System.out.println(Cnp.asTicket(solution));
}

autre question ton programme contient 2 sources quand je compile ( car j'ai essayé mais j'ai 100 erreurs :-) ) j'ai tout mis dans un meme fichier

Ah non. Il faut compiler chaque fichier séparément. En plus, il faut que chaque fichier porte le meme nom que la classe => un fichier "Cnp.java" et un fichier "SystemeReducteur.java".

[zhao]

Bonjour Xavier :-)

Jai enfin pu compiler ton programme :-) et je l'ai lancé au debut il ne voulait pas car il manquais dans le MAIn une parenthese fermante ( du moins c'est ce que j'ai supposé car ensuite il a accepté ) et il ne voulait pas de cette ligne :

for(int solution:solutions)
et j'ai mis for(int solution:bestsolution) a la place peut tu me confirmer si c'est ok pour ses 2 oublis car le prog est compiler mais peut etre que cela ne veut rien dire .

pour 10 j'ai bien trouvé les 14 carrément génial ton programme je suis aux anges ce problème m'avais tellement pris la tète quelle revanche :-)

plusieurs questions :

cette ligne a telle un rapport avec le nombre de combinaisons gardées ?
for(int loop=0;loop<100;loop++) si oui il faut donc augmenter le nombre si je cherche par exemple le mini pour 15 6/5 qui est de 143 si je me trompe pas ? je te demande par curiosité car je vois que tu as remplacé par cette ligne :

do {
bestsolution = tf.computeSolutions();
} while(bestsolution.length>MAXLENGTH);

qui prends comme valeur a la plce de 100 le MAXLENGTH c'est pour etre sur de comprendre donc escuse pour la naiveté de mes questions:-)

peut t'on mettre le resultat dans un fichier comme en C sous forme 1 2 3 4 5 6
c'est pour verifier avec mon programme de verification qui as besoin de ce genre de fichier pour 10 pas de probleme je les copies a la main mais par exemple pour 15 c'est un peu long .

derniere question ( pour le moment ;-) ) et la plus importante .

vu ton pseudo aurais tu le pseudocode le plus precis possible pour que puisse bien comprendre ton algo afin d'essayer de le traduire en C ?
Bine cordialement

je voulais te demander j'ai lancer ton programme avec les options suivante :
13 6 5 61 cela fait 2 h qui tourne et n'as pas trouver de solution ( ce qui n'est pas important pour moi au niveau du temps ) mais est ce normal ? ou alors dans ton programme tout est fait pour 10 6 5 14 peut etre qu'il faut augmenter certains choses ( tableau etc..) donc je voulais etre sur avant de le laisser tourner des heures et des heures :-)
pour 13 je met 61 car c'est le minimum a ma connaissance .
cordialement

Bon apres 3h j'ai arreter le programme avec comme argument 13 6 5 61 je prefere attendre tes reponses car il y a quand meme quelque chose de bizarre pour 10 6 5 14 il met quelques minutes a sortir les 14 par curiosité j'ai lancé
avec les parametres suivants :
9 6 5 8 ( je sais que le minimum est 7 mais j'ai mis 8 expres pour avoir un resultat rapide ) et la surprise au bout de 30 mn toujours pas de resultats alors que le mini pour 10 est tres rapide donc je me dit logiquement qu'il y a quelque chose qui va pas quelque part car meme si il faisait toutes les possibilitées pour 9 il aurait deja trouvé bref j'attends ta venue pour comprendre ton programme fait comme si il etait fait pour 10 6 5 14 et uniquement pour ça :-)
cordialement

encore moi :-)

tu vas avoir pas mal de reponses a donner :-)

j'ai pris l'ancienne version sans le MAXLENGTH et j'ai mis dans le programme 9 6 5 et j'ai lancé maintenant je comprends pourquoi il ne trouve pas 8 ( ni 7 bien sur ) car j'ai lancé le programme des dizaines de fois et il me donne comme resultat 12 ( alors que le mini est 7 ) et uniquement 12 donc ton programme a priori ne fonctionne que pour 10 6 5 :-)