De la nécéssité de ne plus inventer la pièce de 62 cts mais celles de 3 et 4 cts

Vous avez raté le début ?

Quatrième question : Comment je fais pour payer 2,98€ avec mon jeu de 1c, 6cts, 14cts, 62 cts, 99cts, et 1,40€ ?
Et voilà le gros problème de notre nouveau système : il ne suffit pas d'être doué en calcul mental, il faut aussi être un ordinateur capable de tester toutes les combinaisons donnant la somme voulue.
Comment feriez-vous pour payer cette somme de 2,98€ ? Et bien, vous utiliseriez l'algorithme glouton, c'est à dire, prendre la plus grande pièce possible, puis faire la soustraction :
298 = 140+140+14+1+1+1+1 : 7 pièces
Pourtant, on peut faire cette même somme avec 4 pièces :
298 = 99+99+99+1

Un exemple plus simple : payer 18€ avec des pièces de 1, 6 et 14€
L'algorithme glouton donne 5 pièces : 18=14+1+1+1+1
Alors qu'une simple réflexion donne 3 pièces : 18=6+6+6

Le jeu de pièce optimal calculé plus tôt est malheureusement basé sur le principe que les usagers doivent posséder un ordinateur interne pour rendre la monnaie avec le minimum de pièces...

Cinquième question : Quel est le meilleur jeu de pièces, alors ?
Pour celà, on va appeler effmoy_gl(298,[1,6,14,62,99,140]) le nombre de pièces à donner pour payer 298 cts avec le jeu de pièces [1,6,14,62,99,140], et effmoy_gl(500,[1,6,14,62,99,140]) le nombre moyen de pièces à payer pour payer une somme entre 1cts et 500cts avec le jeu de pièces  [1,6,14,62,99,140].
Bref, après un temps de calcul moins long, on trouve :
effmoygl(500,[1,6,14,62,99,140])=5,992 (Ce qui est quand même moins bon que les 4,67 pièces quand on cherche la décomposition optimale)

Le palmarès des meilleurs jeux de pièce, en considérant l'algorithme glouton, est donc celui-ci :
Pour les sommes entre 1 et 499 centimes :
* 4 pièces, les gagnants sont...
[1,5,23,109]* et [1,5,23,110]* (7,1 pièces en moyenne)
* 5 pièces, les gagnants sont...
[1,4,13,44,147], [1,4,13,44,150]*, [1,4,14,47,160]* et [1,4,14,48,160]* (5,8 pièces en moyenne)
* 6 pièces, les gagnants sont...
[1,3,8,26,64,202], [1,3,8,26,64,203], [1,3,8,26,64,204], [1,3,10,25,79,195], [1,3,10,25,79,196] et [1,3,10,25,79,197] (5,4 pièces en moyenne)

Notre actuel jeu de pièces [1,2,5,10,20,50,100,200]* donne 4,6 pièces en moyenne

