Université Bordeaux 1 Session de janvier 1998
Département de Formation Premier Cycle
Module I20, GM MIP, MIP(E), IUP-MIAGE Epreuve de J.Bétréma
Date : 22 janvier 1998 Durée : 1h30

Un corrigé est disponible.

Les 5 exercices sont indépendants. Donner des réponses simples et précises : les fonctions C demandées sont très courtes (quelques lignes). On ne demande pas de tout traiter : les candidat(e)s sont libres de choisir les exercices qui leur conviennent. Les exercices 3 et 4 sont probablement les plus faciles. Bonne chance !

Exercice 1

Soit une fonction f donnée : int f (int x); on considère la suite définie par la récurrence :
x0 = a , xi = f ( xi-1 ) pour i > 0.
Ecrire, sans utiliser de tableau, une fonction boucle qui calcule le plus petit indice strictement positif i < n tel que xi = x2i ; s'il n'existe pas de tel indice, la fonction retourne 0 ; a et n sont des paramètres, ainsi que f.

Exercice 2

On considère un tableau d'entiers a ordonné strictement : a0 < a1 < a2 < ... Pour trouver si un entier x donné figure parmi le segment ai ... aj , et si oui calculer son indice, on procède par dichotomie : on calcule k = (i + j) / 2 (au sens de la division d'entiers en C, par exemple 7/2 = 3), si x = ak l'indice k est trouvé, si x < ak on poursuit la recherche dans la moitié gauche du segment et sinon dans la moitié droite.
  1. Traduire cet algorithme en une fonction int indice (long a[], long x, int i, int j). Quelle valeur la fonction doit-elle retourner si x ne figure pas parmi ai ... aj ?
  2. On suppose que a contient les 10 valeurs suivantes : 3, 5, 6, 12, 15, 16, 20, 21, 22, 23. Simuler brièvement les calculs effectués lors des appels indice (a,20,0,9) et indice (a,17,0,9).
  3. Quelle est la complexité de cet algorithme en fonction de la taille du tableau ?

Les exercices suivants supposent qu'on dispose d'une fonction int premier (long n) qui retourne 1 si n est premier, 0 sinon. Pas de panique, ces exercices ne demandent aucune connaissance particulière en arithmétique. Ecrire la fonction premier est hors sujet, et ne rapportera aucun point.

Exercice 3

Ecrire une fonction PremierSuivant qui calcule le plus petit nombre premier supérieur ou égal à n.

Exercice 4

Ecrire une fonction CardinalPremiers qui calcule le nombre d'entiers premiers compris entre a et b.

Ecrire une fonction densite qui compare la densité des nombres premiers voisins de N avec 1 / ln N . Cette question est volontairement vague : si vous ne la comprenez pas, ne la traitez pas !

Exercice 5

Ecrire une fonction creux qui calcule le plus long intervalle [c d] inclus dans [a b] (a et b sont des paramètres) et ne contenant aucun nombre premier. Cette fonction doit calculer simultanément c et d.