Tableau [][] : vérifier qu'il n'y a pas de ligne identique

Tableau [][] : vérifier qu'il n'y a pas de ligne identique - Java - Programmation

Marsh Posté le 13-03-2009 à 19:32:22    

Salut!
Je cherche à faire une petite fonction qui vérifiera qu'il n'y ai pas de lignes identiques dans un tableau à 2 dimensions.
 
Par exemple si tab[0] == tab[2] ou tab[0] == tab[1]...  ca renvoie un booléen true
 
je réfléchis depuis un moment et j'arrive pas à trouver, malgré des for et encore des for...  
 
j'ai fais ca pour l'instant
 

Code :
  1. boolean testLigne(){
  2.      boolean test=false;
  3.      for( int i=0 ; i< n-1; i++ )
  4.         for( int k=0 ; k< n-1; k++ )
  5.           for (int j=0 ; j< n;j++)
  6.              if(i!=k && tab[i][j]==tab[k][j])
  7.                 test=true;
  8.   return test;
  9. }


 
n c'est la taille du tableau (tableau carré tab[n][n])
 
Quelqu'un a une idée ?

Message cité 1 fois
Reply

Marsh Posté le 13-03-2009 à 19:32:22   

Reply

Marsh Posté le 13-03-2009 à 21:20:19    

Hello,
 
Débutant en Java, je ne pense pas qu'il faille comparer les valeurs de cette manière. Si tu fais tab[0] == tab2[0], tu cherches à savoir si les variables pointent sur la même adresse. Pour moi si tu veux comparer les 2 valeurs, tu dois faire tab[0].equals(tab2[0]) là il va te retourner true.
 
Je pense que des personnes confirmées pourront affirmer ou infirmer cela.
 
Cordialement,
Redfield
 

kakashii a écrit :

Salut!
Je cherche à faire une petite fonction qui vérifiera qu'il n'y ai pas de lignes identiques dans un tableau à 2 dimensions.
 
Par exemple si tab[0] == tab[2] ou tab[0] == tab[1]...  ca renvoie un booléen true
 
je réfléchis depuis un moment et j'arrive pas à trouver, malgré des for et encore des for...  
 
j'ai fais ca pour l'instant
 

Code :
  1. boolean testLigne(){
  2.      boolean test=false;
  3.      for( int i=0 ; i< n-1; i++ )
  4.         for( int k=0 ; k< n-1; k++ )
  5.           for (int j=0 ; j< n;j++)
  6.              if(i!=k && tab[i][j]==tab[k][j])
  7.                 test=true;
  8.   return test;
  9. }


 
n c'est la taille du tableau (tableau carré tab[n][n])
 
Quelqu'un a une idée ?


Reply

Marsh Posté le 13-03-2009 à 22:28:12    

Tout dépend de quoi est le tableau. Si ce sont des types primitifs, il faut utiliser ==. Si ce sont des objets, il faut utiliser .equals.

 

Sinon, pour l'algo: si le tableau est petit (disons N < 100 lignes), des boucles imbriquées iront. S'il est grand, la complexité est en O(N^2). Un algo simple est alors de faire un tri des lignes (il faut trouver une relation d'ordre entre les lignes rapide) et de repérer d'éventuels doublons en comparant les lignes successives 2 à 2. Pour la comparaison entre 2 lignes, il faut évidemment quitter au premier élément qui diffère.

Message cité 1 fois
Message édité par el muchacho le 13-03-2009 à 22:39:34
Reply

Marsh Posté le 13-03-2009 à 22:28:44    

Hello!Plusieurs remarques:  
1) Ton indice "k" n'a pas besoin de varier de 0 à n-2, il devrait plutôt aller de (i+1) à (n-1).  
2) La logique de ton "if" n'est pas la bonne. Ton booléen "test" va devenir "true" dès qu'un seul nombre est identique dans les deux lignes que tu compares. Ce n'est pas bon car tu veux que "test" devienne "true" si et seulement si tous les entiers sont identiques. Il faudrait plutôt faire l'inverse: au début, tu supposes que les lignes seront identiques, et "test" va devenir "false" dès qu'un seul nombre est différent dans les deux lignes.  
3) Il faudra penser à réinitialiser "test" à chaque nouvelle comparaison de deux lignes.


