TD 3: Pointeurs, Tableaux

Corrigés: 1.4.cc 1.5.cc 1.6.cc 2.1.cc 2.2.cc 2.3.fast_but_uses_some_mem.cc (rapide, mais utilise de la mémoire) et la version sans mémoire: 2.3.cc

Rappels

Exercice 1: Pointeurs, tableaux, algorithmes

  1. [Removed]
  2. [Removed]
  3. [Removed]
  4. Écrivez un fichier 1.4.cc contenant une fonction SortRev qui prend en argument un tableau d'entiers de taille arbitraire, et qui renvoie une copie du tableau triée par ordre décroissant. Le tableau pris en entrée ne doit pas être modifié.
    Indications:
    Vérifiez que votre code marche avec le fichier 1.4.main.cc:
    g++ 1.4.main.cc && ./a.out
    Essayez par exemple avec 1 4 3 9 -4 5 2 5

    RENDU: 1.4.cc

  5. (*) Écrivez un fichier 1.5.cc contenant une fonction HIndex qui calcule le h-Index d'un scientifique, étant donné une liste du nombres de citations qu'il a eu pour chacun de ses articles:
    int HIndex(int num_articles, const int* num_citations) {
      ...
    }
    Indication: on pourra utiliser la question précédente.

    Vérifiez votre code en copiant 1.4.main.cc dans 1.5.main.cc, et en le modifiant pour faire tourner HIndex() et afficher le résultat. Le h-Index de l'exemple donné dans le 1.4 doit être 4, par exemple.
    Autres cas à tester:
    RENDU: 1.5.cc

  6. (***) Écrivez une version 1.6.cc du fichier précédent qui n'utilise pas sort() (même indirectement) et qui fonctionne en temps linéaire, c'est-à-dire une complexité O(N), où N est le nombre d'articles. NOTE: sort() fonctionne en O(N log(N)).

    RENDU: 1.6.cc


Exercice 2: matrices

  1. Écrire un fichier 2.1.cc correspondant au fichier 2.1.h suivant:
    // Computes the trace (sum of elements of the diagonal) of a square NxN matrix,
    // flattened in memory.
    double trace(double* matrix, int N);
    RENDU: 2.1.cc

  2. De même avec 2.2.h:
    // Computes the matrix product of two matrices A and B of respective sizes NxM and MxP,
    // and returns a newly allocated NxP matrix. All matrices are flattened.
    double* matrix_prod(int n, int m, int p, double* a, double *b);
    RENDU: 2.2.cc

  3. De même avec 2.3.h:
    // Computes the transpose of a NxM matrix (see wikipedia), in-place. Stores
    // the result in the source matrix.
    void transpose(int n, int m, double* matrix);
    RENDU: 2.3.cc

  4. (****) Améliorer votre 2.3.cc pour qu'il n'utilise aucune mémoire supplémentaire (et qu'il marche meme sur des matrices non carrées).

    RENDU: 2.3.cc, amelioré.