Polytechnique X 2004 epreuve d algorithmique classe prepa pc

Description

´ECOLE POLYTECHNIQUE´ ´ECOLE SUPERIEURE DE PHYSIQUE ET CHIMIE INDUSTRIELLESCONCOURS 2004` `´FILIEREMP - OPTION PHYSIQUE ET SCIENCES DE L’INGENIEUR FILIEREPCCOMPOSITION D’INFORMATIQUE(Dur´ee : 2 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.Compression ternaireOn attachera une grande importance `a la concision, `alaclart´e, et `alapr´ecision de la r´edaction.On supposera que le langage de programmation utilis´eposs`ede deux op´erations x div y et x mod ydonnant le quotient et le reste de la division euclidienne de x par y.Le temps d’ex´ecution T(f) d’une fonction f est le nombre d’op´erations ´el´ementaires (addi-tion, soustraction, multiplication, division, affectation, etc.) n´ecessaire au calcul de f.Lorsquece temps d’ex´ecution d´epend d’un param`etre n,ilseranot´e T (f). On dit que la fonction fns’ex´ecute :• en temps lin´eraire en n, s’il existe K>0 tel que pour tout n, T (f)≤ Kn ;n2• en temps quadratique en n, s’il existe K>0 tel que pour tout n, T (f)≤ Kn .nNombres ternairesEn base 3, les entiers 0, 1, 2, 3, 4, 5, 6, 7, 8 sont repr´esent´es par 00, 01, 02, 10, 11, 12, 20,21, 22.Lechiffredepoidsfortdebc est b ;lechiffredepoidsfaibleestc.´Question 1. Ecrire la fonction entier(b,c) retournant l’entier compris entre 0 et 8 qui s’´ecritbc en base 3.1´Question 2. Soit x un entier v´erifiant 0≤ x≤ 8. Ecrire une fonction ...

Informations

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

Extrait

´ ECOLE POLYTECHNIQUE ´ ´ ECOLE SUPERIEURE DE PHYSIQUE ET CHIMIE INDUSTRIELLES

CONCOURS 2004

` ´ MP FILIERE- OPTION PHYSIQUE ET SCIENCES DE L’INGENIEUR

COMPOSITION D’INFORMATIQUE (Dure´e:2heures)

FILIERE PC `

L’utilisation des calculatricesee´orissautstpan’erpe´ettecruop.veeu Lelangagedeprogrammationchoisiparlecandidatdoitˆetresp´ecifie´entˆetedelacopie.  

Compressionternaire

Onattacheraunegrandeimportance`alaconcision,a`laclarte´,et`alapre´cisiondelare´daction. Onsupposeraquelelangagedeprogrammationutilis´eposse`dedeuxope´rationsxdivyetxmody donnant le quotient et le reste de la division euclidienne dexpary.

Letempsd’ex´ecutionT(f) d’une fonctionflestmbnod’re´eopitar´snoe´letnemid-(sdaiaere tion,soustraction,multiplication,division,affectation,etc.)ne´cessaireaucalculdef. Lorsque cetempsd’exe´cutionde´pendd’unparam`etrene´tonarels,iT n (f). Ondit que la fonctionf s’ex´ecute:

•etnpsemn´liaierenren, s’il existeK >0 tel que pour toutn,T n (f)≤Kn; 2 •en temps quadratique enn, s’il existeK >0 tel que pour toutn,T n (f)≤Kn.

Nombres ternaires

Enbase3,lesentiers0,1,2,3,4,5,6,7,8sontrepr´esente´spar00,01,02,10,11,12,20, 21,22. Lechiffre de poids fort debcestb; le chiffre de poids faible estc.

Question 1. bcen base 3.

´ Ecrire la fonctionentier(b,cneitreocpmirestnre0et8quis’´ecrit’ltnanruoter)

1