-------------------------------------------------------
Exercice 1
-------------------------------------------------------
Un exercice elementaire. Une variable sert a memoriser
la position de derniere occurrence de c, une autre 
sert a memoriser la derniere distance minimale connue.
Chaque variable est initalisee a -1, pour indiquer que
sa valeur est encore indefinie. Une variable de plus
sert a calcuer la distance courante lorsque l'on 
rencontre c.   

int espacement(char *s, char c) {
  int pc = -1;
  int dm = -1;
  int dc;
  int i;
  for (i = 0; s[i] != '\0'; i++) {
    if (s[i] == c) {
      if (pc >= 0) {
        dc = i - 1 - pc;
        if (dm < 0 || dm > dc) 
          dm = dc;
      }
      pc = i;
    }
  } 
  return dm;
}
-------------------------------------------------------
Exercice 2
-------------------------------------------------------
Il faut simplement paralleliser le traitement precedent, 
en l'effectuant pour chaque valeur du type char. Les 
variables pc et dm deviennent des tableaux d'entiers a 
256 elements, chaque case memorisant l'information propre 
a une valeur de char. A noter qu'invoquer la fonction 
precedente pour chaque valeur de char > 0 relit s... 
255 fois - la consigne interdisant ces relectures etait 
clairement enoncee, il fallait donc une autre methode.

int *espacements(char *s) {
  int pc[256];
  int dm = malloc(sizeof(int[256]));
  int dc;
  int i;

  
  // initialisation.
  for (i = 0; i < 256; i++) {
    dm[i] = -1;
    pc[i] = -1;
  }

  for (i = 0; s[i] != '\0'; i++) {  
    if (pc[s[i]] >= 0)
      dc = i - 1 - pc[s[i]];
      if (dm[s[i]] < 0 || dm[s[i]] > dc) 
        dm[s[i]] = dc;
    }
    pc[s[i]] = i;
  } 
  return dm;
}
-------------------------------------------------------
Exercice 3
-------------------------------------------------------
Le tableau pc sert a present a memoriser la derniere
position connue de chaque caractere. Lorsque l'on 
rencontre a nouveau un caractere, la position memorisee
a l'etape precedente est celle de la case du tableau 
des distances qui doit etre mise a jour.

int *distances(char *s, int len) {
  int pc[256];
  int ds = malloc(sizeof(int[len]));
  int i;

  // initialisation.
  for (i = 0; i < 256; i++) {
    ds[i] = -1;
    pc[i] = -1;
  }
  for (i = 0; s[i] != '\0'; i++) {
    if (pc[c] >= 0)
      ds[pc[c]] = i - 1 - pc[c];
    pc[c] = i;
  } 
  return dm;
}

-------------------------------------------------------
Exercice 4
-------------------------------------------------------
L'exercice le plus difficile de l'enonce. Voici une
methode possible, sans allocations. 

On doit comparer la premiere ligne et la derniere, la 
seconde et l'avant-derniere, etc. A chaque comparaison, 
la premiere ligne sera appelee "ligne du haut", la 
seconde "ligne du bas". Au debut de chaque iteration de 
la boucle principale ci-dessous :
- dlh est place au debut de la ligne du haut,
- flb est place a la fin de la ligne du bas.
Le traitement consiste a reperer dans un premier
temps le debut de la ligne du bas, stocke dans dlb.
La position flb est deplacee en dlb - 1, en preparation
de l'iteration suivante. Les deux lignes sont comparees,
puis dlh est deplace a droite du '\n' de la ligne du
haut. Le traitement se poursuit tant que les deux
compteurs ne se sont pas croises.

