Matrius esparses (1): conversió

Una matriu esparsa (o dispersa) és una matriu en la qual la majoria dels
elements són zero. En lloc d’emmagatzemar tots els elements, la
representació esparsa guarda només els elements no nuls juntament amb
les seves posicions, estalviant memòria i temps de còmput. Per exemple,
la matriu:

$$\begin{pmatrix}
0 & 3 & 0 & 0 \\
0 & 0 & 5 & 0 \\
1 & 0 & 0 & 7
\end{pmatrix}$$

en representació esparsa per files queda:

  --------- --------------
   Fila 0:  (1,3).
   Fila 1:  (2,5).
   Fila 2:  (0,1) (3,7).
  --------- --------------

on cada parella (col,val) indica la columna i el valor de cada element
no nul, i el punt final . marca el final de la fila (fins i tot quan la
fila és buida).

En aquest problema, representem una matriu d’enters amb el tipus Matriu
i la versió esparsa amb el tipus MatriuEsparsa, definits a matrius.hh:

    typedef vector<vector<int>> Matriu;

    struct Casella {
        int pos;    // índex de columna
        int valor;  // valor de l'element
    };

    struct MatriuEsparsa {
        int ncols;                   // nombre de columnes
        vector<list<Casella>> files; // files de la matriu esparsa
    };

Fes la funció següent:

    /**
     * @brief Converteix una Matriu en una MatriuEsparsa.
     *
     * @param M Matriu rectangular de mida n x m.
     *
     * @pre M pot ser qualsevol matriu rectangular (incloent buida).
     * @post Retorna una nova MatriuEsparsa S, amb S.ncols == m i S.files.size() == n,
     *       on S.files[i] conté, ordenades per columna ascendentment, les caselles
     *       {pos, valor} dels elements no nuls de la fila i de M.
     */
    MatriuEsparsa matriu_converteix_a_esparsa(const Matriu& M);

Observació

Els fitxers públics (icona del gatet) contenen:

  ------------ ----------------------------------------------------
  main.cc      el programa principal, amb la entrada/sortida feta
  matrius.hh   els tipus Matriu, Casella i MatriuEsparsa
  Makefile     per compilar amb make còmodament
  .vscode      carpeta per compilar i depurar amb VSCode
  ------------ ----------------------------------------------------

Cal enviar únicament la implementació de la funció
matriu_converteix_a_esparsa, incloent-hi l’include de matrius.hh. No cal
enviar el main.

Entrada

La primera línia conté dos enters n i m (0 ≤ n, m ≤ 1000), el nombre de
files i columnes de la matriu. A continuació hi ha n línies, cadascuna
amb m enters separats per espais que representen les files de la matriu.

Sortida

La primera línia conté dos enters n i m, les dimensions de la matriu
esparsa resultant. A continuació hi ha n línies, cadascuna amb les
caselles no nul·les de la fila, en ordre ascendent de columna, amb el
format (col,val) separades per espais, seguides d’un punt .. Les files
sense cap element no nul es mostren únicament amb el punt ..

Informació del problema

Autoria: Pau Fernández

Generació: 2026-02-25T09:47:50.543Z

© Jutge.org, 2006–2026.
https://jutge.org
