-------------------------------------------------------
Partie I
-------------------------------------------------------
Exercice 1.1
-------------------------------------------------------
Un exercice tres elementaire. Une variable s sert a 
memoriser la somme des elements de t jusqu'a la 
position courante.

int est_propagation(int *t, int *u, int n) {
  int i, s = 0;
  for (i = 0; i < n; i++) {
    s+=t[i];
    if (u[i] != s)
      return 0;
  }
  return 1;
}

A noter que recalculer a chaque iteration la somme des 
elements t[0] + ... + t[i] est non seulement inutile, 
mais rend le traitement quadratique (et dans certaines 
copies, assez confus).
-------------------------------------------------------
Exercice 1.2
-------------------------------------------------------
Autre caracterisation de la propagation droite : si u 
est la propagation droite t, alors t[0] == u[0], et 
t[i] == u[i] - u[i-1] a partir de la position 1. Cette
remarque permet de reconstruire t a partir de u.

int *propagation_inverse(int *u, int n) {
  int *t = malloc(sizeof(int[n])), i;
  t[0] = u[0];
  for (i = 1; i < n; i++) {
    t[i] = u[i] - u[i-1];
  }
  return t;
}

L'allocation memoire est ici necessaire : en declarant
t par "int t[n]",  on ne declare qu'un tableau local
(une erreur commise dans plusieurs copies) dont rien ne 
garantit que le contenu sera preserve en retour d'appel.
-------------------------------------------------------
Exercice 2
-------------------------------------------------------
Un exercice pouvant etre laborieux, ou au contraire 
facile a programmer, selon la methode choisie. Voici 
une methode lineaire en max(n,m) (i.e. sans boucles 
imbriquees, comme le suggerait l'enonce). 

On utilise un tableau de marquage de meme longueur que 
t, indiquant par des 1 toutes les positions dans t qui 
apparaissent dans le tableau pos.

(1) etape 1 : construction du tableau de marquage
(2) initialisation des marques a 0
(3) remplissage du tableau des marques par parcours
    du tableau pos : un 1 a la position i dans le
    tableau des marques indique que t[i] doit etre
    conserve. le nombre d'elements a conserver
    est stocke dans p.
(4) si la position est valide et n'a pas deja ete
    rencontree, on met a 1 cette position dans le 
    tableau des marques. 
(5) etape 2, construction du tableau filtre.
    iu est la position d'ecriture dans u.
(6) si la position courante est marquee, on ecrit 
    sa valeur dans u.
(7) il ne faut pas oublier de liberer le
    tableau des marques.

int *filtrage(int *t, int n, int *pos, int m) {
  int *marques, *u, i, iu, p;
  marques = malloc(sizeof(int[n]))  // (1)
  for (i = 0; i < n; i++)           // (2)
    marques[i] = 0;
  p = 0;
  for (i = 0; i < m; i++) {         // (3)
    if (pos[i] >= 0 && 
        pos[i] <  n &&
        marques[pos[i]] == 0) {     // (4)
      marques[pos[i]] = 1;
      p++;
    }
  }
  u = malloc(sizeof(int[p]));       // (5)
  iu = 0;  
  for (i = 0; i < n; i++) {
    if (marques[i]) {               // (6)
      u[iu] = t[i];
      iu++;
    }
  }
  free(marques);                    // (7)
  return u;
}

Cet exercice n'etait pas si simple : a deux exceptions 
pres, il a ete traite de maniere assez confuse (retour 
de tableau local et/ou de taille incorrecte et/ou non 
alloue, tri incertain de positions collectees, retour 
d'un tableau de positions, exercice mal pompe avec 
oubli d'un bloc, etc).
-------------------------------------------------------
Partie II
-------------------------------------------------------
Trois exercices de programmation tres classiques, ne se 
servant que des elements de base du langage. Les deux 
premiers sont a peu pres du niveau cible de ce cours.
-------------------------------------------------------
Exercice 3
-------------------------------------------------------
(1) les lignes des deux textes vont etre lues en 
    parallele, avec deux compteurs, un pour chaque 
    texte.
(2) le traitement s'effectue (par exemple) jusqu'a la 
    fin de t. 
(4) si la fin de la ligne courante est atteinte dans 
    t et si la fin de s n'est pas deja atteinte, 
    les caracteres restants dans la ligne courante 
    de s doivent etre ignores : on se deplace dans s 
    jusqu'au marqueur de fin de ligne.
(5) les caracteres lus au positions courantes doivent
    etre egaux. si la fin de s est deja atteinte, la 
    comparaison (fausse) est celle de '\0' dans s 
    contre un caractere non nul dans t. si l'on est 
    passe par la boucle de (4), la comparaison (vraie)
    est celle des marqueurs de fin de ligne.
(6) on decale les positions de lecture dans s et t.
(7) en fin de boucle principale, la fin de t a ete 
    atteinte, et la fin de s doit aussi avoir ete 
    atteinte. l'ecriture gere en particulier le cas ou 
    t est vide : dans ce cas, on passe immediatement a 
    ce test, et t n'est un pre-acrostiche de s que 
    si s est vide.

int est_pre_acro(char *s, char *t) {
  int is = 0, it = 0;                         // (1)
  while(t[it] != '\0') {                      // (2)
    if (t[it] == '\n' && s[is] != '\0') {     // (3)
      while (s[is] != '\n') 
        is++;
    }
    if (s[is] != t[it])                       // (4)
        return 0;
    is++;                                     // (5)
    it++;
  }
  return (s[it] == '\0');                     // (6)
}

Noter qu'il est sans espoir de resoudre cet exercice
avec un seul compteur (ou sans au moins une seconde 
variable, permettant de decaler la position de lecture 
dans l'un des deux textes) : les lignes de meme rang 
dans s et t peuvent etre de tailles differentes, donc 
une comparaison de la forme s[i] == t[i] n'a plus de 
sens apres la lecture parallele des premieres lignes. 

D'autre part, le decompte du nombre de lignes est 
inutile : pendant la lecture, le cas ou s contient 
moins de lignes est directement gere par (4). En fin 
de lecture, le cas ou s contient plus de lignes est 
gere par (6).
-------------------------------------------------------
Exercice 4
-------------------------------------------------------
(1) la variable i va servir de position de lecture dans
    t. la variable d va servir a decaler la lecture 
    dans s, en ignorant le caractere a priori supprime.
    la variable co va servir a memoriser ce caractere,
(2) on parcourt les deux chaines en parallele, jusqu'a 
    la premiere difference, ou jusqu'a atteindre la 
    fin d'une des deux chaines.
(3) si s[i] == '\0', la premiere chaine est prefixe
    de la seconde (au sens large, c'est-a-dire avec 
    eventuellement egalite), donc t n'est pas un 
    lipossible de s.
(4) sinon, le caractere ote est a priori s[i].
(5) on continue la lecture de t.
(6) les occurrences de co dans s sont ignorees : on 
    incremente le decalage de la lecture dans s jusqu'a 
    ce que l'on rencontre un autre caractere que co.
(7) les caracteres lus aux positions courantes dans s 
    et t doivent etres egaux. 
(8) en sortie de boucle, la fin de t a ete atteinte, 
   et la fin de s doit aussi avoir ete atteinte.

int lipossible(char *s, char *t) {
  int i = 0, d = 0;                           // (1)
  char co;                                    // (2)
  while (s[i] != '\0' && 
         t[i] != '\0' && 
         s[i] == t[i]) {
    i++;
  }
  if (s[i] == '\0')                           // (3)
    return 0;
  co = s[i];                                  // (4)
  while (t[i] != '\0') {                      // (5)
    while (s[i + d] == co)                    // (6)
      d++;
    if (s[i + d] != t[i])                     // (7)
      return 0;
    i++
  }
  return (s[i + d] == '\0');                  // (8)
}

Comme precedemment, un seul compteur ne permet pas de 
resoudre cet exercice - il en faut deux, ou sinon, une
variable de decalage, comme dans la solution ci-dessus.
Autre remarque : NULL n'est pas une valeur de char, mais
une valeur de pointeur.
-------------------------------------------------------
Exercice 4
-------------------------------------------------------
Un exercice plus difficile. Voici une solution, 
minimisant le nombre de boucles et de relectures.

On va garder en memoire un tableau d'entiers de meme 
longueur que la premiere ligne, dans lequel les 
positions ne pouvant pas etre celles d'une colonne
constante seront progressivement mises a 1. 

(1) si la chaine est vide, elle ne contient pas de
    colonne constante.
(2) on calcule la longeur de la premiere ligne sans
    son '\n'. dans toute la suite, l vaudra la 
    longueur de cette ligne.
(3) on alloue un tableau de longueur l.
(4) on se place dans s apres la premiere ligne. 
    dans la boucle qui suit, a chaque iteration, 
    i vaut le depart de la ligne courante, et k vaut 
    le nombre de positions dans t passees a 1.
(5) on parcourt la ligne courante de s.
(6) si une position dans cette ligne est dans les 
    limites de t, non encore a 1 dans t, et si le
    caractere de meme position dans la premiere ligne
    differe de celui lu, on met a 1 la case de t
    correspondante, et on incremente k. La derniere
    instruction est equivalente a :
    t[p]  = 1;
    k = k + 1;
(7) on replace i immediatement apres la ligne lue.
(8) si la ligne lue est plus courte que la premiere,
    il faut aussi marquer toutes les positions dans t
    apres la derniere position de la ligne courante, 
    qui ne peuvent etre des positions de colonnes
    constantes.
(9) en sortie de boucle, il reste au moins une colonne
    constante si le nombre de 1 dans t ne depasse pas l.

int *col_cst(char *s) {
  int i, j, k = 0, l = 0;
  int *t;                                    
  if (s[l] == '\0')                          // (1)
    return 0;
  while(s[l + 1] != '\n')                    // (2) 
    l++;
  t = calloc(l, sizeof(int));                // (3)
  i = l + 2;                                 // (4)
  while(s[i] != '\0') {                      // (5)
    p = 0;
    while (s[i + p] !=\n') {                 // (6)
      if (p < l && !t[p] && s[i + p] != s[p])
        k += (t[p] = 1);
      p++;
    }
    i += p + 1;                              // (7)
    while (p < l) {                          // (8)
      if (!t[p]) 
        k += (t[p] = 1);
      p++;
    }
  }
  free(t);
  return (k < l);                            // (9)
}
-------------------------------------------------------
Partie III
-------------------------------------------------------
Les notions de liste chainee et de recurrence ont ete 
presque totalement incomprises. Quelques remarques 
generales, qui ne concernent pas seulement la notion 
de recurrence :
- une liste chainee n'est pas un tableau.
- ecrire pc -> suiv n'a de sens que si pc est different 
  de NULL (i.e. il faut gerer le cas pc == NULL avant
  d'acceder au champ, autrement dit gerer tous les cas 
  de base).
- ecrire pc -> suiv apres avoir libere pc par free 
  n'a pas de sens (l'espace memoire d'adresse pc a 
  peut-etre deja ete recycle).
- pour la meme raison, renvoyer pc apres avoir libere 
  pc n'a pas de sens (la valeur de retour est dans ce
  cas indefinie).
- lorsqu'une fonction n'est pas en void, elle doit 
  finir son execution par un return (sa valeur de 
  retour est indefinie sinon).
- lorsqu'une fonction n'est pas en void, on peut 
  l'appeler sous forme imperative (en ecrivant 
  par exemple "elagage_gauche(pc -> suiv);" au lieu de
  "pce =  elagage_gauche(pc -> suiv);", mais la valeur 
  de retour est alors perdue. Les appels recursifs ne 
  font pas exception a cette regle.
Sur les deux derniers points : presque tous les appels 
recursifs des copies sont ecrits sous forme imperative 
(avec, donc, perte de la valeur de retour), et beaucoup
de fonctions n'ont pas meme de return.
-------------------------------------------------------
Exercice 6
-------------------------------------------------------
(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 pc.
(2) sinon, il faut memoriser l'adresse de la cellule 
    qui suit la premiere...
(3) liberer la premiere cellule...
(4) puis renvoyer l'elagage gauche de la liste qui 
    suit la premiere cellule.

struct cell *elagage_gauche(struct cell *pc) {
  struct cell *pcs;
  if (pc == NULL)            // (1.1)
    return pc;
  if (pc -> suiv == NULL)    // (1.2)
    return pc;
  pcs = pc -> suiv;            // (2)
  free(pc);                    // (3)
  return elagage_gauche(pcs);  // (4)
}
-------------------------------------------------------
Exercice 7
-------------------------------------------------------
(1) si la liste est vide la fonction n'effectue pas 
    de traitement et se contente de renvoyer NULL
(2) sinon, et si la liste ne contient qu'une seule
    cellule, celle-ci est liberee - la liste 
    resultante est vide, la fonction renvoie NULL.
(3) sinon, on memorise l'adresse de la seconde 
    cellule.
(4) la premiere cellule est liberee.
(5) la seconde cellule est recablee a l'elagage
    alterne de la liste commencant apres cette seconde
    cellule.
(6) on renvoie l'adresse de la seconde cellule.

struct cell *elagage_alterne(struct cell *pc) {
  struct cell *pcs;
  if (pc == NULL)            // (1)
    return NULL;
  if (pc -> suiv == NULL) {  // (2)
    free(pc);
    return NULL;
  }
  pcs = pc -> suiv;          // (3)
  free (pc);                 // (4)
                             // (5)
  pcs -> suiv = elegage_alterne(pcs -> suiv);
  return pcs;                // (6)
}

A noter que l'exercice a ete plusieurs fois mal compris.
Il faut liberer une cellule sur deux a partir de la 
premiere (en particulier liberer pc si pc != NULL), et 
non a partir de la seconde (si pc -> suiv != NULL, 
pc -> suiv doit etre conserve).
-------------------------------------------------------
Exercice 8
-------------------------------------------------------
(1) si la liste est vide la fonction n'effectue pas 
    de traitement et se contente de renvoyer NULL
(2) sinon, et si l'elagage se fait apres la cellule de
    position 0, on se contente de recabler la premiere
    cellule a l'elagage de la suite. la position nc
    dans la liste initiale correspond a la position 
    (nc - 1) dans la suite.
(3) sinon, la cellule de position 0 doit etre supprimee.
    on memorise le depart de la liste qui suit cette 
    cellule.
(4) on libere la cellule de position 0.
(5) il reste a renvoyer l'elagage de la suite. par 
    convention, si k est nul, toute la liste doit etre 
    supprimee, et la prochaine suppression se fait a la 
    position 0. sinon, la prochaine suppression est a 
    la position k - 1 (eventuellement 0 si k vaut 1).
    
struct cell *egalage(struct cell *pc, int nc, int k) {
  struct cell *pcs;
  if (pc == NULL)            // (1)
    return pc;
  if (nc > 0) {              // (2)
    pc -> suiv = elagage(pc -> suiv, nc - 1, k);
    return pc;
  }
  pcs = pc -> suiv;          // (3)
  free(pc);                  // (4)
                             // (5)
  return elagage(pcs, k > 0 ? k - 1 : 0, k); 
}
-------------------------------------------------------