Programmation impérative : TP 6

Matrices carrées

But : réaliser un programme de manipulation de matrices carrées d'entiers.

On considèrera des matrices au sens « vraie 2d », c'est-à-dire que pour accéder à la case de coordonnées i,j, on doit pouvoir écrire t[i][j]. Dans la plupart des fonctions et procédures demandées, on sera amené à donner également en paramètre la taille de la matrice.

  1. Définir le type matrix.
  2. Réaliser et tester une fonction qui effectue l'allocation dynamique et renvoie une matrix de taille m fournie.
  3. Réaliser et tester une procédure d'affichage d'une matrix.
  4. Réaliser et tester une procédure d'affichage des adresses des cases d'une matrix. (Cf. format %p pour printf.)
  5. Dans la fonction main, permettre la saisie de la taille m au clavier, et tester.
  6. Réaliser et tester une fonction qui effectue le remplissage d'une matrix donnée par tirage aléatoire (cf. infra) de chaque élément entre 0 et un entier n fourni.
  7. Réaliser et tester une fonction d'addition de deux matrix (le résultat sera retourné, attention aux tailles).
  8. Réaliser et tester une procédure qui libère la mémoire allouée dynamiquement lors de la création d'une matrix.
  9. Réaliser et tester une fonction de multiplication de deux matrix (le résultat sera retourné, attention aux tailles).
  10. Réaliser et tester une fonction qui retourne la trace d'une matrix (somme des éléments diagonaux).
  11. Réaliser et tester une fonction qui calcule la transposée d'une matrix (le résultat sera retourné).
  12. Réaliser et tester une procédure qui effectue le remplissage d'une matrix donnée par les éléments du triangle de Pascal (0 ailleurs).

Annexe : Génération de nombres pseudo-aléatoires

La bibliothèque standard de C définit un générateur de nombre pseudo-aléatoire. La fonction

  int rand();
permet d'obtenir un entier pseudo-aléatoire compris en 0 et RAND_MAX. (RAND_MAX est une constante définie par le compilateur.) La séquence des nombres obtenus est déterministe, donc plusieurs exécutions du même programme donneront les mêmes valeurs.

Il est possible de changer ces valeurs en modifiant la « graine » initiale à partir de laquelle les valeurs pseudo-aléatoires successives sont obtenues. Pour cela, on utilise la fonction

  void srand(unsigned int seed);
qui utilise donc seed comme valeur initiale. Il ne faut faire appel à cette fonction qu'une seule fois par exécution (en général, au début de la fonction main), et non pas à chaque appel à rand, sinon la graine est réinitialisée et on retombe sur les même valeurs.

Pour avoir une valeur de graine différente à chaque exécution, on peut utiliser l'heure courante. La fonction

time_t time(time_t *tloc);
retourne le nombre de secondes depuis le premier janvier 1970.

On pourra donc faire :

#include <stdlib.h>
#include <time.h>

    ... fonctions qui utilisent rand() ...

int main() {
  srand(time(NULL));  
    ...
}

Pour obtenir une valeur pseudo-aléatoire comprise entre 0 et un certain entier n on pourrait faire rand() % (n + 1) mais si on fait cela certaines valeurs seront plus fréquentes que d'autres. Une bonne façon de procéder est d'utiliser la fonction auxiliaire suivante :

/*@ requires max <= RAND_MAX
  assigns nothing
  ensures returns a pseudo-random value between 0 and max included
  if rand() is assumed to be uniform, so is this function */
int rand_up_to(int max) {
  int r;
  do
    r = rand();
  while (r >= RAND_MAX - (RAND_MAX % (max + 1)));
  return r % (max + 1);
}