(A noter que pour les jeux de pièces avec un *, l'algorithme glouton donne toujours la meilleure décomposition)

Sixième question : C'est quoi cette fonction effmoy_gl de $£¤µ% ?????
Je vous l'accord, cette fonction se base sur un très mauvais principe : celui que toutes les sommes payables sont réparties équitablement, ce qui n'est pas tout à fait vrai (pas du tout vrai, en fait)
Les gens suivant activement ce blog se rappelle très bien la loi de Benford, qui régit également les prix affichés dans les magasins (A une certaine échelle). Autre chose à prendre également en compte : l'euro a étrangement fait monter les prix, puisqu'ils terminent très souvent par des 0 ou des 5...
Beaucoup de choses à prendre en compte finalement... Et ma flemme m'empêche de le programmer...

Septième question : Ouais, mais bon...
Malgré toute la bonne volonté du monde, il y a peu de chances de voir un jour adapté en pièces ces jeux de pièces mathématiquement parfaits... Pourquoi ? Parce que le monde n'est pas prêt à faire tous les jours des calculs avec des soustractions à retenues...
Il y a un seul moyen de résoudre ce problème : que les calculs de rendus se fassent en procdédant chiffres par chiffre. D'abord les unités, puis les dizaines, puis les centaines...
Le problème se ramène donc à chercher le jeu de pièce le plus performant sur les sommes de 1 à 9 centimes, on prendra ensuite les pièces de dizaines et centaines correspondantes.
Avec une répartition équilibrée des sommes de 1 à 9 centimes, on trouve, pour notre jeu actuel :
effmoy(10,[1,2,5])=1.7 pièces par chiffres
Notre système est donc plutôt correct, mais le meilleur est le système [1,3,4], avec effmoy(10,[1,3,4])=1.6 pièces par chiffres.

(A noter que le système [1,2,5] est à égalité avec les sytsèmes [1,4,6], [1,4,5], [1,2,7], [1,2,6], [1,2,4], [1,3,8], [1,3,7], [1,3,6] et [1,3,5]. Le pire est évidemment [1,8,9])

S'il y a une réforme faisable, ça serait de changer notre jeu de pièces actuel contre [1,3,4,30,40,300,400,...] ! C'est la banque centrale qui serait contente, puisque cela voudrait dire moins de pièces à imprimer...

Et si on considère notre amie la loi de Benford, on découvre que le système [1,3,4] est meilleur que [1,2,5]...

Il y a évidemment une mise en garde, puisque notre faux-amis l'algorithme glouton n'aime pas trop ce système, à cause de 6.
Avec l'algorithme glouton, on a 6=4+1+1 (3 pièces)
Sans cet algorithme, on a 6=3+3 (2 pièces)
Mais pour un seul contre exemple plutôt facile à contourner, on ne va quand même pas cracher sur cette révolution monétaire, non !?

Huitième question : Ben alors, on change quand de monnaie ?
Je proposerai bien maintenant, mais il semble que Roland Yéléhada ait une petite réserve à émettre :
"C'est bien joli, tout ça, mais la loi de Benford, elle s'applique beaucoup plus aux phénomènes naturels qu'aux phénomènes humains ! En Europe, on aime bien les prix ronds, avec plein de 0 et de 5 !..."
Et ben en fait, il a part tord, l'ami Roland... [1,3,4] est meilleur pour les répartitions équiprobables et selon la loi de Benford des chiffres, mais se fait dépasser en efficacité quand on considère une grande probabilité de présence de 5 et de 0. Par "grande probabilité", on entend "que la présence de 5 ou de 0 ait une fréquence de plus de 33,33%".

Seulement, et juste pour contredire Roland, parlons de nos non-amis les publicitaires, qui se font un plaisir de vendre des choses à 9,99€. Et bien, le jeu de pièces [1,3,4,10,30,40,100,300,400, ...] serait quand même plus efficace...

Et pour ceux qui disent qu'il vaut mieux payer avec un billet de 10€ une somme de 9,99€, ils seront heureux d'apprendre qu'ils pourront toujours le faire facilement !

Pour moi, il n'y a qu'une seule chose à faire pour rendre l'Europe meilleure : votons les pièces de 3, 4, 30 et 40 centimes !

(Et pour ceux qui douteraient de la nécessité de tous ces calculs, il faut quand même savoir qu'ils ont une vraie utilité pour les banques émetrices, celle de décider le nombre pièces de chaque types à imprimer, selon leur fréquences relatives...)

---

Sources :
Toujours Pour la science, n°335, septembre 2005
et toujours mes petits programmes en Isetl

Comments

[2PetitsVerres]

Il faudrait également envisager la possibilité de pièces à valeur faciales négatives, ça pourrait peut-être rendre le tout encore plus efficace, non ?

[Phoenixx]

C'est pas mal tout ça mais comme aujourd'hui j'ai un esprit de contradicition, je veux te signaler que je crois qu'on ne dit pas imprimer des pièces, mais frapper des pièces ... Voilà, c'était la petite parenthèse "je fais chier le monde" ^^ Sinon, très intéressantes ces deux notes, heureusement que t'es là pour écrire ce à quoi on ne penserait même pas !

[Whiteshoulders]

Faudra aussi voir a considerer l'aspect culturel de la chose, le fait qu'on ai 5 doigts a chaque mains, tout ça. Parce que si on avait eut 3 doigts a une main et 4 a l'autre, je dit pas (et encore, ça serait pas 10, 30, 40 mais 7, 21 et 28)(nombres qui ne se seraient certainement pas appelé comme ça en plus)

[Tipierre]

Ouais, mais toutes ces pieces ne sont pas des diviseurs de 100, contrairement à notre actuel jeu de pièces... Ce qui complique les calculs...