Discussion :

[TgRoX]

Bonjour,

Je bute depuis un moment sur l'algorithme qui me permettra de vérifier qu'un tableau 2D ne comporte que des chiffres uniques. J'ai eu un élan d'inspiration qui s'est vite estompé, je vous l'écris :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
   int chiffreTeste;
   for(int idLig = 0; idLig < TailleTableau2D; idLig++){
      chiffreTeste = idLig;
      for(int idCol = 0; idCol < TailleTableau2D; idCol++){
         if(idLig == idColà){
            continue;
         }
         if(tableau2D[idLig][idCol] == chiffreTest){
            cout << "Le tableau ne comporte pas que des valeurs uniques";
            break;
         }
      }
   }

Je me suis très vite rendu compte que ma variable chiffreTeste s'incrémentait à chaque tour de boucle et que par conséquent je n'effectue le test de chiffreTeste que sur une ligne et non sur le tableau entier.

Quelques conseils ?

Merci à vous

[cob59]

A ma connaissance on ne peut pas le faire directement avec la STL, mais c'est tout comme :

Code :

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

1
2
3
4
std::vector<int> vec ( tableau2D, tableau2D + TailleTableau2D );
std::sort( vec.begin(), vec.end() );
auto it = std::adjacent_find(vec.begin(), vec.end());
assert ( it == vec.end() );

Ou plus fourbe encore :

Code :

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

1
2
3
 
std::set<int> s( tableau2D, tableau2D + TailleTableau2D );
assert ( s.size() == TailleTableau2D );

Après, il y a sûrement plus optimal.

[Iradrille]

Code :

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

1
2
std::set<int> s( idLig, idLig + TailleTableau2D );
assert ( s.size() == TailleTableau2D );

Intuitivement je serai parti la dessus.

Les deux solutions que tu proposes sont en O(n * log n).

Code :

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

1
2
std::unordered_set<int> s( idLig, idLig + TailleTableau2D );
assert ( s.size() == TailleTableau2D );

Devrait être meilleur pour de grands tableaux (O (n)).
Pour de petits tableaux, il faudrait tester pour voir ce qui est le meilleur.

Si le tableau est déjà trié, alors un std::adjacent_find est clairement la meilleure solution (O(n)).

edit: à adapter si la mémoire du tableau 2D n'est pas consécutive. Il faut dans ce cas faire nbLignes (ou nbColonnes) insertions.

[Bousk]

Si tu es en C++11 tu as accès à
http://www.cplusplus.com/reference/algorithm/any_of/
http://www.cplusplus.com/reference/algorithm/all_of/
http://www.cplusplus.com/reference/algorithm/none_of/
Sinon, tu peux toujours ruser avec
http://www.cplusplus.com/reference/algorithm/find_if/

Si tu veux les réimplémenter c'est assez trivial, et tu peux par exemple utiliser l'exemple Python pour te rendre compte d'où mettre tes return en particulier
http://docs.python.org/2/library/functions.html#all
http://docs.python.org/2/library/functions.html#any

[TgRoX]

Bonjour,

Merci à vous pour vos réponses. J'ai entre temps réalisé un code qui semble fonctionner. Je vais étudier vos solutions un peu plus en détail car je n'ai pas encore le niveau nécessaire en c++ me permettant de les utiliser sans me poser de questions.

Pour ma part j'ai réalisé le code suivant (je ne recherche pas actuellement le code le plus optimisé, je cherche juste une solution qui marche, après quoi je vois si je peux faire quelque chose).

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
 
   if(ok){
 
      for(int iTest = 0; iTest < tailleCarre; iTest++){
         if(ok == false){
            break;
         }
         for(int jTest = 0; jTest < tailleCarre; jTest++){
            if(ok == false){
               break;
            }
            int chiffreTeste = carreMagique[iTest][jTest];
            for(int idLig = 0; idLig < tailleCarre; idLig++){
               if(ok == false){
                  break;
               }
               for(int idCol = 0; idCol < tailleCarre; idCol++){
                  if(idCol == jTest){
                     continue;
                  }
                  if(carreMagique[idLig][idCol] == chiffreTeste){
                     ok = false;
                     cout << "no !" << endl;
                     cout << carreMagique[idLig][idCol] << ' ' << chiffreTeste;
                     break;
                  }
               } 
            }
         }
      }   
   }