int super_palindrome(char *s) {
  int dlh = 0;
  int flb = 0;
  int dlb;
  int j;

  // placement de flb sur le marqueur de la
  // derniere ligne...
  while(s[flb] != '\0') flb++;
  // si elle existe.
  if (flb == 0)
    return 1;
  flb--;

  // le compteur flb est a present a la fin de
  // la derniere ligne - ou en -1 s'il n'y a
  // qu'une ligne vide, mais dans ce cas, la
  // condition ci-dessous est imediatement fausse.

  while (dlh > flb) {
    // on cherche a rebours le debut de la
   //  ligne du bas. le test dlb >= 0 gere
   // le cas ou il n'y a qu'une seule ligne
   // non vide - dans ce cas, dlb descend
   // jusqu'a -1.
    dlb = flb;
    while (dlb >= 0 && s[dlb - 1] != '\n')
      dlb;
    // si les compteurs se sont rejoints,
    // ou si dlb vaut -1, ou bien le texte
    // ne contient qu'une ligne, ou bien
    // tout le texte a ete verifie. 
    if (dlb < 0 || dlb == dlh)
      return 1; 
    // sinon, on memorise immediatement la
    // position a gauche de dlb en preparation
    // de l'iteration suivante.
    flb = dlb - 1; 
    // on verifie a present l'egalite des lignes
    // du haut et du bas
    do {
      if (s[dlh] != s[dlb]) 
        return 0;
     dlh++;
     dlb++;
    } while(s[dlh - 1] != '\n');
    // en sortie du while, dlh est a droite
    // du '\n' de la derniere ligne haute,
    // et flb a gauche de la derniere ligne 
    // basse. la boucle principale continue.
  }
  return 1;
}
-------------------------------------------------------
Exercice 5
-------------------------------------------------------
L'exercice n'a pas ete traite.
-------------------------------------------------------
Exercice 6
-------------------------------------------------------
Les exercices de cette derniere partie etaient tres
simples, a condition d'avoir compris les notions de
listes chainees et de recurrence.

(1) si la liste est vide (1.1) ou ne contient qu'une 
    seule cellule (1.2), la fonction n'effectue pas 
    de traitement et se contente de renvoyer 1.
(2) sinon, il faut verifier que les deux premieres
    clefs sont distinctes, et tester la liste
    commencant apres la premiere cellule.

int sans_paliers(struct cell *pc) {
  if (pc == NULL)            // (1.1)
    return 1;
  if (pc -> suiv == NULL)    // (1.2)
    return 1;
  return                     // (2)
    pc -> clef != pc -> suiv -> clef &&
    sans_palier (pc -> suiv);
}
-------------------------------------------------------
Exercice 7
-------------------------------------------------------
L'exercice est le meme ou presque - mais il faut a 
present faire un test sur trois clefs.

(1) si la liste est vide (1.1) ou ne contient qu'une 
    seule cellule (1.2), la fonction n'effectue pas 
    de traitement et se contente de renvoyer 1. Si
    les deux premieres clefs sont egales, la liste
    n'est pas en dents de scie (1.3). Sinon, et si
    la liste ne contient que deux cellules (1.4), 
    elle est en dents de scie.
(2) sinon, il faut verifier que les trois premieres
    clefs sont en dents de scie, et tester la liste
    commencant apres la premiere cellule.

int en_dents_de_scie (struct cell *pc) {
  if (pc == NULL)            // (1.1)
    return 1;
  if (pc -> suiv == NULL)    // (1.2)
    return 1;
  if (pc -> clef == pc -> suiv -> clef) // (1.3)
    return 0;
  if (pc -> suiv -> suiv == NULL)  // (1.4)
    return 1;

  return 
    //  ou bien c1 < c2 > c3...
    ((pc -> clef < pc -> suiv -> clef &&
      pc -> suiv -> clef > pc -> suiv -> suiv -> clef) ||
    //  ou bien c1 > c2 < c3
     (pc -> clef > pc -> suiv -> clef &&
      pc -> suiv -> clef < pc -> suiv -> suiv -> clef))
    // et, la suite est en dents de scie
    && en dents_de_scie(pc -> suiv);
}
-------------------------------------------------------
Exercice 8
-------------------------------------------------------
Un exercice tres elementaire - noter que pour une fois,
on peut se permettre de perdre la valeur de retour de
l'appel recursif, puisque cette fonction renvoie toujours
son argument.

struct cell *jonction_voisins(struct cell *pc) {
  struct cell *npc;
  // cas de base
  if (pc == NULL)
    return pc;
  if (pc -> suiv)
    return pc;
  // creation et insertion de la jonction.
  npc = malloc(sizeof(struct cell));
  npc -> clef = pc -> clef + pc -> suiv -> clef;
  npc -> suiv = jonction_voisins(pc -> suiv);
  pc  -> suiv = npc;
  return pc;
}
-------------------------------------------------------