N.S.I. WorkSpace Compétence,T-Th-E4,Terminale E4b – Le problème du rendu de monnaie : le retour !

E4b – 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

Article sous licence Cliquez pour plus d’informations