C'est très moche je vous l'accorde mais ça semble fonctionner. J'étudie de ce pas vos solutions !

[Bousk]

Tous ces if(ok) sont vraiment très moches et je comprends pas comment un esprit logique peut arriver à ça
alors qu'il suffit de placer un return false au milieu et un return true tout en bas.

[oodini]

Si tu stockais ton tableau 2D comme un tableau aplati, comme cela est souvent recommandé, tu pourrais utiliser std::unique_copy, puis comparer sa longueur avec celle du tableau original.

[Mat.M]

je suis d'accord avec Bousk c'est mal programmé
J'ai lu rapidement le code une fonction récursive serait peut-être plus appropriée

[TgRoX]

Salut,

Peut être aurais-je du préciser que je suis débutant et que je ne programme que depuis 4 mois. Il est clair que mes connaissances sont bien plus maigres que les vôtres et que mon esprit logique n'est pas aussi bien affûté que le vôtre.

Concernant la récupération des données dans un tableau aplati, je ne le fais pas car le chapitre en question de cet exercice concerne les tableaux multidimensionnels.

Je prends cependant bonne note de vos conseils et vais essayer de les appliquer. Je ne me suis pas encore attaqué aux fonctions récursives par contre, je ne serai pas capable de réaliser une telle manipulation.

Merci.

[koala01]

Salut,

Salut,

Peut être aurais-je du préciser que je suis débutant et que je ne programme que depuis 4 mois. Il est clair que mes connaissances sont bien plus maigres que les vôtres et que mon esprit logique n'est pas aussi bien affûté que le vôtre.

A ta décharge, je dois reconnaitre que l'algorithmie de base est souvent laissée beaucoup trop de coté dans la plupart des bouquins et tutoriels. Y compris ceux destinés aux débutants .

Par contre, la logique que tu suis est une logique basée sur le SESE (Single Entry Single Exit), et je crois sincèrement que tu n'aurais pas eu cette approche sans que "quelqu'un" ne t'ai soufflé dans l'oreille qu'il vallait mieux faire de la sorte

Ce "quelqu'un" mériterait d'être pendu haut et court car l'approche SESE n'est vraiment pas adpatée au C++ de manière générale

Concernant la récupération des données dans un tableau aplati, je ne le fais pas car le chapitre en question de cet exercice concerne les tableaux multidimensionnels.

Et alors

Qu'est ce qui t'empêche de te dire qu'un tableau "aplati" sera plus efficace qu'un tableau composé réellement de deux dimensions

C'est un argument d'autant moins convainquant que, si je peux comprendre le besoin de s'assurer qu'une valeur est unique dans un tableau plat, j'ai beaucoup plus de mal à envisager un cas d'utilisation réel au fait de s'assurer de la chose dans un tableau à plus d'une dimension

Je prends cependant bonne note de vos conseils et vais essayer de les appliquer. Je ne me suis pas encore attaqué aux fonctions récursives par contre, je ne serai pas capable de réaliser une telle manipulation.

le principe de base est simple : tu appelles la fonction dans laquelle tu te trouves en faisant varier les arguments de manière à tendre vers un cas où "il n'y a plus rien à faire".

La clé du succès est de tester en priorité si tu es dans ce cas particulier (que l'on appelle le cas de base) avant de faire quoi que ce soit d'autre.

Mais, sincèrement, la récursivité n'est pas la méthode la plus adaptée à la résolution de ton problème. Elle ne ferait que rajouter de la complexité à quelque chose qui peut être simplement effectué par des boucles, ce qui fait perdre tout intérêt à la pratique.

Dans certaines circonstances, la récursivité est utile et nécessaire parce qu'il serait beaucoup plus compliqué d'arriver à un résultat similaire avec de simples boucles. Il ne faut alors pas hésiter à l'utiliser.

Mais, si ce n'est pas le cas, s'il est au moins aussi facile d'implémenter quelque chose à l'aide de boucles que de le faire sous une forme récursive, il y a toujours intérêt à privilégier les boucles