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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
| package xxx;
import java.util.*;
public class xxx {
public static void main(String[] args ) {
Scanner keby = new Scanner(System.in);
System.out.println("Veuillez saisir le nombre d’étudiants :");
//la liste des étudiants;
int n=keby.nextInt();
String [][] tabEtud = new String[n][4];
System.out.println("Veuillez saisir le nombre pair d’étudiant incompatible :");
//liste de pair étudiants incompatible dans le même dortoir
int n1=keby.nextInt();
String [][] tabEtudInc = new String[n1][2];
System.out.println("Veuillez saisir le nombre d’étudiants à sélectionné par pair :");
//duex étudiants par dortoir qui correspond à 2*nombres de dortoirs;
int m=keby.nextInt();
String [][] tabEtudSelect = new String[m][2];
Integer Indice=0;
String clobalId="001";
String choix ;
do
{
System.out.println("------Menu principal ---------");
System.out.println(" 1. Liste d’étudiants ");
System.out.println(" 2.Liste d’étudiants incompatibles ");
System.out.println(" 3. Sélection d’étudiants ");
System.out.println(" 4.Quitter ");
System.out.println(" Taper votre choix : ");
choix = keby.nextLine();
switch(choix)
{
case "1": saisieEtudiant (tabEtud, keby);
break;
case "2": saisieIncompatibilite (tabEtudInc, keby);
break;
case "3": Selection ( tabEtudSelect, tabEtud , tabEtudInc , keby, clobalId, Indice);
break;
default: System.out.println("Veuillez respecter le menu!");
}
}
while(choix!="4");
}
public static void saisieEtudiant(String [][] tabEtud, Scanner keby) {
int n=tabEtud.length;
int i=0;
String idEtud;
String nom;
String prenom;
String adresse;
do {
System.out.println("Veuillez saisir l’Id de l’étudiants :");
idEtud=keby.nextLine();
tabEtud[i][0]= idEtud;
System.out.println("Veuillez saisir le nom de l’étudiants :");
nom=keby.nextLine();
tabEtud[i][1]=nom;
System.out.println("Veuillez saisir le prénom de l’étudiants :");
prenom=keby.nextLine();
tabEtud[i][2]=prenom;
System.out.println("Veuillez saisir l’adresse de l’étudiants :");
adresse=keby.nextLine();
tabEtud[i][3]=adresse;
i =i+1;
} while (i<n);
}
public static void saisieIncompatibilite (String [][] tabEtudInc, Scanner keby) {
int n=tabEtudInc.length;
String idEtud1;
String idEtud2;
int i=0;
do {
System.out.println("Veuillez saisir l’Id de l’étudiant1 incompatible:");
idEtud1=keby.nextLine();
tabEtudInc[i][0]= idEtud1;
System.out.println("Veuillez saisir l’Id de l’étudiant2 incompatible:");
idEtud2=keby.nextLine();
tabEtudInc[i][1]= idEtud2;
i =i+1;
} while (i<n);
}
//la selection se fait par tirage au sort;
public static void Selection (String [][] tabEtudSelect, String [][]tabEtud , String [][]tabEtudInc , Scanner
keby,String clobalId, Integer Indice) {
int n= tabEtud.length;
Boolean Ajouter =false ; // à chaque selection Ajouter=vrai pur sortir du while et revenir dans for
String [][] tabTirage = new String[1][2]; //les deux tirés sont rangés et puis remplacer au tirage suivant;
ArrayList<String> tabEtudCopy = new ArrayList< String > (); // mets la liste étudiant dans ArrayList
par rendre facile le traitement;
ArrayList<String> tabEtudSelectCopy = new ArrayList< String > (); //recupère les selection et à la
sortie recopierra dans tabEtudSelect
for(int i = 0; i<n; i++)
{
// transfert de la liste &tudiant dans la copie
tabEtudCopy.add ( tabEtud[i][0] ) ;
}
System.out.println("Veuillez saisir le nombre de chambres:");
// permet de saisir en fonction du nombres de dortoirs
int c = keby.nextInt();
String id1;
String id2;
String idRe;
for(int i = 0; i<c; i++) {
Ajouter=false; // chaque ajout egal vrai pour sortir du do while
do {
Random random = new Random (); // tirage au sort ou nombre aleatoire
int nb;
n = tabEtudCopy.size() ; // determine le nombre elements dans etudiant
nb = random.nextInt(n); // choix dans l'intervale 0 et n
id1 = tabEtudCopy.get(nb); // si id1 est retenu alors l'etudiant de id1 serra selectionné
clobalId=id1;
idRe = recherche (tabEtudInc , clobalId, Indice); // est ce id1 est dans la liste des incompatibilié
if (idRe == "-1" ) {
// si non alors il est ajouté
tabTirage[0][0]=id1; // il est rangé dans le tirage;
tabEtudCopy.remove(nb); // supprimé dans ce tableau pour eviter de tombe sur la meme valeur au
prochain tirage
n= tabEtudCopy.size();
nb = random.nextInt(n);
id2 = tabEtudCopy.get(nb);
tabTirage[0][1]=id2; // son binomme est aussi tiré (je crois que vous comprenez le processus)
tabEtudCopy.remove(nb);
Ajouter=true; // il est à vrai pour revenir dans for et passer au seconde chambre
}
else {
//sinon alors on cherche le second et on verifie s'il sont incompatibles
tabEtudCopy.remove(nb); // evidemment il faut supprimer id1 avant
n= tabEtudCopy.size();
nb = random.nextInt(n);
id2 = tabEtudCopy.get(nb);
if (((id1 == tabEtudInc[Indice][0]) && (id2 != tabEtudInc[Indice][1])) || ((id1 == tabEtudInc[Indice][1]) && (id2 != tabEtudInc[Indice][0]))){
// si le marriage est possible alors on les tire tous les deux
tabTirage[0][0]=id1;
tabTirage[0][1]=id2;
tabEtudCopy.remove(nb);
Ajouter=true;
}
else
tabEtudCopy.add(id1);
/*
sinon le mariage n'est pas possible alors
on remet dans la table tabEtudCopy l'id1 qui a été supprimé pour recommencer
sans changer de chambre;
donc Ajouter reste toujours à false;
*/
}
} while (Ajouter==false);
// les deux tirés sont rangés dans la selection
n = tabEtudSelectCopy.size() ;
tabEtudSelectCopy.add ( tabTirage[0][0] ) ;
tabEtudSelectCopy.add ( tabTirage[0][1] ) ;
}
/*
recuperation de la selection en array ou tableau static si le travail est finit;
mais je dis à tabEtudCopy et tabEtudSelectCopy merci car leurs souplesses m'ont rendu
la tâche assez facile
*/
int j=0;
for(String elem:tabEtudSelectCopy )
{
tabEtudSelect[j][0]= elem; // recuperation
j++;
}
}
public static String recherche (String [][]tabEtudInc , String clobalId, Integer Indice){
int n= tabEtudInc.length;
String sortietest="-1"; // on cherche les incompatibilités et sort avec "-1" si id n'existe pas
for( int i = 0; i < n ; i++) {
for(int j = 0; j < 2; j ++ ) {
if ( clobalId.equals(tabEtudInc [ i ][ j ]) ) {
Indice= i ;
sortietest = tabEtudInc [ i ][ j ] ;
}
}
}
return sortietest ;
}
} |
Une aide pour trouver la complexité de cet algorithme
Répondre avec citation
Partager