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 de monnaie est donné sous forme d'une liste de valeurs décroissantes définie de façon globale et qui peut être utilisée dans les fonctions sans être donnée en paramètre.
On suppose qu'il n'y a pas de limitation quant au nombre de pièces et billets disponibles.
On souhaite, étant donnée une somme à rendre, déterminer la plus petite liste de pièces dont la somme est égale à celle-ci.
L'algorithme utilisé est le suivant :
On regarde les valeurs possibles en partant de la plus grande;
Si on peut rendre la valeur considérée, on le fait.
Sinon on passe à la valeur inférieure.
On continue tant que l'on n'a pas tout rendu.
La fonction rendu_monnaie prend en paramètre un entier a_rendre qui correspond à la somme à rendre et renvoie la liste des valeurs rendues, dans l'ordre décroissant.
Cette fonction utilise une fonction récursive rendu_monnaie_rec qui implémente l'algorithme ci-dessus.
Les deux façons d'écrire rendu_monnaie_rec
On propose 2 façons d'écrire la fonction rendu_monnaie_rec :
Dans cette version, la fonction rendu_monnaie_rec prend 2 paramètres :
a_rendre : un entier qui correspond à la somme à rendre.
i : un entier qui correspond à l'indice de la valeur considérée dans PIECES.
Elle renvoie la liste des valeurs rendues, dans l'ordre décroissant.
Si on peut rendre PIECES[i], on concatène cette valeur devant la liste obtenue par l'appel récursif.
Cette version est plus simple à écrire, mais la concaténation nécessite de recopier toutes les valeurs de la liste à chaque fois, ce qui donne un coût quadratique à cette implémentation.
Dans cette version, la fonction rendu_monnaie_rec prend 3 paramètres :
a_rendre : un entier qui correspond à la somme à rendre.
i : un entier qui correspond à l'indice de la valeur considérée dans PIECES.
deja_rendu : la liste des valeurs déjà rendues.
Elle renvoie la liste des valeurs rendues, dans l'ordre décroissant.
Si on peut rendre la valeur PIECES[i], on la rajoute à la liste deja_rendu en utilisant append avant de faire l'appel récursif.
Cette version est un peu plus compliquée à écrire mais en utilisant append, le coût reste linéaire.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)