Corrigé de l’Examen d’Informatique

mai 2003 – 3h

Question I.1

Ecrire une fonction compte_debut(A,B) qui retourne le nombre de caractères en commun au début de deux chaînes de caractères. Faire la même chose avec une fonction compte_fin(A,B).

Exemples : compte_debut(« anti », « antimoine ») --> 4

compte_debut (« aller», « antimoine ») --> 1

compte_debut (« bibi », « antimoine ») --> 0

Réponse

On parcourt les deux chaînes en parallèle tant que les caractères sont identiques ET qu’aucune des deux chaînes n’est entièrement parcourue.

Fonction compte_debut(A,B : chaîne de caractères) --> entier

Entier cpt <-- 0

Entier lA <-- longueur(A)

Entier lB <-- longueur(B)

Tant que (cpt < lA) et (cpt < lB)

Si (A[cpt] = B[cpt])) alors

cpt <-- cpt + 1

sinon

retourner cpt

fin si

Fin Tant que

Retourner cpt

Fin

Pour compte_fin, c’est pareil mais en partant de la fin. C’est-à-dire que la fonction retourne le nombre de caractères en commun à la fin des deux chaînes.

Fonction compte_fin(A,B : chaîne de caractères) --> entier

Entier cpt <-- 0

Entier lA <-- longueur(A)

Entier lB <-- longueur(B)

Tant que (cpt < lA) et (cpt < lB)

Si (A[(lA – 1) - cpt] = B[(lB – 1) - cpt])) alors

cpt <-- cpt + 1

sinon

retourner cpt

fin si

Fin Tant que

Retourner cpt

Fin

_______________________________

Question I.2

Définir et écrire une fonction fusion(A,B) qui fusionne deux chaînes de caractères en une seule C contenant les deux chaînes A et B. On fera en sorte que C soit la plus courte possible.

Exemples : fusion(« anti », « antimoine ») --> « antimoine »

fusion(« neveu », « antimoine ») --> « antimoineveu »

fusion(« apprenant », « antimoine ») --> « apprenantimoine »

fusion(« interne », « antimoine ») --> « interneantimoine »

Réponse

En effet, c’esrt un peu plus compliqué que la fonction précédente, et san doute il faut se définir des focntions intermédiaire. L’idée ici est que pour le couple de chaînes (A, B), on chercherà connaître combien de caractères peuvent fusionner entre la fin de A et le debut de B. On parcourt donc A de droite à gauche et B de gauche à droite en parallèle. On définit la fonction tester_superposition qui tester une superpositon de n caractères entre A et B. Par exemple :

tester_supperposition (antimoine, neveu, 0) --> Vrai

tester_ superposition (antimoine, neveu, 1) --> Faux

tester_ superposition (antimoine, neveu, 2) --> Vrai

tester_superposition (antimoine, neveu, 3) --> Faux ; pour n >= 3 c’est toujours Faux

Fonction tester_ superposition (A, B :chaîne de caractères, n :entier) --> booléen

Entier lA <-- longueur(A)

Entier lB <-- longueur(B)

Si (n > lA) ou (n > lB) alors

Retourner Faux

Fin si

Pour i = 0 à n-1 faire

