Quelques remarques sur l'examen en attendant les notes definitives. Au final, et malgre un bareme tres favorable, le niveau est seulement moyen : environ une moitie des copies sont a peu pres au niveau (dont certaines seulement grace au projet). Dans les autres, la syntaxe du langage est a peu pres globalement acquise, mais les bases de la programmation (capacite a analyser un probleme, a le decomposer en elements simples, a en trouver une methode de resolution puis a l'implementer sans trop d'erreurs) sont encore tres insuffisantes. VP. -------- Partie I -------- Theme : boucles imbriquees. Cet partie, de niveau elementaire, a ete largement aborde et dans l'ensemble relativement bien comprise, meme si presque toutes les copies effectuent au moins un acces en dehors de m dans l'une ou l'autre des fonctions. Question I.1 ------------ On doit avoir, pour chaque ligne i autre que la derniere (donc en faisant varier i de 0 a TAILLE - 1 exclus): - m[i][0] == m[i+1][1] - ... - m[i][j] == m[i+1][j+1] - ... - m[i][TAILLE-2] == m[i+1][TAILLE-1] - m[i][TAILLE-1] == m[i][0] On peut donc, pour chaque i, soit faire tous ces tests sauf le dernier via une boucle en j allant de 0 a TAILLE - 2 inclus et ajouter un test singulier pour la case m[i][TAILLE-1], soit mieux encore, ecrire un test uniforme en utilisant l'operateur modulo (TAILLE % TAILLE == 0) : int enroulement(int m[TAILLE][TAILLE]) { int i, j; for (i = 0; i < TAILLE - 1; i++) for (j = 0; j < TAILLE; j++) if (m[i][j] != m[i+1][(j + 1)%TAILLE]) return 0; return 1; } Noter que la boucle en i gere correctement le cas ou TAILLE est egal a 1 ou 0 - dans ce cas, le corps de la boucle externe n'est pas execute, et la matrice est trivialement un enroulement droit. erreurs-type I.1 ---------------- - oubli de la gestion singuliere de la derniere colonne. (e.g. test m[i][j] == m[i+1][j+1] pour chaque case, avec en particulier acces en dehors de m sur la derniere colonne et la derniere ligne) - copie de la premiere ligne dans un tableau auxiliaire, avec rotation du tableau auxiliaire a chaque changement via une fonction auxiliaire. Meme menee a bout (ce qui n'est pas toujours le cas dans les copies ayant tente cette approche) cette methode est inefficace. Sans etre fausse dans son principe, elle montre plutot que vous n'avez pas reussi a analyser vraiment le probleme. - adaptation approximative de la fonction "cascade" de l'examen de 2004 pour cette question et la suivante (et la, aucune analyse du probleme... un enroulement est en particulier une cascade, mais l'inverse est faux). Question I.2 ------------ Avec le meme operateur %, l'enroulement peut etre ecrit en notant que la case n. 0 de t doit apparaitre sur la colonne i de la ligne i pour chaque i : void enrouler(int t[TAILLE], int m[TAILLE][TAILLE]) { int i, j; for (i = 0; i < TAILLE; i++) for (j = 0; j < TAILLE; j++) m[i][(i + j) % TAILLE] = t[j]; } On peut sinon decomposer la boucle interne en deux parties, corespondant aux copies de deux tranches de t : - m[i][j] = t[j - i] pour j allant de i a TAILLE - 1 - m[i][j] = t[TAILLE - i + j] pour j allant de 0 a i - 1. On peut encore recopier t sur la premiere ligne, puis recopier chaque ligne sur la suivante en effectuant sa rotation, sur le modele du test. erreurs-type I.2 ---------------- - principe de la copie en deux tranches compris, mais erreurs dans les calculs de decalages. - rotation de t apres chaque copie de ligne via une fonction auxiliaire (c.f. ci-dessus). - enroulement gauche au lieu de droit. --------- Partie II --------- Theme : parcours de structure lineaire avec mise en memoire d'information. Les questions de cette partie n'etaient pas toutes du meme niveau de difficulte. La question 4 (tableau des positions a partir du tableau des longueurs) etait la plus simple. Les questions 1 et 3 (pyramidal, tableau des longueurs), assez similaires dans leur traitement, etaient de difficulte moyenne. La question 2 (incremental) etait plus difficile, et la 5 (symetrique) assez difficile. Les erreurs communes aux questions de cette partie, tres frequentes meme dans les reponses pour lesquelles le principe du traitement a ete plutot bien compris, ont ete : - erreurs dans les calculs de decalages (\n non pris en compte ou mal pris en compte). - erreurs dans les mises a jour d'indices (indice non mis a jour, erreur de replacement d'un indice) - controle confus : tests inutiles, gestion approximative de 3, 4, 5 indices dependants, confusion entre position absolue et position relative a un autre indice, confusions d'indices. Question II.1 ------------- Il faut, d'une facon ou d'une autre, calculer la longueur de chaque ligne en ayant memorise la longueur de la ligne precedente, afin de comparer ces deux longueurs. int pyramidal(char *s) { /* lp : longueur de la ligne precedente (ou 0) * lc : longueur de la ligne courante */ int i = 0, lp = 0, lc = 0; for (i = 0; s[i] != '\0'; i++) { if (s[i] == '\n') { if (lc < lp) return 0; lp = lc; lc = 0; } else lc++; } return 1; } erreurs-type II.1 ----------------- - pompage vraiment trop primaire. Question II.2 ------------- Il faut pour cette question memoriser la position de depart de la ligne precedente, de maniere a pouvoir la comparer a la ligne courante. // dlp est place au debut de la ligne // precedente apres la premiere iteration, // et sinon, au debut de la premiere ligne : // a la premiere iteration, la premiere // ligne sera comparee avec elle-meme. // // (1) on verifie que la ligne precedente // est prefixe de la ligne courante. // // (2) on memorise dans dlp le debut // de la ligne courante. // // (3) on cherche la fin de la ligne // courante // (4) on place i apres la fin de celle-ci. int incremental(char *s) { int i = 0, dlp = 0, j; while (s[i] != '\0') { j = 0; while (s[dlp + j] != '\n') { // (1) if (s[dlp + j] != s[i + j]) return 0; j++; } dlp = i; // (2) while (s[i + j] != '\n') // (3) j++; i += j + 1; // (4) } return 1; } erreurs-type II.2 ----------------- - utilisation assez incertaine d'un ou plusieurs tableaux auxiliaires. Question II.3 ------------- Cette question ressemble assez a la premiere : il faut calculer la longueur de la ligne courante, et la stocker dans le tableau des longueurs. On doit d'abord parcourir integralement s pour compter le nombre de lignes (i.e. le nombre de \n) pour connaitre la longueur de t. int *tableau_longeurs(char *s) { /* nl : nombre de lignes * lc : longueur de la ligne courante * it : position d'ecriture dans t */ int i, it, nl = 0, *t, lc = 0; /* calcul du nombre de lignes */ for (i = 0; s[i] != '\0'; i++) nl += (s[i] == '\n'); /* allocation de t */ t = malloc((1 + nl) * sizeof(int)); /* placement en 0 dans t */ it = 0; /* parcours de s */ for (i = 0; s[i] != '\0'; i++) { /* a chaque fin de ligne */ if (s[i] == '\n') { /* transfert de la longueur de la ligne * courante dans t */ t[it] = lc; it++; /* reinitialisation de la longeur */ lc = 0; } /* incrementation de la longueur */ else lc++; } t[it] = -1; return t; } erreurs-type II.3 ----------------- Les erreurs les plus frequentes concernent moins le remplissage du tableau (un traitement elementaire) que son allocation : - extension magique du tableau alloue par mallocs repetes, - taille d'allocation magiquement initialisee a la bonne valeur, ou allocation a posteriori apres ecriture dans un tableau non alloue. - ecriture et retour de tableau non alloue - retour d'un tableau local. - oubli du +1 dans l'allocation pour le marqueur de fin. - allocation d'un tableau de meme longueur que s (+1) et non de taille egale au nombre de lignes de s (+1) - tableau en int t, retour de *t ou &t. Question II.4 ------------- Le calcul du tableau des positions a partir du tableau des longueur est un traitement elementaire. La seule chose a ne pas oublier est de tenir compte des \n en fin de ligne. // i : indice de lecture dans t et d'ecriture dans p // pos : position courante dans le texte d'origine. // // (1) calcul de la longeur de t // // (2) calcul des positions successives de debuts // de lignes dans le texte d'origine. noter le +1 // pour tenir compte du \n a la fin de chaque ligne. int *tableau_positions(int *t) { int i, *p, pos = 0; for (i = 0; t[i] != -1; i++); // (1) p = malloc((1 + i)*sizeof(int)); for (i = 0; t[i] != -1; i++) { // (2) p[i] = pos; pos += t[i] + 1; } p[i] = -1; return p; } erreurs-type II.4 ----------------- - pas d'allocation du tableau ou retour de tableau local Question II.5 ------------- Un exercice, comme indique dans l'enonce, difficile, et resolu (a quelques erreurs pres) dans une seule copie. Voici une maniere de l'ecrire : // nl : nombre de lignes du texte symetrique // nc : nombre de colonnes du texte symetrique. // // (1) recherche du max de t, egal au // nombre de lignes du symetrique, // et calcul de la longueur de t, // egal au nombre de colonnes sans la colonne de \n // // (2) remplissage char *symetrique(char *s) { int *t, *p, i, j, nl = 0, nc = 0; char *ts; t = tableau_longueurs(s); p = tableau_positions(t); for (i = 0; t[i] != -1; i++) { // (1) nc++; if (t[i] > nl) nl = t[i]; } ts = malloc((nc + 1)*nl*sizeof(char)); for (i = 0; i < nl; i++) { // (2) for (j = 0; j < nc; j++) if (i < t[j]) ts[i * (nc + 1) + j] = s[p[j] + i]; else ts[i * (nc + 1) + j] = ' '; ts[i * (nc + 1) + nc] = '\n'; } ts[(nc + 1)*nl] = '\0'; free(t); free(p); return ts; } ---------- Partie III ---------- Theme : recurrence. Cette partie ne presentait aucune difficulte majeure, a condition d'avoir compris les notions de chainage et de recurrence. Si la premiere notion semble a peu pres acquise, la seconde semble encore tres incertaine, comme en temoigne l'assez joyeuse proliferation de syntaxe semi-aleatoire dans l'ecriture des fonctions : - appels recursifs ecrits de facon imperative (suivis ou non d'un return), melange confus entre iteration et recurrence, - affectation d'appel recursif a pc -> suiv, a pc -> clef (??), pas d'appel recursif, retour de pc -> suiv ou de pc -> clef. - utilisation de compteurs locaux magiquement partages par tous les appels, ou un peu mieux (mais pas encore ca), compteur global. Question III.1 -------------- // (1) par definition, la liste vide est duplicante // (2) par definition, la liste singleton ne l'est pas // (3) si une liste contient au moins deux clefs, elle // est duplicante si ses deux premieres clefs sont // egales, et si la liste commencant a la seconde clef // est duplicante. int duplicante(struct cell *pc) { if (pc == NULL) // (1) return 1; if (pc -> suiv == NULL) // (2) return 0; return (pc -> clef == pc -> suiv -> clef) // (3) && duplicante(pc -> suiv -> suiv); } erreurs-type III.1 ------------------ - oubli ou mauvaise gestion des cas de base (liste vide, liste a une seule clef) - definition de "duplicante" mal comprise. Question III.2 -------------- Noter que l'enonce precise que la fonction suppose que la liste contient au moins i + 1 clefs (en fait, supposer qu'elle contient i clefs suffit) : inutile, donc, de faire des tests pour verifier que pc -> suiv est bien defini. // (1) la liste commencant a la clef de rang 0 // dans pc est pc elle-meme // (2) si i > 0, la liste commencant a la clef // de rang i dans pc est la liste commencant a // la clef de rang i - 1 dans la liste commencant // a la clef de rang 1 dans pc, c'est-a-dire la // liste pc -> suiv. struct cell *suite(int i, struct cell *pc) { if (i == 0) // (1) return pc; return // (2) suite(i - 1, pc -> suiv); } erreurs-type III.2 ------------------ - pas de condition d'arret (1) - premiere clef de rang 1 au lieu 0. Question III.3 -------------- // On suppose k positif ou nul. // (1) si k == 0, pc commence bien par 0 clefs identiques. // (2) si k == 1, pc ne doit pas etre vide. // (3) si k >= 2, pc doit contenir au moins deux elements. // (4) de plus, ses deux premiers elements doivent etre // egaux, et la liste commencant apres la clef de rang 0 // doit commencer par k - 1 valeurs de clefs identiques. int *clef_prefixe(int k, struct cell *pc) { if (k == 0) // (1) return 1; if (k == 1) // (2) return pc != NULL; if (pc -> suiv == NULL) // (3) return 0; return // (4) pc -> clef == pc -> suiv -> clef && clef_prefixe(k - 1, pc -> suiv); } erreurs-type III.3 ------------------ - enonce mal compris. Question III.4 -------------- // (1) si la liste est vide, elle est bien n-replicante // (2) sinon, elle doit commencer par n clefs identiques, // et la liste commencant a la clef de rang n doit aussi // etre n-replicante. int replicante(int n, struct cell *pc) { if (pc == NULL) // (1) return n; return // (2) clef_prefixe(n,pc) && replicante(suite(n,pc)); } ---------------- Casse-tete final ---------------- Theme : calcul de composante connexe d'un graphe par construction de sa cloture transitive. Il faut determiner toutes les pieces que l'on peut atteindre a partir de l'entree du labyrinthe pour lesquelles il existe un chemin de retour. Le plus simple est de commencer par surcharger le plan en indiquant, pour chaque piece i, l'ensemble de toutes les pieces que l'on peut atteindre en partant de i et en se deplacant au hasard de piece en piece. Il suffit d'iterer sur la matrice l'operation suivante, jusqu'a ce qu'elle ne fasse plus passer a 1 aucune case : pour chaque i, j, k, si m[i][j] et m[i][k] sont a 1 et m[i][k] est a 0, on fait passer a 1 la case m[i][k]. On peut montrer qu'apres ce traitement, m[i][j] est a 1 si et seulement si il existe une suite non vide de passages menant de i a j. Pour chaque couple de pieces i, j distincts, on peut donc immediatement savoir si on peut aller de i jusqu'a j puis revenir en i (en particulier pour i == 0) : m[i][j] et m[j][i] doivent etre tous les deux a 1.