Programmation Dynamique

Principe

Indépendance des sous-problèmes

• Énoncé au format pdf
• Corrigé au format pdf

Énoncé du problème Un commerçant cherche à rendre la monnaie à ses clients de façon optimale, c’est-à-dire avec le nombre minimal de pièces et de billets. Dans ce problème, On suppose que les clients ne donnent que des sommes entières en euros (pas de centimes pour simplifier) ; Les valeurs des pièces et billets à disposition sont : 1, 2, 5, 10, 20, 50, 100, 200 et 500. On suppose que l’on a autant d’exemplaires que nécessaire de chaque pièce et billet ; Dans la suite, afin de simplifier, on désigne par « pièces » à la fois les pièces et les billets. [Lire]

Rappel : récursivité terminale La définition de la fonction factorielle est $$ n! = \begin{cases} 1 & \text{if } n = 0 \cr n \times (n-1)! & \text{sinon} \end{cases} $$ Définir la fonction fact_env qui calcule la factorielle d’un entier naturel $n$, sans oublier le jeu de tests. La spécification de la fonction est : 1 2 3 4 5 6 def fact_env(n: int) -> int: """ Retourne la factorielle de n. [Lire]