- En cours de remplissage
- Lue
- Réponse
Problème du rendu de monnaie
Avec quelques sortes de pièces, comment payer un montant exact avec le moins de pièces possible, et de combien de façons peut-on le faire ? La réponse gloutonne, la plus grande pièce d'abord, marche pour la vraie monnaie mais échoue pour certains jeux de pièces. Un tableau qui construit chaque montant à partir de plus petits trouve toujours la bonne réponse. Touchez une pièce du plateau pour la poser sur le comptoir, et touchez une pièce sur le comptoir pour la reprendre. La jauge se remplit jusqu'au montant : faites-le exactement, avec le moins de pièces possible. Minimum de pièces montre la meilleure réponse, et Glouton montre ce que l'on obtient en prenant toujours la plus grande pièce qui rentre, ce qui ne donne pas toujours le minimum. Modifiez les pièces (en centimes) et le montant dans le panneau. La vue Tableau montre comment la programmation dynamique trouve le minimum de pièces, ou compte le nombre de façons de faire le montant : appuyez sur Lecture pour voir le tableau se remplir, ou sur Étape et Retour pour avancer pas à pas, et faites glisser le curseur des étapes pour aller n'importe où. Chaque pièce peut servir autant de fois que vous le voulez. Quand le tableau est sélectionné, les flèches avancent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.
Comment ça marche
- Touchez les pièces du plateau pour former exactement le montant, et regardez la jauge se remplir en cents.
- Essayez d'utiliser le moins de pièces possible, puis appuyez sur Minimum de pièces ou Glouton pour comparer.
- Ouvrez la vue Tableau et appuyez sur Lecture pour voir chaque case lire le montant plus petit dont elle dépend.
Minimum de pièces
Le montant 0 ne demande aucune pièce. Pour chaque montant plus grand, essayez chaque pièce qui ne le dépasse pas : ce qui reste après cette pièce est un montant plus petit, déjà dans le tableau, donc une pièce de plus donne un candidat. Le plus petit candidat va dans la case, et la pièce qui l'a donné est gardée dans la ligne du dessous. Quand le tableau est plein, on relit les pièces à partir de la cible : prenez sa dernière pièce, allez au montant qui reste, et recommencez jusqu'à 0.
Nombre de façons
Pour compter des combinaisons plutôt que des ordres, le tableau ajoute une pièce par ligne. Une case compte les façons de faire son montant avec les pièces jusqu'à sa ligne : les façons sans la pièce la plus récente, c'est-à-dire la case du dessus, plus les façons qui utilisent la pièce la plus récente au moins une fois, c'est-à-dire la case située autant de colonnes plus à gauche sur la même ligne. Comme les pièces sont ajoutées dans un ordre fixe, 1 + 2 et 2 + 1 sont la même façon et ne sont comptées qu'une fois.
Questions fréquemment posées
Pourquoi la méthode gloutonne échoue-t-elle ?
L'algorithme glouton prend toujours la plus grande pièce qui rentre et ne revient jamais sur son choix. Avec les pièces 1, 3 et 4 et un montant de 6, il prend 4, puis 1 et 1 : trois pièces, alors que deux pièces de 3 suffiraient. Pour des systèmes de pièces comme l'euro ou le dollar américain, le glouton se trouve être optimal ; on dit que ces systèmes sont canoniques.
Quelle est la différence entre compter les façons et compter les ordres ?
Les façons traitent 1 + 2 et 2 + 1 comme la même combinaison ; les ordres les comptent séparément. L'application compte les façons, en ajoutant les pièces une ligne à la fois. Pour compter plutôt les ordres, on parcourt les montants et on essaie chaque pièce pour chacun.
Quelle est la rapidité de l'algorithme du rendu de monnaie ?
Les deux tableaux demandent le nombre de sortes de pièces multiplié par le montant, en nombre d'étapes. C'est rapide pour des montants de quelques milliers, mais un montant peut être un nombre énorme ; mesuré en nombre de chiffres, le problème est donc NP-difficile en général.
Et si un montant est impossible à faire ?
Sa case reste à ∞, par exemple pour les montants 1 et 3 avec les pièces 2 et 5. En mode Nombre de façons, son nombre vaut simplement 0.
Des données sont-elles envoyées quelque part ?
Non. Tout est calculé dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur