Le glouton n'échoue pas au hasard

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 six pièces là où deux suffisent ( $S = 30$ ).

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.

Énoncé

Corrigé

Exercices semblables