Polytechnique X 2004 informatique classe prepa mp

Description

´ `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 ...

Informations

• Publié par: shura
• Nombre de lectures: 115
• Langue: Français

Extrait

´ ECOLE POLYTECHNIQUE

CONCOURS D’ADMISSION 2004

` MP FILIERE OPTION INFORMATIQUE

COMPOSITION D’INFORMATIQUE (Dur´ee:4heures)

L’utilisation des calculatricesne’oris´eestpasautrpe´evuecruoettep. Lelangagedeprogrammationchoisiparlecandidatdoiteˆtrespe´cifie´enteˆtedelacopie.  

M´ediansetConvexite´

Onattacheraunegrandeimportancea`laconcision,`alaclarte´,eta`lapre´cisiondelare´daction. Lesdeuxprobl`emessontinde´pendants.

Premierprobl`eme:Se´lection

Unme´diand’un ensembleX={e 1 , e 2 , . . . e n }dennombres entiers distincts est un nombree dansXetsplutptrtsseittnemetcinargsulpombrlesn´el´esd’sttsmenemeneirtcdlsqquueeteedans Xdiff`eertn’dualpsued(1n >0). Sintiesaimpel,rde´menainutss;iqieunest pair, il y a deux m´edianspossibles. Leproble`medelactle´esoinnaregts`etaorcnoisl´ementduverl’´ekdansX,se’c’´el´eel`at-ir-dntmee se trouvant enkeme`i-noitisopdquanXceorrordtn1(siases´eenttri≤k≤n). Nous supposerons l’ensembleXlasietedes´slee´repr´esent´eparlpetylearepird-a`-tse’c,stnem ensemble:rinap´dfie (*Caml*){Pascal} type ensemble = ^cellule; type ensemble == int list;; cellule = record contenu:integer; suivant:ensemble; end; En Pascal, la liste vide estnilet 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;

Cette fonction est applicable pour construire les listes du typeensemble.

1