Rendu de monnaie

1. 1

   Indice

   Itérer sur la liste des pièces en utilisant la division entière et le modulo pour compter les éléments.
   Écrire une fonction nb_ccp(m: int, P: list[int]) -> int | None qui calcule le nombre de pièces nécessaires pour rendre le montant m à partir de la liste des pièces P triée par ordre décroissant. Par exemple nb_ccp(150, [100, 25]) renvoie 3.
2. 2

   Indice

   Modifier légèrement le code précédent en utilisant une liste vide à laquelle on ajoute des tuples (n,p) à chaque itération.
   Écrire une fonction ccp(m: int, P: list[int]) -> list[tuple[int, int]] | None qui renvoie la liste des couples (nombre, pièce) correspondant aux pièces utilisées pour rendre le montant m. S'il n'y pas de solution, la fonction renvoie une liste vide. Par exemple ccp(150, [100, 25]) renvoie [(1, 100), (2, 25)].
3. 3

   Indice

   Définir les cas de base (conditions d'arrêt), puis appeler la fonction récursivement avec le montant réduit et la liste tronquée. Utiliser le tranchage de liste L[start:stop] et la concaténation de listes +.
   Écrire une fonction rec_ccp(m: int, P: list[int]) -> list[tuple[int, int]] qui calcule la composition du rendu en implémentant l'algorithme glouton de manière récursive. Par exemple rec_ccp(150, [100, 25]) renvoie [(1, 100), (2, 25)].