Résolution du problème de rendu de monnaie

I. Formalisation de l'algorithme

L'algorithme peut être décrit selon l'une des façons suivantes :

rendre_monnaie(somme:Nombre, listePieces:[Nombre*]) retourne decomposition:[Nombre*] :
    initialiser somme_restant_à_atteindre à somme
    initialiser decomposition à la liste vide
  deb:
    chercher la plus grande valeur dans listePieces < somme_restant_à_atteindre et l'appeler piece
    ajouter pièce à decomposition
    enlever pièce à somme_restant_à_atteindre
    si somme_restant_à_atteindre > 0, recommencer à deb

rendre_monnaie(somme:Nombre, listePieces:[Nombre*]) retourne decomposition:[Nombre*] :
    initialiser somme_restant_à_atteindre à somme
    initialiser decomposition à la liste vide
    tant_que somme_restant_à_atteindre > 0:
      chercher la plus grande valeur dans listePieces < somme_restant_à_atteindre et l'appeler piece
      ajouter pièce à decomposition
      enlever pièce à somme_restant_à_atteindre

Dans un premier temps, on pourra laisser les élèves écrire la première version s'ils sont plus à l'aise avec celle-ci, mais il faudra rapidement qu'ils arrivent à écrire directement la deuxième version.

II. Passage à un programme

def rendre_monnaie(somme, liste_pieces):
"""
Fonction déterminant comment rendre une certaine somme d'argent avec des pièces.
somme: Nombre ; la somme qu'il faut rendre
liste_pieces: [Nombre*] ; la liste des types de pièces disponibles
retour: [Nombre*] ; la liste des pièces à rendre
"""
# initialiser somme_restant_à_atteindre à somme
somme_restant_a_atteindre = somme
# initialiser decomposition à la liste vide
decomposition = []
# Prendre successivement la plus grande pièce possible
#jusqu'à avoir atteint la bonne somme
while somme_restant_a_atteindre > 0:
  #chercher la plus grande valeur dans listePieces < somme et l'appeler piece
  piece = chercher_plus_grande_piece_possible(liste_pieces, somme_restant_a_atteindre)
  #ajouter pièce à decomposition
  decomposition.append(piece)
  # enlever pièce à somme_restant_à_atteindre
  somme_restant_a_atteindre = somme_restant_a_atteindre - piece
  return decomposition
    

III. La fonction chercher_plus_grande_piece_possible

A. Analyse des hypothèses

• liste triée
• Version en allant du plus petit au plus grand

chercher_plus_grande_piece_possible(listePieces, somme):
  dernière_piece_vue = 0
  tant_que listePiecesPasComplètementParcourue et derniere_piece_vuePasTropGrande:
    si prochaine_piece_possible <= somme:
      derniere_piece_vue = prochaine_piece_possible
    passer à la pièce suivante
  renvoyer dernière_piece_vue

• Version en allant du plus grand au plus petit (analyser le problème de la terminaison)

chercher_plus_grande_piece_possible(listePieces, somme):
  tant_que pieceCourante > somme:
    passer à la pièce suivante
  renvoyer pieceCourante

• liste non triée (analyser la complexité par rapport aux cas précédents)

    chercher_plus_grande_piece_possible(listePieces, somme):
      pieceConvenable = prochainePiece
      tant_que listePiecesPasComplètementParcourue:
        si prochainePiece < somme et prochainePiece > pieceConvenable:
          pieceConvenable = prochainePiece
      renvoyer pieceConvenable
    

B. Trier la liste

Il est apparaît judicieux de trier la liste. On peut alors envisager où la trier : dans chercher_plus_grande_piece_possible() ou dans rendreMonnaie(), et à quel endroit dans ces fonctions.

Le tri n'a besoin d'être fait qu'une seule fois, car la liste des pièces triées ne change pas tout au long du processus. Il est donc judicieux de trier cette liste avant la boucle de la fonction rendreMonnaie(). On pourra alors assumer dans chercher_plus_grande_piece_possible() que la liste des pièces est triée. Cela peut d'ailleurs être traduit par une assertion verifierListeTriee().

Par ailleurs, un tri par ordre décroissant donne un test plus simple dans la boucle. À noter que là encore, 2 solutions sont possibles :

• Trier la liste par ordre décroissant et la parcourir à partir de l'indice 0
• Trier la liste par ordre croissant et la parcourir à partir du dernier indice

Enfin, le parcours peut être fait de 2 façons possibles :

• Avec un while, et une condition de sortie bien défini ;
• Avec un for, et un break pour sortir au bon moment.

C. Et en Python...

def chercher_plus_grande_piece_possible(listePieces, somme):
  assert liste_croissante(listePieces)
  indice = len(listePieces) - 1
  pieceCourante  = listePieces[indice]
  while pieceCourante > somme:
    indice = indice - 1
    pieceCourante = listePieces[indice]
  return pieceCourante

D. Quant à l'assertion...

def liste_croissante(liste):
  indice = 0
  liste_triee = True;
  while indice < len(liste) - 2 and liste_triee:
    if liste[indice] > liste[indice + 1]:
      liste_triee = False
  indice = indice + 1
  return liste_triee

IV. Rajout du tri dans la fonction rendre_monnaie

def rendre_monnaie(somme, liste_pieces):
  """
    Fonction déterminant comment rendre une certaine somme d'argent avec des pièces.
    somme: Nombre ; la somme qu'il faut rendre
    liste_pieces: [Nombre*] ; la liste des types de pièces disponibles
    retour: [Nombre*] ; la liste des pièces à rendre
  """
  # initialiser somme_restant_à_atteindre à somme
  somme_restant_a_atteindre = somme
  # initialiser decomposition à la liste vide
  decomposition = []
  # trier la liste par ordre croissant
  liste_pieces_triee = sorted(liste_pieces)
  # Prendre successivement la plus grande pièce possible
  #jusqu'à avoir atteint la bonne somme
  while somme_restant_a_atteindre > 0:
    #chercher la plus grande valeur dans listePieces < somme et l'appeler piece
    piece = chercher_plus_grande_piece_possible(liste_pieces_triee, somme_restant_a_atteindre)
    #ajouter pièce à decomposition
    decomposition.append(piece)
    # enlever pièce à somme_restant_à_atteindre
    somme_restant_a_atteindre = somme_restant_a_atteindre - piece
    return decomposition