Algorithme glouton et rendu de monnaie

[Winston]

Fil dérivé du débat concernant le choix des valeurs des pièces et des billets. Je le place en taverne car h16 a menacé de "grosse tarte dans ta gueule" toute personne abordant ce sujet sur son fil des 134 G$.

la question en gros : Pourquoi n'y a-t-il pas de billets de 7 euros ?

On pouvait y lire des explications mathématiques délirantes, et étant un cuistre notoire je me dois de réagir en montrant à vos yeux ébahis que je maitrise parfaitement un sujet dont le commun des mortels n'a absolument rien à foutre.

Tout d'abord il faut savoir que le système qui optimiserait le nombre de pièces ou billets à rendre est très simple et connu : emettre un titre pour chaque valeur. On aurait ainsi des billets de 93,35 € par exemple. mais ce système serait assez peu pratique à l'usage.

En fait le choix des valeurs 1, 2, 5, 10, 20, 50, 100, 200 n'est pas ancien et il n'est pas non plus universel. Aux USA on trouve par exemple des pièces de 25cts ou en Roumanie des pièces de 3 lei.

Ces valeurs ont été choisies pour faciliter le rendu de monnaie en respectant l'algorithme glouton, c'est à dire que répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante donnera forcément le résultat optimum.

Ce choix permet de trouver l'optimum à coup sûr et de manière totalement intuitive mais aussi d'automatiser le rendu de monnaie.

Par exemple si une machine doit vous rendre 37cts voici le calcul extremement simple qu'elle fera :

La plus grosse pièce qui ne dépasse pas le montant est 20, je donne 20, reste 17, la plus grosse pièces qui ne dépasse pas 17 est 10, je donne 10, reste 7, la plus grosse pièce ne dépassant pas 7 est 5, je donne 5 reste 2, la plus grosse pièce ne dépassant pas 2 est 2, je donne 2, reste 0, j'arrête de donner.

Intuitivement un humain fera la même chose.

Ce système est très simple mais cause parfois des incohérence, ainsi beaucoup de machines à café vous indiquent qu'elles ne peuvent plus vous rendre la monnaie car il n'y a plus de pièces d'une valeur particulière, alors qu'en réalité elle disposent de la somme à rendre en utilisant une autre combinaison.

Avec un autre système de valeurs, l'algorithme glouton ne serait pas forcément optimal.

Exemple avec 1, 3, 4 ,7 etc… pour rendre 6cts.

L'algorithme glouton donne 4+1+1 alors que l'optimum est 3+3. Un tel choix aurait pour conséquence de complexifier grandement l'automatisation du rendu de monnaie.

Voilà !

Vous pouvez maintenant poster des images de filles dénudées dans ce thread.

[Nick de Cusa]

[Ash]

Vous pouvez maintenant poster des images de filles dénudées dans ce thread.

Ah bin tout de même !

http://frenchcarcan.com/2009/06/02/roberta-4/

[0100011]

On notera que dans leurs premières versions les automates de la poste (pendant plusieurs années) ne rendaient que des pièces de 1 (ce qui me mettait en joie à chaque fois). Dernièrement j'ai noté une évolution, mais ils n'ont toujours pas le rendu optimal. Ca converge doucement dans l'administration française…

[A.B.]

On notera que si on a une suite de pieces supercroissante, la methode gloutonne est tjs optimale

Par exemple

5 > 2+1

10 > 5+2+1

20 > 10+5+2+1

50 > 20+10+5+2+1

100 > 50+20+10+5+2+1

200 > 100+50+20+10+5+2+1

500 > 200+100+50+20+10+5+2+1

[Rincevent]

Je viens de me rendre compte qu'une suite négative et décroissante pouvait être supercroissante. Dingue, ça.

[john_ross]

Ces valeurs ont été choisies pour faciliter le rendu de monnaie en respectant l'algorithme glouton, c'est à dire que répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante donnera forcément le résultat optimum.

Ce choix permet de trouver l'optimum à coup sûr et de manière totalement intuitive mais aussi d'automatiser le rendu de monnaie.

Par exemple si une machine doit vous rendre 37cts voici le calcul extremement simple qu'elle fera :

