IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Une aide pour trouver la complexité de cet algorithme


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur Java
    Inscrit en
    avril 2015
    Messages
    330
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Guinée

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Associations - ONG

    Informations forums :
    Inscription : avril 2015
    Messages : 330
    Points : 0
    Points
    0
    Par défaut Une aide pour trouver la complexité de cet algorithme
    Bonjour;

    Je voudrais votre idée sur la complexité de l'algorithme de ce programme ci-dessous:

    Le programme consiste à faire la sélection de 100 ou 200 ou 300 Etudiants parmi 400 ou 500 etc pour l'acquisition d'un dortoir au campus;

    Voici le code:

    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
    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  ;   
     
    		 }
     
       }

  2. #2
    Membre émérite

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    851
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 851
    Points : 2 674
    Points
    2 674
    Par défaut Todo
    Bonjour,

    Quand on soumet un code, il est bien de le rendre lisible pour les personnes à qui on s'adresse comme pour soi-même (pas de doubles sauts de ligne systématiques et un respect des indentations).

    Il y a des erreurs de logique :
    • Le nombre m de paires d'étudiants à sélectionner (soit le nombre de chambres ou son double) n'est jamais utilisé. Il y a systématiquement plus de places que d'étudiants ? Si oui pourquoi le saisir ?
    • Par exemple, la saisie des incompatibilités est au moins en n*(n-1)/2 (apparemment n² ici) et non pas n (complexité en n2) En effet rien n'empêche un étudiant d'être incompatible avec tous les autres (n-1), un autre encore (n-2) etc.
    • Il n'y a rien qui empêche d'avoir deux fois le même identifiant dans un couple incompatible (erreur de saisie des incompatibiltés non contrôlée).
    • A contrario, un étudiant n'est, par défaut, pas incompatible avec lui-même. Comme le tirage au sort ne vérifie pas que le hasard a donné deux fois le même identifiant, il y a des chambres qui seront habitées par des couple d'une seule personne (c'est nouveau ).
    • Si tout le monde est incompatible avec tout le monde (même si l'erreur dans la saisie des incompatibilités et celle sur les couples d'une personne cachent ce cas) comment on sort de la recherche de couples?
    • etc


    Par ailleurs, des facilités de java ne sont pas utilisées (par exemple Ajouter = true au lieu d'un break);.
    Il y a une complexité inutile : tabTirage ne sert à rien, l'argument clobalId de Selection ne sert à rien (il est écrasé de suite),...

    Le problème de la complexité suppose un algorithme qui fonctionne ce qui n'est pas le cas. L'usage de fonctions random donnera un estimation statistique de la complexité avec un valeur moyenne et une valeur dans le pire des cas.

    Un conseil, faites tourner à la main (ie sans ordinateur) votre algorithme sur des cas très limités (par exemple 10 étudiants et 3 chambre pour 11 incompatibilités). C'est fastidieux mais évite beaucoup d'erreurs.

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  3. #3
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur Java
    Inscrit en
    avril 2015
    Messages
    330
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Guinée

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Associations - ONG

    Informations forums :
    Inscription : avril 2015
    Messages : 330
    Points : 0
    Points
    0
    Par défaut
    Bonsoir Monsieur Guesset ;

    Je voudrais vous envoyer un message privé si vous n’aviez pas réagi aujourd’hui ;

    Citation Envoyé par Guesset Voir le message

    Quand on soumet un code, il est bien de le rendre lisible pour les personnes à qui on s'adresse comme pour soi-même (pas de doubles sauts de ligne systématiques et un respect des indentations).

    Il y a des erreurs de logique :
    • Le nombre m de paires d'étudiants à sélectionner (soit le nombre de chambres ou son double) n'est jamais utilisé. Il y a systématiquement plus de places que d'étudiants ? Si oui pourquoi le saisir ?

    m est bien utilisé :

    -Ici :


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    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];
    -Ici: à la fin de sélection

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
    int j=0;
     
    for(String elem:tabEtudSelectCopy )
       {
         tabEtudSelect[j][0]= elem; 	// recuperation	        
     
         j++;
     
       }
    Le nombre de chambre c est égale à m/2 ; donc m = 2* c ;

    Citation Envoyé par Guesset Voir le message

    • Par exemple, la saisie des incompatibilités est au moins en n*(n-1)/2 (apparemment n² ici) et non pas n (complexité en n2) En effet rien n'empêche un étudiant d'être incompatible avec tous les autres (n-1), un autre encore (n-2) etc.
    -Je n’ai pas compris la complexité ; ça boucle de 0 à n-1 seulement avec n< n saisie avec saisieEtudiant() ;

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    Int i=0 ;
     
    do {
     
     i =i+1;
     
     } while (i<n);
    - je ne me suis pas soucié du contrôle de saisie qui n’est pas l’objectif recherché ; mais on peut le faire et si je peu je le ferai ; seulement on suppose que la liste est correcte et a été bien fournit par la direction ou un décideur et non par l’informaticien ;

    Citation Envoyé par Guesset Voir le message
    [*]Il n'y a rien qui empêche d'avoir deux fois le même identifiant dans un couple incompatible (erreur de saisie des incompatibiltés non contrôlée).[/LIST]
    Cette question et comme le reste:

    On suppose que la liste est correcte et on porte confiance à l’agent de saisie pour le moment;

    Le résultat recherché ou ma question : est ce la complexité est polynomiale ?

    Après on passera à la perfection avec le tableau ou List ; càd Class Etudiant etc..

    vous avez tout à fait raison sur les avantage de java comme l'utilisation de break ; je voulais faire ça simple pour ressortir l'idée comme je ne suis pas balaise en code; d’ailleurs au départ je voulais m’arrêter à l'algo mais je sais que les gent poserait de question si je l'ai fait avec un programme;

    -Pour la trace voici une trace :


    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
    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
     
    Veuillez saisir le nombre d’étudiants :
    15
    Veuillez saisir le nombre pair d’étudiant incompatible :
    2
    Veuillez saisir le nombre d’étudiants à sélectionné par pair :
    10
    ------Menu principal ---------
       1. Liste d’étudiants     
     2.Liste d’étudiants incompatibles  
      3. Sélection d’étudiants  
               4.Quitter      
          Taper votre choix : 
    Veuillez respecter le menu!
    ------Menu principal ---------
       1. Liste d’étudiants     
     2.Liste d’étudiants incompatibles  
      3. Sélection d’étudiants  
               4.Quitter      
          Taper votre choix : 
    1
    Veuillez saisir l’Id de l’étudiants :
    001
    Veuillez saisir l’Id de l’étudiants :
    002
    Veuillez saisir l’Id de l’étudiants :
    003
    Veuillez saisir l’Id de l’étudiants :
    004
    Veuillez saisir l’Id de l’étudiants :
    005
    Veuillez saisir l’Id de l’étudiants :
    006
    Veuillez saisir l’Id de l’étudiants :
    007
    Veuillez saisir l’Id de l’étudiants :
    008
    Veuillez saisir l’Id de l’étudiants :
    009
    Veuillez saisir l’Id de l’étudiants :
    010
    Veuillez saisir l’Id de l’étudiants :
    011
    Veuillez saisir l’Id de l’étudiants :
    012
    Veuillez saisir l’Id de l’étudiants :
    013
    Veuillez saisir l’Id de l’étudiants :
    014
    Veuillez saisir l’Id de l’étudiants :
    015
    ------Menu principal ---------
       1. Liste d’étudiants     
     2.Liste d’étudiants incompatibles  
      3. Sélection d’étudiants  
               4.Quitter      
          Taper votre choix : 
    2
    Veuillez saisir l’Id de l’étudiant1 incompatible:
    001
    Veuillez saisir l’Id de l’étudiant2 incompatible:
    003
    Veuillez saisir l’Id de l’étudiant1 incompatible:
    006
    Veuillez saisir l’Id de l’étudiant2 incompatible:
    009
    ------Menu principal ---------
       1. Liste d’étudiants     
     2.Liste d’étudiants incompatibles  
      3. Sélection d’étudiants  
               4.Quitter      
          Taper votre choix : 
    3
    Veuillez saisir le nombre de chambres:
    5
    tabEtudSelect: 014
    tabEtudSelect: 004
    tabEtudSelect: 010
    tabEtudSelect: 011
    tabEtudSelect: 005
    tabEtudSelect: 006
    tabEtudSelect: 012
    tabEtudSelect: 003
    tabEtudSelect: 013
    tabEtudSelect: 015
    ------Menu principal ---------
       1. Liste d’étudiants     
     2.Liste d’étudiants incompatibles  
      3. Sélection d’étudiants  
               4.Quitter      
          Taper votre choix : 
    Veuillez respecter le menu!
    ------Menu principal ---------
       1. Liste d’étudiants     
     2.Liste d’étudiants incompatibles  
      3. Sélection d’étudiants  
               4.Quitter      
          Taper votre choix :
    Merci pour votre intervention

  4. #4
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 3 612
    Points : 8 353
    Points
    8 353
    Par défaut
    Quel est l'intérêt de la question 'complexité de l'algorithme', 'complexité Polynomiale' ?
    Une complexité polynomiale peut être pire qu'une complexité exponentielle dans plein de configurations.
    Une complexité en n^10 (donc polynomiale) va créer des problèmes beaucoup plus tôt qu'une complexité exponentielle.

    Tu ajoutes un compteur à un endroit stratégique.
    Tu fais tourner ton algorithme avec 40 étudiants à choisir parmi 80, et tu regardes le résultat de ce compteur.
    Puis tu recommences avec 40 étudiants à choisir parmi 120
    Puis tu recommences avec 80 étudiants à choisir parmi 160
    Tu essaies différentes configurations( une douzaine), et tu vois si quand tu multiplies ton nombre d'étudiants par 2, ce compteur est multiplié par 2, ou par 4, ou par 100.

    Ou sinon, tu regardes ligne à ligne ce que fait ton code.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  5. #5
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur Java
    Inscrit en
    avril 2015
    Messages
    330
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Guinée

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Associations - ONG

    Informations forums :
    Inscription : avril 2015
    Messages : 330
    Points : 0
    Points
    0
    Par défaut
    Bonjour Monsieur tbc92;

    Citation Envoyé par tbc92 Voir le message
    Quel est l'intérêt de la question 'complexité de l'algorithme', 'complexité Polynomiale' ?
    C'est très important de se situer avant de continuer;

    D'abord j'ai fait la trace plusieurs fois sans détecter un résultat faux qui est un grand espoir; maintenant si vos analyses montre que c'est polynomiale cela ne veux pas dire que l'algo est parfait ; ça m’encouragera investiture mon temps afin de le transformer en un algorithme acceptable avec vous les experts;

    Donc avec ou sans cette algorithme, on aura la certitude que le problème principal que je vais vous affiché ici serra résolu par quel qu’un qui a un meilleur algo que moi;

    Donc j'ai besoin de le savoir !


    Citation Envoyé par tbc92 Voir le message
    Tu ajoutes un compteur à un endroit stratégique.
    C'est ici je dois placer ce compteur? càd dans sélection

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     
    for(int i = 0; i<c; i++)  {
     
    			 Ajouter=false;			 
    		 do {		
     
                     compteur++ ;
     
    		    } while (Ajouter==false);
     
     
    		 }
    Merci pour votre intervention

  6. #6
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 3 612
    Points : 8 353
    Points
    8 353
    Par défaut
    Tu peux mettre compteur++ plusieurs fois, à plusieurs endroits. Comme ça, tu vas mesurer le cumul de plusieurs choses. Et tu ne vas pas passer à côté d'un traitement qui pourrait poser problème.

    Ou tu peux chronométrer le temps d'exécution. Si quand on ajoute 5 étudiants (55 au lieu de 50) , le temps d'exécution augmente de 50%, c'est un bon indicateur pour dire que ça va exploser quand on va atteindre 100 ou 200 étudiants.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  7. #7
    Membre émérite

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    851
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 851
    Points : 2 674
    Points
    2 674
    Par défaut
    Bonjour,

    1. Quand je dis que m ne sert à rien c'est qu'il n'est pas utilisé dans la boucle principale de sélection qui utilise c (nombre de chambres) une valeur qui est saisie localement. Il n'y a aucune garantie que m = 2*c.
    2. Dans une population de n personnes combien y a t'il de paires possibles ? C'est simple, c'est n*(n-1)/2 (la division par 2 vient du fait que la paire (a, b) = (b, a) ). Donc, dans le pire des cas (tous les étudiants sont des caractériels) la dimension sera n*(n-1)/2 (un triangle de la matrice carrée hors la diagonale). Si on ne veut pas se casser la tête on peut utiliser une matrice n² en prenant soin de rendre incompatible la diagonale (pas de couple avec soi-même) et en enregistrant systématiquement NoDuo[id1][id2] = true et NoDuo[id2][id1] = true au moment de la création des incompatibilités.


    Un programme qui ne vérifie rien cours à l'échec d'autant qu'ici on utilise des saisies manuelles dont le taux d'erreur n'est jamais marginal.

    Je répète que l'algorithme ne fonctionne pas. Outre les remarques précédentes, la possibilité d'avoir id1 = id2 n'est pas exclue dans la sélection et ça ce n'est pas une erreur de saisie mais de programmation. Un autre exemple, si c > n/2 la boucle de sélection ne s'arrête pas : après avoir "consommé" tous les étudiants il reste des chambres libre et l'algo va continuer à chercher à les remplir alors qu'il n'a plus personne à mettre dedans.

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  8. #8
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur Java
    Inscrit en
    avril 2015
    Messages
    330
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Guinée

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Associations - ONG

    Informations forums :
    Inscription : avril 2015
    Messages : 330
    Points : 0
    Points
    0
    Par défaut
    Citation Envoyé par tbc92 Voir le message
    Tu peux mettre compteur++ plusieurs fois, à plusieurs endroits. Comme ça, tu vas mesurer le cumul de plusieurs choses. Et tu ne vas pas passer à côté d'un traitement qui pourrait poser problème.

    Ou tu peux chronométrer le temps d'exécution. Si quand on ajoute 5 étudiants (55 au lieu de 50) , le temps d'exécution augmente de 50%, c'est un bon indicateur pour dire que ça va exploser quand on va atteindre 100 ou 200 étudiants.
    OK

    Je vais recommencer;

    J'avais fait 3 tests dans sélection() déjà à partir de
    15 Etudiants 2 incompatibles et 10 sélections;
    30 Etudiants, 5 incompatibles, 20 sélections ;
    80 Etudiants, 20 incompatibles, 40 sélections ;
    et pour tous ces tests compteur= nombre de chambres c;
    ce qui veut dire que le minimum cpteur=c;

    je vais mettre partout et recommencer;

    Citation Envoyé par Guesset Voir le message
    Bonjour,

    1. Quand je dis que m ne sert à rien c'est qu'il n'est pas utilisé dans la boucle principale de sélection qui utilise c (nombre de chambres) une valeur qui est saisie localement. Il n'y a aucune garantie que m = 2*c.
    Monsieur Quesset

    voilà sont entrée ici tabEtudSelect

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    public static  void Selection (String [][] tabEtudSelect, String [][]tabEtud , String [][]tabEtudInc , Scanner keby,String  clobalId, Integer Indice) {
    et voilà intermédiaire:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
     ArrayList<String> tabEtudSelectCopy = new ArrayList< String > ();
    qui est aussi rempli: balisé par for(int i = 0; i<c; i++) {, c étant le nombre de chambres

    tabEtudSelectCopy.add ( tabTirage[0][0] ) ; Etudiant 1
    tabEtudSelectCopy.add ( tabTirage[0][1] ) ; Etudiant 2

    chaque chambre a 2 étudiants;

    et en fin votre souci est attaqué ici:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
                     int j=0;
    		  for(String elem:tabEtudSelectCopy )
    	       {
    		tabEtudSelect[j][0]= elem; 	// recuperation	  
    		 System.out.println("tabEtudSelect: "+elem);
     
    		     j++;
     
    	      }
    Je vois que vous êtes plus en avance que moi mais pour aller surement et lentement veuillez m'accorder un temps pour ça;

    je sais bien que c'est possible si l'agent de saisie 2 fois id1 donc l’étudiant est incompatible à lui même;
    id1 = id2

    si c > n/2 ce n'est pas le cas c=m/2;, m est le nombre d'étudiants à sélectionner ; 2 étudiants /c;

    si c > n/2 alors l'affaire est résolu tout le monde serra sélectionné ou si si c > m/2, ça laissera plus de chance pour ceux qui ne devraient pas être sélectionnés;

    Merci

  9. #9
    Membre émérite

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    851
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 851
    Points : 2 674
    Points
    2 674
    Par défaut Mesure de complexité
    Bonjour,

    Je ne reviendrais pas sur ce que j'ai signalé qui ne semble pas assimilé (par exemple, dans selection() le risque que les deux tirages au sort donnent le même id n'est pas traité : ce n'est donc pas un problème de saisie).

    Il faut faire attention avec la mesure de complexité. La complexité est une tendance de comportement. Comme l'écrit tbc92, les mesures donnent une indication qui pour être valable doit s'appuyer sur des jeux d'essais assez importants en volumes et couvrant les divers cas de figure extrêmes : pas d'incompatibilité, tous incompatibles, pas assez de chambre, trop de chambres, etc.

    Tiens une question bête. Que se passe-t-il s'il y a un nombre impair d'étudiants et suffisamment de place pour tous ? Et bien, avec la démarche actuelle, il y en aura un qui restera sur le carreau (hormis le fait que la boucle de sélection ne s'arrête pas). Prenons 99 étudiants et 50 chambres et un taux d'incompatibilité assez faible. 98 seulement trouveront une place et la boucle passera en mode infini dès le 99e.

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  10. #10
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 3 612
    Points : 8 353
    Points
    8 353
    Par défaut
    Guesset,
    pour arriver à ces conclusions, tu as investi pas mal de temps. Tu as certainement reformaté le code proposé, pour le rendre lisible (indentation, sauts de lignes ...)
    Si c'est le cas, peux-tu partager le code réécrit.
    Je pense que des intervenants habituels ont été totalement rebutés par le code trop difficile à lire.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  11. #11
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur Java
    Inscrit en
    avril 2015
    Messages
    330
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Guinée

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Associations - ONG

    Informations forums :
    Inscription : avril 2015
    Messages : 330
    Points : 0
    Points
    0
    Par défaut
    Bonsoir Monsieur Guesset !!

    Citation Envoyé par Guesset Voir le message

    Je ne reviendrais pas sur ce que j'ai signalé qui ne semble pas assimilé (par exemple, dans selection() le risque que les deux tirages au sort donnent le même id n'est pas traité : ce n'est donc pas un problème de saisie).
    Je ne vous ai pas compris au départ car pour moi vous faite référence à la table incompatibilité ;
    A ce niveau on peu supposer qu’une liste d’étudiants et une liste d’étudiants incompatibles est fournit sur un support donc on n’a pas besoin de saisir(car on fait une importation des données) si on est beaucoup exigeant sur le Control de saisie ;

    Maintenant revenons au mouton :

    Non c’est traité et d’ailleurs c’est le lieu de comprendre l’importance de tabTirage, tabEtudCopy et tabEtudSelectCopy qui servent de l’intermédiaires en évitant d’écraser les données de départ ;

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    // si non alors il est ajouté
     
    tabTirage[0][0]=id1; // il est rangé dans le tirage;
     
    tabEtudCopy.remove(nb); // supprimé dans ce tableau pour éviter de tomber sur la même valeur au prochain tirage
    Avec aussi id2

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    tabTirage[0][1]=id2; // son binôme est aussi tiré (je crois que vous comprenez le processus)
     
    tabEtudCopy.remove(nb); // il est aussi supprimé
    Regarder bien cette partie; il est impossible de choisir une incompatibilité

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
       if (((id1 == tabEtudInc[Indice][0]) && (id2 != tabEtudInc[Indice][1])) ||   ((id1 == tabEtudInc[Indice][1]) && (id2 != tabEtudInc[Indice][0]))){
    Que se passe-t-il s'il y a un nombre impair d'étudiants et suffisamment de place pour tous ?

    Oui ça c’est vrais ce sont les conditions de sortie

    Un étudiant serra logé tout seul qui n’est pas interdit aussi d’où :

    n=tabEtudCopy.size() //détermine le nombre d’éléments dans Etudiant ;

    si (n = =1) alors
    il est sélectionné

    et break loop ; pour sortir définitivement de la boucle for

    Est ce bien corrigé ici: surtout merci; je excuse beaucoup pour indentation car je m'efforce beaucoup sans y arrivé;


    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
    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
     
     
    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
      int compteur=0;
     
      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;
     
         loop:
     
     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
     
    	 if(n == 1){ 
     
    	  id1 = tabEtudCopy.get(n);// il est le seul à être logé	 
     
              tabTirage[0][0]=id1; // il est rangé dans le tirage;
     
    	  break loop; //fin de selection
     
    		      } else {
     
    		       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
     
    		        compteur++;//pr la trace
     
    		      }
    	 	         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;
     
    		               compteur++;//pr la trace
     
    		               }
     
    		               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		 
    		 */
     
    		 System.out.println("Compteur: "+compteur);// pr la trace
     
    		 int j=0;
    		  for(String elem:tabEtudSelectCopy )
    	       {
     
    		tabEtudSelect[j][0]= elem; 	// recuperation	  
     
    	         System.out.println("tabEtudSelect: "+elem);
     
    		j++;
     
    	    }
     
     
    	 }
    pour les autres Monsieur tbc92 a déjà évoqué et je suis entrain; le courant viens d'arrivé dans notre chambre( depuis hier il y avait coupure d’électricité);

    Merci!

  12. #12
    Membre émérite

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    851
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 851
    Points : 2 674
    Points
    2 674
    Par défaut Relais
    Bonjour tbc92,

    Citation Envoyé par tbc92 Voir le message
    ...Tu as certainement reformaté le code proposé, pour le rendre lisible (indentation, sauts de lignes ...)
    Si c'est le cas, peux-tu partager le code réécrit...
    Pas de problème, mais je me suis contenté de le remettre en forme sans réellement le réécrire. En général, je n'interviens sur le code que si celui proposé est proche de la solution ou pour l'optimiser.
    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
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    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 :");
          // Liste des étudiants
          int n = keby.nextInt();
          String[][] tabEtud = new String[n][4];     // Une structure ou class aurait été préférable
          System.out.println("Veuillez saisir le nombre pair d’étudiant incompatible :");
          // Liste de paires é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électionner par pair :");
          // 2 étudiants par chambre soit 2*nombres de chambres (mais c ressaisi plus loin !)
          int m = keby.nextInt();
          String [][] tabEtudSelect = new String[m][2];
          Integer Indice    = 0;
          String  clobalId  = "001";                 // globalId ? C'est un nombre pourquoi String ?
          String  choix;                             // Pourquoi utiliser String ?
          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 {                                       // C'est un do while qui mime exactement un for
             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();              // Pourquoi pas tabEtud[i][3] = 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);                            // Pourquoi pas n² ou mieux n*(n-1)/2 ?
       }
     
       // Sélection 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;                   // Si Ajouter = vrai sortir du while
          String[][] tabTirage = new String[1][2];   // 2x tirés, rangés et remplacés au tirage suivant
          // Mets la liste étudiant dans ArrayList pour faciliter le traitement
          ArrayList<String> tabEtudCopy = new ArrayList< String > (); 
          // Récupère les selections et à la sortie recopierra dans tabEtudSelect
          ArrayList<String> tabEtudSelectCopy = new ArrayList< String > ();
          for(int i = 0; i < n; i++) {
             tabEtudCopy.add(tabEtud[i][0]);         // Transfert de la liste étudiant dans la copie
          }
          System.out.println("Veuillez saisir le nombre de chambres:");
          // Permet de saisir le nombres de chambres
          int c = keby.nextInt();                    // Nombre de chambres, devrait être = m / 2
          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 retenu, l'etudiant sera selectionné
                clobalId = id1;
                idRe = recherche(tabEtudInc, clobalId, Indice); // id1 dans liste d'incompatibilié ?
                if(idRe == "-1") {
                   // Sinon alors il est ajouté
                   tabTirage[0][0] = id1;            // Il est rangé dans le tirage
                   tabEtudCopy.remove(nb);           // Oté du tableau pour ne pas retomber sur le même
                   n   = tabEtudCopy.size();
                   nb  = random.nextInt(n);
                   id2 = tabEtudCopy.get(nb);
                   tabTirage[0][1] = id2;            // Son binomme est aussi tiré
                   tabEtudCopy.remove(nb);
                   Ajouter = true;                   // Pour sortir du while, aller chambre suivante
                }
                else {
                   // Sinon alors on cherche le second et on vérifie 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 couplage 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); 
                   /* Si le duo n'est pas possible, on remet dans la table tabEtudCopy l'id1 qui a
                      été supprimé pour recommencer sans changer de chambre. Ajouter reste 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]);
          }
          /* récupére la selection en tableau static si le travail est fini */
          int j = 0;
          for(String elem:tabEtudSelectCopy) {       // Tiens on repasse de c à m !
             tabEtudSelect[j][0] = elem;             // Récupération
             j++;
          }
       }
     
       //______________________________________________________________________________________________
       public static String recherche(String [][]tabEtudInc, String clobalId, Integer Indice) {
          int n = tabEtudInc.length;
          String sortietest="-1"; // cherche les incompatibilités, 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  ;   
       }
    }
    Ca tombe bien car je commence à être las d'un sujet facile qui tourne en rond. Je ne dois pas être assez pédagogique. Alors si le code réagencé peut inciter quelqu'un à prendre le relais...

    Salut
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  13. #13
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur Java
    Inscrit en
    avril 2015
    Messages
    330
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Guinée

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Associations - ONG

    Informations forums :
    Inscription : avril 2015
    Messages : 330
    Points : 0
    Points
    0
    Par défaut
    Bonsoir Mr Tbc92;

    J'ai fait plusieurs essai avec plus de 100 étudiants , cpteur étais toujours égale aux nombres de chambres c;
    mais comme Mr Guesset parlait dans ces explications ceux-ci : pas d'incompatibilité, tous incompatibles, pas assez de chambre, trop de chambres, etc.

    pour rendre la tache facile je suis revenus aux nombres d'étudiants=15 avec tous une incompatibilités sauf un;

    Et voilà ce que j'ai découvert:

    il accédé une seule fois à ce test ci-dessous :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
     if(((id1 == tabEtudInc[Indice][0]) && (id2 != tabEtudInc[Indice][1])) 
     || ((id1 == tabEtudInc[Indice][1]) && (id2 != tabEtudInc[Indice][0]))) {
    il fait ce tirage sans mettre Ajouter à vrai et sans incrémenter le compteur aussi alors que j'ai planqué dedans un compteur comme vous me l'aviez conseillé

    Mais pour tous le reste le programme trouve exactement les valeurs avec plusieurs essai à l'appuis et d’ailleurs je n'ai pas encore dormis car j'ai passé la nuit dessus;

    il reste tout de même dans la boucle car Ajouter=false;

    C'est java qui a un problème ou la syntaxe que j'ai donnée qui est fausse?

    ça rend fou cas même si à des endroits on fait while {...} qui ne fonctionne pas et en remplaçant avec do {...} while ça prend ou un do {...} while qui produit double affichage comme dans mon menu principal ; alors on procédera à un moment donner par tâtonnement comme un élève toto;

    Veuillez regardez une trace: je n'ai pas pu intercepter le début d’exécution mais ça se comprend;

    la ligne: 002 = 014 ET 013 != 002 OU 002 = 002 ET 013 != 014 est bel et bien vrai mais ne rentre pas dedans;

    tabEtudSelectCopy: 008 ne figure pas dans incompatibilité donc ça exécute compteur++

    tabEtudSelectCopy: 014 figure dans incompatibilité donc ça ne exécute compteur++ alors que c'est tiré

    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
    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
     
     Veuillez saisir le nombre d’étudiants :
    15
    Veuillez saisir le nombre pair d’étudiant incompatible :
    7
    Veuillez saisir le nombre d’étudiants à sélectionner par pair :
    10
    ------Menu principal ---------
       1. Liste d’étudiants     
     2.Liste d’étudiants incompatibles  
      3. Sélection d’étudiants  
               4.Quitter      
          Taper votre choix : 
    Veuillez respecter le menu!
    ------Menu principal ---------
       1. Liste d’étudiants     
     2.Liste d’étudiants incompatibles  
      3. Sélection d’étudiants  
               4.Quitter      
          Taper votre choix : 
    1
    Veuillez saisir l’Id de l’étudiants :
    001
    Veuillez saisir l’Id de l’étudiants :
    002
    Veuillez saisir l’Id de l’étudiants :
    003
    Veuillez saisir l’Id de l’étudiants :
    004
    Veuillez saisir l’Id de l’étudiants :
    005
    Veuillez saisir l’Id de l’étudiants :
    006
    Veuillez saisir l’Id de l’étudiants :
    007
    Veuillez saisir l’Id de l’étudiants :
    008
    Veuillez saisir l’Id de l’étudiants :
    009
    Veuillez saisir l’Id de l’étudiants :
    010
    Veuillez saisir l’Id de l’étudiants :
    011
    Veuillez saisir l’Id de l’étudiants :
    012
    Veuillez saisir l’Id de l’étudiants :
    013
    Veuillez saisir l’Id de l’étudiants :
    014
    Veuillez saisir l’Id de l’étudiants :
    015
    ------Menu principal ---------
       1. Liste d’étudiants     
     2.Liste d’étudiants incompatibles  
      3. Sélection d’étudiants  
               4.Quitter      
          Taper votre choix : 
    2
    Veuillez saisir l’Id de l’étudiant1 incompatible:
    001
    Veuillez saisir l’Id de l’étudiant2 incompatible:
    003
    Veuillez saisir l’Id de l’étudiant1 incompatible:
    005
    Veuillez saisir l’Id de l’étudiant2 incompatible:
    007
    Veuillez saisir l’Id de l’étudiant1 incompatible:
    009
    Veuillez saisir l’Id de l’étudiant2 incompatible:
    011
    Veuillez saisir l’Id de l’étudiant1 incompatible:
    013
    Veuillez saisir l’Id de l’étudiant2 incompatible:
    015
    Veuillez saisir l’Id de l’étudiant1 incompatible:
    014
    Veuillez saisir l’Id de l’étudiant2 incompatible:
    002
    Veuillez saisir l’Id de l’étudiant1 incompatible:
    010
    Veuillez saisir l’Id de l’étudiant2 incompatible:
    004
    Veuillez saisir l’Id de l’étudiant1 incompatible:
    012
    Veuillez saisir l’Id de l’étudiant2 incompatible:
    006
    ------Menu principal ---------
       1. Liste d’étudiants     
     2.Liste d’étudiants incompatibles  
      3. Sélection d’étudiants  
               4.Quitter      
          Taper votre choix : 
    3
     
    -----------------
    idRecherché a été trouvé: 002
     tabEtudInc[0][0] 001
     tabEtudInc[0][1] 003
     tabEtudInc[1][0] 005
     tabEtudInc[1][1] 007
     tabEtudInc[2][0] 009
     tabEtudInc[2][1] 011
     tabEtudInc[3][0] 013
     tabEtudInc[3][1] 015
     tabEtudInc[4][0] 014
     tabEtudInc[4][1] 002
     tabEtudInc[5][0] 010
     tabEtudInc[5][1] 004
     tabEtudInc[6][0] 012
     tabEtudInc[6][1] 006
    indice : 4
    002 = 014 ET  013 != 002 OU  002 = 002 ET  013 != 014
    Compteur: 1
    tabEtudSelectCopy: 008
    tabEtudSelectCopy: 014
    nb: 5
    -----------------
    idRecherché a été trouvé: 005
     tabEtudInc[0][0] 001
     tabEtudInc[0][1] 003
     tabEtudInc[1][0] 005
     tabEtudInc[1][1] 007
     tabEtudInc[2][0] 009
     tabEtudInc[2][1] 011
     tabEtudInc[3][0] 013
     tabEtudInc[3][1] 015
     tabEtudInc[4][0] 014
     tabEtudInc[4][1] 002
     tabEtudInc[5][0] 010
     tabEtudInc[5][1] 004
     tabEtudInc[6][0] 012
     tabEtudInc[6][1] 006
    indice : 1
    005 = 005 ET  006 != 007 OU  005 = 007 ET  006 != 005
    Compteur: 1
    tabEtudSelectCopy: 008
    tabEtudSelectCopy: 014
    nb: 1
    -----------------
    idRecherché a été trouvé: 009
     tabEtudInc[0][0] 001
     tabEtudInc[0][1] 003
     tabEtudInc[1][0] 005
     tabEtudInc[1][1] 007
     tabEtudInc[2][0] 009
     tabEtudInc[2][1] 011
     tabEtudInc[3][0] 013
     tabEtudInc[3][1] 015
     tabEtudInc[4][0] 014
     tabEtudInc[4][1] 002
     tabEtudInc[5][0] 010
     tabEtudInc[5][1] 004
     tabEtudInc[6][0] 012
     tabEtudInc[6][1] 006
    indice : 2
    009 = 009 ET  012 != 011 OU  009 = 011 ET  012 != 009
    Compteur: 1
    tabEtudSelectCopy: 008
    tabEtudSelectCopy: 014
    nb: 5
    -----------------
    idRecherché a été trouvé: 010
     tabEtudInc[0][0] 001
     tabEtudInc[0][1] 003
     tabEtudInc[1][0] 005
     tabEtudInc[1][1] 007
     tabEtudInc[2][0] 009
     tabEtudInc[2][1] 011
     tabEtudInc[3][0] 013
     tabEtudInc[3][1] 015
     tabEtudInc[4][0] 014
     tabEtudInc[4][1] 002
     tabEtudInc[5][0] 010
     tabEtudInc[5][1] 004
     tabEtudInc[6][0] 012
     tabEtudInc[6][1] 006
    indice : 5
    010 = 010 ET  009 != 004 OU  010 = 004 ET  009 != 010
    Compteur: 1
    tabEtudSelectCopy: 008
    tabEtudSelectCopy: 014
    nb: 0
    -----------------
    idRecherché a été trouvé: 007
     tabEtudInc[0][0] 001
     tabEtudInc[0][1] 003
     tabEtudInc[1][0] 005
     tabEtudInc[1][1] 007
     tabEtudInc[2][0] 009
     tabEtudInc[2][1] 011
     tabEtudInc[3][0] 013
     tabEtudInc[3][1] 015
     tabEtudInc[4][0] 014
     tabEtudInc[4][1] 002
     tabEtudInc[5][0] 010
     tabEtudInc[5][1] 004
     tabEtudInc[6][0] 012
     tabEtudInc[6][1] 006
    indice : 1
    007 = 005 ET  012 != 007 OU  007 = 007 ET  012 != 005
    Compteur: 1
    tabEtudSelectCopy: 008
    tabEtudSelectCopy: 014
    nb: 6
    -----------------
    idRecherché a été trouvé: 003
     tabEtudInc[0][0] 001
     tabEtudInc[0][1] 003
     tabEtudInc[1][0] 005
     tabEtudInc[1][1] 007
     tabEtudInc[2][0] 009
     tabEtudInc[2][1] 011
     tabEtudInc[3][0] 013
     tabEtudInc[3][1] 015
     tabEtudInc[4][0] 014
     tabEtudInc[4][1] 002
     tabEtudInc[5][0] 010
     tabEtudInc[5][1] 004
     tabEtudInc[6][0] 012
     tabEtudInc[6][1] 006
    indice : 0
    003 = 001 ET  006 != 003 OU  003 = 003 ET  006 != 001
    Compteur: 1
    tabEtudSelectCopy: 008
    tabEtudSelectCopy: 014
    nb: 8
    -----------------
    Mr Guesset je suis très content de savoir que ce sujet soit facile; ce qui veut dire que cette nouvelle méthode pourra porter fruit;

    le problème auquel je fait référence montre que c'est un problème millénaire qui doit avoir cette égalité << solution facile=vérification facile >> et non <<solution difficile = vérification facile >> je sais qu'il y a des solution s il y a longtemps mais qui sont tous difficiles et vous voyez que je suis sur une bonne piste pour le moment;

    Donc ne vous décourage pas hein; aidez moi sur mon sujet de toto;

  14. #14
    Membre émérite

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    851
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 851
    Points : 2 674
    Points
    2 674
    Par défaut De facile à difficile
    Bonjour,

    Le problème devient difficile si la solution ne doit pas dépendre de l'ordre du tirage au sort.

    Supposons qu'un tirage u donne un idu dont tous les appariables possibles ont déjà été affectés à une chambre. Il n'y a donc plus de couplage possible avec lui alors que si il avait été tiré en premier il aurait été possible de lui trouver un colocataire. L'algorithme actuel nonobstant ses autres problèmes ne peut répondre à cette contrainte.

    Si le taux d'incompatibilité reste faible, cette contrainte peut ne pas être satisfaite car la probabilité d'un échec devient faible mais il faut cependant traiter l'éventualité de ce cas.

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  15. #15
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur Java
    Inscrit en
    avril 2015
    Messages
    330
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Guinée

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Associations - ONG

    Informations forums :
    Inscription : avril 2015
    Messages : 330
    Points : 0
    Points
    0
    Par défaut
    Bonjour Monsieur Guesset

    Citation Envoyé par Guesset Voir le message

    Le problème devient difficile si la solution ne doit pas dépendre de l'ordre du tirage au sort.
    Supposons qu'un tirage u donne un idu dont tous les appariables possibles ont déjà été affectés à une chambre.
    Je ne suis pas assez dense en français mais si je comprends vous voulez dire que si l l'ordre de tirage n'est pas respecté le problème sera difficile?

    Ici c'est le tirage avec remise donc deux personnes doit être tirée avant de décider leurs sort; ils sont compatibles alors on les enregistre dans la sélection dans le cas contraire ils sont tous les deux remis et un ou les deux peuvent encore être tirées comme aucun des deux ne serra tiré dans les prochains tirage ;

    Ce problème est difficile quand on est trop collant à l'analyse combinatoire; le problème auquel je fais référence mentionne que cet un problème à des millions de solutions et fait partie de NP-difficile;

    moi je trouve que c'est le contraire quand on passe par le tirage au sort avec remise;

    Attention avec le tirage sans remise car on risque d'être bloqué indéfiniment à une certaines phase du tirage;

    pour revenir à la réalité; une fille est incompatible avec un garçon et , si le tirage tombe sur une fille et un garçon ils sont tous remis; c'est pour quoi pour favoriser les filles on les donne leurs propre dortoirs en tout cas chez nous dans notre Université c'est le cas;

    ici dan notre Université la contrainte possible serrait un étudiant en informatique ne peut pas loger avec un médecin; on était loger avec des Mathématiciens et Économiste;

    Dans ce cas si l'on est informaticien soit on est tiré avec cet ensemble donc on est sélectionné soit on est remis dans l'urne et on est pas sélectionné du tout, peut être on peut aussi avoir la chance d'être tiré une autre fois;

    Donc OUI une personne peut être tiré sans être sélectionner si c'est ce que vous voulez entendre!

    Ce n'est pas une injustice ce état de fait car il y aura toujours des malheureux qui n'auront pas de place dont les autres ne sont pas mieux qu'eux;

    Merci!

  16. #16
    Membre émérite

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    851
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 851
    Points : 2 674
    Points
    2 674
    Par défaut
    Bonjour,

    Non ce n'est pas ça. Supposons un tirage (7, 5), (3, 6) et (2, ?) mais pas de chance 2 n'est compatible qu'avec 7 et 6. Si le même tirage était dans un autre ordre, par exemple, (3, 6), (2, 7), (5, ?) 5 pourrait (peut être) avoir un colocataire. C'est une contrainte supplémentaire.

    A défaut, le problème ne me semble pas de typo NP car sa complexité en n est de l'ordre de n*ln(n) ceci étant modulé par le taux d'incompatibilité et le ratio nombre de chambres/nombre d'étudiants.

    On peut descendre la complexité et éviter une boucle sans fin en tirant le colocataire au hasard mais s'il ne convient en prenant le suivant dans la liste ou le tableau et ainsi de suite (après n-1 on repasse à 0) quand on retombe sur le tirage aléatoire initial du colocataire on sait qu'il n'y a pas de solution donc qu'il faut remettre en cause le choix du premier étudiant (id1 qui ne va avec personne).

    Si j'ai le temps et le courage, je ferai un dessin plus explicite qu'un texte.

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  17. #17
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur Java
    Inscrit en
    avril 2015
    Messages
    330
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Guinée

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Associations - ONG

    Informations forums :
    Inscription : avril 2015
    Messages : 330
    Points : 0
    Points
    0
    Par défaut
    Bonsoir Mr Guesset;

    Votre analyse est très poussée et je ne suis pas contre s'il y a un deuxième algo qui utilise à peu près le tirage au sort;

    Pour l'instant c'est une solution qu'on doit se contenter d'ici votre solution;

    Citation Envoyé par Guesset Voir le message
    Non ce n'est pas ça. Supposons un tirage (7, 5), (3, 6) et (2, ?) mais pas de chance 2 n'est compatible qu'avec 7 et 6. Si le même tirage était dans un autre ordre, par exemple, (3, 6), (2, 7), (5, ?) 5 pourrait (peut être) avoir un colocataire. C'est une contrainte supplémentaire.
    Vous voulez que 3 utilise la mince chance qu'il a pour être tiré;

    Un tirage est reposé sur la chance et tout le monde se remet à Dieu donc; la volonté divine !!

    Choisir (2, ?) et remettre le choix (? ) dans l'urne est comme si 2 est en priorité par rapport à (? ) qui est une manipulation humaine et non divine; pour ne pas favoriser l'un des deux on les remet tous dans l'urnes pour recommencer;

    Tirer (3, 6) en deuxième ordre, comme on se sert des contraintes de 3 pour le ramener viole le choix de hasard;
    au lieu de mettre 2 en priorité, c'est 2 et 3 qui sont prioritaires donc un traitement de faveur;

    Dans notre Université les garçons sont plus nombreux que les filles; donc le choix tombera plus facilement sur un garçon qu'une fille d'où la séparation des dortoirs filles et garçons pour l’égalité fille garçon;

    Plus de contraintes = moins de chances; et les contraintes ne doivent pas être imaginaires mais plutôt naturelles( filles/garçons, religieux A /religieux B, boursiers étrangers/ nationaux, handicapé/non handicapé etc....)

    sinon on peu décider que l'étudiant A est incompatible avec tous les autres (injustice humaine) ou tout le monde est incompatible avec tout le monde qui n'est jamais une réalité et relève purement de mauvaise fois dans le sémantique;

    le bon hasard se passe de la façon suivante: CHOIX DES DEUX ÉLÉMENTS AVANT, PUIS APRES ON FAIT L'ANALYSE DES CONTRAINTES;

    Mais si l'on analyse les contraintes avant le choix rien ne dira qu'il aura corruption ou manipulation humaine ou un choix forcé;

    Citation Envoyé par Guesset Voir le message
    A défaut, le problème ne me semble pas de typo NP car sa complexité en n est de l'ordre de n*ln(n) ceci étant modulé par le taux d'incompatibilité et le ratio nombre de chambres/nombre d'étudiants.
    C'est ce que je veux bien comprendre car je suis très pauvre avec ce calcule de complexité

    Je voudrais avoir des explications terre à terre; pour quoi ln(n)? comment vous l'aviez calculé?

    de toute façon le code s’exécute désormais avec succès; mon problème était lié à la méthode egale () pour un test if sur Stirng

    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
    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
     
     
    package complexite;
    import java.util.*;
    public class complexite {	
    	 //______________________________________________________________________________________________
    	   public static void main(String[] args ) {
    	      Scanner keby = new Scanner(System.in);	
    	      System.out.println("Veuillez saisir le nombre d’étudiants :");
    	      // Liste des étudiants
    	      int n = keby.nextInt();
    	      String[][] tabEtud = new String[n][4];     // Une structure ou class aurait été préférable
    	      System.out.println("Veuillez saisir le nombre pair d’étudiant incompatible :");
    	      // Liste de paires é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électionner par pair :");
    	      // 2 étudiants par chambre soit 2*nombres de chambres (mais c ressaisi plus loin !)
    	      int m = keby.nextInt();
    	      String [][] tabEtudSelect = new String[m][2];	       
    	      String  clobalId  = "001"; // globalId ? C'est un nombre pourquoi String ?
    	      String  choix;                   // Pourquoi utiliser String ?
    	      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);
    	          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;		      
          do { // C'est un do while qui mime exactement un for
             System.out.println("Veuillez saisir l’Id de l’étudiants :");
             tabEtud[i][0] = keby.nextLine();		         
            /* System.out.println("Veuillez saisir le nom de l’étudiants :");
             tabEtud[i][1] = keby.nextLine();		         
             System.out.println("Veuillez saisir le prénom de l’étudiants :");
             tabEtud[i][2] = keby.nextLine();		         
             System.out.println("Veuillez saisir l’adresse de l’étudiants :");
             tabEtud[i][3] = keby.nextLine(); */		        
             i = i + 1;
          } while (i < n);
    	   }
     
    		   //____________________________________________________________________________________________
      public static void saisieIncompatibilite(String [][] tabEtudInc, Scanner keby) {
                int n = tabEtudInc.length;		     
    	    int i = 0;
    	      do {
    	         System.out.println("Veuillez saisir l’Id de l’étudiant1 incompatible:");
    	         tabEtudInc[i][0] = keby.nextLine();		        
    	         System.out.println("Veuillez saisir l’Id de l’étudiant2 incompatible:");
    	         tabEtudInc[i][1] = keby.nextLine();		         
    		    i = i + 1;
    	      } while(i < n);    
    	   }
     
    	   // Sélection par tirage au sort ________________________________________________________________
       public static void Selection(String [][] tabEtudSelect, String [][]tabEtud,
    	      String [][]tabEtudInc, Scanner keby,String clobalId) {
    	      int n = tabEtud.length;
    	      int Indice=0; // indice de id incompatible necessaire pour le test de compatibilité		     
    	      Boolean Ajouter = false;                   // Si Ajouter = vrai sortir du while
    	      String[][] tabTirage = new String[1][2];   // 2x tirés, rangés et remplacés au tirage suivant
    	      // Mets la liste étudiant dans ArrayList pour faciliter le traitement
    	      ArrayList<String> tabEtudCopy = new ArrayList< String > (); 
    	      // Récupère les selections et à la sortie recopierra dans tabEtudSelect
    	      ArrayList<String> tabEtudSelectCopy = new ArrayList< String > ();
    	      int c = tabEtudSelect.length/2; // Nombre de chambres, doit être = m / 2 et m = tabEtudSelect.length
    	      for(int i = 0; i < n; i++) {
    	        tabEtudCopy.add(tabEtud[i][0]); // Transfert de la liste étudiant dans la copie
    	      }	 	     		      
    	     String id1;
    	      String id2;		      
    	      String idRe;
    	      int inRe;
    	      /*Saisie des étudiants  dans des chambres; i=0 une chmbre donc deux étudiants; i=1 une seconde
    	      chambre donc deux "tudiants encore ainsi de suite*/
    	      loop:
    	      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
    	       if(n == 1){ 
    	   	   id1 = tabEtudCopy.get(n);          // il est le seul à être logé	dans une chambre 		 		   			
    	   	    break loop;                       //fin de selection	
    	   	  } else {
    	            nb = random.nextInt(n);              // Choix dans l'intervale  0 et n
    	           id1= tabEtudCopy.get(nb);            // Si id1 retenu, l'etudiant sera selectionné		            
    	           clobalId = id1;                      //clobalId est un string car c'est id1 declaré comme variable clobale
    	           idRe = recherche(tabEtudInc,clobalId); // id1 dans liste d'incompatibilié ?		          
    	           if(idRe == "-1") {		            	
    	             // Sinon alors il est ajouté
                        tabTirage[0][0] = id1;            // Il est rangé dans le tirage
    	            tabEtudCopy.remove(nb);           // Oté du tableau pour ne pas retomber sur le même
    	            n   = tabEtudCopy.size();
    	            nb  = random.nextInt(n);
                        id2 = tabEtudCopy.get(nb);
                        tabTirage[0][1] = id2;            // Son binomme est aussi tiré
    	            tabEtudCopy.remove(nb);
    	               Ajouter = true;                   // Pour sortir du while, aller dans la chambre suivante		              
    	            }
    	            else {           			            			            	            	
    	              // Sinon alors on cherche le second et on vérifie s'il sont incompatibles
    	               inRe = recherche2(tabEtudInc,clobalId); // avant on cherche son indice  d'incompatibilié ?
    	               Indice =inRe;
    	               tabEtudCopy.remove(nb);           // Evidemment il faut supprimer id1 avant
    	               n   = tabEtudCopy.size();
    	               nb  = random.nextInt(n);
    	               id2 = tabEtudCopy.get(nb);	              		                  	            		               
    	               if(((id1.equals(tabEtudInc[Indice][0])) && (!id2.equals(tabEtudInc[Indice][1]))) 
                         || ((id1.equals(tabEtudInc[Indice][1])) && (!id2.equals(tabEtudInc[Indice][0])))) {
                         // Si le couplage 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);             	 	               
    	               /* Si le duo n'est pas possible, on remet dans la table tabEtudCopy l'id1 qui a
    	                 été supprimé pour recommencer sans changer de chambre. Ajouter reste 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]);
    		          }
    		      /* récupére la selection en tableau static si le travail est fini 
    		      et tabEtudSelectCopy aura une taille = 2*c   */		      
    		      int j = 0;
    		      for(String elem:tabEtudSelectCopy) {       // Tiens on repasse de c à m !
    		      tabEtudSelect[j][0] = elem;             // Récupération
    		       System.out.println("tabEtudSelect: "+elem);
    	              j++;
    		      }
    		    }
     
    		   //___________________________________________________________________________________________
       public static String recherche(String [][]tabEtudInc, String clobalId) {
    		      int n = tabEtudInc.length;		     
    		      String sortietest="-1"; // cherche les incompatibilités, sort avec "-1" si id n'existe pas
    		      loop:
    		      for(int i = 0; i < n ; i++) {
    		      for(int j = 0; j < 2; j++ ) {
    		       if(clobalId.equals(tabEtudInc[i][j])) {     		               
    		       sortietest = tabEtudInc[i][j];
    		       break loop;
    		         }
    		       }
    		      }	      
     
    		      return sortietest   ;   
    		   }
       public static int recherche2(String [][]tabEtudInc, String clobalId) {
    		      int n = tabEtudInc.length;
    		      int Indice=0; // cherche son indice dans la table incompatibilité
    		     loop:
    		     for(int i = 0; i < n ; i++) {
    		     for(int j = 0; j < 2; j++ ) {
    	             if(clobalId.equals(tabEtudInc[i][j])) {	
    		     Indice = i;			              
    		     break loop;
    	               }
    	             }
    	            }		    
    	          return Indice   ;   
    		       }
                        }

  18. #18
    Membre émérite

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    851
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 851
    Points : 2 674
    Points
    2 674
    Par défaut Complexité
    Bonjour,

    Quand il y a des tirages au sort, l'étude de complexité est toujours de type probalistique.

    Quelle est la probabilité que le tirage au sort soit défaillant ? C'est u/n où u est le nombre d'étudiants incompatibles (pas pour le tirage de id1, avec id1 pour le tirage de id2) ou déjà affectés à une chambre.

    Pour une chambre
    Dans tous les cas il y a 1 tirage.
    Pour qu'il y ait un tirage en plus il faut que le précédent ait échoué soit u/n
    Pour qu'il y ait un tirage en plus il faut que les précédents aient échoué soit (u/n)²
    ...
    Le nombre de tirage moyen est donc : 1 + u/n + (u/n)² + (u/n)3 + (u/n)4 + ... C'est une série géométrique qui converge vers 1/(1-u/n) soit n/(n-u). On voit déjà qu'il y a un problème quand u se rapproche de n.

    Pour toutes les chambres
    Supposons un taux moyen d'incompatibilité de 0 <= a < 1. Pour la première étape, u = a*n et la formule précédente devient 1/(1-a) .
    Pour la seconde étape on aura n/(n-2 -a*(n-2)) puisqu'il y a 2 étudiants qui sont retirés du jeu (mais pas du tirage aléatoire qui est toujours sur n.
    Pour l'étape i (en supposant que i commence à 0 et se termine à c-1)) on aura n/(n-2i -a*(n-2i)) soit n/((n-2i)(1-a)) (en toute rigueur, c'est vrai pour id1 (avec a=0) mais il faudrait écrire n/((n-2i-1)(1-a)) pour id2 puisque id1 doit être retiré du jeu).
    Au total nous aurons :
    Nom : Complexité.png
Affichages : 62
Taille : 4,8 Ko
    D'où, sauf erreur, la complexité en O(n * ln(n)). On néglige ici le choix du premier des deux occupants d'une chambre car la contrainte est plus faible (il n'a pas de coefficient a d'incompatibilité) et cela ne change pas l'ordre de complexité.

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  19. #19
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 3 612
    Points : 8 353
    Points
    8 353
    Par défaut
    Dans ton programme, il y a 2 étapes.
    1. Saisie des données.
    2. Traitement / placement des étudiants.

    Je regarde juste la partie Saisie des données.
    Je pense que dans cette partie, la fonction readline ( cf BufferedReader serait beaucoup plus adaptée que keby().
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  20. #20
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur Java
    Inscrit en
    avril 2015
    Messages
    330
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Guinée

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Associations - ONG

    Informations forums :
    Inscription : avril 2015
    Messages : 330
    Points : 0
    Points
    0
    Par défaut
    Bonjour Monsieur tbc92

    Citation Envoyé par tbc92 Voir le message
    Dans ton programme, il y a 2 étapes.
    1. Saisie des données.
    2. Traitement / placement des étudiants.

    Je regarde juste la partie Saisie des données.
    Je pense que dans cette partie, la fonction readline ( cf BufferedReader serait beaucoup plus adaptée que keby().
    Si un exemple d'utilisation n'est pas là ça serra difficile pour moi de l'utiliser; surtout que le lien est en anglais;

    Merci Monsieur Guesset pour votre exploit

    Je vais d'abord revisser tout ça voir si je peu comprendre;

    Mois j'avais fait mon petit calcule de tocard que j'avais honte de mettre;

    Je me suis basé sur chaque ligne en déterminant les opération élémentaires mais je suis resté bloqué dans la sélection() et dans do--while que j'ai pas puis interpréter car il y a trop d'imbrication; d'abord il y a la boucle for et après do..while avec les fonctions de recherche;

    Seulement j'ai une liste de complexité que je veux comprendre ; je sais qu'il y a la complexité en temps polynomial et la complexité exponentielle;
    mais dans cette liste je vois d'autres , les quatre premières sont il aussi polynomial?

    O(1) temps constant ; est il polynomial?

    O(log n) logarithmique; est il polynomial?

    O(n) linéaire; est il polynomial?

    O(n × log n) ; est il polynomial?

    O(n2) quadratique, polynomial

    O(n3) cubique, polynomial

    O(2n) exponentiel (problèmes très difficiles)

    Merci

Discussions similaires

  1. [RegEx] Aide pour trouver une fonction contenant telle variable
    Par xtremdisc dans le forum Langage
    Réponses: 4
    Dernier message: 30/08/2016, 12h36
  2. Réponses: 2
    Dernier message: 02/04/2012, 16h56
  3. Besoin d'aide pour trouver une classe à créer.
    Par tonykart13 dans le forum Général Python
    Réponses: 13
    Dernier message: 09/02/2012, 21h18
  4. Réponses: 3
    Dernier message: 02/03/2007, 16h28
  5. Réponses: 21
    Dernier message: 10/04/2006, 14h29

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo