Université Louis Pasteur Département d’Informatique

Septembre 1991

LICENCE D’INFORMATIQUE

Méthode de programmation

Durée: 3 heures

Première partie (13 points)

On supposera connues les fonctions C de manipulation de chaînes de caractères

(strcmp, strlen, strcpy . . . ).

Soit T (char T[1000];) une chaîne de caractères composée de lettres majuscules, de blancs et de points. Les points délimitent les phrases, les mots d’une même phrase sont séparés par un ou plusieurs blancs.

1. Ecrire la fonction Prochain(i) qui rend l’indice du premier mot rencontré dans la chaîne après l’élément i (Prochain(3)=8).

j e  s u i s  u n e  c h a î n e
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

2. Ecrire un programme récursif qui remplit un tableau d’entiers de sorte que l’élément i contienne le nombre de mots de T de longueur i.

3. Ecrire le programme localise(m) qui rend l’indice du premier caractère du mot m dans T (-1 s’il ne le trouve pas).

4. Ecrire la fonction substitue(old,new) qui remplace toutes les occurrences du mot old par new (on supposera que la précondition long(old)≥long(new) est toujours vérifiée).

5. Ecrire un programme qui affiche sans duplication la liste alphabétique des palindrômes (mots qui se lisent de la même manière de gauche à droite et de droite à gauche comme kayak, été, ici, …).

Deuxième partie (7 points) Soit T un tableau déclaré par int T[1000].

1. Ecrire un programme qui compte le nombre de nombres différents de T sans utiliser de tableau auxilliaire, sans modifier T.

2. Ecrire un programme itératif qui trie T, sans tableau auxilliaire.

3. Ecrire un programme récursif qui trie T, sans tableau auxilliaire.

4. Ecrire un programme de tri dichotomique, sans tableau auxilliaire.