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);