L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.
On attachera une grande importance à la clarté, à la précision et à la concision de la rédaction.

Dans tout le problème un système monétaire est un ensemble de

entiers naturels non-nuls distincts

, avec

. Les

sont les dénominations du système. Par convention, les dénominations sont présentées par ordre décroissant. Par exemple, le système de l'euro est l'ensemble

Une somme (d'argent) est une suite finie

d'entiers appartenant à

. Les éléments de cette suite sont des espèces. On remarquera bien que deux espèces d'une somme peuvent porter la même dénomination, qu'une somme peut être vide, et qu'il n'y a pas nécessairement d'espèces de dénomination 1 dans une somme. Par convention, les espèces sont présentées par ordre de dénominations décroissantes.

La valeur d'une somme

, notée

, est tout simplement la somme arithmétique de ses espèces, tandis que sa taille, notée

, est le nombre de ses éléments (l'entier

ci-dessus). Étant donné un entier naturel

, une somme de valeur

est un représentant de

. Par exemple, le portefeuille d'un citoyen européen peut contenir 3 billets de 10 euros, deux billets de 5 euros et une pièce de 1 euro. Cette somme est notée

, sa valeur est 41 et sa taille 6 .

Une somme

est extraite d'une autre

dite portefeuille, si et seulement si

est une suite extraite de

. Intuitivement, « la somme

est extraite de

» signifie que l'on paye sa valeur à l'aide d'espèces prises dans le portefeuille

. Par exemple, notre citoyen européen peut payer exactement 15 euros en extrayant un billet de 10 euros et un autre de 5 euros de son portefeuille.

Programmation. Dans les deux premières parties du problème, les systèmes monétaires et les sommes sont représentés en machine par des listes d'entiers.

    (* Caml *)
type systeme == int list ;;
type somme == int list ;;

tvp
type
    liste = `cellule ;
    cellule = record
        contenu : integer ; suivant : liste ;
    end ;
    systeme = liste ;
    somme = liste ;

En outre, on supposera (pour les arguments) et on garantira (pour les résultats) les propriétés suivantes :

tous les entiers présents dans les listes sont strictement positifs;
toutes les listes sont triées en ordre décroissant;
les listes de type systeme contiennent des entiers distincts ; leur dernier élément est 1.

En Pascal, la liste vide est nil et l'on pourra pour construire les listes utiliser la fonction suivante :

function cons(contenu : integer ; suivant : liste) : liste ;
var r : liste ;
begin
    new(r) ;
    r^.contenu := contenu ;
    r^.suivant := suivant ;
    cons := r
end ;

Cette fonction est applicable pour construire les listes des deux types somme et systeme.

Question 1. Écrire la fonction valeur qui prend une somme en argument et renvoie sa valeur.

    (* Caml *) { Pascal }
valeur : somme -> int | function valeur(s:somme) : integer ;

I. Payer le compte exact.

Dans cette partie on considère le problème du paiement exact. Dans les termes du préambule, cela revient, étant donné un entier naturel

, à trouver un représentant de

Une démarche possible pour payer exactement le prix

est la démarche dite gloutonne, que l'on peut décrire informellement ainsi :

donner l'espèce la plus élevée possible - c'est à dire de la plus grande dénomination disponible et telle que ;
recommencer en enlevant l'espèce donnée au prix à payer - c'est dire poser égal à .

Évidemment, le processus s'arrête lorsque le prix initial est entièrement payé.

Question 2. Dans cette question, on suppose que l'acheteur dispose toujours des espèces dont il a besoin.
a) Montrer que la démarche gloutonne réussit toujours.
b) Écrire une fonction glouton qui prend en argument un système monétaire sys et un prix à payer p et renvoie la liste des espèces à utiliser pour payer. La sommme renvoyée sera calculée en suivant la démarche gloutonne.

    (* Caml *)
glouton : systeme -> int -> somme

        { Pascal }
function glouton
    (sys:systeme ; p:integer):somme ;

Question 3. On tient cette fois compte des ressources de l'acheteur. Dans les termes du préambule cela revient à trouver une somme ayant pour valeur le prix à payer et extraite d'une somme donnée, dite portefeuille.
a) Montrer, à l'aide d'un exemple utilisant le système européen, que la stratégie gloutonne peut échouer pour un prix donné, même si il est possible de payer compte tenu des ressources disponibles.
b) Écrire une fonction paye_glouton qui prend en argument une somme pf, représentant le contenu du portefeuille, ainsi qu'un prix

; et qui renvoie une somme extraite de pf et dont la valeur est p. La somme renvoyée sera calculée en suivant la démarche gloutonne, si cette démarche échoue, la fonction paye_glouton doit renvoyer la liste vide.

    (* Caml *)
paye_glouton : somme -> int -> somme

        { Pascal }
function paye_glouton
    (pf:somme ; p:integer):somme ;

Question 4. Écrire une fonction compte_paiements qui prend en arguments un portefeuille pf et un prix

; et qui renvoie le nombre de façons de payer

à l'aide des espèces de pf. Autrement dit cette fonction renvoie le cardinal de l'ensemble des représentants de

extraits de pf.

    (* Caml *)
compte_paiements : somme -> int -> int

        { Pascal }
function compte_paiements
    (pf:somme ; p:integer):integer ;

Remarque. Deux espèces de même dénomination sont distinguées. Ainsi, si le portefeuille est

et le prix 2, alors il y a trois façons de payer.

II. Payer le compte exact et optimal.

Une somme est optimale lorsque sa taille est minimale parmi un ensemble de sommes de valeur donnée. Par exemple, la somme

montre que le portefeuille de notre citoyen européen (

) n'est pas optimal parmi les sommes de valeur 41 . En effet, la taille de

est 3 et elle est strictement inférieure à la taille de

Dans cette partie un portefeuille

est fixé. Pour tout entier naturel

, on pose

égal à un représentant de

optimal parmi les représentants de

extraits de

, si une telle somme existe; ou la somme vide, si une telle somme n'existe pas. Le but de cette partie est la détermination de

Question 5. Le but de cette question préalable est de préciser quelques opérations sur les sommes.
a) Soit une somme

comprenant

espèces de dénomination

, on définit l'ajout de

, noté

, comme la somme qui comprend

espèces de dénomination

et qui est inchangée autrement. Écrire la fonction ajoute qui prend en arguments une somme

et une dénomination d et qui renvoie la liste représentant l'ajout de d à s.

    (* Caml *)
ajoute : somme -> int -> somme

        { Pascal }
function ajoute
    (s:somme ; d:integer):somme ;

b) On définit la différence de deux sommes

, notée

, comme suit. Pour toute dénomination

, soit

le nombre d'espèces de dénomination

comprises dans

le nombre d'espèces de dénominations

comprises dans

si , alors comprend espèces de dénomination ;
sinon, ne comprend aucune espèce de dénomination .

Écrire la fonction diff qui prend deux sommes en arguments et renvoie leur différence.

    (* Caml *)
diff : somme -> somme -> somme

    { Pascal }
function diff(s,t:somme):somme ;

Question 6. Soit

un entier naturel. On note

l'ensemble des entiers naturels

, tels que la somme

est de taille

. On définit également une suite de fonctions

où la fonction

est la restriction à

de la fonction

Déterminer

dans le cas du portefeuille européen

et pour

égal à 0,1 et 2 .

Question 7. On suppose donné un tableau global de sommes, tab, de taille suffisante (cette condition est précisée par la suite) et dont chaque case vaut initialement la liste vide.

Pour un entier

donné, on encode simultanément l'ensemble

et la fonction

de la façon suivante:

une liste d'entiers représente ;
si est défini, alors la case d'indice de tab contient . Sinon, la case d'indice de tab n'existe pas ou contient la liste vide.
a) Écrire la fonction etape qui prend en arguments, un portefeuille , un prix à payer et une liste d'entiers représentant l'ensemble , et qui renvoie une liste d'entiers représentant . On supposera en outre que le tableau tab encode avant l'appel de la fonction etape et on demande que le tableau tab encode au retour de la fonction etape.

            (* Caml *)
etape :
    somme -> int -> int list
        -> int list

        { Pascal }
function etape
    (pf:somme ; p:integer ; ti:liste):liste ;

On notera :

les listes représentant et ne sont pas nécessairement triées;
la condition « tab est de taille suffisante » est précisée : le tableau tab est supposé tel qu'il existe bien des cases d'indice , pour inférieur ou égal à p .
b) En déduire une fonction optimal qui prend en argument un portefeuille pf et un prix et qui renvoie une somme optimale de valeur et dont les espèces sont extraites de pf. Si il n'est pas possible de faire l'appoint, la fonction optimal renverra la liste vide.

    (* Caml *)
optimal : somme -> int -> somme

    { Pascal }
function optimal(pf:somme ; p:integer):somme ;

III. Étude des systèmes monétaires.

Un système monétaire est dit canonique, lorsque la stratégie gloutonne sans limitation de ressources (cf. question ??) appliquée à tout prix

produit une somme optimale parmi les représentants de

Question 8. Montrer que l'ancien système britannique

n'est pas canonique.
Le but de cette partie est de produire un programme qui décide si un système monétaire est canonique. Dans cette étude on fixe un système monétaire

dénominations, représenté cette fois par le vecteur
de

entiers naturels

. Une somme

sera également représentée par un vecteur de

entiers naturels,

, mais

est cette fois le nombre d'espèces de dénomination

présentes dans la somme

Ainsi le système européen est le vecteur

et le portefeuille du citoyen est le vecteur (

). Les définitions (et les notations) de la valeur et de la taille sont inchangées :

Par ailleurs les sommes sont ordonnées (totalement) selon l'ordre lexicographique, noté

et défini ainsi : pour tous vecteurs

, on a

si et seulement si :

il existe , tel que ;
et, pour tout , on a .

Ainsi on a par exemple

. On note

la relation d'ordre définie par

, si et seulement si

On définit un second ordre total sur l'ensemble des sommes, noté

, de la façon suivante :

Les relations d'ordre introduites permettent les définitions suivantes des représentants gloutons et optimaux (il n'est pas demandé de comparer ces nouvelles définitions aux anciennes). Étant donné un entier naturel

, le représentant glouton de

, noté

est le plus grand selon l'ordre lexicographique

des représentants de

. Tandis que le représentant optimal de

, noté

, est le plus grand selon l'ordre

des représentants de

Dès lors le système

est canonique, si et seulement si on a

pour tout entier naturel

. En revanche,

n'est pas canonique, si et seulement si il existe un ou des entiers naturels

, dits contreexemples, tels que

, c'est à dire tels que

Programmation. Dans cette partie on considère l'entier

(nombre de dénominations du système monétaire) fixé. Les systèmes monétaires et les sommes sont représentées en machine par des tableaux d'entiers.

Caml

let

int

type tsysteme

int vect

;
type tsomme

int vect

;

        { Pascal }
const
    n = ... ;
type
    tsysteme = array [1..n] of integer ;
    tsomme = array [1..n] of integer ;

(En Caml, on supposera ces tableaux de taille

, de sorte que les indices des tableaux correspondent à ceux des vecteurs.)

Question 9. Écrire la fonction tglouton qui prend en argument un système monétaire sys selon le nouveau type et un prix p et qui renvoie le représentant glouton de ce prix. Le coût de tglouton (c'est-à-dire le nombre maximum d'instructions élémentaires utilisées lors d'un appel à tglouton) doit être linéaire en

        (* Caml *)
tglouton :
    tsysteme -> int -> tsomme

            { Pascal }
function tglouton
    (sys:tsysteme ; p:integer) : tsomme;

Question 10.

a) Montrer que

entraîne

Soit

, indice, avec

. On pose

égal à la somme composée d'une seule espèce de dénomination

. Soit encore

, entier naturel.
b) On suppose que

comprend au moins une espèce de dénomination

. Montrer qu'alors on a

. (Le deuxième

ci-dessus est la différence des sommes, que l'on peut simplement voir comme la soustraction appliquée aux vecteurs et définie composante par composante.)
c) De même, si

est tel que

comprend au moins une espèce de dénomination

, montrer que l'on a alors

Question 11. Dans cette question on suppose le système monétaire

non-canonique et on considère le contre-exemple minimal

, c'est à dire l'entier

tel que :

et donc
et, pour tout entier .

On note

. Soient encore

l'indice minimal tel que

l'indice maximal tel que

.
a) On note

. Montrer qu'il n'existe pas d'indice

, tel que

.
b) Montrer que l'on a

.
c) Montrer que l'on a

Question 12. Toujours en supposant le système

non-canonique et en conservant les définitions et notations de la question précédente, on admet l'encadrement suivant (qui cette fois s'applique aux sommes) :

a) Montrer que cet encadrement permet de connaître les composantes de

en fonction de celles de

, en supposant

connus.
b) Écrire une fonction canonique, qui prend en argument un système monétaire sys et décide si ce système est canonique.

Caml Pascal

canonique : tsysteme bool function canonique(sys:tsysteme) : boolean

Le coût de canonique doit être en

.
c) Montrer que le système européen est canonique.

Caml	Pascal
canonique : tsysteme bool	function canonique(sys:tsysteme) : boolean