Quelques remarques sur l'examen, en attendant les notes definitives. 

Je ne m'attendais pas a ce que l'enonce soit integralement traite, 
mais au moins a ce que l'eventail des themes proposes (matrices et
boucles imbriquees, listes chainees et recurrence, tableaux et 
codage/decodage d'information) soit suffisamment large pour p
ermettre a chacun de traiter correctement au moins deux sections 
sur trois.

Au final, les copies se repartissent en deux groupes nettement
disjoints : un peu plus de la moitie d'un bon ou tres bon niveau, 
et un peu moins de la moitie d'un niveau insuffisant ou tres 
insuffisant - il reste a cette partie du groupe a profiter du 
projet de programmation pour rattraper son retard.

Exercice I
==========
Exercice sur un theme classique, massivement non traite, non 
compris, ou non fini : il a malgre tout ete bien reussi dans 
3 copies. Dans 2 autres, la methode choisie ne donne un resultat 
correct que dans un cas tres particulier (partie utile ne 
contenant aucun 0).

La seule difficulte etait de comprendre comment decomposer le 
traitement demande (calcul de la prtie utile) en taches plus 
elementaires (calculs de mins et de maxs). Il fallait :

(1) calculer
- le min des numeros de lignes contenant une valeur non nulle
- le min des numeros de colonnes contenant une valeur non nulle
- le max des numeros de lignes contenant une valeur non nulle
- le max des numeros de colonnes contenant une valeur non nulle

(2) detecter le cas ou la matrice est nulle.

(3) combiner les resultat de (1/2) pour initialiser la structure 
    a renvoyer.

Comme indique dans l'enonce, (1) pouvait etre realisee en un seul
parcours de la matrice - il suffisait de faire les 4 calculs en 
parallele, chacun travaillant avec sa propre variable.

utile
-----
struct rectangle utile(int m[TAILLE][TAILLE]) {
  int
    i, j,
    lmin = TAILLE, 
    cmin = TAILLE, 
    lmax = -1, 
    cmax = -1;
  struct rectangle r;

  for (i = 0; i < TAILLE; i++) 
    for (j = 0; j < TAILLE; j++) {
      if (m[i][j] != 0) {
	if (i < lmin) lmin = i;
	if (i > lmax) lmax = i;
	if (j < cmin) cmin = j;
	if (j > cmax) cmax = j;
      }
    }

  /* cas ou l'une des variables - e.g. lmin - est encore
   * a sa valeur initiale. dans ce cas, la matrice est
   * necessairement nulle - le test (m[i][j] != 0) n'a jamais 
   * ete verifie.
   */
  if (lmin == TAILLE) { 
    r.ligne   = 0;
    r.colonne = 0;
    r.largeur = 0;
    r.hauteur = 0;
    return r;
  }

  r.ligne   = lmin;
  r.colonne = cmin;
  r.largeur = cmax - cmin + 1;
  r.hauteur = lmax - lmin + 1; 
  return r;
}

Exercice II
===========
Le but de cet exercice etait de tester votre comprehension de
la notion de recurrence. 

L'exercice a ete assez moyennement reussi. Les fonction "egales"
et "prefixes" n'ont ete correctement ecrites dans aucune copie.
La fonction "copier" n'a ete correctement ecrite que dans 
3 copies (a une erreur negligeable pres dans deux d'entre elles).
 
Voici les erreurs les plus frequentes :

(1) Les cas ou l'une, l'autre, ou bien les deux listes arguments
sont vides n'ont pas ete bien geres (oubli, ou bien erreur de 
comprehension, en particulier pour prefixe). 

(2) Seule la moitie des copies contiennent des appels recursifs 
correctement ecrits. par exemple, dans la fonction "egales", on 
peut ecrire un appel de la forme :
  
  // ... tests, etc., puis :
  return egales (pc1 -> suiv, pc2 -> suiv);

Dans presque toutes les autres, cette forme devient :

  egales (pc -> suiv, pc2 -> suiv);  // (a)
  return 1;                          // (b)

soit, a l'execution :

  (a) appel recursif, mais perte de la valeur de retour 
      de cet appel.
  (b) retour de 1 quelle que soit la reponse de l'appel 
      precedent.

(3) Plusieurs copies contiennent, dans les fonctions "egales"
ou "prefixe", une structure while, par exemple :
    
  while (pc1 != NULL && pc2 != NULL) { ... }

L'utilisation d'un while serait justifiee si j'avais demande 
d'ecrire ces fonctions sans recurrence en parcourant les
listes, mais pas ici.

(4) Pour tester l'egalite des clefs des premieres cellules de 
pc1 et pc2, il faut ecrire (pc1 -> clef == pc2 -> clef), et non 
(pc1 == pc2), qui teste l'egalite des adresses pc1 et pc2
(c'est-a-dire qui teste si les deux cellules sont au meme 
emplacement en memoire).

egales
------
La fonction doit repondre 1 si et seulement si les suites de 
clefs de pc1 et pc2 sont egales. En particulier, si pc1 et pc2
sont vides, leurs suites de clefs sont egales, puisqu'elles dont 
toutes deux egales a la suite vide.

int egales(struct cell *pc1, struct cell *pc2) {
  /* on renvoie 1 si et seulement si :
   * - ou bien pc1 et pc2 sont toutes deux vides
   * - ou bien pc1 et pc2 sont toutes deux non vides, et
   *       leurs premieres clefs sont egales, et
   *       leurs suites sont egales.
   */
  return
    (pc1 == NULL && pc2 == NULL) ||
    (pc1 != NULL && pc2 != NULL  &&
     pc1 -> clef == pc2 -> clef  &&
     egales (pc1 -> suiv, pc2 -> suiv));
}

