Polytechnique X 2004 informatique classe prepa mp

´ `ECOLE POLYTECHNIQUE FILIEREMPOPTION INFORMATIQUECONCOURS D’ADMISSION 2004COMPOSITION D’INFORMATIQUE(Dur´ee : 4 heures)L’utilisation des calculatrices n’est pas autoris´ee pour cette ´epreuve.Le langage de programmation choisi par le candidat doit ˆetre sp´ecifi´eentˆete de la copie.M´ edians et Convexit´ eOn attachera une grande importance `a la concision, `alaclart´e, et `alapr´ecision de la r´edaction.Les deux probl`emes sont ind´ependants.Premier probl`eme : S´electionUn m´ edian d’un ensemble X = {e ,e ,...e } de n nombres entiers distincts est un nombre e1 2 ndans X tel que les nombres d’´el´ements strictement plus petits et strictement plus grands que e dansX diff`erent d’au plus de 1 (n>0). Si n est impair, le m´edian est unique ; si n est pair, il y a deuxm´ edians possibles.Le probl`eme de la s´election consiste `atrouverl’´el´ement de rang k dans X,c’est-`a-dire l’´el´ement ese trouvant en k-i`eme position quand X est tri´e en ordre croissant (1≤ k ≤ n).Nous supposerons l’ensemble X repr´esent´e par la liste de ses ´el´ements, c’est-`a-dire par le typeensemble d´ efini par :(* Caml *) { Pascal }typeensemble = ^cellule;type ensemble == int list;;cellule = record contenu:integer;suivant:ensemble; end;En Pascal, la liste vide est nil et l’on pourra utiliser la fonction suivante pour construire les listes :function cons(x:integer; s:ensemble) : ensemble;var r:ensemble;begin new(r); r^.contenu := x; r^.suivant := s; cons := r end ...