--------------------------------------------------- Exercice I --------------------------------------------------- Un exercice classique sur les boucles imbriquees : int etalement(int m[TAILLE][TAILLE]) { int i, j; for (i = 0; i < TAILLE; i++) { for (j = i; j < TAILLE; j++) { if (m[i][j] != m[i][i]) return 0; if (m[j][i] != m[i][i]) return 0; } } return 1; } --------------------------------------------------- Exercice II --------------------------------------------------- Cet exercice etait plutot dfficile. Il demandait une bonne analyse du probleme et de la methode proposee. La correction presentee ici utilise un tableau de marquage de meme longueur que la chaine, i.e. un tableau d'entiers initialises a 0, passant a 1 lorsqu'une parenthese de la chaine est cochee. Afin de simplifier le code, on peut dans un premier temps ecrire les fonctions auxilaires determinant si un caractere est une parenthese ouvrante, fermante, ouvrante ou fermante, ainsi que la fonction associant sa fermante une ouvrante. int ouvrante(char c) { return c == '(' || c == '{' || c == '['; } int fermante(char c) { return c == ')' || c == '}' || c == ']'; } int parenthese(char c) { return ouvrante(c) || fermante(c); } int associee(char c) { switch(c) { case '(' : return ')'; case '{' : return '}'; case '[' : return ']'; } exit(1); } /* recherche de la premiere parenthese non cochee * a partir de pos incluse */ int premiere_nc(int pos, char *s, int *marquage) { int i; for (i = pos; s[i] != '\0'; i++) if (!marquage[i] && parenthese(s[i])) return i; return -1; } int bien_par(char *s) { int *marquage, l, pos_g, pos_d; /* allocation du tabelau de marquage */ l = strlen(s); marquage = calloc(l, sizeof(char)); while (1) { /* on cherche la premiere parenthese non * cochee a partir de la position 0 */ pos_g = premiere_nc(0, s, marquage); /* si il n'y a plus de parentheses non cochees, * le traitement est termine */ if (pos_g < 0) break; /* sinon, et si la premiere est une parenthese * fermante, elle ne peut pas avoir d'ouvrante * associee */ if (fermante(s[pos_g])) return 0; /* sinon, on se deplace sur le premier couple * de positions de la forme : * pos_g .... pos_d * ouvrante / marquees / fermante */ /* on superpose d'abord les deux positions */ pos_d = pos_g; /* tant que l'on est sur * pos_g .... pos_d * ouvrante / marquees / ouvrante */ while (ouvrante(s[pos_d])) { /* on remplace pos_g par pos_d, * on recalcule pos_d */ pos_g = pos_d; pos_d = premiere_nc(pos_g + 1, s, marquage); /* cas ou pos_g est sur une ouvrante * sans fermante associee apres pos_g */ if (pos_d < 0) return 0; } /* case de parentheses ouvrante / fermante * non associables */ if (s[pos_d] != associee(s[pos_g])) return 0; /* marquage du couple de positions */ marquage[pos_g] = 1; marquage[pos_d] = 1; /* on recommence le traitement */ } return 1; } --------------------------------------------------- Exercice III --------------------------------------------------- Les fonctions de cet exercice ne presentaient pas de difficultes particulieres, a l'exception peut-etre de la derniere, qui demandait quelques precautions pour ses cas limites: int croissante(struct cell *pc) { if (pc == NULL) return 1; if (pc -> suiv == NULL) return 1; return pc -> clef <= pc -> suiv -> clef && croissante(pc -> suiv); } struct cell *canonique(int n) { struct cell *pc = NULL, *nc; int i; for (i = n - 1; i >= 0; i--) { nc = (struct cell *) malloc(sizeof(struct cell)); nc -> clef = i; nc -> suiv = pc; pc = nc; } return pc; } struct cell *primitive(int init, struct cell *pc) { struct cell *nc; nc = (struct cell *) malloc(sizeof(struct cell)); nc -> clef = init; if (pc == NULL) nc -> suiv = NULL; else nc -> suiv = primitive(init + pc -> clef, pv -> suiv); return nc; } struct cell *derivee(struct cell *pc) { struct cell *nc; if (pc == NULL || pc -> suiv == NULL) return NULL; nc = (struct cell *) malloc(sizeof(struct cell)); nc -> clef = (pc -> suiv -> clef - pc -> clef); nc -> suiv = derivee(pc -> suiv); return nc; } struct cell *inserer(struct cell *pc_1, int pos, struct cell *pc_2) { if (pc_1 == NULL) return pc_2; if (pc_2 == NULL) return pc_1; if (pos == 0) { pc_2 -> suiv = inserer(pc_1, 0, pc_2 -> suiv); return pc_2; } pc_1 -> suiv = inserer(pc_1 -> suiv, pos - 1, pc_2); return pc_1; }