[PDF] [PDF] Programmation dynamique – Rendu de monnaie

View - Download [PDF] Programmation dynamique – Rendu de monnaie

Previous PDF

Next PDF

NSI Lycée Louis de Foix

Programmation dynamique

- Rendu de monnaie

Énoncé du problème

É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 ? Le système de monnaie peut être identifiée à une liste croissante de n nombre, ou un tableau : monnaie = [1, 2, 5, 10, 20, 50, 100, 200, 500] pour la zone euro si on ne tient pas compte des centimes. On souhaite écrire une fonction rendu prenant en argument la liste monnaie et un entier s, correspondant

à la somme d"argent à rendre, et renvoyant un tableau de longueur n indiquant le nombre de pièces ou

billets à rendre de chaque sorte. Ainsi, rendu([1, 2, 5], 9) renverra [0, 2, 1].

Algorithme glouton On rend toujours la pièce ou le billet de valeur maximal (tant qu'on ne dépasse pas la somme à rendre).

Cet algorithme

glouton est la méthode employée en pratique, car il renvoie la solution optimale avec les systèmes de monnaie généralement utilisés dans le monde. Ces systèmes sont dit s canoniques. L e système de l"euro est canonique. Pour rendre 6 €, on rend un billet de 5 € et une pièce de 1 €.

Avec un système de monnaie (1, 3, 4), pour rendre 6, l"algorithme glouton rend 4, puis 1, puis 1, soit 3

pièces, alors que la solution optimale est de rendre deux pièces de 3.

1. Programmer la fonction rendu_glouton(monnaie, s) qui renvoie une solution au problème de rendu de

monnaie en utilisant l"algorithme glouton.

Programmation dynamique

Deux approches permettent de résoudre le problème du rendu de monnaie par programmation dynamique.

Exemple : monnaie = (1, 2, 5) et s = 13

Première approche

On trouve une solution optimale pour chaque somme d"argent de 0 à s.

En effet, si on connait les façons optimales de rendre toute somme d"argent strictement inférieure à s,

alors pour rendre une somme s, on rend une pièce, à choisir dans la liste monnaie, et une somme strictement inférieure à s, ce qui correspond à un probl ème déjà résolu. Ainsi, on trouve la solution optimale avec une somme s en comparant les n solutions pour chaque pièce de la liste monnaie. On remplit le tableau par colonne. On peut noter directement les solutions dans le tableau. monnaie\somme 0 1 2 3 4 5 6 7 8 9 10 11 12 13

1 0 1 0 1 0 0 1 0 1 0 0 1 0 1

2 0 0 1 1 2 0 0 1 1 2 0 0 1 1

5 0 0 0 0 0

1 1 1 1 1 2 2 2 2

Total 0 1 1 2 2 1 2 2 3 3 2 3 3 4

Si on ne

recherche pas la composition du rendu de monnaie mais juste le nombre de pièces, on peut se contenter d "un tableau à une ligne (la dernière).

NSI Lycée Louis de Foix

Deuxième approche

On s"inspire du problème du sac à dos : on complète le tableau par ligne en notant dans chaque case le

nombre de pièces nécessaires pour atteindre la somme correspondant à la colonne. On augmente le jeu de

monnaie d"une nouvelle pièce à chaque ligne. monnaie\somme 0 1 2 3 4 5 6 7 8 9 10 11 12 13

0 ь ь ь ь ь ь ь ь ь ь ь ь ь ь

1 0 1 2 3 4 5 6 7 8 9 10 11 12 13

2 0 1 1 2 2 3 3 4 4 5 5 6 6 7

5 0 1 1 2 2 1 2 2 3 3 2 3 3 4

Pour chacune des deux approches :

2. Compléter le tableau dans le cas monnaie = (1, 3, 4) et s = 10.

On note :

n le nombre de pièces de monnaie différentes monnaie un tableau de taille n contenant les valeurs des pièces (des entiers) s la somme à rendre T un tableau d'entiers à n + 1 lignes et s + 1 colonnes

3. Écrire l'algorithme de résolution par programmation dynamique en langage naturel.

Avec la deuxième approche, il faudra ensuite reconstituer la composition du rendu de monnaie à partir

du tableau sous forme de tableau avec le nombre de pièces de chaque type, comme [0, 2, 1] pour

obtenir 9 € avec le jeu de monnaie [1, 2, 5], ou sous forme de liste de pièces comme [5, 2, 2].

4. Quelle est la complexité en temps et en mémoire ?

5. Programmer les fonctions rendu_dynamique_1(monnaie, s) et rendu_dynamique_2(monnaie, s) qui

renvoient une solution optimale du problème du rendu de monnaie avec les deux approches de programmation dynamique. Dans un premier temps, on pourra renvoyer le tableau T et vérifier qu"on obtient le résultat attendu sur les deux exemples traités à la main.quotesdbs_dbs43.pdfusesText_43

[PDF] fragment 128 questions

[PDF] feuillet d'hypnos 128 analyse

[PDF] feuillets d'hypnos texte intégral

[PDF] poésie dimanche rené de obaldia

[PDF] poésie dimanche jacques prévert

[PDF] la cromagnonne et le cosmonaute (poésie)

[PDF] otto dix la tranchée lieu de conservation

[PDF] poésie de rené de obaldia moi j'irai dans la lune

[PDF] poesie dimanche charlotte fait de la compote

[PDF] rené de obaldia innocentines

[PDF] gestion des conflits interpersonnels

[PDF] gestion des conflits ppt

[PDF] gestion de conflits au travail

[PDF] rené descartes biographie pdf

[PDF] les types de conflits