prefixe
-------
La fonction doit repondre 1 si et seulement si la suite des clefs
de pc1 est prefixe de celle de pc2. En appelant S1 la suite des 
clefs de pc1, S2 celle de pc2, on doit donc avoir :
 
  - S2 est egal a  (S1 suivi d'une certaine suite).

En particulier, la suite vide... est prefixe de toute autre 
suite, puisque pour toute suite S, on a :

  - S est egal a  (la suite vide suivi de S).


int prefixe(struct cell *pc1, struct cell *pc2) {
  /* on renvoie 1 si et seulement si :
   * - ou bien pc1 est vide
   * - ou bien pc1 et pc2 sont toutes deux non vides, et
   *       leurs premieres clefs sont egales, et
   *       la suite de pc1 est prefixe de celle de pc2
   */
  return
    (pc1 == NULL) ||
    (pc1 != NULL && pc2 != NULL  &&
     pc1 -> clef == pc2 -> clef  &&
     prefixe (pc1 -> suiv, pc2 -> suiv));
}

copier
------
La copie de la liste vide est la liste vide. Dans le cas ou la 
liste a copier est non vide, il faut creer une copie de sa 
premiere cellule, et a la chainer a une copie de la suite.

struct cell *copier(struct cell *pc) {
  struct cell *nc;
  if (pc == NULL) return NULL;
  nc = (struct cell *) malloc(sizeof(struct cell));
  nc -> clef = pc -> clef;
  nc -> suiv = copier(pc -> suiv);
  return nc;
}

Probleme
========
Aucune des fonctions a programmer n'etait algorithmiquement 
difficile, a condition comprendre l'enonce. En fait, seule la 
decompression demandait un peu de travail.

Etonnement, la question 1 a suscite un nombre invraisemblable 
d'erreurs de syntaxe - pour des fonctions ne mettant pourtant en 
jeu que les elements les plus basiques de C. Meme les fonctions 
correctement redigees font presque toutes les memes erreurs 
algorhitmiques :

- dans afficher_lexique, pas de retour-chariot apres le dernier mot
- dans afficher_mot, arret sur ' ' seul, i.e pas de gestion du 
  caractere '\0' si le mot du lexique a afficher est le dernier.
- dans afficher_texte, ajout d'un ' ' en trop apres le dernier mot.


afficher_lexique
----------------
On affiche tous les caracteres du lexique - sauf les espaces 
remplaces par des \n - plus un \n final apres le dernier mot.


void afficher_lexique(char *lexique) {
  int i;
  for (i = 0; lexique[i] != '\0'; i++)
    if (lexique[i] == ' ') printf("\n");
    else printf("%c",lexique[i]);
  printf("\n");
}

afficher_mot
------------
On affiche tous les caracteres a partir de la position pos, en 
s'arretant au 1er espace ou bien a la fin du lexique
   

void afficher_mot(int pos, char *lexique) {
  int i;
  for (i = pos; lexique[i] != ' ' && lexique[i] != '\0'; i++)
    printf("%c",lexique[i]);
}

afficher_texte
--------------
On affiche la suite des mots a chacune des positions de comp, en 
ajoutant un ' ' apres chacune des positions examinees sauf la 
derniere.

void afficher_texte(int *comp, char *lexique) {
  int i = 0;
  for (i = 0; comp[i] != -1; i++) {
    afficher_mot(comp[i], lexique);
    if (comp[i+1] != -1) printf(" ");
  }
}

taille_lexique
--------------
Le nombre de mots du lexique est le nombre de ses espaces + 1


int taille_lexique(char *lexique) {
  int i, k = 0;
  for (i = 0; lexique[i] != '\0'; i++)
    if (lexique[i] == ' ') k++;
  return k + 1;
}

taille_mot
----------
La taille d'un mot debutant en pos est le nombre de caracteres 
compris entre son premier caractere et l'espace suivant, ou bien 
la fin du lexique s'il s'agit du dernier mot.


int taille_mot(int pos, char *lexique) {
  int i;
  for (i = pos; lexique[i] != ' ' && lexique[i] != '\0'; i++);
  return i - pos;
}

pos_suivante
------------
La position suivante est celle qui suit l'espace suivant si cet 
espace existe. 

int pos_suivante(int pos, char *lexique) {
  int i;
  for (i = pos; lexique[i] != ' ' && lexique[i] != '\0'; i++);
  if (lexique[i] == ' ') return i + 1;
  return -1;
}

taille_texte
------------
La taille totale du texte est la somme de la taille de ses mots, 
plus une case pour chaque mot sauf le dernier.

int taille_texte(int *comp, char *lexique) {
  int i = 0, l = 0;
  for (i = 0; comp[i] != -1; i++) {
    l += taille_mot(comp[i], lexique);
    if (comp[i+1] != -1) l++;
  }
  return l;
}

decompresser
------------

char *decompresser(int *comp, char *lexique) {
  int i, j, k = 0;
  char *texte;

  /* allocation : 1 caractere de plus pour le '\0' */
  texte = (char *) malloc((1 + taille_texte(comp, lexique)) * sizeof(char));

  /* lecture de la suite de positions */
  for (i = 0; comp[i] != -1; i++) { 

    /* transfert du mot a la position courante */
    for (j = comp[i]; lexique[j] != ' ' && lexique[j] != '\0'; j++)
      texte[k++] = lexique[j];

    /* ajout d'un espace si la position courante n'est pas la derniere */
    if (comp[i+1] != -1) texte[k++] = ' ';

    /* ajout du marqueur de fin sinon */
    else texte[k++] = '\0';
  }
  return texte;
}