chercher le maximum d'une matrice 2D

Version imprimable

28/05/2008, 13h15
poitou86

chercher le maximum d'une matrice 2D

Bonjour à tous et toutes,

mon problème consiste à chercher le maximum dans une matrice de deux dimensions sauf avec une particularité. Cette dernière se représente comme suit :
dans un premier temps je dois chercher le maximum dans toute la matrice et dans la suite je cherche toujours le maximum dans toute la matrice excepté de maximum trouvé dernièrement et ainsi de suite ... comme solution trier la matrice mais je veux dire ici que je tiens à retenir l'indice de ce maximum si je fais le tri les valeurs ne correspondent plus à leurs indices initiales dans la matrice !!!

Comment je fais ??? AIdez moi SVP

MERCI.
28/05/2008, 14h04
Alp

Tu peux te baser sur un conteneur standard contenant les indices et qui préserve l'ordre dans lequel tu insères. A la fin, tu obtiens donc une séquence contenant les indices, allant du maximum de ta matrice jusqu'au minimum. (pour le choix du conteneur -> FAQ C++)

Pour parcourir la matrice, je pense que tu as une idée...

Salut,

Le plus facile consistera sans doute à créer une structure qui soit en mesure de maintenir les coordonnées et la valeur dans la matrice, et de redéfinir l'opérateur < pour la structure

Elle pourrait très bien prendre la forme de
Code:

1 2 3 4 5 6 7 8 9 10 11 12 struct Coordonee { /* j'utilise le type size_t car je sais par avance qu'aucun indice ne sera * négatif, et que cela me permet d'assurer le fait que la structure * fonctionnera quelles que soient les dimensions de la matrice ;) */ size_t ligne; size_t colonne; leTypedElementDeLaMatrice valeur; bool operator<(const Coordonee& c1, const Coordonee& c2) const {return c1.valeur<c2.valeur;} };
Il faudra ensuite prévoir un moyen de contenir les différents éléments triés.

Une liste semble être la structure la plus adaptée pour ce faire (à défaut d'en savoir plus sur ce que tu veux faire une fois que tu dispose des éléments triés).

Je te conseillerais donc de te tourner vers la classe list fournie par le standard dans l'espace de noms std, et nécessitant l'inclusion du fichier <list>.

La déclaration de ta collection de coordonnées pouvant alors prendre la forme de
Code:

1 2 std::list<Coordonee> triListe;
il te sera alors loisible de remplir la collection avec un algorithme (je ne vais quand meme pas tout faire pour toi non plus :D) proche de
Code:

1 2 3 4 5 6 7 8 9 Pour L = 0 à nombre_Ligne Pour C = 0 à nombre_Colonne Coordonne actuel actuel.ligne <-- L actuel.colonne <-- C actuel.valeur <-- laMatrice[L][C] insérer actuel dans triListe fin Pour Fin Pour
Il ne te restera alors plus qu'à invoquer la méthode sort() sur ta liste pour obtenir la liste triée, mais, comme les valeurs seront placées dans l'ordre croissant, et que tu souhaite les avoir dans l'ordre décroissant, il faudra, au choix, utiliser les itérateurs inversé riterator, rbegin() et rend() soit demander à la liste d'inverser les éléments avec reverse() ;)

Une proposition:

Code:

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
#include <iostream>
#include <set>
#include <boost/multi_array.hpp>
 
typedef boost::multi_array<int, 2> Array2;
 
template <typename T>
struct IndexedArrayValue {
   IndexedArrayValue( const T & val, int i = -1, int j = -1) : value(val), index1(i), index2(j) {}
   T value;
   size_t index1, index2;
};
 
struct CompIAV {
   bool operator () ( const IndexedArrayValue<int> & left, const IndexedArrayValue<int> & right ) {
      if ( left.value == right.value ) {
         if ( left.index1 < right.index1 ) return true;
         else return ( left.index2 < right.index2);
      }
      return ( left.value < right.value );
   }
};
 
int main()
{
   Array2 array( boost::extents[3][3] );
   //... remplissage du tableau
 
   std::set<IndexedArrayValue<int>, CompIAV> indexedValues;
   for ( size_t i = 0; i < array.shape()[0]; i++)
      for ( size_t j = 0; j < array.shape()[1]; j++ )
         indexedValues.insert( IndexedArrayValue<int>(array[i][j], i, j ) );
 
   std::cin.get();
   return 0;
}

29/05/2008, 14h41
nicroman

Citation:

Envoyé par poitou86

Comme solution trier la matrice mais je veux dire ici que je tiens à retenir l'indice de ce maximum si je fais le tri les valeurs ne correspondent plus à leurs indices initiales dans la matrice !!!

Il ne faut pas trier les valeurs... mais les indices par rapport à leur valeur...