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.

Algorithme glouton

Un client nous achète un objet qui coûte 53 euros. Il paye avec un billet de 200 euros. Il faut donc lui rendre 147 euros, par exemple un billet de 100, deux billets de 20, un billet de 5 et une pièce de 2.

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} $$

1. 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. Algorithme : récursivité enveloppée """

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def fact_env(n: int) -> int:
    """
    Retourne la factorielle de n.

    Algorithme : récursivité enveloppée
    """
    if n == 0:
        return 1

    return n * fact_env(n - 1)


if __name__ == "__main__":
    assert fact_env(0) == 1
    assert fact_env(1) == 1
    assert fact_env(5) == 120
    assert fact_env(8) == 40320