Quelques remarques en attendant les notes definitives.
L'enonce etait assez long, et je ne m'attendais pas
a ce que tout le monde le finisse. Le niveau est assez
heterogene, mais plutot satisfaisant dans l'ensemble 
- cinq copies sont clairement d'un niveau clairement 
tres insuffisant (vides, ou vides de sens : assemblage
chaotique de code et/ou patchwork de corrections 
d'exercices), mais les autres tentent au moins de 
resoudre reellement les exercices poses (plusieurs 
sont meme clairement d'un tres bon niveau).

Partie I (Matrice)
------------------
Les deux exercices etaient assez faciles, mais le 
second presentait tout de meme une difficulte : il 
fallait comprendre l'enonce, ce qui n'etait pas
completement immediat.

Exercice 1
----------
Il suffit de verifier que pour chaque case de m, le 
contenu de cette case est le meme que celui : de la 
case atteinte par symetrie horizontale (1), de celle 
atteinte par symetrie verticale (2), et enfin, de 
celle atteinte en composant ces deux symetries (3). 

Pour les bornes des boucles, on peut prendre : 0 a H/2
inclus pour les lignes, 0 a L/2 inclus pour les 
colonnes (l'inclusion est necessaire). 

On peut aussi optimiser ces bornes, en fonction de 
la parite de H, et L : il n'est pas trop difficile 
de verifier que si H (resp. L) est impair, la boucle 
parcourant les lignes (resp. les colonnes) doit 
atteindre la ligne centrale de rang H/2 (resp. la 
colonne centrale de rang L/2). Mais si H (resp. L) est
pair, elle peut s'arreter immediatement avant la 
ligne H/2 (resp. avant la colonne L/2).


Erreurs-types
-------------
- boucles de 0 a H exclus, 0 a L exclus (redondances)
- boucles de 0 a H/2 exclus, 0 a L/2 exclus (incomplet)
- erreur d'indices (H - i et L - j).
- test incomplet (1 ou 2 tests sur 3)

Solution
--------
int bisymetrique(int m[H][L]) {
  int i, j, n, p;
  // calcul des bornes des deux boucles
  if (H % 2 == 1)
    n = H/2;
  else n = H/2 - 1;
  if (L % 2 == 1) 
    p = L/2;
  else p = L/2 - 1;
  // parcours effectif de m
  for (i = 0; i <= n; i++)
    for (j = 0; j <= p; j++) 
      if (m[i][j] != m[H - 1 - i][j] ||       // (1)
          m[i][j] != m[i][L - 1 - j] ||       // (2)
          m[i][j] != m[H - 1 - i][L - 1 - j]) // (3)
        return 0;
  return 1;
}

Exercice 2
----------
L'enonce precise que le contenu de m doit etre 
initialise a 0 (1). Ensuite, il suffit d'incrementer 
m[t[i]][t[i+1]] pour chaque i de 0 a n - 1 exclus (2).

Erreurs-types
-------------
- m non initialise
- boucle de 0 a n inclus (t[i+1] hors du tableau)

Solution
--------

(1) mise a 0 de tous les elements de m.
(2) calcul des successions.

void successions(int n, int *t, int m[N][N]) {
  int i, j;
  for (i = 0; i < N; i++)     // (1)
    for (j = 0; j < N; j++) 
      m[i][j] = 0;
  for (i = 0; i < n - 1; i++) // (2)
    m[t[i]][t[i + 1]]++;
} 

Partie II (Chaines)
------------------
Des enonces ultra-classiques, n'utilisant que de 
simples boucles et des tests, mais malgre tout pas 
evidents. Il faut, dans chaque fonction, parcourir 
le texte ou au moins une partie du texte, tout en 
memorisant les bonnes informations (position de 
depart de la ligne courante, longueur de cette ligne, 
nombre de lignes deja lues, etc.).


Exercice 3
----------
Il faut memoriser le nombre de caracteres de la toute 
premiere ligne, et verifier pour chaque autre ligne 
a la meme longueur. Il faut aussi memoriser le nombre 
total de lignes lues, et comparer en fin de traitement
ce nombre a la taille de la premiere ligne.
 
variables :
 i  : compteur de la boucle principale
 cl : compteur de lignes
 n  : taille de la premiere ligne, -1 si cette ligne 
      n'a pas encore ete lue
 cc : compteur de caracteres de la ligne courante

etapes :
(0) on gere le cas limite ou le texte est vide 
(1) parcours du texte
(2) si le caractere courant n'est pas \n, on 
    incremente simplement le compteur de caracteres 
    de la ligne courante (cc)
(3) sinon, on vient de finir la lecture d'une ligne. 
    si n est encore negatif, on vient de finir de lire
    la toute premiere ligne : n passe au nombre de 
    caracteres de cette ligne.
(4) sinon, la premiere ligne a deja ete lue, et on a 
    lu jusqu'a maintenant que des lignes de longueur 
    n. si la ligne courante ne fait pas n caracteres, 
    le texte n'est pas carre : on quitte la fonction 
    en renvoyant 0.
(5) la ligne est de la bonne longueur. on reinitialise
    cc, et on incremente le compteur de ligne (cl)
(6) en fin de boucle, le nombre de lignes lu (cl) 
    doit etre egal a n.

int carre(char *s) {
  int i, cl = 0, n = -1, cc = 0; 
  if (s[0] == '\0')                // (0)
   return 1; 
  for (i = 0; s[i] != '\0'; i++) { // (1)
    if (s[i] != '\n')              // (2)
      cc++;
    else {
      if (n < 0)                   // (3)
        n = cc;
      else 
        if (n != cc)               // (4)
          return 0;
      cc = 0;                      // (5)
      cl++;
    }
  }
  return n == cl;                  // (6)
}

Exercice 4.1
------------
Il faut necessairement chercher la position de depart 
de la ligne n.k, et calculer sa longueur.
 
variables :
 pk : position de debut de la ligne n.k (apres (1))
 j  : compteur auxiliaire
 lk : longueur de la ligne n. k (apres (2))
 cl : compteur de lignes
 t  : zone memoire allouee

etapes :
(1) on cherche le debut de la ligne n. k
(2) on calcule la taille de cette ligne (lk)
(3) la taille d'allocation est lk + 1 
(4) copie effective de la ligne n.k dans t
(5) marquage, et retour.

char *ligne(int k, char *s) {
  int pk = 0, j, cl = 0, lk;
  char *t;
  while(cl < k) {         // (1) 
    if (s[pk] == '\0')
      return NULL;
    if (s[pk] == '\n')
      cl++;
    pk++;
  }
  for (lk = 0; s[pk + lk] != '\n'; lk++); // (2)
  t = malloc((lk + 1)* sizeof(char));     // (3)
  for (j = 0; j < lk; j++)                // (4)
    t[j] = s[pk + j];
  t[j] = '\0';                            // (5)
  return t;
}


Exercice 4.2
------------
Il faut d'abord calculer le nombre total de lignes
pour connaitre la taille d'allocation - donc, 
parcourir une premiere fois le texte. Il faut ensuite 
reparcourir chaque ligne en calculant sa longueur, 
copier le caractere de rang k dans la zone allouee 
s'il existe, un espace sinon.

 
variables :
 i  : compteur global (pour les deux parcours)
 cl : compteur de ligne (pour le second)
 nl : nombre total de lignes
 lc : longueur de la ligne courante
 t  : zone memoire allouee

etapes :
(1) on calcule le nombre total de lignes (nl)
(2) la taille d'allocation est nl + 1. on marque 
    immediatement la fin de t.
(3) on replace i en 0 (donc au debut de la ligne n. 
    0). on initialise a 0 le compteur de ligne (cl). 
    ensuite, pour chaque ligne :
(4) on calcule la longueur de la ligne courante (lc)
(5) on copie dans t son caractere n.k s'il existe,
    un espace sinon.
(6) on incremente le compteur de ligne (cl). on 
    deplace i apres le \n de la ligne courante.
(6) retour.

char*colonne(int k, char *s) {
  int i, cl, nl = 0, lc = 0;
  char *t;
  for (i = 0; s[i] != '\0'; i++)            // (1)
    if (s[i] == '\n')
      nl++;
  t = malloc((nl + 1) * sizeof(char));      // (2)
  t[nl] = '\0';
  i  = 0;                                   // (3)
  cl = 0;
  while(cl < nl) {                           
    for (lc = 0; s[i + lc] != '\n'; lc++);  // (4)
    if (k < lc)                             // (5)
      t[cl] = s[i + k];
    else t[cl] = ' ';
    cl++;                                   // (6)
    i = i + lc + 1;
  }
  return t;
}


Exercice 4.3
------------
Il faut necessairement calculer la position de depart 
de la ligne n.k, sa longueur, ainsi que la taille 
totale du texte (et en deduire la taille du texte 
moins sa ligne n.k).
 
variables :
 pk : position du debut de la ligne n.k
 j  : compteur auxiliaire
 ls : taille totale de s
 cl : compteur de lignes
 lk : longueur de la ligne n.k
 t  : zone memoire allouee

etapes :
(1) on place pk sur le debut de la ligne n. k 
(2) on calcule la taille de cette ligne (lk)
(3) on calcule la taille totale de s (ls)
(4) la taille d'allocation est ls - (lk + 1) + 1,
    (lk + 1, car il faut compter le \n de la
     ligne n.k, lui aussi elimine), soit ls - ln.
(4) copie de toute la zone entre 0 et i exclus.
(5) copie de toute la zone entre la fin de la ligne
    n.k (en s[pk + lk + 1]) jusqu'au marqueur de
    fin du texte inclus (en s[ls]).
(6) retour.


char *effacer_ligne(int k, char *s) {
  int pk = 0, j, ls, nl = 0, lk;
  char *t;

  while(nl < k) {        // (1)
    if (s[pk] == '\0')
      return NULL;
    if (s[pk] == '\n')
      nl++;
    pk++;
  }
  for (lk = 0; s[pk + lk] != '\n'; lk++);       // (2)
  for (ls = pk + (lk + 1); s[ls] != '\0'; ls++);// (3)
  t = malloc((ls - lk)* sizeof(char));
  for (j = 0; j < pk; j++)                      // (4)
    t[j] = s[j];
  for (j = pk + lk + 1; j <= ls; j++)           // (5)
    t[j - (lk + 1)] = s[j];
  return t;                                     // (6)
}

Exercice 4.4
------------
Pour allouer une sone exactement de la bonne taille,
il faut calculer la taille totale du texte (valeur
de i en fin de la premiere boucle), ainsi que le
nombre de caracteres a effacer (combien de lignes
sont de longueur strictement inferieure a k). Ensuite,
on copie chaque ligne sauf son caractere de rang k
dans la zone allouee.

variables :
 i  : compteur principal
 j  : compteur auxiliaire
 ne : nombre de caracteres a effacer
 cc : compteur de caracteres de la ligne courante
 t  : zone memoire allouee

etapes :
(1) on compte le nombre de caracteres a effacer (ne)
(2) en fin de boucle, i vaut le nombre de 
    caracteres de s. la taille d'allocation est 
    i - ne + 1.
(3) on replace i au debut du texte, et j au debut
    de la zone allouee. pour chaque ligne :
(4) on parcourt ses caracteres, en les copiant tous 
    sauf celui de position k s'il existe.    
(5) on copie aussi le '\n' de cette ligne.
(6) on deplace i apres le caractere \n de la ligne
    courante.

char *effacer_colonne(int k, char *s) {
  int i, j, ne = 0, cc = 0;
  for (i = 0; s[i] != '\0'; i++)           // (1)
    if (s[i] != '\n')
      cc++;
    else {
      if (k < cc)
	ne++;
      cc = 0;
    }
  t = malloc((i - ne + 1) * sizeof(char)); // (2)
  i = 0;                                   // (3)
  j = 0;
  while (s[i] != 0) {
    for (cc = 0; s[i + cc] != '\n'; cc++)  // (4)
      if (cc != k) {
	t[j] = s[i + cc];
	j++;
    }
    t[j] = s[i + cc];                      // (5)
    j++; 
    i = i + cc + 1;                        // (6)
  }
  return t;
}


Partie III (Listes chainees)
----------------------------
Les exercices 5 et 6 n'etaient pas trop durs a traiter,
a condition bien sur d'avoir compris la notion de 
recurrence. L'exercice 7 etait plus difficile, et le
casse-tete quasi-infaisable.

Exercice 5
----------
(1) si les deux listes sont vides, l'amalgame est vide.
(2) sinon, l'amalgame contient au moins une cellule.
(3) on additionne a 0 les clefs des listes encore
    actives, et on avance leurs pointeurs vers leurs
    successeurs. le resultat de l'addition est la clef
    de la cellule allouee. 
(4) le successeur de la cellule allouee est l'amalgame
    des successeurs des listes encore actives (leurs
    pointeurs ont deja ete deplaces en (3)).

struct cell amalgame(struct cell *pcg, 
                     struct cell *pcd) {
  struct cell *pcn;
  if (pcg == NULL && pcd == NULL)    // (1)
    return NULL;
  pcn = malloc(sizeof(struct cell)); // (2)
  pcn -> clef = 0;                   // (3)
  if (pcg != NULL) {
    pcn -> clef += pcg -> clef;
    pcg = pcg -> suiv;
  }
  if (pcd != NULL) {
    pcn -> clef += pcd -> clef;
    pcd = pcd -> suiv;
  }
  pcn -> suiv = amalgame(pcg, pcd);  // (4)
  return pcn;
}

Exercice 6
----------
(1) si (pcg est vide ou k == 0) et pcd est vide,
    le croisement est vide : (a) aucune clef ne peut
    etre prise dans pcg si elle vide, et si k == 0,
    aucune clef ne doit etre prise dans pcg; (b) si 
    pcd est vide, aucune clef ne peut etre prise 
    dans pcd.
(2) si k > 0 et si pcg est vide (donc pcd non vide, 
    puisque le test (1) n'a pas ete verifie) le 
    croisement contient, d'apres l'enonce, la suite 
    de clefs apres les k premieres clefs de pcd, ou 
    encore, la suite de clefs commencant apres les  
    k - 1 premieres cellules de pcd -> suiv.
(3) sinon, le croisement contient au moins une clef.    
(4) si k > 0 (donc pcg non vide, puisque le test (2)
    n'a pas ete verifie), la premiere clef du croisement 
    est la premiere de pcg. sinon, k == 0 (donc pcd
    est non vide, puisque le test (1) n'a pas ete 
    verifie) il s'agit de la premiere clef de pcd. 
(5) on avance les pointeurs des listes encore
    active vers leurs successeurs. on decremente
    k s'il est positif.
(6) on chaine la nouvelle cellule au croisement des
    successeurs.

struct cell *croiser(int k, struct cell *pcg, 
                            struct cell *pcd) {
  struct cell *pcn;

  if ((pcg == NULL || k == 0) && pcd == NULL)  // (1)
    return NULL;

  if (pcg == NULL && k > 0)                    // (2)
    return croiser(k - 1, NULL, pcd -> suiv); 

  pcn = malloc(sizeof(struct cell));           // (3)

  if (k > 0)                                   // (4)
    pcn -> clef = pcg -> clef;
  else pcn -> clef = pcd -> clef;
   
  if (pcg != NULL)                             // (5)
    pcg = pcg -> suiv;
  if (pcd != NULL)
    pcd = pcd -> suiv;
  if (k > 0)
    k--;                    
  pcn -> suiv = croiser(k, pcg, pcd);          // (6)
  return pcn;
}

 



Exercice 7
----------
Un exercice assez difficile... Voici une solution
en temps quadratique en le nombre de cellules.

(1) on sauvegarde le debut de la liste.
(2) on gere le cas liste vide.
(3) si pc est sur une cellule chainee a NULL,
    la liste n'est pas bouclante.
(4) sinon, on deplace pc vers son successeur. on place
    pcc sur la cellule initiale pci. on parcourt avec 
    pcc toutes les cellules de pci a pc. 
(5) si pc est chainee a pcc, la liste est bouclante.
(6) condition d'arret de la boucle interne : pcc a 
    atteint pc.
(7) entretien de la boucle interne : pcc avance vers 
    son successeur.
(8) entretien de la boucle externe : pc avance vers
    son successeur.

int bouclante(struct cell *pc) {
  struct cell *pci = pc, *pcc;   // (1)
  if (pc == NULL)                // (2)
      return 0;
  while(1) {
    if (pc -> suiv == NULL)      // (3)
      return 0;
    pcc = pci;
    while(1) {
      if (pcc == pc -> suiv)     // (5)
	return 1;
      if (pcc == pc)             // (6)
	break;
      pcc = pcc -> suiv;         // (7)
    }
    pc = pc -> suiv;             // (8)
  }
}

Casse-tete final
----------------
Un casse-tete vraiment difficile. On souhaite ne 
parcourir la liste qu'une seule fois. Il faut donc 
d'une facon ou d'une autre inscrire dans chaque 
cellule deja visitee une information permettant de 
savoir qu'on l'a deja visitee. On ne peut pas se 
contenter d'alterer sa clef (toute clef choisie pour 
marquer l'information "deja visitee" peut deja faire 
partie de la liste). Mais on peut alterer son 
successeur - par exemple, lui donner la valeur d'une 
adresse dont on sait qu'elle ne peut pas faire partie 
de la liste... e.g. une nouvelle adresse de cellule 
allouee par malloc. Dans les fonctions ci-dessous, 
cette adresse porte le nom "dummy". 

La fonction "parcours", recursive, verifie si la
cellule courante (*pc) est chainee a une cellule
chainee a dummy : si c'est le cas, *pc est chainee
a une cellule deja visitee, et la liste est bouclante.
L'appel courant renvoie alors immediatement sa reponse.
Sinon, on sauvegarde dans le contexte de l'appel
(variable pcs) le successeur de pc, on chaine pc a
dummy, et on relance sur le "vrai" successeur de pc
(pcs). L'appel recursif revoie sa reponse. L'appel
courant retablit le successeur de pc (pcs), et 
renvoie a son appelant la reponse de l'appel recursif. 

int parcours(struct cell *pc, struct cell *dummy) {
  struct cell *pcs;
  int rep;
  if (pc -> suiv == NULL)
    return 0;
  if (pc -> suiv -> suiv == dummy)
    return 1;
  pcs = pc -> suiv;
  pc -> suiv = dummy;
  rep = parcours (pcs, dummy);
  pc -> suiv = pcs;
  return rep;
}

int bouclante(struct cell *pc) {
  struct cell *dummy;
  int rep;
  if (pc == NULL)
    return 0;
  dummy = malloc(sizeof(struct cell));
  rep = parcours(pc, dummy);
  free(dummy);
  return rep;
}