------------------------------------------------------- Partie I ------------------------------------------------------- L'exercice 1 a ete plutot bien compris, mais la plupart des copies commencent a perdre pied des l'exercice 2 avec, dans l'ensemble, beaucoup de difficultes pour controler de maniere correcte les parcours de chaines (interversion ponctuelle ou systematique des connecteurs &&/||, conditions d'arret confondues avec des conditions d'entretien et, le plus frequemment, acces a une partie de la memoire de contenu indefini faute d'avoir memorise suffisamment d'information). - Une erreur mineure, mais demandant une clarification : la notation pour le caractere de position i dans une chaine n'etait introduite que pour presenter les differentes definitions, elle ne fait pas partie de la syntaxe du langage C : il fallait ecrire comme d'habitude s[i], t[i], ... et non si, ti, ... - Aucun exercice de cette partie ne necessitait le calcul prealable de la longueur des chaines (la contrainte de non-relecture interdisant de toute maniere ce calcul). Plusieurs copies tentent de contourner cette restriction de maniere incorrecte. Le point suivant n'a peut-etre pas ete totalement compris : il est tout simplement impossible en C, lorsque l'on ne dispose que de l'adresse d'une chaine, de calculer sa longueur sans la parcourir au moins une fois. - une variable non initialisee ne peut pas magiquement valoir la longueur d'une chaine. - sizeof ne permet pas de connaitre la taille d'une chaine. Au mieux, sizeof permet de connaitre la taille d'un tableau declare localement (mais une chaine peut ne pas occuper tout le tableau dans lequel elle est stockee, donc cette information ne fournit qu'une longueur maximale). - dans le cas d'un parametre s de type pointeur vers char, sizeof(s) ne renverra que la taille necessaire pour stocker un pointeur vers char, quelle que soit la taille de la chaine d'adresse s. - la syntaxe "s.length" n'est valide que pour connaitre la taille d'un tableau en Java. ------------------------------------------------------- Exercice 1 ------------------------------------------------------- Un exercice tres elementaire, et plutot bien traite (au connecteur pres, voir ci-dessous) : // (1) le decompte des occurrences communes se fait sur // les positions communes de s et t. int communes(char *s, char *t) { int i = 0, k = 0; while (s[i] != '\0' && t[i] != '\0') { // (1) if (s[i] == t[i]) 0 k++; i++; } return k; } Remarques --------- La condition doit etre en "&&", et non en "||" (une erreur tellement frequente dans cet exercice que j'ai fini par ne plus la relever - dans les suivants, la correction est devenu moins simple, l'inversion &&/|| ne semblant pas toujours uniforme d'un exercice a l'autre, ou meme d'une boucle a l'autre dans une meme fonction) : - la boucle doit s'arreter des que la fin d'une de deux chaines est atteinte, c'est-a-dire des que s[i] == '\0' OU t[i] == '\0' - donc, la boucle doit continuer tant que la negation de cette condition est verifiee, c'est-a-dire tant que s[i] != '\0' ET t[i] != '\0' (NON (A OU B) donne (NON A) ET (NON B)). ------------------------------------------------------- Exercice 2 ------------------------------------------------------- // (1) le decompte des occurences dijsointes se fait sur les positions communes de s et t... // (2) puis sur la partie restante de la chaine la plus // longue. int disjointes(char *s, char *t) { int i = 0, k = 0; char *r; while (s[i] != '\0' && t[i] != '\0') { // (1) if (s[i] != t[i]) k++; i++; } r = (s[i] == '\0') ? t : s; // (2) while(r[i] != '\0') { k++; i++; } return k; } Variantes --------- En (2), plutot que d'utiliser une variable de plus (r), on peut aussi finir le parcours en dirigeant l'execution vers une boucle, parmi deux possibles : if (s[i] == '\0') { while (t[i] != '\0') { k++; i++; } } else { while (s[i] != '\0') { k++; i++; } } Il est egalement possible d'utiliser une seule boucle, avec deux drapeaux signalant la rencontre de la fin d'une chaine : fin_s = 0; fin_t = 0; while (1) { // detection de la fin de chaque chaine if (s[i] == '\0') fin_s = 1; if (t[i] == '\0') fin_t = 1; // sortie si les deux sont terminees if (fin_s && fin_t) break; // increment si l'une est fini et pas l'autre // et sinon, en cas de difference. if (fin_s || fin_t || s[i] != t[i]) k++; i++; } On peut aussi (une solution proposee, correcte au connecteur pres) utiliser un compteur par chaine - dans la boucle ci-dessous, le compteur de la chaine la plus courte restera bloque sur son marqueur de fin pendant tout le parcours de la partie restante de la plus longue (avec decompte du nombre de caracteres dans cette partie, puisque tous ses caracteres sont non nuls) : is = 0; it = 0; while (s[is] != '\0' || t[it] != '\0') { if (s[is] != t[it]) k++; if (s[is] != '\0') is++; if (t[it] != '\0') it; } Remarques --------- La boucle suivante n'effectue le decompte des differences que sur les positions de la plus courte des deux chaines. while (s[i] != '\0' && t[i] != '\0') { // ERR if (s[i] != t[i]) k++; i++; } Meme si && est cense signifier ||, pour poursuivre la lecture dans la plus grande des deux chaines, la solution suivante ne fonctionne pas : while (s[i] != '\0' || t[i] != '\0') { // ERR if (s[i] != t[i]) k++; i++; } Une telle boucle effectuerait le traitement demande si le marqueur de fin de la plus courte des deux chaines etait suivi d'une suite de '\0' jusqu'a la position du marqueur de fin de la plus longue (e.g. abcde\0 contre xy\0\0\0\0). En pratique, ceci n'a presque aucune chance de se produire. Plus generalement, pour cet exercice et les suivants, beaucoup de solutions incorrectes sont basees sur l'illusion que pour toute chaine w, une fois la condition (w[i] == '\0') verifiee pour une certaine valeur de i, cette condition restera vraie pour toutes les valeurs de i plus grandes - mais apres le marqueur de fin de w, le contenu de la memoire est quelconque, tout comme la valeur de cette condition. En particulier, au dela de ce marqueur, comparer les caracteres de w avec ceux d'une autre chaine n'a plus de sens. Autre solution qui ne fonctionne pas, pour la raison opposee (c'est-a-dire l'illusion qu'une fois la condition (w[i] == '\0') verifiee pour un certain i, elle sera fausse pour les valeurs de i plus grandes) : compter le nombre de '\0' rencontres via les acces s[i], t[i] pour detecter la fin d'une, puis des deux chaines : fins = 0; while (fins != 2) { // ERR if (s[i] == '\0') fins++; if (t[i] == '\0') fins++; if ((fins == 0 && (s[i] != t[i])) || fins == 1) k++; i++; } Cette solution fonctionnerait si le marqueur de fin de la chaine la plus courte etait suivi de caracteres non nuls jusqu'a la position du marqueur de la chaine la plus longue. Mais si, en memoire, on par exemple - a l'adresse s : a b c d e \0 - a l'adresse t : x y \0 \0 la rencontre du second \0 dans la seconde chaine provoquera la sortie du while, alors que la premiere chaine n'a pas encore ete parcourue. ------------------------------------------------------- Exercice 3 ------------------------------------------------------- Un exercice plutot mal compris (et plusieurs fois interprete comme la simple recherche d'une occurrence commune dans s, t ou dans s, u, au sens de l'exercice 1). Cet exercice n'a ete correctement traite (a quelques erreurs mineures pres) que dans quatre copies. On peut, pour cette fonction, reprendre simplement la forme generale de la precedente, avec les memes sortes de variantes pour le controle (aiguillage final vers une boucle residuelle, drapeaux, ou encore, un indice par chaine) : // (1) tant que la fin d'une des deux chaines n'a pas // ete atteinte, on verifie que chaque caractere // de s est bien un caractere de t ou de u. // (2) on finit la verification dans la chaine qui n'a // pas provoque la sortie de boucle. // (3) la seconde boucle se finissant avec la plus // grande des deux chaines, on verifie que s s'est // bien termine au meme moment. int est_melange(char *s, char *t, char* u) { int i = 0; char *r; while (t[i] != '\0' && u[i] != '\0') { // (1) if (s[i] != t[i] && s[i] != u[i]) return 0; } r = (t[i] == '\0') ? u : t; // (2) while (r[i] != '\0') { if (s[i] != r[i]) return 0; i++; } return s[i] == '\0'; // (3) } ------------------------------------------------------- Exercice 4 ------------------------------------------------------- Un exercice un peu plus difficile - la definition etait moins simple que les precedentes, et meme en l'ayant bien comprise (en realisant, par exemple, que le traitement n'etait pas symetrique, comme le suggerait l'exemple), la verification demandee necessitait un controle un peu plus fin. // (1) tant que la fin de t n'a pas ete atteinte, on // compare en parallele s et t, en cassant cette // boucle a la premiere difference. // (2) a chaque egalite, la fin de u ne doit pas avoir // ete atteinte, puisque s doit etre de meme // longueur que u. // (2) la comparaison se poursuit dans u. // (3) la seconde boucle se finissant avec u, on // verifie que s s'est bien termine au meme moment. int est_croisement(char *s, char *t, char *u) { int i = 0; while (t[i] != '\0') { // (1) if (s[i] != t[i]) break; if (u[i] == '\0') // (2) return 0; } while (u[i] != '\0') { // (3) if (s[i] != u[i]) return 0; } return s[i] == '\0'; // (4) } ------------------------------------------------------- Exercice 5 ------------------------------------------------------- Pour cet exercice, les copies se divisent de maniere tres nette en deux groupes : ceux qui ont trouve l'algorithme, et l'ont implemente sans (trop de) difficultes ; les autres, dont le code n'a pas vraiment de sens. La methode ci-dessous (la plus simple) est fondee sur la propriete suivante : - si t est vide, s doit etre vide. - sinon, les chaines s et t doivent commencer par le meme caractere et, a partir de la position initiale, on doit pouvoir lire successivement ce caractere au moins autant de fois dans s que dans t. Dans le second cas, en se deplacant dans s, t apres le prefixe forme de ce caractere initial commun, les chaines lisibles a partir des positions atteintes doivent verifier la meme propriete. // (1) on calcule : // - la longueur cs de la plus longue suite formee // du caractere t[it], lisible dans s a partir // de la position courante is, // - la longueur ct de la plus longue suite formee // du caractere t[it], lisible dans t a partir // de la position courante it. // (2) la premiere suite doit etre au moins aussi // longue que la premiere. // (3) la boucle principale se finissant avec t, on // verifie que s s'est bien termine au meme moment. int est_demultiplication(char *s, char *t) { int is = 0, it = 0, cs, ct; while(t[it] != '\0') { cs = 0; ct = 0; // (1) while (s[is + cs] == t[it]) cs++; while (t[it + ct] == t[it]) ct++; if (cs < ct) // (2) return 0; is = is + cs; it = is + ct; } return s[is] == '\0'; // (3) } Noter que (2) gere le cas ou s[is] != t[it] : on a necessairement ct > 0, et si s[is] != t[it], alors cs == 0, donc la condition en (2) devient fausse. Une autre methode, decoulant d'un algorithme plus compact, mais moins simple a comprendre : // (1) aux positions courantes is, it dans s, t // (2) on doit pouvoir lire dans s, t le meme // caractere c... // (3) et s'il l'on ne peut lire c qu'une seule fois // dans t, la lecture dans s devra se poursuivre // apres la plus longue suite de c lisible a // a partir de la position courante. // (4) la boucle principale se finissant avec t, on // verifie que s s'est bien termine au meme moment. int est_demultiplication(char *s, char *t) { int is = 0, it = 0; while(t[it] != '\0') { if (s[is] != t[it]) // (1) return 0; if (s[is] != t[it + 1]) // (2) while (s[is] == t[it]) is++; else is++; // (3) it++; } return s[is] == '\0'; // (4) } ------------------------------------------------------- Exercice 6 ------------------------------------------------------- Un probleme assez difficile a realiser en respectant toutes les contraintes, mais beaucoup plus simple avec deux lectures au maximum. Il a ete peu aborde, et quelques reponses sont hors-sujet (la question posee n'etait pas celle de l'exercice 1 de l'examen de juin 2011). Deux reponses sont a peu pres satisfaisantes (avec trop de tableaux). Voici une solution plutot dense, en une seule lecture. Elle pourrait etre simplifiee, au prix de duplications de code, en aiguillant le traitement de la boucle principale vers : la lecture complete d'une ligne de rang pair, ou, la lecture complete d'une ligne de rang impair. // (1) dia : la derniere initiale, dans l'ordre // alphabetique, lue aux lignes precedentes // ou la lettre qui precede 'a' tant // qu'aucune initiale n'a ete lue. // (2) dic : la derniere initiale, dans l'ordre de // lecture gauche-droite, lue sur la ligne // courante // (3) ipm : l'initiale du premier mot de la ligne // courante. // (4) sens : le sens d'enumeration alphabetique // (1 pour -->) // // (5) recherche du debut du mot suivant // (6) si l'on trouve un debut de mot : // (6.1) s'il s'agit du premier mot, // (6.1.1) on initialise ipm et dic. // (6.1,2) si le sens d'enumeration est --> // on verifie que ipm est bien // le successeur de dip. // (6.2) sinon, et si le sens d'enumeration est <--, // les initiales doivent decroitre. // (6.3) on passe tous les caracteres du mot. // a l'iteration suivante, on sera place // sur le premier espace apres le mot // courant, ou en fin de ligne. // (7) sinon, la fin de la ligne est atteinte. // (7.1) si au moins une initiale a ete lue, // (7.1.1) si le sens d'enumeration est <--, // on doit avoir atteint le successeur // de dip. // (7.1.2) mise a jour de dip, en fonction du // sens. effacement de dic, ipm. // (7.2) inversion du sens. // int boustr_abc(char *s) { char dia = 'a' - 1; // (1) char dic = '\0'; // (2) char ipm = '\0'; // (3) int i, sens = 1; // (4) while (s[i] != '\0') { while (s[i] == ' ' && s[i] != '\n') // (5) i++; if (s[i] != '\n') { // (6) if (ipm == '\0') { // (6.1) ipm = s[i]; // (6.1.1) dic = s[i]; if (sens && s[i] != dip + 1) // (6.1.2) return 0; } else { // (6.2) if (!sens && s[i] != dic - 1) return 0; dic = s[i]; } while (s[i] != ' ' && s[i] != '\n') // (6.3) i++; } else { // (7) if (dic != '\0') { // (7.1) if (!sens && dic != dip + 1) // (7.1.1) return 0; dip = sens ? dic : ipm; // (7.1.2) dic = '\0'; ipm = '\0'; } sens = !sens; // (7.2) i++; } } return 1; } ------------------------------------------------------- Partie II ------------------------------------------------------- ------------------------------------------------------- Exercice 7 ------------------------------------------------------- // (1) la recurrence se termine si k est nul, ou si // la liste est vide. // (2) sinon, il faut supprimer les k - 1 premieres // cellules de la liste commencant apres la // premiere... // (3) sans oublier la premiere. struct cell *supprimer_debut(int k, struct cell *pc) { struct cell *pcs; if (pc == NULL || k == 0) // (1) return pc; pcs = supprimer_debut(k - 1, pc -> suiv); // (2) free(pc); // (3) return pcs; } Variante -------- // (1) la recurrence se termine si k est nul, ou si // la liste est vide. // (2) sinon, on memorise la liste pcs commencant // apres la premiere cellule. // (3) on supprime la premiere cellule. // (4) on renvoie la liste obtenue en supprimant les // k - 1 premieres cellules de pcs. struct cell *supprimer_debut(int k, struct cell *pc) { struct cell *pcs; if (pc == NULL || k == 0) // (1) return pc; pcs = pc -> suiv; // (2) free(pc); // (3) return supprimer_debut(k - 1, pcs); // (4) } Remarques --------- Les codes suivants recensent les deux erreurs-types commises dans cet exercice et le suivant (les deux erreurs sont considerees individuellement, mais souvent superposees dans les solutions proposees, et parfois melangees a des boucles while). (A) Illusion du partage de variable. struct cell *supprimer_debut(int k, struct cell *pc) { struct cell *pcs; int i = 0; if (pc == NULL || i == k) // (1) ERR return pc; pcs = supprimer_debut(k, pc -> suiv); // (2) ERR free(pc); i++; // (3) ERR return pcs; } Rappel de cours : il y a autant d'exemplaires de i en memoire que d'exemplaires de supprimer_debut en cours d'execution. - en (1), le i de l'appel en cours d'execution vaut 0 (sa valeur d'initialisation), et la condition (i == k) ne sera pas verifiee si k est non nul. - en (2), le nouvel exemplaire lance dispose de son propre i, encore initialise a 0, et k conserve sa valeur, donc la recurrence ne peut plus se baser sur la valeur de k pour arreter l'imbrication des appels. - en (3), les modifications effectuees par les appels recursifs sur leur propre i n'ont pas affecte le i de l'appel courant : ce i vaut toujours 0, et passe a 1. La chaine d'appels ne s'arretera que lorsque la condition (pc == NULL) sera verifiee. Au retour de son d'appel recursif, chaque exemplaire detruira sa premiere cellule. Au final, toute la liste sera detruite. (B) Appel recursif incantatoire. struct cell *supprimer_debut(int k, struct cell *pc) { struct cell *pcs; if (pc == NULL || k == 0) // (1) return pc; pcs = pc ->suiv; free(pc); // (2) supprimer_debut(k - 1, pcs); // (3) ERR return pcs; // (4) } Rappel de cours : si une fonction renvoie une valeur, et si l'on ecrit un appel de fonction sous forme imperative ("f(x);" au lieu de "y = f(x);" ou "return f(x);"), sa valeur de retour est perdue. Les appels recursifs obeissent a la meme regle : en (3), la valeur de retour de l'appel est perdue. Si pcs est liberee par l'appel recursif, la valeur renvoyee par (4) sera celle d'une adresse qui n'est plus allouee. Variante du contre-exemple precedent : la meme chose, mais sans return en (4) (valeur de retour indefinie), ou encore, avec "return NULL;" (donc retour de NULL dans tous les cas, et des cellules non liberees qui deviennent inaccessibles faute de pointeur). ------------------------------------------------------- Exercice 8 ------------------------------------------------------- // (1) si la liste est vide ou si k est nul, aucune // cellule ne peut ou ne doit etre supprimee. // (2) sinon, on demande via un appel recursif la // suppression des k dernieres cellules de la liste // commencant apres la premiere cellule. // (3) si cette demande a supprime strictement moins // de k cellules, il faut aussi supprimer la // premiere - et indiquer dans le retour que // l'on a supprime une cellule de plus. // (4) sinon, l'appel recursif a bien provoque la // suppression des k dernieres cellules, et l'on // se contente de transmettre sa reponse. int supprimer_fin(int k, struct cell *pc) { int n; if (pc == NULL || k == 0) // (1) return 0; n = supprimer_fin (k, pc -> suiv); // (2) if (n < k) { // (3) free(pc); return n + 1; } return k; // (4) } -------------------------------------------------------