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 |
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 !
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.
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.
- 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 ?
- 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).
- 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.
Ecrire une fonction PremierSuivant qui calcule le plus petit nombre premier supérieur ou égal à n.
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 !
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.