********** Exercice 1 ********** il suffit de compter le nombre de fins de tranches. une position i quelconque dans la chaine d'adresse s est une fin de tranche si et seulement si s[i] != s[i + 1]. cette propriete est valide pour toutes les tranches, y compris la derniere (le dernier caractere de la chaine est est necessairement distinct du '\0' place a sa droite). int nbr_tranches(char *s) { int n = 0; // compteur de fins de tranches for (int i = 0; s[i] != '\0'; i++) { if (s[i] != s[i + 1]) { n++; } } return n; } ********** Exercice 2 ********** on ajoute un compteur (l) calculant la longueur de la portion deja lue la tranche courante (1). le compteur est reinitialise sur les fins de tranches (2, 2.1). avant chaque reinitialisation, la longueur de la tranche courante est comparee avec la plus grande longueur de tranche deja connue (lmax) - on met a jour cette longueur maximale si necessaire (2.1). int tranche_max(char *s) { int l_max = 0, l = 0; for (int i = 0; s[i] != '\0'; i++) { l++; // (1) if (s[i] != s[i+1]) { // (2) if (l > l_max) { // (2.1) l_max = l; } l = 0; // (2.2) } } return l_max; } ********** Exercice 3 ********** l'exercice est presque identique au precedent, mais lorsque l'on arrive sur une fin de tranche (2), avant de reinitialiser le compteur de longueur de tranche (2.5), on compare la longueur de la tranche courante avec la longueur de la tranche precedente (l_prec, mis a jour en 2.3 apres la comparaison en 2.2), a moins que l'on ne soit sur la toute premiere tranche : lprec est dans ce cas encore egal a 0, et la longueur de la tranche courante est memorisee comme prochaine longueur precedente (2.4). int tranches_incr(char *s) { int l_prec = 0, l = 0; for (int i = 0; s[i] != '\0'; i++) { l++; // (1) if (s[i] != s[i+1]) { // (2) if (l_prec != 0) { // (2.1) if (l != l_prec + 1) // (2.2) return 0; l_prec++; // (2.3) } else { l_prec = l; // (2.4) } l = 0; // (2.5) } } return 1; } ********** Exercice 4 ********** les deux chaines n'auront pas en general les memes longueurs de tranche : elles ne peuvent donc etre parcourues avec un seul compteur, il faut un compteur de lecture par chaine. (1) tant que l'une des deux chaines n'a pas ete entierement parcourue, et en supposant que chaque position i, j est un debut de tranche ou la position de \0... (2) si s[i] != t[j], ou bien l'une des chaines s'est finie avant l'autre, ou bien les chaines contiennent deux tranches de meme numero, mais formees de deux caracteres distincts. dans tous les cas, elles ne sont pas similaires. (3) on parcourt la tranche courante dans s, et l'on se place sur la position immediatement a droite de sont dernier caractere (3.1). (4) on parcourt la tranche courante dans t, et l'on se place sur la position immediatement a droite de sont dernier caractere (4.1). (5) arrive a ce point, les deux chaines se sont terminees apres lecture du meme nombre de tranches, et les tranches de meme numero etaient bien formees du meme caractere : elles sont similaires. int tranches_similaires(char *s, char *t) { int i = 0, j = 0; while (s[i] != '\0' || t[j] != '\0') { // (1) if (s[i] != t[j]) // (2) return 0; while (s[i] == s[i + 1]) // (3) i++; i++; // (3.1) while (t[j] == t[j + 1]) // (4) j++; // (4.1) j++; } return 1; // (5) } ********** Exercice 5 ********** (1) on parcourt une premiere fois la chaine pour calculer le nombre de tranches. (2) on alloue une zone de la bonne taille pour le stockage de la chaine resultat (+1 pour le '\0'). il faut un second compteur (j) pour l'ecriture dans cette zone. (3) la chaine est relue. (4) a chaque fin de tranche, on ecrit n fois le caractere de la tranche courante dans l'espace alloue (4.1 - noter le j++ : on ecrit en fc[j], puis j est incremente pour la prochaine ecriture). (5) une fois la chaine reguliere construite, on place le marqueur de fin de chaine. char *forme_reguliere(int n, char *s) { int p = nbr_tranches(s), i, j = 0; // (1) char *fc = malloc((1 + n * p) * sizeof(char)); // (2) for (int i = 0; s[i] != '\0'; i++) // (3) if (s[i] != s[i + 1]) // (4) for (int k = 0; k < n; k++) // (4.1) fc[j++] = s[i]; fc[j] = '\0'; // (5) return fc; } **************** Exercices 6 et 7 **************** deux exercices ultra-classiques. (1) gestion du cas liste vide (2) gestion du cas liste singleton : l'unique cellule est celle que l'on doit liberer, et la liste resultante est la liste vide. (3) cas inductif : la premiere cellule de pc n'est pas la derniere, et l'on chaine cette premiere cellule avec la liste obtenue en supprimant la derniere cellule de pc -> suiv, via un appel recursif. struct cell *suppr_der (struct cell *pc) { if (pc == NULL) // (1) return NULL; if (pc -> suiv == NULL) { // (2) free(pc); return NULL; } pc -> suiv = suppr_der (pc -> suiv); // (3) return pc; } (1) gestion du cas liste vide et liste singleton (les conditions sont evaluees de gauche a droite, la seconde condition n'est donc atteinte que si pc != NULL). (2) gestion du cas liste a deux elements : la premiere cellule est l'avant derniere, et est celle que l'on doit liberer. noter qu'il faut memoriser pc -> suiv avant de liberer pc. (3) cas inductif : la premiere cellule de pc n'est pas l'avant-derniere, et l'on chaine cette premiere cellule avec la liste obtenue en supprimant l'avant-derniere cellule de pc -> suiv, via un appel recursif. struct cell *suppr_av_der (struct cell *pc) { struct cell *pcs; if (pc == NULL || pc -> suiv == NULL) // (1) return pc; if (pc -> suiv -> suiv == NULL) { // (2) pcs = pc -> suiv; free(pc); return pcs; } pc -> suiv = suppr_av_der(pc -> suiv); return pc; } ******** PROBLEME ******** la methode suivante est immediate, mais n'est pas la plus efficace (voir plus bas) : A. on cherche la position de 0 dans la matrice. si 0 est introuvable, la matrice n'est pas un un mille-pattes. sinon, a partir de cette position... B. on cherche parmi les voisins de la position courante. le successeur de la valeur lue a la position courante. si l'on trouve ce successeur, on se deplace a sa position et l'on revient a l'etape B. sinon, on passe a l'etape C. C. la matrice est un mille-patte si et seulement la derniere valeur lue est (H * L) - 1. ***************** solution minimale ***************** la fonction ci-dessous implement la methode precedente avec un minimum de moyens syntaxiques : matrice de dimension constante (H, L, supposes definis par deux #define), pas de structure pour la position courante (deux variables pi, pj). (A) recherche de la premiere occurrence de 0. (A.1) si pi est encore a -1, 0 n'a pas ete trouve, et la matrice n'est pas un mille-pattes. sinon, on enchaine avec l'etape B. (B.1) tableau des n. de lignes des 4 voisins de la position courante (pi, pj) (B.2) tableau des n. de colonnes des 4 voisins de la position courante. (B.3) on examine les quatre voisins de la position courante (pi, pj). si l'un d'eux est dans les limites de la matrice et contient le successeur de m[pi][pj] (B.4), on interrompt l'examen des voisins (B.5). (B.6) si l'examen des voisins s'est termine sans avoir ete interrompu (B.6), le successeur de m[pi][pj] est introuvable, et l'on passe a l'etape (C) (break interrompt le while global). (B.7) sinon, on memorise la position du voisin contenant le successeur de la valeur courante, et l'on revient au debut de l'etape (B). int est_serpent(int m[H][L]) { int pi = -1, pj, i, j, d; for (i = 0; i < H && pi < 0; i++) // (A) for (j = 0; j < L && pi < 0; j++) { if (m[i][j] == 0) { pi = i; pj = j; } } if (pi < 0) // (A.1) return 0; while (1) { // (B) int qi[] = {pi - 1, pi, pi + 1, pi}; // (B.1) int qj[] = {pj, pj - 1, pj, pj + 1}; // (B.2) for (d = 0; d < 4; d++) { // (B.3) if (qi[d] >= 0 && // (B.4) qi[d] < H && qj[d] >= 0 && qj[d] < L && m[qi[d]][qj[d]] == m[pi][pj] + 1) break; // (B.5) } if (d == 4) // (B.6) break; pi = qi[d]; // (B.7) pj = qj[d]; } return m[pi][pj] == H * L; // (C) } ********************** solution plus complete ********************** /***************************/ /* positions et directions */ /***************************/ /* type des positions */ typedef struct { int i; // ligne int j; // colonne } position; /* test d'egalite de deux positions */ int pos_egales(position p, position q) { return p.i == q.i && p.j == q.j; } /* type enumere pour les quatres directions */ enum direction {N, S, E, O}; /* alias pour ce type */ typedef enum direction direction; /* calcul de la position voisine d'une position * donnee, dans une direction donnee */ position deplacement(position p, direction d) { switch (d) { case N : return (position) {p.i - 1, p.j}; case S : return (position) {p.i + 1, p.j}; case E : return (position) {p.i, p.j + 1}; case O : return (position) {p.i, p.j - 1}; } /* jamais atteint */ return p; } /************/ /* matrices */ /************/ /* type des matrices - les fonctions d'allocation * et de liberation sont supposees ecrites */ typedef { int hauteur; int largeur; int **contenu; } matrice; /* acces a une valeur dans une matrice */ int valeur(matrice *m, position p) { return m -> contenu[p.i][p.j]; } /* test d'interiorite d'une position */ int est_interieure (matrice *m, position p) { return p.i >= 0 && p.j >= 0 && p.i < m -> hauteur && p.j < m -> largeur; } /**************/ /* traitement */ /**************/ /* partie de l'etape A : recherche de 0 - ou retour * d'une position non dans m si 0 est introuvable. */ position position_zero(matrice *m) { int i, j; position p; for (i = 0; i < H; i++) for (j = 0; j < L; j++) { p = (position) {i, j}; if (valeur(m, p) == 0) return p; } return (position) {-1, -1}; } /* partie de l'etape B : recherche de la position * du successeur de la valeur a la position p - ou * retour de p si cette position est introuvable */ position successeur(matrice *m, position p){ int succ = valeur(m, p) + 1, i; position q; direction all[4] = {N, S, E, O}; for (i = 0; i < 4; i++) { q = deplacement(p, all[i]); if (est_interieure(m, q) && valeur(m, q) == succ) return q; } return p; } /* fonction principale */ int est_mille_pattes(matrice *m) { position p = position_zero(m), q; // (etape A) if (!est_interieure(m, p)) // (echec de A) return 0; while(1) { // (etape B) q = successeur(m, p); // (recherche) if (pos_egales(p, q)) // (fin de B) break; p = q; // (deplacement) } return // (etape C) valeur(m, p) == m -> hauteur * m -> largeur; } ********************** solution plus efficace ********************** une copie propose une solution meilleure que la precedente, avec un seul parcours de la matrice - bravo, je ne l'avais pas vue : (A) on parcourt la matrice. pour chaque valeur examinee : - s'il s'agit de 0, on memorise le fait que cette valeur a ete rencontree. - s'il s'agit de (H * L) - 1, on memorise aussi le fait que cette valeur a ete rencontree. - s'il ne s'agit pas de 0, on verifie que le predecesseur de cette valeur se trouve parmi les positions voisines. si ce predecesseur est introuvable, on interrompt le traitement : la matrice n'est pas un mille-pattes. (B) si le traitement n'a pas ete interrompu, la matrice est un mille-pattes si et seulement si les valeurs 0 et (H * L) - 1 ont toutes les deux ete rencontrees. voici une implementation minimale de cette methode : (A.1, A.2) mise en memoire de la rencontre de 0 (min) et de (H * L) - 1 (max). (A.2) tableau des n. de lignes des 4 voisins de la position courante (i, j) (A.3) tableau des n. de colonnes des 4 voisins de la position courante. (A.4) on examine les quatre voisins de la position courante (i, j). si l'un d'eux est dans les limites de la matrice et contient le successeur de m[i][j] (A.6), on interrompt l'examen des voisins (A.7). (A.8) si l'examen des voisins s'est termine sans avoir ete interrompu, le successeur de m[i][j] est introuvable, et la matrice n'est pas une mille-pattes. int est_serpent(int m[H][L]) { int i, j, d, flag_min = 0, flag_max = 0; for (i = 0; i < H; i++) for (j = 0; j < L; j++) { if (m[i][j] == 0) flag_min = 1; // (A.1) else { if (m[i][j] == H * L - 1) // (A.2) flag_max = 1; int ti[] = {i - 1, i, i + 1, i}; // (A.3) int tj[] = {j, j - 1, j, j + 1}; // (A.4) for (d = 0; d < 4; d++) { // (A.5) if (qi[d] >= 0 && // (A.6) qi[d] < H && qj[d] >= 0 && qj[d] < L && m[ti[d]][tj[d]] == m[i][j] + 1) break; // (A.7) } if (d == 4) // (A.8) return 0; } } return flag_min && flag_max; // (B) } **************** CASSE-TETE FINAL **************** on garde toutes les declarations et fonctions des parties "positions et directions", et "matrices". on ajoute a la partie "matrices" la fonction d'allocation reprise du cours n.7 (a l'inversion des parametres pres). matrice *allouer_matrice (int hauteur, int largeur) { matrice *pm; int i; pm = malloc (sizeof(matrice)); pm -> largeur = largeur; pm -> hauteur = hauteur; pm -> contenu = malloc(hauteur * sizeof(int *)); for (i = 0; i < hauteur; i++) pm -> contenu[i] = calloc(largeur, sizeof(int)); return pm; } on peut aussi, pour ameliorer la lisibilite du code ainsi que sa modularite, ajouter a cette partie une fonction d'ecriture a une position donnee : void ecriture(matrice *m, position p, int v) { m -> contenu[p.i][p.j] = v; } ************************** recherche d'un remplissage ************************** (A) fonction de remplissage. en parametres : m : l'adresse d'une matrice contenant un mille- pattes partiel, dont les cases non encore remplies contiennent par convention la valeur -1. p : la derniere position d'ecriture (position de 0 au premier appel). valeur de retour : 1 si la matrice d'adresse m peut etre completee en un mille-pattes. dans ce cas, la matrice contient en fin d'appel l'une de ces completions, choisie aleatoirement parmi toutes les completions possibles. 0 sinon. dans ce cas, la matrice est en fin d'appel, dans l'etat ou elle etait en debut d'appel. (1) table des directions des positions voisines de la derniere position d'ecriture (directions "candidates" pour la completion) (2) nombre de direction encore candidates (3) si la derniere valeur ecrite est (H * L) - 1, la matrice est totalement remplie (et est un mille-pattes) : on le signale a l'appelant. (4) tant qu'il reste des directions candidates... (5) on tire au hasard un numero de direction (6) on prend la direction associee (7) on calcule la position associee (8) on tasse vers la gauche le tableau des directions candidates. (9) si la position calculee est interieure a la matrice et non encore occupee... (10) on ecrit a cette position la valeur qui suit celle ecrite en p. (11) on demande a un appel recursif de tenter de completer la matrice resultante. (12) si cette completion termine, la matrice d'adresse m est totalement remplie (par un mille-pattes) : on le signale a l'appelant. (13) sinon, la matrice est dans l'etat ou elle etait immediatement avant l'appel recursif. on remet la matrice dans l'etat ou elle etait au debut de l'appel courant en effacant la valeur ecrite a la position tiree, puis l'on revient en (4). (14) arrive a ce point, la matrice est dans l'etat ou elle etait au debut de l'appel courant. toutes les positions autour de la position p ont ete examinees, mais aucune n'a permis de construire un mille-pattes : on le signale a l'appelant. int remplissage(matrice *m, position p) {// (0) direction suites[] = {N, S, E, O}; // (1) int restants = 4; // (2) if (valeur(m, p) == // (3) ((m -> hauteur) * (m -> largeur) - 1)) return 1; while(restants != 0) { // (4) int ns = rand () % restants; // (5) direction ds = suites[ns]; // (6) position ps = deplacement(p, ds);// (7) suites[ns] = suites[--restants]; // (8) if (est_interieure(m, ps) && // (9) valeur(m, ps) == -1) { ecriture(m, ps, valeur(m, p) + 1); // (10) if (remplissage(m, ps)) // (11) return 1; // (12) ecriture(m, ps, -1); // (13) } } return 0; // (14) } (B) fonction principale. (1) allocation de la matrice (2) remplissage par le "vide" (-1) (3) tirage d'une position pour 0, ecriture de 0 a cette position, et premier appel de la fonction de remplissage (la valeur est perdue, mais elle est necessairement egale a 1). matrice *generer(int hauteur, int largeur) { matrice *m = allouer_matrice(hauteur, largeur); // (1) for (int i = 0; i < h; i++) // (2) for (int j = 0; j < l; j++) ecriture(m, (position) {i, j}, -1); position p = // (3) { rand() % m -> hauteur, rand() % m -> largeur }; ecriture(m, p, 0); remplissage(m, p); return m; }