Le glouton n'échoue pas au hasard

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 16 — Algorithmes gloutons

Énoncé

Le cours montre que le glouton du rendu de monnaie se trompe sur ${1, 3, 4}$ pour $S = 6$ . Pour chacun des systèmes ci-dessous, trouver la plus petite somme mal rendue : ${1, 2, 5, 10, 20, 50}$ , ${1, 5, 10, 25}$ , ${1, 7, 10}$ , ${1, 15, 25}$ , ${4, 9, 16, 25}$ .

Corrigé

On compare, pour chaque $S$ , le nombre de pièces du glouton à l'optimum calculé par une table (chapitre chap:dynamique). Mesuré :

Système	premier $S$ fautif	glouton	optimum
${1, 2, 5, 10, 20, 50}$ (euro)	aucun jusqu'à $1000$	---	---
${1, 5, 10, 25}$ (dollar)	aucun jusqu'à $1000$	---	---
${1, 3, 4}$	$6$	3 pièces	2 pièces
${1, 7, 10}$	$14$	5 pièces	2 pièces ( $7 + 7$ )
${1, 15, 25}$	$30$	6 pièces	2 pièces ( $15 + 15$ )
${4, 9, 16, 25}$	$12$	échec total	3 pièces ( $4 + 4 + 4$ )

Le cas ${4, 9, 16, 25}$ est le plus instructif : pour $S = 12$ , le glouton prend $9$ , il reste $3$ , et aucune pièce ne tient. Il ne rend pas une réponse trop grande : il ne rend rien du tout, alors qu'une solution existe. Sans pièce de $1$ , un glouton peut être bloqué. Un programme écrit sans y penser bouclera, ou lèvera une exception, sur une entrée parfaitement légitime.

Combien de sommes sont mal rendues, pour $S \leq 1000$ :

Système	sommes fautives	pire écart
${1, 3, 4}$	249	1 pièce
${1, 7, 10}$	297	3 pièces (à $S = 14$ )
${1, 15, 25}$	585	8 pièces (à $S = 60$ )
${1, 2, 5, 10, 20, 50}$	0	---
${1, 5, 10, 25}$	0	---

Sur ${1, 15, 25}$ , le glouton se trompe plus d'une fois sur deux, et peut rendre neuf pièces là où deux suffisent.

Ce que cela enseigne. Les deux systèmes monétaires réels sont canoniques : le glouton y est exact, et ce n'est pas un accident — leurs valeurs ont été choisies pour cela. Mais l'optimalité du glouton est une propriété du système, pas de la méthode. Un glouton essayé sur les pièces qu'on a dans la poche paraîtra toujours correct, et c'est précisément le piège que le chapitre annonce. Le problème 16.5 donne le critère qui tranche.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.