:: Enseignements :: ESIPE :: E3INFO :: 2015-2016 :: Algorithmique ::

Manipulation de tableaux et puissances

Dans ce TP, on implante et compare d'abord des algorithmes simples sur les tableaux. Ensuite, on compare les deux algorithmes pour la puissance vus en TD.

Exercice 1 - Insertion et recherche dans un tableau

On souhaite écrire des fonctions d'insertion et de recherche d'un élément dans un tableau.

Commencer par récupérer l'archive Base.zip et extraire les fichiers dans votre répertoire de travail. Le fichier arrays.h contient des en-têtes de quatre fonctions qui sont censées effectuer des insertions et des recherches dans des tableaux triés et non triés. Vous écrivez le code de ces fonctions dans le fichier arrays.c.
Le fichier arrays_ref.o contient des fonctions de référence avec lesquelles vous pouvez tester l'exactitude et la performance de vos fonctions. La commande make permet de compiler le programme bench qui effectue les tests :
```
$ make
gcc -c -o bench_main.o bench_main.c -Wall -ansi
gcc -c -o benchmark.o benchmark.c -Wall -ansi
gcc -c -o arrays.o arrays.c -Wall -ansi
gcc -o bench bench_main.o benchmark.o arrays_ref.o arrays.o
$ ./bench -h
```
Si vous voulez écrire une autre fonction main qui utilise les fonctions de référence et les autres fonctions dans benchmark.h, vous pouvez le faire dans un fichier mon_prog.c et le compiler avec :
```
$ gcc -o mon_prog mon_prog.c benchmark.o arrays_ref.o arrays.o
```
Lancer ./bench -a et constater que les fonctions insert_unsorted, find_unsorted, insert_sorted et find_sorted ne fonctionnent pas correctement.
Écrire les fonctions insert_unsorted et find_unsorted pour un tableau non trié. Vérifier avec ./bench -u que vos fonctions sont correctes. Le comportement des fonctions est décrit ci-dessous :
- void insert_unsorted(int arr[], int *size, int elt);
  Insertion dans un tableau non trié. On insère l'élément elt à la fin du tableau, puis on incrémente *size de 1.
- int find_unsorted(int arr[], int size, int elt);
  Recherche dans un tableau non trié. On parcourt le tableau tant qu'il y a des éléments et que l'on n'a pas trouvé la valeur elt.
Ensuite, écrire les fonctions pour un tableau trié et les vérifier avec ./bench -s.
- void insert_sorted(int arr[], int *size, int elt);
  Insertion dans un tableau trié (en ordre croissant). On décale tous les éléments de la fin du tableau jusqu'à la position où on veut insérer l'élément elt, puis on incrémente *size de 1.
- int find_sorted(int arr[], int size, int elt);
  Recherche dans un tableau trié (en ordre croissant). On effectue une recherche dichotomique dans une partie triée, commençant à l'indice first=0 jusqu'à l'indice last=size-1.
  - Si la partie est vide, l'élément n'est pas présent; sinon, on détermine l'élément à l'indice middle, au milieu de la partie.
  - Si cet élément est celui recherché, c'est fini: on l'a trouvé.
  - Si l'élément à l'indice middle est supérieur à l'élément recherché, on poursuit la recherche dans la partie qui se trouve avant l'indice middle.
  - Si l'élément à l'indice middle est inférieur à l'élément recherché, on poursuit la recherche dans la partie qui se trouve après l'indice middle.
Finalement, lancer ./bench -a et comparer les temps d'exécution entre la version triée et la version non triée. Vérifier que les temps sont cohérents avec les complexités des fonctions.

Exercice 2 - Puissances

Écrire les deux fonctions de calcul de xⁿ vues en TD, mais en prenant les deux paramètres x et n de type entier. Vérifier en utilisant quelques valeurs différentes pour x et n que les fonctions renvoient le même résultat.

Quelles valeurs pour x et n sont raisonnables par rapport à la taille d'un int ? Essayer avec des puissances de 2 et 3. Jusqu'à quelle valeur de n le résultat a-t-il un sens ?
Changer le type int pour unsigned long. Quelles valeurs pour x et n sont désormais raisonnables ?
Ajouter dans vos fonctions un compteur pour le nombre de multiplications effectuées. Comparer les deux fonctions avec des grandes valeurs de x et n. (Même si la valeur de retour des fonctions n'a pas de sens, le nombre de multiplications est correct.)

Exercice 3 - Pour ceux qui s'ennuient

Sur la base de ce petit programme ci-dessous qui affiche à l'écran tous les mots d'un fichier dont le nom est passé en argument, on souhaite utiliser nos fonctions sur les tableaux pour les trois usages suivants:

obtenir un tableau dont chaque élément correspond à la longueur d'un mot du texte.
utiliser ce tableau pour trouver la longueur médiane des mots du texte correspondant à ce fichier (la valeur telle qu'il y a autant de mots sont de longueur inférieure que de mots de longueur supérieure).
utiliser ce tableau pour afficher, pour chaque longueur de mot, combien de mots dans le texte ont cette longueur.

Vous pourrez tester avec le fichier texte VictorHugo_LesMiserables-II-Cosette.txt ou avec d'autres textes que vous pourrez trouver sur le site du Projet Gutenberg.