Quelques remarques sur l'examen, en attendant les
resultats definitifs... 
VP

----------------------------------------------------

Le sujet etait plutot centre sur la partie la plus 
elementaire de C : boucles, matrices et chaines 
(au lieu de listes chainees, allocation memoire
et recurrence sur les listes, les themes centraux 
des sujets des annees precedentes). Certains des
exercices n'etaient pas evidents a traiter en 
respectant les contraintes de l'enonce (e.g. une 
seule lecture de chaine dans pangramme), mais il 
vous restait toujours la possibilite de proposer 
une reponse ne respectant pas ces contraintes 
(quitte a ecrire des fonctions plus couteuses en 
temps et en memoire).

Au final, les copies se repartissent de facon assez 
nette en deux moities (inegales) : une (petite) 
moitie de copies de niveau plutot bon (dont quelques
unes de tres fort niveau), et une (plus grande) 
moitie de copies soit tres incompletes, soit avec 
tres peu d'exercices reellement compris.
 
A quelques exceptions pres, la syntaxe de base du 
langage C (variables, types, tableaux, boucles et
conditions) semble globalement acquise, ce qui est 
toujours ca, meme si j'ai trouve dans quelques 
copies des erreurs qui ne devraient plus etre 
commises a ce niveau, en particulier :

- confusion entre traitement et scanf - e.g. 
  printf "entrez le nombre de 1" + scanf dans la 
  fonction tasser_gauche.
- erreurs de controle (ou sens exact de return non 
  compris ?), parfois dans chaque fonction, e.g. : 
    for (i = 0;... ) {
      if (s[i] ...) 
         return 0
      else return 1
    }
  qui garantit qu'au tout premier passage dans la 
  boucle (i == 0), l'execution de la fonction sera 
  interrompue par l'un ou l'autre des return, quel
  que soit le resultat du test.
