Exercice 3 — Algorithme glouton — Olympiades 2013 Rouen et AEFE Afrique occidentale

Sujet

Dans une majorité de pays, on utilise des pièces de 1 unité, $2,5,10,20,50,100$ unités, etc. Certains pays comme les États-Unis ont mis en circulation des pièces de 25 unités. Des pièces de 3 roubles, 3 kopecks (russes) et 3 banis (roumains) ont aussi existé.
En fonction des pièces disponibles, un système monétaire est plus ou moins efficace. Un jeu de pièce sera dit efficace si, en moyenne, le nombre de pièces pour rendre la monnaie est petit.
On représentera le jeu de pièces d'une région par une liste (en centimes) : pour l'Europe, la liste des pièces est $[200,100,50,20,10,5,2,1]$.
On note $\operatorname{Eff}(x)$ le nombre minimum de pièces nécessaires pour obtenir $x$ centimes avec les pièces dont on dispose.

Déterminer $\operatorname{Eff}(47)$ et $\operatorname{Eff}(39)$.
On considère l'algorithme suivant

Saisir $P$

Affecter à C la valeur 0
Pour $k$ allant de 1 à 8
Tant que $P-\operatorname{liste}(k) \geqslant 0$
Affecter à $P$ la valeur $P-\operatorname{liste}(k)$
Affecter à $C$ la valeur $C+1$
FinTantque
FinPour Afficher $C$
On suppose que la liste $[200,100,50,20,10,5,2,1]$ a été préalablement enregistrée.
L'instruction « liste $(k)$ » renvoie alors le k-ième élément de la liste contenant les valeurs des pièces.
Par exemple : liste $(3)=50$, liste $(8)=1$.
a) Qu'affiche cet algorithme si on prend $P=98$ ?
b) Interpréter ce résultat.
3. Afin d'évaluer l'efficacité d'un jeu de pièces dans une région, on définit l'efficacité moyenne $E f f_{\text {moy }}(X)$ comme le nombre moyen de pièces qu'il faut pour composer les sommes de 0 unité, 1 unité, . . . jusqu'à $X-1$ unités.

\[ E f f_{m o y}(X)=\frac{E f f(0)+E f f(1)+\cdots+E f f(X-1)}{X} \]

a) Pour le système européen on prendra $X=500$, car cette somme et celles supérieures peuvent être payées avec le plus petit billet, celui de 5 euros. Proposer une modification de l'algorithme précédent qui permettrait de déterminer le nombre moyen de pièces nécessaires pour rendre la monnaie en Europe.

b) Pour les États-Unis, la liste des pièces disponibles est [100, 25, 10, 5, 1] et le plus petit billet est celui de $1 \$$.

En supposant que l'on ait maintenant enregistré la liste des pièces américaines, que suffit-il de modifier dans l'algorithme de la question précédente pour déterminer le nombre moyen de pièces pour rendre la monnaie aux États-Unis?

Remarque : En programmant ces algorithmes, on obtient que le nombre moyen de pièces est de 4,6 en Europe contre 4,7 aux États-Unis.

Eff $(47)=4$ et Eff $(39)=5$.
a) Si on prend $P=98$, l'algorithme affiche 6 .
b) L'algorithme calcule Eff ( $P$ ), où $P$ est la somme à décomposer. Il faut donc au minimum 6 pièces parmi celles dont on dispose pour obtenir 98 centimes.
a) Pour le système européen (par exemple) :

Affecter à C la valeur 0
Pour P allant de 0 à 499
    Pour k allant de 1 à 8
        Tant que P - liste (k) \geqslant0
        Affecter à P la valeur P-liste(k)
        Affecter à C la valeur C+1
        FinTantque
    FinPour
FinPour Affecter à C la valeur C/500 Afficher C

b) Pour le système américain :

Affecter à C la valeur 0
Pour P allant de 0 à 99
    Pour k allant de 1 à 5
        Tant que P - liste (k) \geqslant0
        Affecter à P la valeur P-liste(k)
        Affecter à C la valeur C+1
        FinTantque
    FinPour
FinPour
Affecter à C la valeur C/100
Afficher C

Exercice 3 — Algorithme glouton

Sujet

Saisir \(P\)