Si A[(lA –1 – i] != B[i] alors

Retouner Faux

Fin si

Fin pour

retourner Vrai

Fin

Le premier si correspond à un test d’erreur, car clairement si le n demandé est plus grand que la longueur d’une des deux chaînes , il faut retourner Faux. Dans le second si, il s’agit d’un schéma ou l’on sort dès qu’un élément ne vérifie pas une certaine propriété.

Maintenant, pour tester la fusion il suffit de tester toutes les valeurs possibles de superposition et de ne retenir que la plus grande. Dans ce cas, il suffit d’énumerer les valeurs de fusion possibles de façon décroissante et de reourner la première qui marche.

Fonction tester_ fusion (A, B :chaîne de caractères)

--> entier

Entier res <-- min (longueur (A), longueur(B))

Booleen test

Tant que Vrai faire

Test <-- tester_ superposition(A, B, res)

Si Test alors

Retourner res

Sinon

Res <-- res -1

Fin si

Fin tant que

Fin

Dans le pire des cas, ou il n’y a aucune superposition, res vaut 0 et tester_superposition rend Vrai. Donc, on sort bien de tester_fusion avec la plus grande valeur possible de superposition pour le couple (A, B).

Enfin, la fonction fusion doit chercher a déterminer pour quel couple (A, B) ou (B, A) la fusion est la plus grande.

Fonction fusion (A, B :chaîne de caractères) --> F :chaîne de caratères

Entier lA <-- longueur(A)

Entier lB <-- longueur(B)

Entier fusAB <-- tester_ fusion(A,B)

Entier fusBA <-- tester_ fusion(B,A)

MaxF = max(fusAB, fusBA)

Chaîne F <-- nouvelle chaîne de taille (lA + lB – maxF)

Si fusAB < fusBA alors

Pour i = 0 à lB faire

F[i]<--B[i]

Fin pour

Pour i = 0 à (lA – fus) faire

F[i + lB] <-- A[i + fus]

Fin pour

sinon

Pour i = 0 à lA faire

F[i]<--A[i]

Fin pour

Pour i = 0 à (lB – fus) faire

F[i + lA] <-- B[i + fus]

Fin pour

Fin si

Retourner F

Fin

_______________________________

Question II.1

On souhaite remplir un tableau carré à deux dimensions (n*n) avec un texte T. Définir et écrire cette fonction remplir_matrice_carré. Par exemple :

remplir_matrice_carré (« lechatboitdulait », 5) -->

L	E	C	H	A
T	B	O	I	T
D	U	L	A	I
T	L	E	C	H
A	T	B	O	I

Réponse

Pour chaque case de la matrice, on determine son caractère correspondant dans T. La fonction ne rend rien car elle modifie la matrice (effet de bord). On note x mod y est le reste de la division de x par y (x et y entiers)

Fonction remplir_matrice_carré (T :chaîne de caractères, M : tableau [n*n]de caractères)

--> vide

Entier numcar

Entier lT <-- longueur(T)

pour i = 0 à n – 1 faire

pour j = 0 à n – 1 faire

numcar <-- i* n + j

M[i, j] <-- T[numcar mod lT]

fin pour

fin pour

Fin

Si on est alergique aux calculs, on peut alternativement gérer lecompteur numcar explicitement :

Fonction remplir_matrice_carré (T :chaîne de caractères, M : tableau [n*n]de caractères)

--> vide

Entier numcar <-- 0

Entier lT <-- longueur(T)

pour i = 0 à n – 1 faire

pour j = 0 à n – 1 faire

M[i, j] <-- T[numcar mod lT]

numcar <-- numcar + 1

fin pour

fin pour

Fin

Une seule des deux versions était nécessaire.

_______________________________

Question II.2

On souhaite décaler circulairement les lignes et les colonnes d’une matrice carrée de caractères, à l’aide de deux valeurs numériques. La première valeur C décale l’ensemble des colonnes, la seconde valeur L les lignes. Une valeur positive décale vers le bas ou à droite, une valeur négative vers le haut ou à gauche. Par exemple :

L	E	C	H	A
T	B	O	I	T
D	U	L	A	I
T	L	E	C	H
A	T	B	O	I

C = 2 et L = 3

C = 2

-->

H	A	L	E	C
I	T	T	B	O
A	I	D	U	L
C	H	T	L	E
O	I	A	T	B

L = 3

-->

A	I	D	U	L
C	H	T	L	E
O	I	A	T	B
H	A	L	E	C
I	T	T	B	O

Ecrire cette fonction décaler_matrice(M : tableau , C, L : entier)

Réponse

On commencer par une version (un peu difficile ?) qui modifie la matrice. On va écrire une fonction décaler_ligne et une fonction décaler_colonne. Ces fonctions modifient la matrice, il ne pas ici s’agit de faire une copie de la matrice. Par contre, il est nécessaire de copier la ligne concernée (ou la colonne), avant de décaler les valeurs (comme on copie une valeur quand on veux échanger le contenu de deux variables).

Fonction copier_ligne (M : tableau [n*n] de caractères ;

NLigne : entier ;

T :tableau [n] de caractères)

--> vide

pour i de 0 à n-1 faire

T[i] <-- M[NLigne , i]

fin pour

fin

Fonction copier_colonne (M : tableau [n*n] de caractères ;

NCol : entier ;

T :tableau [n] de caractères)

--> vide

pour i de 0 à n-1 faire

T[i] <-- M[i, Ncol]

fin pour

fin

Fonction decaler_ligne (M : tableau [n*n] de caractères ;

k :entier ; Nligne :entier)

--> vide

T <-- nouveau tableau [n] de caractères

copier_ligne(M, Nligne, T)

pour i = 0 à n – 1 faire

M[Nligne, (i + k) mod n] <-- T[i]

fin pour

Fin

Fonction decaler_colonne (M : tableau [n*n] de caractères ;

k :entier ; Ncol :entier)

--> vide

T <-- nouveau tableau [n] de caractères

copier_colonne(M, NCol, T)

pour i = 0 à n – 1 faire

M[(i + k) mod n, NCol] <-- T[i]

fin pour

Fin

Fonction decaler_matrice (M : tableau [n*n] de caractères ;

c, l :entier)

--> vide

pour i = 0 à n – 1 faire

decaler_colonne(M, c, i]

fin pour

pour i = 0 à n – 1 faire

decaler_ligne(M, l, i]

fin pour

Fin

Décaler la matrice consiste a d’abord décaler toutes ses colonnes puis toutes ses lignes (ou l’inverse, c’est commutatif).

La version qui consiste à produire une autre matrice (dite copie) est à la fois correcte et plus facile.

Fonction decaler_ligne_copie (M, M’ : tableau [n*n] de caractères ;

k :entier ; Nligne :entier)

--> vide

pour i = 0 à n – 1 faire

M’[Nligne, (i + k) mod n] <-- M[Nligne ,i]

fin pour

Fin

Fonction decaler_colonne_copie (M, M’ : tableau [n*n] de caractères ;

k :entier ; Ncol :entier)

--> vide

pour i = 0 à n – 1 faire

M’[(i + k) mod n, NCol] <-- M[i, NCol]

fin pour

Fin

Fonction decaler_matrice (M : tableau [n*n] de caractères ;

c, l :entier)

--> M’

M’ <-- nouveau tableau [n*n] de caractères

pour i = 0 à n – 1 faire

decaler_colonne_copie (M, M’, c, i]

fin pour

pour i = 0 à n – 1 faire

decaler_ligne_copie (M, M’, l, i]

fin pour

retourner M’

Fin

Une seule des deux solutions était demandée.

_______________________________

BAREME 5 pts à chaque question avec 1 et 3 faciles – 2 et 4 plus longues

Remarques générales : il vaut mieux faire des fonctions intermédiaires, afin de rendre le code plus lisible. Répondez aux questions en commençant par les plus faciles, ici 1 et 3. Respecter les types de données et leurs opérations. Si la signature de votre focntion indique un résultat d’un certain type, vérifier que son corps retourne bien une veleur de ce type et pas d’un autre. Vérifier, que vous avez une chance de sortir de vos boucle (ou d’y rentrer).