A (trop) peu d'exceptions pres, le niveau des copies 
est insuffisant, meme sur les questions de niveau 
elementaire... l'enonce n'etait pourtant pas plus 
difficile que celui de la premiere session, et ne 
portait que sur les bases du langage. J'esperais par 
ailleurs qu'un semestre de plus a programmer vous 
permettrait d'en traiter une bonne partie sans 
erreurs.

(1) Les contraintes de l'enonce et/ou l'enonce lui-meme
n'ont pas toujours ete respectes, ce qui a produit dans 
quelques copies du code inutilement complexe et/ou 
incorrect, ou meme hors-sujet : versions iteratives des 
fonctions recursives, patchwork semi-aleatoire de 
corrections d'exercices, ajout artificiel de bornes 
constantes sur les donnees, changement du type des 
fonctions, usage inadapte et incertain de la recurrence, 
fonction(s) main, fonction(s) d'affichage, etc.
 
Tous ces elements n'ont fait que vous faire perdre du
temps (et me fait me demander si cet examen n'aurait pas
gagne a etre fait sans notes) : les contraintes etaient 
simplement destinees soit a tester votre comprehension 
d'une notion particuliere (e.g. ecrire une fonction par 
recurrence, et non par iteration, ni en court-circuitant 
le principe d'un calcul par recurrence en utilisant une 
variable statique), soit a vous inciter a reflechir
suffisamment a un probleme particulier pour en trouver 
la solution la plus simple.

(2) La notion de recurrence est non comprise dans la 
presque totalite des copies ayant tente la premiere 
partie. Une majorite de copies commettent encore 
soit l'erreur de base consistant a croire que chaque 
variable locale d'une fonction n'existe qu'en un seul
exemplaire partage par tous ses appels recursifs, 
soit encore l'erreur (plus troublante) consistant a 
croire qu'il suffit, pour ecrire une fonction par 
recurrence, de l'ecrire sous forme iterative, puis 
d'inserer un appel recursif dans sa boucle principale 
pour la transformer en fonction recursive. Aux variantes
pres, j'ai retrouve par exemple dans trop de copies un 
code de cette forme pour la premiere question :

// ERR !
int parite_nombre (struct cell *pc) {
   int n = 0;
   // on doit compter le nombre de clefs
   while (pc != NULL) {
     n++;
     // hum... il faut bien ecrire un appel 
     // recursif quelque part... mettons, ici :
     parite_nombre(pc -> suiv)	
   }
   // on renvoie la parite du nombre de clefs
   return n % 2 == 0;
}

Cette forme d'ecriture (avec qui plus est un appel 
recursif sous forme imperative, c'est-a-dire dont la 
valeur de retour est perdue) est tout simplement vide
de sens : elle montre seulement que n'avez pas compris 
ce qu'est une recurrence. 

