UNIVERSITÉ BORDEAUX 1 Session de Juin 1996
Département de formation premier cycle
Polycopié, notes de cours et de TD autorisées. Autres documents interdits.
Le sujet comporte une page recto-verso. Les 3 exercices sont indépendants ; donnez des réponses simples et précises : les fonctions C demandées sont très courtes (quelques lignes). Ecrire des généralités, ou copier des fonctions vues en cours ou en TD, vous fera perdre du temps sans vous rapporter aucun point.
|
Ecrire en langage C la fonction f définie par :
|
|
Ecrire une fonction C qui calcule le nombre d'inversions d'un tableau t de taille n.
Voici une traduction en langage C :
#define MAX 100
int barre[MAX];
void crible (int n) {
...
}
void liste_premiers () {
int n;
for (n = 0; n < MAX; n++) barre[n] = 0;
crible (2); crible (3); crible (5); crible (7);
for (n = 2; n < MAX; n++)
if (! barre[n]) printf (" %d", n);
printf ("\n");
}
Note : cette question est probablement plus difficile que les autres, bien que la réponse soit aussi courte que d'habitude.
double f (double x, int n) {
int k;
double s = 0, t = 1;
for (k = 0; k < n; k++) {
t = t * (x - k) / x;
s = s + t;
}
return s;
}
int inversions (int *t, int n) {
int i, j, compteur = 0;
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
if ( t[i] > t[j]) compteur++;
return compteur;
}
Note : on peut aussi bien écrire la première boucle :
for (i = 0; i < n - 1; i++) .
La solution suivante n'est pas fausse, mais maladroite :
int inversions (int *t, int n) {
int i, j, compteur = 0;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if ( i < j && t[i] > t[j]) compteur++;
return compteur;
}
void crible (int n) {
int i;
for (i = 2 * n; i < MAX; i = i + n)
barre[i] = 1;
}
Note : on peut en fait commencer le crible avec i=n*n, car les multiples de n précédents ont déjà été barrés.
Cette solution est de loin préférable à la suivante, qui effectue de nombreux calculs inutiles :
void crible (int n) {
int i;
for (i = n + 1; i < MAX; i++)
if (i % n == 0)
barre[i] = 1;
}
Attention : avec cette solution, ajouter
else
barre[i] = 0;
est une grave erreur.
crible (11); crible (13);
dans la fonction liste_premiers.
for (n = 2; n * n < MAX; n++)
if (! barre[n]) crible (n);