CCSE 2002 informatique classe prepa mp

Description

Concours Centrale - Supéiec 2002 Filière INFORMATIQUE MP * Si 15 i SIIL, c i désigne le 171 -uplet dont toutes les composantes sont nulles sauf la i -ème qui vaut I . Formalisation du problème : un nz -uplet dentiers vérifiant C, > c- > > c,,, = I Soif c = Cc., 1, - 2 c ,>i Nous utiliserons le terme système pour désigner un tel In -uplet. Les c, sont les valeurs faciales des pièces en service. Par exemple, le système utilisé en zone Euro est (200. IOO. 50. 20. 10. 5. 2. 1 ) Pour chaque, i E 11 I. nlj] , nous disposons d’une quantité’ illimit4e de pièces de valeur cc,). Soit x un entier (le montant ù rendre). Une représentation de x dans le système c est un In -uplet k = (k,. . k,,,) u&ifiant : I?i “Y = k,c, = k c c /=I k, est donc le nombre de pièces (cl) qui seront rendues. Pour épargner les poches des clients, nous souhaitons minimiser le poids de cette représentation, c’est-à-dire la quantité: 17) llkl = c k; = k 1 , ,=/ avec I = ( I. . . . . I ) (le rn -uplet dont toutes composantes sont égales à I ). Partie I - Systèmes de pièces ? - g sont les uniques entiers relatifs vérifiant entière supbricwre : ce Note à l’attention des candidats qui ont choisi le langage Caml L.x]5x<..xj-t 1 ei ,.Y 1 c .Y s .Y i c i [/ 11. CI 11 désigne l’ensemble des entiers relatifs compris 4 * si p.qEZ avecp5r/, Nous utiliserons des listes déntiers pour représenter aussi bien un système (liste entre p et C[ : I[ 1’. q 11 = ; 1’. q] n z de L>aleurs de pièces) ...

Informations

• Publié par: aiolos
• Nombre de lectures: 158
• Langue: Français

Extrait