(3) La syntaxe du langage est a peu pres correcte dans
l'ensemble des copies, mais quelques-unes contiennent 
encore des variables "magiques" (non initialisees, mais 
censees valoir une quantite inconnue avant le traitement,
e.g. le nombre total de lignes d'un texte) ou des 
confusions de types (e.g. if (m[i][j] != NULL) ou encore
justifier_gauche(m)). Ces erreurs ne devraient plus etre 
commises a ce niveau.

(3) Le maniement de la post-incrementation etant propice 
aux erreurs de controle (notamment dans les cas limites),
il aurait sans doute ete plus raisonnable de renoncer a 
l'utiliser dans le cadre de cet examen. Bien sur, on peut
toujours ecrire :

int taille(int h, char m[MAX][MAX]) {
  int j, k = j = 0;
  while (j+=(k++,(m[h-1][j]?1:(h--,-j))),h);
  return k;
}

mais quel est le gain reel de cette ecriture ?


---------------------------------------------------
PARTIE I
---------------------------------------------------
Le but de cette partie etait de tester votre 
comprehension de la recurrence.	Voici une correction 
possible (elle pourrait etre ecrite de facon encore 
plus concise en se servant des conventions d'evaluation 
des conditions) :

// parite_nombre.
// (1) si la liste est vide elle est de
// longueur paire (0).
// (2) sinon, la liste commencant a la
// seconde clef doit etre de longueur
// impaire.

int parite_nombre(struct cell *pc) {
  if (pc == NULL) // (1)
    return 1;
  return // (2)
    parite_nombre(pc -> suiv) == 0; 
}

// parite_clefs.
// (1) si la liste est vide, toutes ses
// clefs sont paires (puisqu'elle ne 
// contient pas de clefs).
// (2) sinon, la premiere clef doit etre
// paire, et, 
// (3) la liste commencant apres 
// cette clef doit verifier le test.

int parite_clefs(struct cell *pc) {
  if (pc == NULL) // (1)
    return 1;
  if (pc -> clef % 2 == 1) // (2)
    return 0;  
  return // (3)
    parite_clefs(pc -> suiv);
}

// parite_alterne.
// (1) si la liste est vide, la suite de
// ses clefs est alternee (puisqu'elle
// est vide). 
// (2) sinon, la premiere clef doit etre 
// paire.
// (3) s'il n'y a pas de seconde clef, 
// le test est verifie.
// (4) sinon, la seconde clef doit etre
// impaire, et, 
// (5) la liste commencant apres la seconde 
// clef doit verifier le test.

int parite_alterne(struct cell *pc) {
  if (pc == NULL) // (1)
    return 1;
  if (pc -> clef % 2 == 1) // (2) 
    return 0;
  if (pc -> suiv == NULL) // (3)
    return 1;
  if (pc -> suiv -> clef % 2 == 0) // (4)
    return 0; 
  return // (5)
    parite_alterne(pc -> suiv -> suiv);
}

---------------------------------------------------
PARTIE II
---------------------------------------------------
Le but de cette partie etait d'evaluer votre capacite
a vous servir correctement des structures de controle
(if, while, for) pour decomposer, a chaque question, 
le traitement demande en taches plus simples. La 
comprehension de l'enonce n'etait pas censee faire
partie du probleme : les diagrammes etaient destines 
a lever toute ambiguite sur la nature de chaque 
traitement.

----
EX 1
----
La maniere la plus simple (et standard) d'ecrire 
cette fonction est d'utiliser deux indices : un
indice d'ecriture (iw) et un indice de lecture
(ir). Les caracteres sont transferes de la position
de lecture vers la position d'ecriture, mais l'indice
de lecture saute tous les espaces au debut de chaque 
nouvelle ligne. Il fallait (idealement) ne pas 
oublier de recopier le \n a la fin de la ligne 
courante lorsqu'il existe, gerer le cas ou cette 
ligne se termine par \0 au lieu de \n, et enfin 
placer un \0 a la fin de la chaine-resultat.

Voici une correction possible :

// (1) tant que l'indice de lecture n'est
// pas sur le marqueur de fin de chaine,
// (2) on cherche le debut du premier mot
// de la ligne courante.
// (3) on recopie la ligne courante a la 
// position courante d'ecriture, jusqu'a 
// atteindre la fin de la ligne (\n ou \0)
// (4) si la ligne se termine sur un '\n',
// il reste des lignes : on recopie aussi
// le caractere \n.
// (5) toutes les lignes ont ete traitees :
// on place le marqueur de fin de chaine.

void justifier_gauche(char *s) {
  int ir = 0;
  int iw = 0;
  while (s[ir] != '\0') { // (1)
    while (s[ir] == ' ')  // (2)
      ir++;
    while (s[ir] != '\n' && s[ir] != '\0') { // (3)
      s[iw] = s[ir];
      ir++;
      iw++;
    }
    if (s[ir] == '\n') { // (4)
      s[iw] = s[ir];
      ir++;
      iw++;
    }
  }
  s[iw] = '\0'; // (5)
}

Voici une autre version plus concise avec des do-while :

// on :
//    - cherche le 1er mot de la ligne courante
//    - on :
//    -   recopie les caracteres
//    - tant que :
//    -   le dernier caractere copie n'est pas
//    -   \n ou \0
// tant que :
//   le dernier caractere copie n'est pas \0

void justifier_gauche(char *s) {
  int ir = 0;
  int iw = 0;
  do {
    while (s[ir] == ' ') ir++;
    do {
      s[iw] = s[ir];
      ir++;
      iw++;
    } while (s[ir - 1] != '\n' && s[ir - 1] != '\0');
  } while (s[ir - 1] != '\0');
}

-------
ETAPE 1
-------
Il faut deux indices i, j pour se deplacer dans la 
matrice, et un indice k pour se deplacer dans la 
chaine (ou sinon une incrementation du pointeur s).

// (1) on parcourt les caracteres de la 
// chaine s.
// (2) si le caractere courant de s est un 
// retour la ligne dans s, on ajoute un \0 
// a la position courante d'ecriture dans m, 
// on revient a la colonne 0 et on passe a 
// la ligne suivante.
// (3) sinon, on copie ce caractere dans 
// m, on avance dans s et sur la ligne 
// courante de m.
// (4) le traitement se termine sur le \0
// de s, que l'on ecrit dans m. le nombre
// total de lignes transferees est i + 1 
// (et non i).

int transferer(char *s, char m[MAX][MAX]) {
  int i = 0, j = 0, k = 0;
  while (s[k] != '\0') { // (1)
    if (s[k] == '\n') {  // (2)
      m[i][j] = '\0'; 
      j = 0;
      i++;
    }
    else { // (3)
      m[i][j] = s[k];
      j++;
    }
    k++;
  }
  m[i][j] = '\0'; // (4)
  return i + 1;
}

-------
ETAPE 2
-------
Cette fonction ne posait acune difficulte. Noter
a l'etape (3) ci-dessous le test j > 0 dans la
condition du while, qui gere correctement le cas ou 
une ligne est vide (i.e. contient \0 a la colonne 0).

// (1) pour chaque ligne de texte stockee dans m
// (2) on cherche sa fin dans m,
// (3) on cherche le caractere apres son 
// dernier mot a partir de la fin,
// (4) on deplace le \0 a cette position. 

void tronquer(int h, char m[MAX][MAX]) {
  int i, j;
  for (i = 0; i < h; i++) { // (1)
    for (j = 0; m[i][j] != '\0'; j++); // (2)
    while (j > 0 && m[i][j-1] == ' ')  // (3)
      j--;
    m[i][j] = '\0'; // (4)
  }
}

-------
ETAPE 3
-------
Un exercice elementaire :

// (1) pour chaque ligne
// (2) on compte son nombre de caracteres
// (3) on met a jour la taille maximale .
int largeur(int h, char m[MAX][MAX]) {
  int max = 0, i, j;
  for (i = 0; i < h; i++) { // (1)
    for (j = 0; m[i][j] != '\0'; j++); // (2)
    if (j > max) // (3)
      max = j;
  }
  return max;
}

-------
ETAPE 4
-------
La difficulte de cet exercice est de ne pas se tromper
dans les decalages :

// (1) pour chaque ligne
// (2) on compte son nombre de caracteres
// (3) on calcule le nombre d'espaces a ajouter
// (4) on decale le texte vers la droite
// (5) on ajoute les espaces

void decaler(int h, int l_max, char m[MAX][MAX] {
  int i, j, spc;
  for (i = 0; i < h;  i++) { \\ (1)
    for (j = 0; m[i][j] != '\0';  j++); // (2)	
    spc = l_max - j; // (3)
    while (j >= 0) { // (4)
      m[i][j + spc] = m[i][j];
      j--;
    }
    while (spc > 0) { // (5)
      m[i][spc - 1] = ' ';
      spc--;
    }
  }
}

-------
ETAPE 5
-------
Il faut deux indices pour se deplacer dans m, et un
autre pour se deplacer dans t :

// (1) pour chaque ligne
// (2) on ecrit son contenu dans t
// (3) on ajoute dans un t un retour a la ligne
// (4) on ajoute dans t un marqueur de fin

void recomposer(int h, char m[MAX][MAX], char *t) {
  int i, j, iw = 0;
  for (i = 0; i < h; i++) { // (1)
    j = 0;
    while (m[i][j] != '\0') { // (2)
      t[iw] = m[i][j];
      iw++;
      j++;
    }
    t[iw] = '\n'; // (3)
    iw++;
  }
  t[iw] = '\0'; // (4)
}

-------
ETAPE 6
-------
Un traitement elementaire :

// (1) pour chaque ligne
// (2) on compte son nombre de caracteres
// (3) on ajoute a la taille courante
// le nombre de caracteres + 1.
int taille(int h, char m[MAX][MAX]) {
  int i, j, k = 0;
  for (i = 0; i < h; i++) {  // (1)
    for (j = 0; m[i][j] != '\0'; j++); // (2)
    k+= j + 1; // (3)
  }
  return k;
}
------------
ETAPE FINALE
------------
Il suffit d'assembler, dans l'ordre, les fonctions 
ecrites.

char *justification_droite (char *s) {
  char m[MAX][MAX], *t;
  int h, l_max;
  h = transferer(s, m); 
  tronquer(h, m);
  l_max = largeur(h, m);
  tasser_droite(h, l_max, m);
  t = malloc((1 + taille(h, m))*sizeof(char));
  recomposer(h, m, t);
  return t;
}