La plus grosse pièce qui ne dépasse pas le montant est 20, je donne 20, reste 17, la plus grosse pièces qui ne dépasse pas 17 est 10, je donne 10, reste 7, la plus grosse pièce ne dépassant pas 7 est 5, je donne 5 reste 2, la plus grosse pièce ne dépassant pas 2 est 2, je donne 2, reste 0, j'arrête de donner.

Intuitivement un humain fera la même chose.

Plus si pas de pieces de 2, allez à la piece de 1, chose qui peut aisément être programmée, pour preuve c'est souvent qu'un distrubuteur automatique m'a rendu la monnaie sur une pièce de 1 euro pour un café à 0.35 avec 50cts et 3pieces de 5 cts.

PS : je posterai plus tard une photo de femme à poil.

[A.B.]

Je viens de me rendre compte qu'une suite négative et décroissante pouvait être supercroissante. Dingue, ça.

<snip des conneries t'as raison>

[Sous-Commandant Marco]

Ah bin tout de même !

http://frenchcarcan.com/2009/06/02/roberta-4/

Roberta Pedon, la bien prénommée, hélas tragiquement et prématurément disparue.

A mon tour:

http://www.celebset.net/Petra_Verkaik_Naked/

[Drake]

la question en gros : Pourquoi n'y a-t-il pas de billets de 7 euros ?

S'il n'existe pas de billets de 7 euros, il existe en revanche des billets de 9, 45 et de 90 kyats :

Si la bêtise, la veulerie ou la duplicité de nos hommes politiques est affligeante, il est des pays où la réalité dépasse l'affliction: l'histoire de ces billets est incroyable et mérite d'être lue http://bruinskeptics.org/2008/05/26/how-as…anmars-economy/

A oui, pardon, j'oubliais : http://images.celebset.net/pics/H/Heidi%20…18194420180.jpg

[john_ross]

Chose promise chose due

http://image-serv.foxhq.com/danielle-ftv-boobage/7.jpg

[Invité jabial]

Chose promise chose due

http://image-serv.foxhq.com/danielle-ftv-boobage/7.jpg

[nerd]Je m'en fous de ça, y en a partout, je veux un exemple de suite négative, décroissante et supercroissante.[/nerd]

[Rincevent]

[nerd]Je m'en fous de ça, y en a partout, je veux un exemple de suite négative, décroissante et supercroissante.[/nerd]

U_0 = -1, U_n = -n pour n entier > 0. Suffit de revenir à la définition.

[Invité jabial]

Il me semble que pour qu'une suite soit supercroissante elle doit être croissante, non?

[Rincevent]

Il me semble que pour qu'une suite soit supercroissante elle doit être croissante, non?

Ce n'est pas dans la définition donnée par fr:WP. Ceci dit, toute suite négative croissante est supercroissante. Mieux, toute suite négative qui est "moins décroissante" qu'une suite de Fibonacci généralisée est supercroissante.

[bernard lhermitte]

On notera que si on a une suite de pieces supercroissante, la methode gloutonne est tjs optimale

Faux.

Contre-exemple :

1,10,12 est supercroissante (10>1 et 12>10+1)

Mais pourtant le rendu de 20 donne 12+1+1+1+1+1+1+1+1 avec glouton, alors qu'on peut clairement faire mieux : 10+10

Vrai si on ne peut rendre qu'au plus une pièce de chaque type…car on est alors vraiment dans le cas du pb du sac à dos (knapsack), où les différents objets ne sont pas disponibles en quantité illimitée (j'imagine que c'est de là que vient votre info).

Vérifier si un jeu de pièce donné est "canonique", c'est-à-dire si l'algo glouton est toujours optimal pour ce jeu, quelque soit la valeur à rendre, est plus délicat. Mais faisable ! Par exemple, Peason a trouvé en 1994 un algorithme qui vérifie ça en n^3 opérations (à une constante multiplicative près), où n est le nb de pièces différentes :

http://citeseer.ist.psu.edu/viewdoc/summar…=10.1.1.57.3243

[Chitah]

'Tain, le gars qui s'inscrit juste pour répondre à ce post sur les suites supercroissantes, c'est fort.

[h16]

L'internet est vaste et les nuits de novembre sont longues.

[Punu]

Je le remets car c'est le dessin le plus vrai de l'histoire de l'humanité.