Message édité par post_it le 13-03-2009 à 22:29:32
Reply

Marsh Posté le 14-03-2009 à 09:50:34    

el muchacho a écrit :

Tout dépend de quoi est le tableau. Si ce sont des types primitifs, il faut utiliser ==. Si ce sont des objets, il faut utiliser .equals.
 
Sinon, pour l'algo: si le tableau est petit (disons N < 100 lignes), des boucles imbriquées iront. S'il est grand, la complexité est en O(N^2). Un algo simple est alors de faire un tri des lignes (il faut trouver une relation d'ordre entre les lignes rapide) et de repérer d'éventuels doublons en comparant les lignes successives 2 à 2. Pour la comparaison entre 2 lignes, il faut évidemment quitter au premier élément qui diffère.


 
ce sont des double en fait ;)
 
merci pour vos remarques
 
post_it j'ai modifié un peu le code avec ce que t'as dis, apparemment pour l'instant ça marche toujours pas
 

Code :
  1. boolean testLigne(){
  2.  boolean test=true;;
  3.  for( int i=0 ; i< n-1; i++ ){
  4.   for( int k=i+1 ; k< n; k++ )
  5.    for (int j=0 ; j<n;j++)
  6.     if(tab[i][j]!=tab[k][j])
  7.      test=false;
  8.  if(test)
  9.   return test;
  10.  }
  11.  return test;
  12. }


 
c'est bizarre, ca marche toujours pas ! Pourtant ça parait bon  :??:


Message édité par kakashii le 14-03-2009 à 10:10:09
Reply

Marsh Posté le 14-03-2009 à 13:08:06    

J'ai mis un affichage et ça marche pas, je comprend pas la  :??:  
 

Code :
  1. boolean testLigne(){
  2.  boolean test=true;
  3.  for( int i=0 ; i< n-1; i++ ){
  4.       test=true;
  5.       for( int k=i+1 ; k< n; k++ ){
  6.        for (int j=0 ; j<n;j++)
  7.         if(tab[i][j]!=tab[k][j])
  8.          test=false;
  9.        if(!test)
  10.          System.out.println("ligne "+i+" différente de ligne "+k);
  11.        else
  12.         System.out.println("ligne "+i+" égale à ligne "+k);
  13.       }
  14.       if(test)
  15.          return test;
  16.  }
  17.  return test;
  18. }


 
edit : apres quelques tests encore, ça marche seulement quand les lignes se suivent !


Message édité par kakashii le 14-03-2009 à 13:11:26
Reply

Marsh Posté le 14-03-2009 à 15:15:33    

Je pense qu'il faut déplacer la ligne "test=true;"
 

Code :
  1. boolean testLigne(){
  2. boolean test=true;
  3. for( int i=0 ; i< n-1; i++ ){
  4.     for( int k=i+1 ; k< n; k++ ){
  5.        test=true;
  6.        for (int j=0 ; j<n;j++)
  7.         if(tab[i][j]!=tab[k][j])
  8.          test=false;
  9.        if(!test)
  10.          System.out.println("ligne "+i+" différente de ligne "+k);
  11.        else
  12.         System.out.println("ligne "+i+" égale à ligne "+k);
  13.       }
  14.       if(test)
  15.          return test;
  16. }
  17. return test;
  18. }


Message édité par post_it le 14-03-2009 à 15:19:13
Reply

Marsh Posté le 14-03-2009 à 15:40:08    

Ah oui bien vu!
Je vous remercie ! Ca a l'air de marcher parfaitement :)

Reply

Marsh Posté le 14-03-2009 à 18:30:16    

De rien !  :)

Reply

Marsh Posté le 16-03-2009 à 09:29:20    

Il y a une méthode pour comparer 2 tableaux de booléens dans la classe java.util.Arrays : equals(double[] a, double[] a2)

 

Comme précisé, ça n'utilise pas == pour comparer les valeurs : pour bien gérer les valeurs NaN et -0.0d, ça créé des instances de Double donc c'est plus gourmand.
Si dans ton cas, tu n'as pas ces cas particuliers, il vaut mieux garder ta méthode


Message édité par Bidem le 16-03-2009 à 09:32:44
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed