On s’intéresse à un algorithme récursif qui permet de rendre la monnaie à partir d’une liste donnée de valeurs de pièces et de billets.
Le système monétaire est donné sous forme d’un tableau de données const pieces = [100, 50, 20, 10, 5, 2, 1]. On supposera qu’il n’y a pas de limitation quant à leur nombre.
On cherche à donner le tableau de pièces à rendre pour une somme donnée en argument. le tableau de pièce est donné en second argument. Le troisième paramétre et l'index sur le tableau pieces.
Donnez la fonction rendu_glouton qui implémente cet algorithme et renvoie le tableau des pièces à rendre.
Exemples des appels récursifs
legende : ▲reste sur la même pièce, ▶ change de pièce.rendu_glouton(68, [ ], 0)
[50, 10, 5, 2, 1]
Voici la liste des appels100€ rendu_glouton(68, [], 0)
50€ ▶ rendu_glouton(68, [], 1)
50€ ▶ ▲ rendu_glouton(18, [50], 1)
20€ ▶ ▲ ▶ rendu_glouton(18, [50], 2)
10€ ▶ ▲ ▶ ▶ rendu_glouton(18, [50], 3)
10€ ▶ ▲ ▶ ▶ ▲ rendu_glouton(8, [50,10], 3)
5€ ▶ ▲ ▶ ▶ ▲ ▶ rendu_glouton(8, [50,10], 4)
5€ ▶ ▲ ▶ ▶ ▲ ▶ ▲ rendu_glouton(3, [50,10,5], 4)
2€ ▶ ▲ ▶ ▶ ▲ ▶ ▲ ▶ rendu_glouton(3, [50,10,5], 5)
2€ ▶ ▲ ▶ ▶ ▲ ▶ ▲ ▶ ▲ rendu_glouton(1, [50,10,5,2], 5)
1€ ▶ ▲ ▶ ▶ ▲ ▶ ▲ ▶ ▲ ▶ rendu_glouton(1, [50,10,5,2], 6)
1€ ▶ ▲ ▶ ▶ ▲ ▶ ▲ ▶ ▲ ▶ ▲ rendu_glouton(0, [50,10,5,2,1], 6)
✕ FIN ✕
rendu_glouton(300, [ ], 0)
[100, 100, 100]
Voici la liste des appels> rendu_glouton(300, [], 0: 100€ )
100€ rendu_glouton(300, [], 0)
100€ ▲ rendu_glouton(200, [100], 0)
100€ ▲ ▲ rendu_glouton(100, [100,100], 0)
100€ ▲ ▲ ▲ rendu_glouton(0, [100,100,100], 0)
✕ FIN ✕
le troisième paramétre correspond à l'indice de recherche dans le tableau des pieces.
Fixant sa valeur à 0, c'est en cela que l'algorithme est glouton, on recherche le plus gros billet à rendre à chaque itération. Ainsi rendre 100€ c'est 1 billet de 100 et pas 2 billets de 50 ou 10 billets de 10.
https://docs.google.com/document/d/11bobArd1BY3zqPNWiPHwJYBLLwtlmrMGdGiqPaahBqM/edit?usp=sharing