Discussion :

[newgate]

Bonsoir à vous
Je cherche un programme C++ pour stocker une matrice à bande sous forme condensée, si quelqu'un peut m'aider je lui serais très reconnaissant
Voici un Exemple :
La matrice à bande originale
1 2 3 0 0
4 5 6 7 0
0 8 9 10 11
0 0 12 13 14
0 0 0 15 16
La matrice sera stockée comme une matrice rectangulaire en omettant les éléments nuls(la forme condensée):
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 0
15 16 0 0

merci à vous.

[Neckara]

Quelle utilisation sera faite de cette matrice à bande ?
Comment est stocké la matrice à bande originale?

Sinon je vous conseille l'utilisation d'un vector de list ou d'une list de list.

[newgate]

Bonsoir
La matrice à bande originale est saisie manuellement (cin) , en gros c'est pour résoudre un système d’équation linéaire par la méthode de Gauss.

[Neckara]

Un vector de vector serait peut être le plus approprié, tu perdras au niveau du chargement mais comme tu utilises cin, ça sera négligeable par contre tu gagneras énormément lors des accès.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
#include <vector>
int i = 0;
std::vector< std::vector< int > > matrice;
//tant que tu n'a pas fini
           //lire une ligne
           matrice.push_back( std::vector<int> );
           //tant que la ligne n'est pas finie de lire
                    matrice[i].push_back( valeur_lue);
           //fin tant que
           ++i;
//fin tant que

Tu peux lire une ligne avec getline et la stocker dans un string.
A partir du string tu peux créer un streamstring puis récupérer tes valeurs avec l'opérateur '>>'.

Essaye déjà de faire un petit programme et montre-nous ce que ça donne. Théoriquement tu as toutes les informations nécessaires^^

[newgate]

Merci Neckara je note ça
Mais ce qui me pose vraiment problème c'est comment le faire, c'est plus le coté algorithme.
merci encore

[Neckara]

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <vector>
#include <string>
#include <sstream>
 
std::string ligne;
int valeurLue;
std::vector< std::vector< int > > matrice;
for( .... ; getline(...., ....) ; .... )
{
           matrice.push_back( std::vector<int> );
           std::streamstring fluxLigne(...);
           while( .... ) //indice : utiliser l'opérateur >>
                    matrice[i].push_back( valeurLue);
}

Après je ne peux pas en faire plus sans faire le code à ta place.
Lis le man pour les différentes méthodes/classes que tu ne connais pas.

[newgate]

Merci Neckara

[oodini]

Si tu veux vraiment une forme condensée, il faut considérer que les quelques premières et dernières lignes ont une longueur différentes, jouer sur les indices de lignes pour gérer cela, et tout stocker à plat.

[newgate]

Bonsoir oodini
Justement c'est ce jeu sur les indices qui me prend la tête!!!

[Aleph69]

Bonjour,

tu as plusieurs choix de stockage possibles pour ta matrice

1 2 3 0 0
4 5 6 7 0
0 8 9 10 11
0 0 12 13 14
0 0 0 15 16

1. Format de stockage par bande :
le principe consiste à stocker chaque bande dans un vecteur en repérant sa position par rapport à la diagonale. Par convention, la position de la diagonale est fixée à zéro. La bande d'indice +1 correspond à celle placée juste au-dessus de la diagonale, celle d'indice +2 est celle encore au-dessus, etc. Les bandes en-dessous de la diagonale sont indicées de la même manière mais avec des nombres négatifs : la bande juste en dessous de la diagonale est indicée par -1, etc. Concrètement, dans ton exemple tu as 4 bandes, donc 4 vecteurs à stocker, d'indices respectifs -1, 0, 1, 2 :
-1 : [4 8 12 15]
0 : [1 5 9 13 16]
1 : [2 6 10 14]
2 : [3 7 11]

2. Format COO (Coordinate) :
c'est le format de stockage le plus simple. Il consiste à stocker chaque valeur non nulle dans un vecteur nzval, et de les repérées par leur indice de ligne et de colonne dans des tableaux respectifs rowind et colind. Ces tableaux sont de la taille du nombre de valeurs non nulles. Dans ton cas, tu as 13 valeurs non nulles avec :
nzval = [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]
rowind = [1 1 1 2 2 2 2 3 3 3 3 4 4 4 5 5]
colind = [1 2 3 1 2 3 4 2 3 4 5 3 4 5 4 5]
Remarque : j'indice les numéros de lignes et colonnes en commençant par 1 mais en C++ tu peux plutôt indicé en partant de zéro c'est plus pratique. Il faut juste tout décaler de -1. Par exemple, pour rowind ça donne
rowind = [0 0 0 1 1 1 1 2 2 2 2 3 3 3 4 4]
Il faut bien sûr faire la même chose pour colind dans ce cas.

3. Format CRS (Compressed Row Storage) :
ce format s'inspire du format COO mais en condensant les indices de ligne. Plutôt que de stocker chaque indice de ligne, on ne stocke que le numéro de la première valeur non nulle de chaque ligne (sorte de pointeur) dans un table rowptr :
nzval = [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]
rowind = [1 4 8 12 15 17] % le 17 correspond au nombre de valeurs non nulles+1
colind = [1 2 3 1 2 3 4 2 3 4 5 3 4 5 4 5]
Remarque : on stocke en plus le nombre de valeurs non nulles +1, ici 17, pour savoir quand s'arrête la dernière ligne.
Remarque 2 : attention, ce format est orienté par ligne, c'est-à-dire qu'il faut stocker les valeurs non nulles dans nzval en parcourant la matrice par ligne.

4. Format CCS (Compressed Column Storage) :
même principe que CRS mais par colonne.

Il existe encore plein d'autres formats mais ceux-ci sont les plus utilisés.

N'hésite pas si quelque chose n'est pas clair.

EDIT : oubli d'une ligne, corrigé.