En terminale

• Le principe
• Exemples simples
• Le rendu de monnaie
• Exercices

Nous avons vu comment rendre la monnaie par un algorithme glouton en première. Nous avons aussi vu que parfois, notre programme glouton ne donne pas la réponse. Nous allons voir que l'on peut réaliser un algorithme récursif. Encore une fois, pour réussir un programme récursif il est crucial de commencer par écrire un algorithme!

On veut récupérer la combinaison des pièces et le nombre de pièces

monnaie(pieces disponibles, montant,combinaison)
	si le montant est 0
		retourner 0 et et  liste vide (les pièces à utiliser!)
	sinon
		mini= infini
		combinaison = liste vide (pour l'instant on n'a pas de pièce)
	pour toutes les pieces disponibles:
		si on peut rendre cette piece (piece< montant):
			nombre de pieces et copmposition rendu = monnaie(pieces dispos, montant-piece, liste vide)
			incrémenter nombre de pieces
			si le nb de pieces< mini:
				le mini devient nb
				combinaison= composition rendu auquel on ajoute la pièce
	renvoyer mini, combinaison

Voici le code, ce n'est tout de même pas très simple!

def rendu_monnaie_rec_combinaison(pieces,montant,combinaison):
  if montant==0:
    return 0,[]
  else:
    mini = 1000
    comb= []
  for i in range(len(pieces)):
    if pieces[i]<=montant:
      nb,temp=rendu_monnaie_rec_combinaison(pieces,montant-pieces[i],[])
      nb = 1 + nb
      if nb<mini:
        mini = nb
        comb=copy.copy(temp)
        comb.append(pieces[i])
  return mini,comb

1. blabla
2. blabla