\n Le problème du rendu de monnaie est un problème d'algorithmique. Il s'énonce de la façon suivante : étant donné un système de monnaie (pièces et billets), comment rendre une somme donnée de façon optimale, c'est-à-dire avec le nombre minimal de pièces et billets ?\n\nPar exemple, la meilleure façon de rendre 7 euros est de rendre un billet de cinq et une pièce de deux, même si d'autres façons existent (rendre 7 pièces de un euro, par exemple). On rencontre des problèmes similaires dans l'utilisation des boites à poids. \n\nSource : [Wikipedia](https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_rendu_de_monnaie)\n
⚠ Pensez à sauvegarder régulièrement votre travail (cliquez sur le bouton qui clignote en bleu en haut à gauche) ⚠
"},{"metadata":{},"cell_type":"markdown","source":"# 1. Présentation du problème\n
Quel est le nombre minimal de pièces à utiliser pour rendre une somme donnée, avec un système monétaire donné, et quelle est la répartition des pièces correspondante ?\n
"},{"metadata":{},"cell_type":"markdown","source":"## Formalisation mathématique :"},{"metadata":{},"cell_type":"markdown","source":"* Soit **V = (v1, v2, v3, …, vi, …, vn)** un n-uplet d’entiers naturels symbolisant le système de pièces (ou de billets) où **vi** représentant la valeur de la pièce **i** et tel que **v1 < v2 < v3 < … < vn** avec **v1 = 1**."},{"metadata":{},"cell_type":"markdown","source":"* Soit **S** un entier positif correspondant à la somme à rendre"},{"metadata":{},"cell_type":"markdown","source":"Il s’agit de trouver **P = (p1, p2, p3, …, pi, … pk)** un n-uplet d'entiers naturels correspondant à l’ensemble des pièces à rendre avec **pi** appartenant à **V** et tel que **p1 + p2 + p3 + … pi … + pk = S**."},{"metadata":{},"cell_type":"markdown","source":"> Exemple :\n>\n> On suppose que le nombre de chaque pièce du système de pièces est illimité et la liste des pièces est triée par ordre croissant.\n>\n> Dans la zone euro, le système monétaire actuellement en circulation est V = (1, 2, 5, 10, 20, 50, 100, 200, 500).\n> Avec les notations précédentes, on a ainsi **v1 = 1, v2 = 2, v3 = 5, ..., v9 = 500** et **n = 9**.\n>\n> Si on veut rendre les pièces pour, par exemple, une somme de S = 9 €, on doit chercher les n-uplets tels que **P = (p1, p2, p3, …, pi, … pk)** vérifiant **p1 + p2 + p3 + ... + pk = 9**.\n>\n> On peut remarquer que seules les pièces (1, 2, 5) sont utilisables car les autres pièces de V ont une valeur plus grande que la somme S à rendre.\n>\n> La contrainte devient donc **p1 + p2 + p3 + ... + pk = 9**.\n>\n> Il y a sept ensembles P qui vérifient cette contrainte : **(1,2,2,2,2)** **(2,2,5)** **(1,1,2,5)** **(1,1,1,1,1,1,1,1,1)** **(1,1,1,1,1,1,1,2)** **(1,1,1,1,1,2,2)** **(1,1,1,2,2,2)**.\n>\n> → L’ensemble qui minimise le nombre de pièces à rendre est alors la solution, il s'agit en l'occurrence ici de (2,2,5) : il faut ainsi trois pièces pour rendre une somme de 9 €, deux pièces de 2 et une pièce de 5."},{"metadata":{},"cell_type":"markdown","source":"# 2. Algorithme glouton\n
Une première approche possible du rendu de monnaie consiste à rendre la plus grande pièce possible, parmi les pièces disponibles (dans la caisse par exemple), puis faire de même avec le reste de la somme à rendre, après avoir déduit la pièce déjà rendue, jusqu'à ce que la somme totale soit rendue.
\nUn algorithme possible serait :\n \n
Choisir la plus grande pièce, du système de pièces, inférieure ou égale à la somme à rendre.
\n
Déduire cette pièce de la somme à rendre.
\n
Si la somme restante à rendre n’est pas nulle alors recommencer à l’étape 1.
\n \n Cet algorithme est dit glouton, il consiste à considérer les pièces une par une, en commençant par les pièces de plus grandes valeurs, et de décroître le montant à rendre (en enlevant la valeur de la pièce que l’on retient à chaque analyse) jusqu’à ce que le montant soit inférieur à la valeur de la pièce que l’on regarde. On considère alors la plus grande valeur de pièce inférieure au montant à rendre, et on itère le raisonnement jusqu’à ce que le montant à rendre atteigne zéro.\n
"},{"metadata":{},"cell_type":"markdown","source":"!!! abstract L'algorithme glouton (en pseudo-code) :\n\nFonction rendu_monnaie_glouton(systeme_monnaie: tableau, somme_a_rendre: entier)\n\n liste_pieces ← liste vide\n \n i ← longueur(systeme_monnaie) - 1\n \n tant que somme_a_rendre > 0\n \n valeur_piece ← systeme_monnaie[i]\n \n si somme_a_rendre < valeur_piece\n i ← i - 1\n sinon\n ajouter valeur_piece à liste_pieces\n somme_a_rendre ← somme_a_rendre - valeur_piece\n \n renvoyer liste_pieces\n \n fin pour\nFin Fonction\n!!!"},{"metadata":{},"cell_type":"markdown","source":"!!! question Travail à faire\nCompéter la fonction ci-dessous pour qu'elle renvoie la liste des pièces à rendre pour une somme déterminée.\n\nRédiger une *docstring* précise (entrées, sortie, précondition(s)).\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"def rendu_monnaie_glouton(systeme_monnaie, somme_a_rendre):\n \"\"\"\n \n \"\"\"\n # Votre code ici","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Vous pouvez faire des tests ici\n","execution_count":null,"outputs":[]},{"metadata":{"editable":false,"deletable":false,"trusted":false},"cell_type":"code","source":"# Cette cellule NE DOIT PAS ETRE modifiée\n# Test final de la fonction rebdu_monnaie\n# Si votre fonction est correcte alors aucun message d'erreur ne devrait apparaitre après l'exécution de cette cellule\n\nsysteme_monnaie = [1, 2, 5, 10, 20, 50, 100, 200]\n\nassert rendu_monnaie_glouton(systeme_monnaie, 19) == [10, 5, 2, 2]","execution_count":null,"outputs":[]},{"metadata":{"editable":false,"deletable":false,"trusted":true},"cell_type":"markdown","source":"!!! question Travail à faire\nTester l'algorithme glouton précédent sur le système monétaire `systeme_monnaie = [1, 5, 6]` pour rendre une somme égale à 10.\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"# Test ici\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"
\n\n### Question 1\n\nEst-ce la solution optimale ? Que peut-on en déduire ?"},{"metadata":{},"cell_type":"raw","source":"# Votre réponse :\n\n"},{"metadata":{},"cell_type":"markdown","source":"!!! question Travail à faire\nTester l'algorithme glouton précédent sur le système monétaire `systeme_monnaie = [2, 5, 10, 20, 50, 100, 200, 500]` pour rendre une somme égale à 21.\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"# Test ici\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"
\n\n### Question 2\n\nEst-ce la solution optimale ? Quelle est la solution optimale ? Que peut-on en déduire ?"},{"metadata":{},"cell_type":"raw","source":"# Votre réponse:\n\n"},{"metadata":{},"cell_type":"markdown","source":"# 3. Pour aller plus loin"},{"metadata":{},"cell_type":"markdown","source":"!!! info Regarder la vidéo suivante (⚠ durée 21 min) : \n[](https://www.youtube.com/watch?v=4NcrRGB3mMI \"Programmation Dynamique avec Python\")\n!!!"}],"metadata":{"kernelspec":{"name":"python3","display_name":"Python 3","language":"python"},"celltoolbar":"Éditer les Méta-Données"},"nbformat":4,"nbformat_minor":2}