Corrigé de l'examen I20, janvier 1998

Voir le sujet.
On notera que le total des points, sans compter la question subsidiaire dans l'exercice 4, est de 26, conformément à l'indication "on ne demande pas de tout traiter". Les notes les meilleures, en particulier celles supérieures à 20, ont été remplacées par des notes entre 17 et 19.

Exercice 1

5 points.
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;
}
La complexité de cet algorithme est linéaire. La détection d'un indice i tel que
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 que
i < 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 :

  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;
  }
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.

Exercice 2

Partie 1 (6 points). Solution itérative :

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;
}
En cas d'échec, la fonction retourne -1, seule valeur qu'on ne peut confondre avec un véritable indice.

Solution récursive :

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

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.

Exercice 3

3 points.
long PremierSuivant (long n) {
  while (! premier (n) ) n++;
  return n;
}
Beaucoup de variantes sont possibles, mais souvent plus longues et moins claires, par exemple :

long PremierSuivant (long n) {
  long i;
  for (i = n; ;i++)
    if (premier (i))
      return i;
}
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).

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.

Exercice 4

3 points.
int CardinalPremiers (long a, long b) {
  int compteur = 0;
  long n;
  
  for (n = a; n <= b; n++)
    compteur = compteur + premier (n);
  return compteur;
}
La solution :
  for (n = a; n <= b; n++)
    if (premier (n))
      compteur++;
est évidemment correcte et seulement un peu moins esthétique. L'important est de ne pas oublier l'initialisation de la variable 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 :

#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);
}
Il faut prendre garde à ne pas calculer d par un quotient d'entiers, qui ici vaut toujours zéro.

Exercice 5

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.

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;
}
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.