- confusion if/while
- confusion char et (char *)
- boucles for "paralleles" (e.g. une en i 
  croissante, une en j decroissante, censees
  s'executer simultanement)

----------------------------------------------------
PARTIE I
----------------------------------------------------
EX 1.1 (tasser_gauche)
----------------------------------------------------
Cet exercice etait de difficulte moyenne, et a ete 
plutot bien compris : les 2/3 des copies contiennent
une reponse au moins proche du traitement demande. 
Voici une solution possible :

/* EX 1.1
 * on implemente litteralement la methode 
 * donnee. chaque ligne est parcourue deux 
 * fois : (1) une fois pour compter ses 1, 
 * et (2) une seconde fois pour la reecrire
 */
void tasser_gauche(int m[HAUTEUR][LARGEUR]) {
  // i : ligne courante
  // j : colonne courante
  // n : compteur de 1 de la ligne courante
  int i, j, n;
  for (i = 0; i < HAUTEUR; i++) {
    n = 0;
    //(1)
    for (j = 0; j < LARGEUR; j++)
      if (m[i][j])
       n++;
    //(2)
    for (j = 0; j < LARGEUR; j++) {
      if (j < n)
        m[i][j] = 1;
      else 
        m[i][j] = 0;
    }
}     

Les erreurs les plus frequentes ont ete : 
- oubli ou mauvais placement de la reinitialisation
  du compteur de 1 (instruction n = 0 ci-dessus)
- reecriture des 1, mais pas des 0.
- erreurs dans les bornes des for (e.g. <= HAUTEUR,
  ou depart a 1 au lieu de 0)

A noter qu'il etait possible d'utiliser d'autres
methodes pour tasser la matrice. Voici par exemple 
la methode la plus rapide (implementee dans une 
copie), avec une seule lecture de chaque ligne et 
reecriture simultanee de la ligne courante :

void tasser_gauche(int m[HAUTEUR][LARGEUR]) {
  // i : ligne courante
  // j : colonne courante
  // w : position d'ecriture sur la ligne courante
  int i, j, w;
  for (i = 0; i < HAUTEUR; i++) {
    w = 0;
    for (j = 0; j < LARGEUR; j++)
      if (m[i][j]){
        if (w < j) {
          m[i][j] = 0;
          m[i][w] = 1;
        }
        w++;
      }
  }
}     

On pouvait aussi envisager de trier les elements 
de chaque ligne en utilisant un algorithme de tri
standard : sans etre optimale, cette solution etait 
correcte et complete, mais elle n'a ete bien
implementee que dans une seule copie.

----------------------------------------------------
EX 1.2 (sup_gauche)
----------------------------------------------------
Cet exercice etait en realite assez facile, a 
condition de garder en tete la definition d'un 
masquage (que des 0 et des 1) superieur (pas de 0 
au dessus d'un 1) gauche (pas de 0 a gauche d'un 1).

Les reponses proposees sont dans l'ensemble assez 
confuses. Une reponse reellement correcte et 
complete n'apparait que dans une seule copie. 
Dans les autres, on trouve :

- beaucoup d'erreurs de controle elementaires (en 
  particulier return 1 mal situes et provoquant 
  une sortie de fonction avant la fin du test)
- presqu'aucune gestion correcte des cas limites 
  (e.g. acces a m[i - 1][j] avec i == 0, ou bien 
   acces a m[i][j-1] avec j == 0)
- des tests incomplets (test de "gauche" mais pas 
  de "superieur", ou l'inverse, ou bien oubli 
  du test "masquage").
- des algorithmes inutilement compliques (e.g. 
  decompte du nombre de 1 sur une ligne, puis 
  verification qu'il y a bien autant de 1 en debut 
  de la ligne, suivi d'une verification - inutile - 
  qu'il n'y a plus que des 0 apres le dernier 1, 
  meme traitement pour les colonnes).

Il suffisait en fait de verifier, pour chaque case 
de m et en une seule lecture (d'ou la contrainte, 
destinee a vous orienter vers la solution la plus
simple), les trois proprietes d'une case d'un 
masquage superieur gauche : elle contient 0 ou 1, 
et si elle contient un 1, les cases situees au 
dessus et a gauche de cette case ne contiennent pas 
un 0 si ces cases existent. Voici une mise en forme 
possible du test :

/* EX 1.2
 * on parcourt la matrice en verifiant 
 * qu'elle ne contient que des 0 et des 1,
 * et qu'aucun 0 ne se trouve au dessus ou
 * a gauche d'un 1.
 */
int sup_gauche(int m[HAUTEUR][LARGEUR]) {
  int i, j;
  for (i = 0; i < HAUTEUR; i++) { 
    for (j = 0; j < LARGEUR; j++) {
      if ((m[i][j] != 0 && m[i][j] != 1) ||
          (i > 0 && m[i-1][j] < m[i][j]) ||
          (j > 0 && m[i][j-1] < m[i][j]))
        return 0; 
    }
  }
  return 1;
}

Noter l'ecriture des deux dernieres composantes de 
la condition du if : m[i-1][j] n'est une case de m 
que si i > 0, et de meme, m[i][j-1] n'est une case 
de m que si j > 0.

----------------------------------------------------
PARTIE II
----------------------------------------------------
EX 2.0 (lettre)
----------------------------------------------------
Un exercice basique : la possibilite de comparer 
deux valeurs de char (en effectuant implicitement 
une comparaison de leurs conversions en int, c'est-
a-dire de leurs codes ASCII) a ete mentionnee des 
le debut de ce cours.

/* EX 2.0
 * simple test du code ascii de c
 */
int lettre(char c) {
  return 'a' <= c && c <= 'z';
}

Pour une raison qui m'echappe, quelques copies 
accedent a c comme s'il s'agissait d'une chaine 
(c[i]) en effectuant une ou plusieurs boucles 
while (on peut a la limite se servir d'un if 
inutile, mais il n'y a ici qu'une seule donnee : c).
----------------------------------------------------
EX 2.1 (pangramme)
----------------------------------------------------
Cet exercice etait une adaptation du tri par 
denombrement vu en TD (exercice 5, TD 5-6), limitee 
a la premiere phase du tri (construction de 
l'inventaire des elements d'un tableau). 

A defaut de trouver la solution optimale, il etait 
assez facile a resoudre sans respecter la contrainte
sur l'unique lecture de s. Malgre cette possibilite,
l'exercice a ete peu et assez mal resolu. 

Deux copies seulement presentent une solution 
correcte et complete (l'une optimale, l'autre non 
optimale). Dans les autres on trouve, entre autres 
choses :

- test de non-repetition des lettres (le test est 
  correct, mais incomplet : il faut aussi verifier 
  que chaque lettre apparait une fois),
- test de non-repetition des caracteres (le test 
  est incorrect et incomplet : il ne faut pas 
  tenir compte des separateurs)
- tentative (confuse, mais au moins correcte dans 
  l'idee) pour isoler les lettres de s et les trier 
- tests hors-sujets (en particulier, test d'egalite 
  de tous les caracteres (?), plus ou moins bien 
  mis en forme).

-----------------
solution optimale
-----------------
Pour eviter de parcourir s plusieurs fois, il faut 
necessairement garder une trace des lettres deja 
rencontrees dans s. L'enonce precisait qu'il n'y a 
que 26 valeurs de lettres possibles. On peut donc 
se servir d'un tableau d'entiers contenant une case 
pour chaque lettre entre 'a' et 'z' (26 lettres, 
donc 26 cases), dont les cases sont initialisee 
a 0. 

Lors du parcours de s, a chaque fois que l'on 
rencontre une lettre, on fait passer de 0 a 1 sa 
case associee. Si cette case contient deja un 1, 
alors la chaine contient deux fois le meme 
caractere, et n'est pas un pangramme. 

Une fois s parcourue, la chaine est un pangramme si 
toutes les lettres ont ete rencontrees exactement
une fois, c'est-a-dire si toutes les cases du 
tableau sont passees a 1.

 
/* EX 2.1
 * (1) on initialise un tableau de marquage
 *     contenant une entree pour chaque 
 *     lettre (soit 26 cases)
 * (2) on parcourt la chaine. si le 
 *     caractere courant est une lettre,  
 *     - on calcule l'indice de sa case (k)
 *     - si la case contient deja un 1, 
 *       le texte n'est pas un pangramme
 *     - sinon, on fait passer cette case a 1
 * (3) on verifie que tous les caracteres 
 *     ont ete rencontres, c'est-a-dire 
 *     que toutes les cases du tableau de 
 *     marquage sont a 1.
 */

int pangramme(char *s) {
  int i, k;
  char table[26];

  //(1)
  for (i = 0; i < 26; i++)
    table[i] = 0;

  //(2)
  for (i = 0; s[i] != '\0'; i++)
    if (lettre(s[i])) {
      // calcul de l'indice de la 
      // case associee a s[i]
      k = s[i] - 'a';
      if (table[k]) 
        return 0;
      table[k] = 1;
    }
  
  //(3)
  for (i = 0; i < 26; i++)
    if (!table[i]) 
      return 0;
  return 1;
}

-----------------------
solutions non optimales
-----------------------
A defaut de trouver la solution optimale, on pouvait
aussi renoncer a ne parcourir s qu'une seule fois, 
et implementer un test avec des moyens plus couteux 
en temps d'execution, mais plus elementaires. On 
pouvait par exemple implementer litteralement la 
condition "pour chaque lettre entre 'a' et 'z', 
cette lettre apparait exactement une fois dans s" 
(avec 26 parcours de s dans le pire des cas). 

Dans le code ci-dessous, la boucle en c parcourt
tous les caracteres entre 'a' et 'z' inclus. la
variable k passe de 0 a 1 lorsque la valeur courante
de c est rencontree pour la premiere fois dans s.

int pangramme(char *s) {
  char c;
  int i, k;
  for (c = 'a' ; c <= 'z'; c++) {
    k = 0;
    for (i = 0; s[i] != '\0'; i++) {
      if (s[i] == c) {
        // k deja a 1 ?
        if (k) // i.e. if (k != 0) 
          return 0;
        else k = 1;
      }
    }
    // k encore a 0 ?
    if (!k) // i.e. if (k == 0) 
      return 0;
  }
  return 1;
}

Si une boucle avec un compteur de type char vous
parait un peu trop exotique, voici une autre 
solution, encore plus simple :

int pangramme(char *s) {
  char t[] ="abcdefghijklmnopqrstuvwxyz";
  int i, j, k;
  for (i = 0 ; i < 26; i++) {
    for (j = 0; s[j] != '\0'; j++) {
      if (s[j] == t[i]) {
        // k deja a 1 ?
        if (k) // i.e. if (k != 0) 
          return 0;
        else k = 1;
      }
    }
    // k encore a 0 ?
    if (!k) // i.e. if (k == 0) 
      return 0;
  }
  return 1;
}

----------------------------------------------------
EX 2.2 (palindromique)
----------------------------------------------------
Cet exercice etait probablement le plus difficile
de l'enonce : il n'etait pas evident d'en trouver
la solution generale.

Le test verifiant si une chaine est un palindrome
simple (si la chaine est egale a son image miroir) 
ne fonctionne pas ici, a cause des separateurs qui 
doivent etre ignores. A defaut de trouver la bonne 
solution, la moitie environ des copies proposent 
une implementation de ce test errone, avec souvent :

- de gros problemes de syntaxe de base (comme 
  l'emploi de "boucles paralleles")
- des erreurs d'indices (erreur dans le calcul
  de la position symetrique de la position
  courante).

int palindrome_simple(char *s) {
  // test de palindrome simple sur s
  int i, long = strlen(s);
  for (i = 0; i < long; i++) 
    if (t[i] != t[long - 1 - i])
      return 0;
  return 1;
}

Notez qu'aucune de ces copies ne precise que ce 
test n'est pas le bon, ce qui ne m'a pas permis
de savoir s'il s'agissait d'une reponse proposee 
faute de mieux (mais fonctionnant malgre tout 
dans le cas particulier ou la chaine ne contient 
aucun separateur), ou si l'enonce n'a pas ete 
compris.

Voici la solution optimale (qui, aux notations pres,
n'apparait que dans seule copie) :

/* EX 2.2
 * on positionne deux indices g et d aux 
 * extremites du texte. on fait avancer g 
 * et reculer d en parallele, en ignorant 
 * les separateurs (1 ou 2) et en comparant
 * s[g] et s[d] lorsque les deux sont places
 * sur des lettres (3). la boucle dure tant 
 * que g et d ne se sont pas rejoints (0).
 */
int palindromique(char *s) {
  int g = 0, d = strlen(s) - 1;
  //(0)
  while (g < d) {
    //(1)
    if (!lettre(s[g])) 
      g++;
    //(2)
    else if (!lettre(s[d])) 
      d--;
    //(3)
    else if (s[g] != s[d]) 
      return 0;
    else {
      g++;
      d--;
    }
  }
  return 1;
}

D'autres solutions etaient envisageables, comme 
par exemple tasser les lettres de s vers la gauche 
(sur place, ou mieux, dans un nouveau tableau, ce 
qui evite de detruire le contenu de s) puis faire 
un test de palindrome simple sur la partie de la 
chaine resultante uniquement constituee de lettres. 

int palindromique(char *s) {
  int long, k, i;
  char *t;

  long = strlen(s);

  // allocation de t : long (et non long + 1)
  // suffit, car le '\0' de s n'a pas besoin 
  // d'etre copie dans t.
  t = malloc(long *sizeof(char));

  // transfert des lettres de s dans t
  // k indique le nombre de lettres transferees
  k = 0;
  for (i = 0; i < long; i++)
    if (lettre(s[i])) {
      t[k] = s[i];
      k++;
    }

  // test de palindrome simple sur t
  for (i = 0; i < k; i++) 
    if (t[i] != t[k - 1 - i]) {
      free(t);
      return 0;
    }
  free(t);
  return 1;
}

Cette solution a ete tentee dans 4 copies, mais 
avec des erreurs dans le transfert des lettres 
(un seul indice) et/ou dans le test final (bornes).

----------------------------------------------------
EX 2.3 (chaine-valise)
----------------------------------------------------
EX 2.3.1 (superpose)
----------------------------------------------------
La premiere question ne comportait pas de difficulte
particuliere (c'est du moins ce que je pensais en
ecrivant l'enonce): il suffisait de comprendre la 
definition d'une superposition a partir du texte,
au besoin en s'aidant du diagramme. Pour que le 
test soit verifie, on doit avoir :

    s[pos]     == t[0]
    s[pos + 1] == t[1]
    s[pos + 2] == t[2]...
 
soit encore :

    s[pos + i] == t[i] 

pour chaque i allant de 0 jusqu'au dernier i tel 
que s[pos + i] soit different de '\0'.

/* EX 2.3.1
 * test de superposition, d'apres la
 * definition de cette notion.
 */
int superpose(int pos, char *s, char *t) {
  int i;
  for (i = 0; s[pos + i] != '\0'; i++)
    if (s[pos + i] != t[i]) 
      return 0;
  return 1;
}  

Curieusement, la definition n'a ete comprise que 
dans 4 copies... les reponses proposees dans les 
autres sont assez cahotiques. 
----------------------------------------------------
EX 2.3.2 (allouer_chaine)
----------------------------------------------------
Une question de cours plutot basique (mais aucune
reponse correcte). Il faut allouer (n + 1) chars 
(et non n, le "+ 1" etant destine au stockage de 
'\0' apres les n caracteres d'une chaine stockee 
a l'emplacement alloue) sans oublier de renvoyer 
l'adresse allouee (une erreur frequente).

/* EX 2.3.2
 * allocation - en tenant compte du
 * marqueur de fin (n + 1).
 */

char *allouer_chaine(int n) {
  return malloc((n + 1) * sizeof(char));
}
----------------------------------------------------
EX 2.3.3 (chaine_valise)
----------------------------------------------------
La difficulte de cette question etait de calculer 
correctement la longueur de la chaine-valise, 
deduite de la premiere position de superposition 
de s a t et de la longueur de t (pos + lt dans
le code ci-dessous).

La suite du traitement ne consiste qu'en la copie
du bon prefixe de s suivi de t dans le tableau
alloue (noter, a l'etape 4, l'ajout de '\0' a la 
fin de la chaine construite, oublie meme dans les 
reponses les plus completes).


/* EX 2.3.3
 * construction de la chaine-valise
 * (2) la taille de la chaine valise 
 *     resultante est pos + longueur de t, 
 *     ou pos est la 1ere position de 
 *     superposition (1).
 * (3) la chaine-valise est construite
 *     par transfert du bon prefixe de s
 *     puis de t, sans oublier le marqueur
 *     de fin (4).
 */
char *chaine_valise(char *s, char *t) {
  // pos : 1ere pos. de superposition
  // lt  : longueur de t
  // mv  : pointeur vers la zone allouee
  int 
    i, pos = 0, 
    lt = strlen(t);
  char *mv;

  //(1) recherche de la 1ere superposition
  while(!superpose(pos, s, t))
    pos++;

  //(2) allocation de la chaine-resultat
  mv = allouer_chaine(pos + lt);

  //(3) transfert des caracteres
  for (i = 0; i < pos; i++)
    mv[i] = s[i];
  for (i = 0; i < lt;  i++)
    mv[i + pos] = t[i];

  //(4) completion par '\0'
  mv[i + pos] = '\0';

  // 5) retour du resultat
  return mv;
}

A ce point de l'enonce, seules 4 copies ont propose
une reponse a peu pres coherente a cette derniere
question de la partie II (calcul de pos, allocation,
copie depuis s, copie depuis t, et enfin, retour).

----------------------------------------------------
PARTIE III
----------------------------------------------------
EX 3.1 (clefs_egales)
----------------------------------------------------
Un exercice classique. Il suffit de parcourir les
clefs et de verifier que chacune est egale a la 
suivante, lorsqu'elle existe. 

Voici une solution par iteration simple :

/* EX 3.1
*  egalite des clefs, version non recursive.
 * on verifie que chaque clef est egale a
 * la suivante si elle existe.
 */
int clefs_egales(struct cell *pc) {
  while (pc != NULL && pc -> suiv != NULL) {
    // comparaison des deux premieres clefs
    if (pc -> clef != pc -> suiv -> clef) 
      return 0;
    // deplacement sur la cellule suivante
    pc = pc -> suiv;
  }
  return 1;
}

et une solution recursive :

/* EX 3.1
 * egalite des clefs, version recursive :
 * les deux premieres clefs doivent etre
 * egales, et toutes les clefs de la liste
 * commencant a la seconde clef doivent
 * etre egales (appel recursif).
 */
int clefs_egales_rec (struct cell *pc) {
  if (pc == NULL || pc -> suiv = NULL) 
    return 1;
  return 
    (pc -> clef == pc -> suiv -> clef) 
    && clefs_egales_rec (pc -> suiv);
}

----------------------------------------------------
EX 3.2 (monotone)
----------------------------------------------------
Un exercice pas evident algorithmiquement. Voici 
une maniere d'implementer le test :

- on parcourt la liste, en calculant a chaque
  etape la difference entre la clef suivante 
  et la clef courante (d dans le code ci-dessous)
- la premiere fois que cette difference est 
  non nulle, on la memorise (dans dinit).
- on verifie aux etapes suivantes que le signe 
  des differences suivantes est le meme que cette
  premiere difference non nulle.

/* EX 3.3
*/
int monotone (struct cell *pc) {
  int  dinit= 0, d;
  while (pc != NULL && pc -> suiv != NULL) {
    // calcul de la difference courante
    d = (pc -> suiv -> clef) - (pc -> clef);
    // stockage s'il s'agit de la premiere 
    // difference non nulle
    if (dinit == 0)
      dinit = d;
    // sinon, comparaison des signes de dinit 
    // et de d : dinit * d n'est negatif que
    // si ces differences sont de signes opposes. 
    else if (dinit * d < 0) 
      return 0;
  }
  return 1;
}

----------------------------------------------------
CASSE-TETE FINAL
----------------------------------------------------
Un casse-tete difficile, peu tente, mais malgre 
tout reussi dans une copie.

/* il n'est pas difficile de caracteriser tous
 * les premiers caracteres de mots : il s'agit
 * de caracteres-lettres soit avec un 
 * separateur immediatement a leur gauche, soit
 * places en premiere position dans la chaine. 
 * la fonction suivante renvoie 1 si s[pos] est
 * un debut de mot, et 0 sinon.
 */

int debut_mot(char *s, int pos) {
  return 
    lettre(s[pos]) &&
    (pos == 0 || !lettre(s[pos - 1]));
}

/* la fonction suivante renvoie la premiere 
 * position d'un debut de mot a droite de pos 
 * dans s (ou la position de '\0' dans s si 
 * cette position est introuvable).
 */
int mot_suiv(char *s, int pos) {
  do {
    pos++;
  }
  while(s[pos] != '\0' && !debut_mot(s, pos));
  return pos;
}

/* la fonction suivante renvoie la derniere 
 * position d'un debut de mot a gauche de pos 
 * dans s (ou -1 si cette position est 
 * introuvable).
 */
int mot_prec(char *s, int pos) {
  do {
    pos--;
  }
  while(pos >= 0 && !debut_mot(s, pos));
  return pos;
}

/* la fonction suivante teste l'egalite
 * de deux mots de s commencant aux 
 * positions p_1 et p_2.
 */
int egalite_mots(char *s, int p_1, int p_2) {
  int i = 0;
  while (lettre(s[p_1 + i])) {
    if (s[p_1 + i] != s[p_2 + i]) 
      return 0;
    i++;
  }
  return !lettre(s[p_2 + i]);
}

/* test principal. on compare la suite des mots 
 * de s lus dans le sens gauche-droite a la 
 * suite de mots lus dans le sens droite-gauche. 
 * les fonctions precedentes servent a se deplacer 
 * de mot en mot, et a comparer les mots a chaque 
 * etape.
 */
int anacyclique(char *s) {
  int 
    dmg = mot_suiv(s, -1),
    dmd = mot_prec(s, strlen(s));

  while (dmg < dmd) {
    if (!egalite_mots(s, dmg, dmd))
      return 0;
    dmg =  mot_suiv(s, dmg);
    dmd =  mot_prec(s, dmd);
  }
  return 1;
}
----------------------------------------------------