Admin CliCours
Exercice 1
#include
#define N 10
int nombre, i,
/* pour la mise au point */
a[N] = { 1, 2, 13, 4, 5, 16, 7, 8, 9, 10 },
b[N] = { 11, 12, 13, 14, 15, 16, 17, 18, 9, 20 };
main() {
nombre = 0;
for (i = 0; i < N; i++)
if (a[i] == b[i])
nombre++;
printf("%d\n", nombre);
}
L'algorithme est simple : chaque fois que a[i] est égal à b[i] on incrémente nombre ; autour de cela, une boucle for fait en sorte que i vaille successivement 0, 1, ... N-1.
Exercice 2
[1] Le programme souvent utilisé est celui-ci :
#include
#define N 10
int i, vmin,
/* pour la mise au point */
t[N] = { 3, 2, 5, 10, 8, 6, 1, 7, 4, 9 };
main() {
vmin = t[0];
for (i = 1; i < N; i++)
if (t[i] < vmin)
vmin = t[i];
printf("vmin : %d\n", vmin);
}
Cette solution est correcte… s’il est certain par ailleurs que N > 0. Si N = 0, l’algorithme donne comme réponse t[0], ce qui est au mieux une valeur indéterminée, au pire une erreur grave.
Voici une autre rédaction qui tient compte de ce cas particulier :
#include
#include
#define N 10
int i, vmin,
/* pour la mise au point */
t[N] = { 3, 2, 5, 10, 8, 6, 1, 7, 4, 9 };
main() {
vmin = INT_MAX;
for (i = 0; i < N; i++)
if (t[i] < vmin)
vmin = t[i];
printf("vmin : %d\n", vmin);
}
Cela consiste à initialiser vmin avec l’infini ou du moins avec la plus grande valeur qu’il est possible de représenter dans le type considéré. La plus grande valeur du type int dépend de l’implémentation ; elle est représentée par la pseudo-constante INT_MAX, définie dans le fichier limits.h.
Si le tableau n’est pas vide (c.-à-d. si N > 0), dès le premier tour t[0] est inférieur à vmin et on est ramenés au cas précédent.
Si le tableau est vide (N = 0) on sort de l’algorithme avec vmin = INT_MIN ; c’est une valeur reconnaissable qu’on peut tester dans la suite du programme. De plus, donner l’infini comme minimum de l’ensemble vide est satisfaisant du point de vue mathématique.
[2] On nous demande également un programme qui donne non seulement la valeur du minimum du tableau, mais aussi l’indice de l’élément correspondant (on recherche plus souvent l’indice que la valeur). Aucune difficulté pour adapter l’une ou l’autre des solutions précédentes :
#include
#include
#define N 10
int i, imin, vmin,
/* pour la mise au point */
t[N] = { 3, 2, 5, 10, 8, 6, 1, 7, 4, 9 } ;
main() {
imin = -1;
vmin = INT_MAX;
for (i = 0; i < N; i++)
if (t[i] < vmin) {
imin = i;
vmin = t[i];
}
printf("imin : %d, vmin : %d\n", imin, vmin);
}
Exercice 3
Voici un algorithme que vous êtes sûrs de programmer de nombreuses fois au cours de votre carrière !
[1] Premier cas, on est assuré que l’élément cherché se trouve dans le tableau :
#include
#define N 10
int i, x,
/* pour la mise au point */
t[N] = { 13, 12, 15, 18, 16, 11, 17, 14, 19, 10 };
main() {
printf("x ? ");
scanf("%d", &x);
i = 0;
while (t[i] != x)
i++;
printf("i : %d\n", i);
}
L’algorithme de recherche séquentielle est constitué par les trois lignes du milieu
...
i = 0;
while (t[i] != x)
i++;
...
Que la valeur de x soit certainement dans le tableau nous garantit que la condition t[i] != x sera fausse pour une valeur de i vérifiant 0 <= i < N, et donc que le programme quittera la boucle en temps utile. C’est une hypothèse risquée, qu’on ne peut pas faire en général (par exemple, dans le programme ci-dessus elle n’est manifestement pas satisfaite puisque la valeur de x provient d’une lecture au clavier).
Il faut donc prévoir qu’on ait t[i] != x pour toute valeur 0 <= i < N et prendre des mesures pour éviter une des fautes de programmation les plus fréquentes : l’accès à un tableau avec un indice en dehors de ses bornes. Il faut se rappeler que lorsque i < 0 ou i >= N la condition t[i] != x n’est ni vraie ni fausse, mais une erreur qui produira au mieux un résultat indéterminé, au pire la mort violente du programme.
[2] Deuxième version du programme, plus réaliste :
#include
#define N 10
int i, x,
/* pour la mise au point */
t[N] = { 13, 12, 15, 18, 16, 11, 17, 14, 19, 10 };
main() {
printf("x ? ");
scanf("%d", &x);
i = 0;
while (i < N && t[i] != x)
i++;
if (i < N)
printf("présent; i : %d\n", i);
else
printf("absent\n");
}
Notez que ce programme est correct à cause de l’évaluation séquentielle de l’opérateur && : si le premier opérande est faux, le second n’est pas évalué. Autrement dit, si i < N n’est pas vrai, alors t[i] != x n’est même pas examiné.
A la sortie de la boucle while il faut savoir si on a trouvé x ou non. Deux possibilités :
- la condition i < N est fausse. Cela implique que i = N et, puisque la boucle n’a pas été abandonnée précédemment, que t[i] != x est vrai pour i = 0, 1, … N-1. On peut affirmer que x n’est pas dans le tableau.
- la condition i < N est vraie. Mais alors, puisqu’on a quitté la boucle, c’est que t[i] != x est faux. C’est-à-dire t[i] = x avec 0 <= i < N : on peut affirmer que x est dans le tableau et que i est l’indice de l’élément correspondant.
[3] L’existence en C de l’instruction break permet une autre rédaction de la solution précédente, ni plus ni moins efficace que la précédente, mais très satisfaisante pour l’esprit car très « évidemment » juste :
...
for (i = 0; i < N; i++)
if (t[i] == x)
break;
if (i < N)
printf("présent; i : %d\n", i);
else
printf("absent\n");
...
[4] Le coût de la recherche séquentielle est une fonction linéaire de la taille du tableau. En effet, le nombre d’opérations d’une recherche dépend de la position de l’élément cherché dans le tableau (les éléments du début sont trouvés tout de suite, ceux de la fin ne sont trouvés qu’au prix du parcours de la plus grande partie du tableau et il faut parcourir tout le tableau pour conclure à l’absence d’un élément). Si toutes les valeurs possibles ont la même probabilité d’être recherchées, alors l’espérance du nombre d’opérations est compris entre n / 2 (si on ne recherche que des éléments présents) et n (si on ne recherche que des éléments absents).
Notons au passage que la recherche séquentielle n’impose aucune contrainte particulière au tableau, qui n’a pas besoin d’être trié). Par conséquent, pour insérer un élément dans un tel tableau il suffit de le copier dans la première case libre (en supposant qu’il reste des cases libres). Cela s’écrit
t[n++] = x;
et a un coût qui ne dépend pas de n, c’est-à-dire négligeable
