Polytechnique X 2004 epreuve facultative 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: 111
• Langue: Français

Extrait

É COLEPOLYTECHNIQU É ECOLESUP É RIEUREDEPHYSIQUEETCHIMIE

CONCOURS 2004

INDUSTRIELLES

I È RE MP -FIL OPTION PHYSIQUE ET SCIENCES DE L’INGÉNIEUR

COMPOSITION D’INFORMATIQUE (Durée : 2 heures)

PC FILI È RE

L’utilisation des calculatricesn’est pas autoriséepour cette épreuve. Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.

⋆ ⋆ ⋆

Compressionternaire

On attachera une grande importance à la concision, à la clarté, et à la précision de la rédaction. On supposera que le langage de programmation utilisé possède deux opérationsxdivyetxmody donnant le quotient et le reste de la division euclidienne dexpary.

Le temps d’exécutionT(f) d’une fonctionfest le nombre d’opérations élémentaires (addi- tion, soustraction, multiplication, division, affectation, etc.) nécessaire au calcul def. Lorsque ce temps d’exécution dépend d’un paramètren, il sera notéT n (f). On dit que la fonctionf s’exécute :

en temps linéraire enn, 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

En base 3, les entiers 0, 1, 2, 3, 4, 5, 6, 7, 8 sont représentés par00,01,02,10,11,12,20, 21,22. Le chiffre de poids fort debcestb; le chiffre de poids faible estc.

Question 1. bcen base 3.

É crirelafonctionentier(b,c) retournant l’entier compris entre 0 et 8 qui s’écrit

1