5 points.La complexité de cet algorithme est linéaire. La détection d'un indice i tel que
int boucle (int a, int n, int f (int)) { int i, x = a, y = a; for (i = 1; i < n; i++) { x = f (x); y = f (f (y)); if (x == y) return i; } return 0; }xi = x2i (*) est un algorithme très efficace de détection de boucle dans une suite récurrente (algorithme de Floyd) : aussi surprenant que cela semble au premier coup d'oeil, l'existence d'indices i et j tels quei < j et xi = xj (**) implique l'existence d'un indice i vérifiant (*), et le plus petit d'entre eux est inférieur au plus petit indice j vérifiant (**).Cette solution a été rarement trouvée ; beaucoup plus souvent la solution proposée :
a une complexité inutilement quadratique. Mais dans les conditions de l'examen 4 points ont été attribués à cette solution qui dénote une maîtrise correcte du langage, pourvu que l'initialisation y = x; soit faite correctement.
for (i = 1; i < n; i++) { x = f (x); y = x; for (j = 0; j < i; j++) y = f (y); if (x == y) return i; }
Partie 1 (6 points). Solution itérative :
En cas d'échec, la fonction retourne -1, seule valeur qu'on ne peut confondre avec un véritable indice.
int indice (long a[], long x, int i, int j) { int k; while (i <= j) { k = (i + j) / 2; if (x == a[k]) return k; if (x < a[k]) j = k - 1; else i = k + 1; } return -1; }Solution récursive :
Bizarrement dans cette solution return est très souvent oublié devant l'appel de la fonction indice. Les else ci-dessus sont facultatifs (car précédés par return).
int indice (long a[], long x, int i, int j) { int k; if (i > j) return -1; k = (i + j) / 2; if (x == a[k]) return k; else if (x < a[k]) return indice (a, x, i, k - 1); else return indice (a, x, k + 1, j); }Dans presque toutes les copies où la question est traitée i (resp. j) est remplacé par k au lieu de k + 1 (resp. k - 1), ce qui pose des problèmes de terminaison de la fonction non résolus (ou résolus de façon artificielle, ce qui n'est pas mieux) : si par exemple i et j sont des entiers consécutifs (j = i+1) la demi-somme vaut i, et la fonction boucle si la branche i = k est choisie.
Certain(e)s étudiant(e)s ont hésité dans l'interprétation de l'énoncé : s'agit-il de trouver l'indice k tel que x = ak ou bien tel que x appartienne à l'intervalle [ak ak+1] ? Seule la première interprétation est cohérente avec la formulation de l'énoncé, mais il n'y aurait pas eu de mal à résoudre le second problème, qui est très voisin, à condition de l'exposer clairement.
La partie 2 permet aux étudiant(e)s de vérifier que leur solution n'est pas manifestement fausse, en particulier dans le cas où x ne figure pas dans le tableau.
Partie 3 (3 points) : la complexité de cet algorithme dichotomique est logarithmique en fonction de la taille du tableau. Les bonnes réponses sont hélas exceptionnelles.
3 points.Beaucoup de variantes sont possibles, mais souvent plus longues et moins claires, par exemple :
long PremierSuivant (long n) { while (! premier (n) ) n++; return n; }
Ecrire if (premier (i)) est très préférable à if (premier (i) == 1) qui est inutilement long. Ecrire while (! premier (n)) est préférable à while (premier (n) == 0).
long PremierSuivant (long n) { long i; for (i = n; ;i++) if (premier (i)) return i; }La boucle ne peut être sans fin, car il existe une infinité de nombres premiers ; les étudiant(e)s qui ont compliqué leur fonction car les entiers représentés en machine forment un ensemble fini, ont fait preuve d'un scrupule louable mais déplacé dans ce contexte. Un examen n'est pas un piège, et utiliser cette fonction avec un argument très proche de 231 n'est ni vraisemblable (environ une chance sur 2 milliards) ni raisonnable. Par contre une remarque sur ce point était évidemment bienvenue.
3 points.La solution :
int CardinalPremiers (long a, long b) { int compteur = 0; long n; for (n = a; n <= b; n++) compteur = compteur + premier (n); return compteur; }est évidemment correcte et seulement un peu moins esthétique. L'important est de ne pas oublier l'initialisation de la variable compteur.
for (n = a; n <= b; n++) if (premier (n)) compteur++;L'énoncé précise que la question subsidiaire (3 points) sur la comparaison de la densité expérimentale et de la densité théorique des nombres premiers ne s'adresse qu'aux étudiant(e)s pour lesquel(le)s ces notions sont familières ; ceux ou celles qui ont compris que comparer signifie «déterminer le plus grand des deux» ont manifesté un manque d'à-propos mathématique. Voici une réponse possible :
Il faut prendre garde à ne pas calculer d par un quotient d'entiers, qui ici vaut toujours zéro.
#include <math.h> double densite (long n) { int p, delta; double d, theorie; if (n > 10000) delta = 1000; else delta = n / 10; p = CardinalPremiers (n - delta, n + delta); d = p / (double) (2 * delta); theorie = 1 / log (n); return (d / theorie); }
6 points. Il faut parcourir l'intervalle [a b], trouver le plus grand écart entre deux nombres premiers consécutifs p et q, et retourner une structure composée de c = p + 1 et d = q - 1. Il faut aussi prendre garde au cas où c = a et/ou d = b.
Les détails de cette fonction sont difficiles à mettre au point en situation d'examen : 4 points sont attribués dès que le squelette est correct. Les fonctions incompréhensibles, farcies de boucles emboîtées, ne rapportent aucun point en dehors de celui attribué à la définition correcte de la structure et de l'en-tête.
struct intervalle { long debut, fin; }; struct intervalle creux (long a, long b) { long c = a, d, n; struct intervalle inter; inter.debut = a; inter.fin = a - 1; for (n = a; n <= b; n++) if (premier (n)) { d = n - 1; if (d - c > inter.fin - inter.debut) { inter.debut = c; inter.fin = d; } c = n + 1; } if (b - c > inter.fin - inter.debut) { inter.debut = c; inter.fin = b; } return inter; }