Le problème du rendu de monnaie : le retour !
Rappel du problème à résoudre : Il s’agit de déterminer un nombre minimal de pièces à rendre pour un montant donné M et dans un système monétaire donné S.
Une solution peut être fournie par un algorithme glouton : cette possibilité a été abordée en classe de Première : .
Si un algorithme glouton fournit une solution, selon le système monétaire et le montant à rendre ce n’est pas toujours la meilleure des solutions optimales.
Se pose alors la question de savoir s’il est possible de résoudre ce problème à l’aide d »un algorithme qui aboutisse, dans tous les cas de figure, à la meilleure solution optimale.
L’idée est d’essayer toutes les combinaisons de pièces possibles et de ne garder que la meilleure.
Cette démarche qui consiste à tester toutes les possibilités est celle d’un algorithme dit « de force brute ».
Résolution du problème par un algorithme de « force brute » basée sur une fonction récursive
Algorithme de force brute "Rendu de monnaie"
Soit :
sm : système monétaire utilisé ; liste de nombres entiers
m : Montant à rendre ; nombre entier
n : nombre de pièces à rendre ; n prend la valeur renvoyée par la
fonction 'RenduMonnaie(sm, m)'
Fonction RenduMonnaie(sm, m)
SI m EST EGAL A zéro, ALORS RENVOYER zéro
SINON
n PREND LA VALEUR DE m + 1
(on considère que m est totalement rendu en pièces de 1)
POUR chacune des pièces p de sm FAIRE
SI p EST INFERIEUR OU EGAL A m, ALORS FAIRE
np : nombre de pièces à rendre ; np PREND LA VALEUR 1 +
la valeur renvoyée par RenduMonnaie(sm , m-p)
SI np EST STRICTEMENT INFERIEUR A n, ALORS FAIRE
n PREND LA VALEUR DE np
FIN DE SI
FIN DE SI
FIN DE POUR
FIN DE SINON
RENVOYER n- Programmez cet algorithme en langage Python.
- Testez le d’abord avec m= 5, sm= [1,2,5,10] puis sm = [1,3,7,9] :
vérifiez qu’il renvoie bien la solution optimale.
Réponse possible et auto-évaluation de la réponse personnelle
- Modifiez le programme en ajoutant un compteur d’appels récursifs.
Présentez les différents appels récursifs sous la forme d’un arbre.
Vérifiez le nombre d’appels récursifs et montrez que certains appels sont redondants.
Réponse possible et auto-évaluation de la réponse personnelle
Réponse possible et auto-évaluation de la réponse personnelle
- Puis avec les mêmes systèmes monétaires augmentez progressivement la valeur de m : m = 10, m = 20, m = 30.
Que constatez vous ?
Réponse possible et auto-évaluation de la réponse personnelle
Amélioration de l’algorithme avec la programmation dynamique
Le principe consiste à conserver le résultat obtenu en retour d’une première série d’appels récursifs successifs, résultat correspondant au plus petit nombre de pièces à rendre pour un montant donné : pour m = 1, n = 1, pour m = 2, n = 1, pour n =3, n = 2, pour m = 4, n = 2 etc.
Et dans la suite du déroulement du programme, si le montant à rendre correspond à un montant dont on connait déjà le plus petit nombre de pièces à rendre, alors on lit sa valeur conservée et on n’effectue pas les appels récursifs nécessaires à la détermination de ce dernier.
<< Cliquez pour plus d’informations <<