Aller au contenu principal
Physique, Chimie et Informatique > Terminales Spé. NSI

Programmation dynamique

Au programme

Contenus Capacités attendues Commentaires
Programmation dynamique Utiliser la programmation dynamique pour écrire un algorithme. - Les exemples de l’alignement de séquences ou du rendu de monnaie peuvent être présentés.
- La discussion sur le coût en mémoire peut être développée.

Documents

25 févr. 2021

Sous-sections de Programmation dynamique

Physique, Chimie et Informatique > Terminales Spé. NSI > Programmation dynamique

Autour de la suite de Fibonacci

Rappel : récursivité terminale

La définition de la fonction factorielle est

n!={1if n=0n×(n−1)!sinonn! = \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 nn, sans oublier le jeu de tests.
    La spécification de la fonction est :

    def fact_env(n: int) -> int:
        """
        Retourne la factorielle de n.
    
        Algorithme : récursivité enveloppée
        """
Réponse
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
Info

En informatique, la récursion terminale, aussi appelée, récursion finale, est un cas particulier de récursivité assimilée à une itération.
Une fonction à récursivité terminale (dite tail-recursive en anglais) est une fonction où l’appel récursif est la dernière instruction à être évaluée. Cette instruction est alors nécessairement « pure », c’est-à-dire qu’elle consiste en un simple appel à la fonction, et jamais à un calcul ou une composition.
Les algorithmes récursifs exprimés à l’aide de fonctions à récursion terminale profitent donc d’une optimisation de la pile d’exécution.
Cette réorganisation économise de l’espace mémoire car aucun état, sauf l’adresse de la fonction appelante, n’a besoin d’être sauvé sur la pile d’exécution. Cela signifie également que le programmeur n’a pas à craindre l’épuisement de l’espace de pile ou du tas pour des récursions très profondes.

Wikipedia
  1. Définir la fonction fact_term qui calcule la factorielle d’un entier naturel nn, sans oublier le jeu de tests.
    La spécification de la fonction est :

    def fact_term(n: int) -> int:
        """
        Retourne la factorielle de n.
    
        Algorithme : récursivité terminale
        """

    La fonction fact_term est en fait une fonction enveloppe de la fonction _fact dont la spécification est :

    def _fact(n: int, acc: int = 1) -> int:
        """
        Fonction qui effectue réellement le calcul récursif.
        """

    La fonction _fact met en œuvre un raisonnement basé sur la récursivité terminale.

Réponse
def fact_term(n: int) -> int:
    """
    Retourne la factorielle de n.

    Algorithme : récursivité terminale
    """

    def _fact(n: int, acc: int = 1) -> int:
        """
        Fonction qui effectue réellement le calcul récursif.
        """
        if n == 0:
            return acc

        return _fact(n - 1, acc * n)

    return _fact(n, 1)


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

Autour de la suite de Fibonacci

En mathématiques, la suite de Fibonacci est une suite d’entiers dans laquelle chaque terme est la somme des deux termes qui le précèdent. Elle commence par les termes 0 et 1 si on part de l’indice 0, ou par 1 et 1 si on part de l’indice 1.

Fn={F0=0F1=1Fn=Fn−1+Fn−2F_n = \begin{cases} F_0 = 0 \cr F_1 = 1 \cr F_n = F_{n-1} + F_{n-2} \end{cases}

Résolutions du problème sans programmation dynamique

  1. Définir la fonction fibo_iter qui calcule le terme de rang nn de la suite de Fibonacci, sans oublier le jeu de tests. Le raisonnement mis en œuvre doit être itératif.
    La spécification de la fonction est :

    def fibo_iter(n: int) -> int:
    """
    Retourne le terme de rang n de la suite de Fibonacci.
    
    Algorithme : itératif
    """
Réponse
def fibo_iter(n: int) -> int:
    """
    Retourne le terme de rang n de la suite de Fibonacci.

    Algorithme : itératif
    """
    u = 0
    v = 1
    for i in range(2, n + 1):
        w = u + v
        u = v
        v = w

    if n == 0:
        return 0
    else:
        return v


if __name__ == "__main__":
    # fibo_iter
    assert fibo_iter(0) == 0
    assert fibo_iter(1) == 1
    assert fibo_iter(10) == 55
    assert fibo_iter(16) == 987
  1. Quelle est la complexité de l’algorithme itératif ?
Réponse

L’algorithme comporte une boucle, la complexité est donc en O(n)O(n).

  1. Définir la fonction fibo_head qui calcule le terme de rang nn de la suite de Fibonacci, sans oublier le jeu de tests. Le raisonnement mis en œuvre doit être récursif.
    La spécification de la fonction est :

    def fibo_head(n: int) -> int:
    """
    Retourne le terme de rang n de la suite de Fibonacci.
    
    Algorithme : récursif (enveloppé)
    """
Réponse
def fibo_head(n: int) -> int:
    """
    Retourne le terme de rang n de la suite de Fibonacci.

    Algorithme : récursif (enveloppé)
    """
    if n == 0:
        return 0
    elif n == 1:
        return 1

    fibo1 = fibo_head(n - 1)
    fibo2 = fibo_head(n - 2)
    return fibo1 + fibo2


if __name__ == "__main__":
    assert fibo_head(0) == 0
    assert fibo_head(1) == 1
    assert fibo_head(10) == 55
    assert fibo_head(16) == 987
  1. Écrire l’arbre des appels récursifs pour n=5n=5. En déduire la complexité de l’algorithme récursif.
    Quelle est la raison d’une telle complexité ?
Réponse
  • Les mêmes calculs sont effectués plusieurs fois.
  • La hauteur de l’arbre des appels est égale à n−1n-1.
  • Si chaque étape est en O(1)O(1), le nombre de calculs effectués est donc 20+21+22+23+…+2n−1=2n2^0 + 2^1 + 2^2 + 2^3 + \ldots + 2^{n-1} = 2^n.

La complexité est donc en O(2n)O(2^n).

  1. En prenant pour exemple la définition de la fonction à la question 2. et l’algorithme itératif, à la question 3., définir la fonction fib_tail qui calcule le terme de rang nn de la suite de Fibonacci à l’aide d’un algorithme récursif terminal.
    La spécification de la fonction fib_tail est :

    def fibo_tail(n: int) -> int:
        """
        Retourne le terme de rang n de la suite de Fibonacci.
    
        Algorithme : récursif (terminale)
        """

    La fonction fib_tail est en fait une fonction enveloppe de la fonction _fibo dont la spécification est :

    def _fibo(n: int, a: int = 0, b: int = 1) -> int:
        """
        Fonction qui effectue réellement le calcul récursif.
        """
Réponse
def fibo_tail(n: int) -> int:
    """
    Retourne le terme de rang n de la suite de Fibonacci.

    Algorithme : récursif (terminale)
    """

    def _fibo_tail(n: int, a: int = 0, b: int = 1):
        if n == 0:
            return a
        elif n == 1:
            return b

        return _fibo_tail(n - 1, b, a + b)

    return _fibo_tail(n)


if __name__ == "__main__":
    assert fibo_tail(0) == 0
    assert fibo_tail(1) == 1
    assert fibo_tail(10) == 55
    assert fibo_tail(16) == 987
  1. Quelle est la complexité de cet algorithme ?
Réponse

La complexité de l’algorithme récursif terminal, en nombre d’additions, est donnée par la récurrence T(n)=1+T(n−1)T(n) = 1+T(n−1). On a donc T(n)=n−1T(n) = n−1 pour _fibo_tail, et par extension pour fibo_tail.

Programmation dynamique

À retenir

En informatique, la programmation dynamique est une méthode algorithmique pour résoudre des problèmes d’optimisation. Le concept a été introduit au début des années 1950 par Richard Bellman.

La programmation dynamique consiste à résoudre un problème en le décomposant en sous-problèmes, puis à résoudre les sous-problèmes, des plus petits aux plus grands en stockant les résultats intermédiaires.

La programmation dynamique s’appuie sur le principe d’optimalité de Bellman : une solution optimale d’un problème s’obtient en combinant des solutions optimales à des sous-problèmes.

La méthode de programmation dynamique, comme la méthode diviser pour régner, résout des problèmes en combinant des solutions de sous-problèmes. Les algorithmes diviser-pour-régner partitionnent le problème en sous-problèmes indépendants qu’ils résolvent récursivement, puis combinent leurs solutions pour résoudre le problème initial. La méthode diviser-pour-régner est inefficace si on doit résoudre plusieurs fois le même sous-problème.

Info

La programmation dynamique est utilisée pour résoudre des problèmes d’optimisation. La conception d’un algorithme de programmation dynamique est typiquement découpée en quatre étapes :

  • Caractériser la structure d’une solution optimale.
  • Définir (souvent de manière récursive) la valeur d’une solution optimale.
  • Calculer la valeur d’une solution optimale.
  • Construire une solution optimale à partir des informations calculées. La dernière étape est utile pour calculer une solution optimale, et pas seulement la valeur optimale. Un problème d’optimisation peut avoir de nombreuses solutions. Chaque solution a une valeur, et on souhaite trouver une solution ayant la valeur optimale. Une telle solution optimale au problème n’est pas forcément unique, c’est sa valeur qui l’est.

Dans le cas du calcul du terme de rang nn de la suite de Fibonacci à l’aide d’un raisonnement récursif, le problème a pour origine les multiples calculs de chacun des sous-termes nécessaires. La programmation dynamique consiste alors à stocker les valeurs des sous-problèmes pour éviter les recalculs.

À retenir

Il existe alors deux méthodes pour calculer effectivement une solution : la méthode ascendante (Bottom-up approach) et la méthode descendante (Top-down approach).

  • Dans la méthode ascendante, on commence par calculer des solutions pour les sous-problèmes les plus petits, puis, de proche en proche, on calcule les solutions des problèmes en utilisant le principe d’optimalité et on mémorise les résultats dans un tableau ou un dictionnaire F.
  • Dans la méthode descendante, on écrit un algorithme récursif mais on utilise la mémoïsation pour ne pas résoudre plusieurs fois le même problème, c’est-à-dire que l’on stocke dans un tableau ou un dictionnaire F les résultats des appels récursifs.
Info

Une fonction mémoïsée stocke les valeurs renvoyées par ses appels précédents dans une structure de données adaptée et, lorsqu’elle est appelée à nouveau avec les mêmes paramètres, renvoie la valeur stockée au lieu de la recalculer. Une fonction peut être mémoïsée seulement si elle est pure, c’est-à-dire si sa valeur de retour ne dépend que de la valeur de ses arguments, sans effet de bord. En ce cas, la transparence référentielle permet de remplacer l’appel de la fonction directement par sa valeur. À la différence d’une fonction tabulée, où la table est statique, une fonction mémoïsée repose sur une table dynamique remplie à la volée.

La mémoïsation est une façon de diminuer le temps de calcul d’une fonction, au prix d’une occupation mémoire plus importante. La mémoïsation modifie donc la complexité d’une fonction, en temps comme en espace.

Résolutions du problème à l’aide de la programmation dynamique

  1. Quel est l’intérêt des structures de données tableau ou dictionnaire pour le stockage des valeurs des sous-problèmes ?

  2. Écrire l’arbre des appels récursifs pour n=5n=5, lorsque la technique de mémoïsation est mise en œuvre. Le comparer à l’arbre obtenu à la question 6.

    Réponse

  3. Définir la fonction fibo_memo qui calcule le terme de rang nn de la suite de Fibonacci, sans oublier le jeu de tests. Le raisonnement doit être récursif et mettre en œuvre la technique de mémoïsation (méthode descendante).

Réponse
def fibo_memo1(n: int) -> int:
    """
    Version mémoïsée de Fibonacci.

    Utilisation d'un dictionnaire et d'une fonction
    enveloppe.
    """
    dic = {0: 0, 1: 1}

    def _fibo(n: int, dic: "dict[int: int]") -> int:
        if n in dic.keys():
            return dic[n]
        else:
            dic[n] = _fibo(n - 1, dic) + _fibo(n - 2, dic)
            return dic[n]

    return _fibo(n, dic)

ou

def fibo_memo2(n: int, tab: list[int] = [0, 1]) -> int:
    """
    Version mémoïsée de Fibonacci.

    Utilisation d'une liste.
    """
    if n < len(tab):
        return tab[n]

    calcul = fibo_memo2(n - 1, tab) + fibo_memo2(n - 2, tab)
    tab.append(calcul)
    return calcul
  1. Quelle est la complexité de l’algorithme avec mémoïsation ?

    Réponse

  2. Définir la fonction fibo_up qui calcule le terme de rang nn de la suite de Fibonacci, sans oublier le jeu de tests. Le raisonnement doit mettre en œuvre la méthode ascendante du problème.

Réponse
def fibo_up(n: int) -> int:
    """
    Retourne la valeur de rang n de la suite de Fibonacci.

    Version itérative avec stockage des valeurs dans une liste.
    """
    tab = [0, 1]
    for i in range(2, n + 1):
        valeur = tab[i - 2] + tab[i - 1]
        tab.append(valeur)
    return tab[n]

Application : nombre de façon d’atteindre la nième marche d’un escalier

On cherche le nombre de méthodes différentes qui permettent d’atteindre la nième marche d’un escalier, sachant que l’on peut monter un, deux ou trois marches à la fois.

  1. Déterminer la relation de récurrence, sachant que l’on note unu_n le nombre de méthodes permettant d’atteindre la nième marche.
Réponse
un={u1=1u2=2u3=4un=un−1+un−2+un−3u_n = \begin{cases} u_1 &= 1 \cr u_2 &= 2 \cr u_3 &= 4 \cr u_{n} &= u_{n-1} + u_{n-2} + u_{n-3} \end{cases}
  1. Quel est l’écueil à éviter lorsqu’on programme le calcul du n-ième terme de la suite précédente de manière récursive ?

    Réponse

    Il faut éviter que les appels récursifs calculent plusieurs fois les mêmes valeurs.

  2. Proposer une version itérative du calcul de unu_n.

def nbre_methodes_iter(n: int) -> int:
    """
    Calcul du nombre de méthodes différentes pour
    accéder à la nième marche d'un escalier.

    Version itérative.
    """
Réponse
def nbre_methodes_iter(n: int) -> int:
    """
    Calcul du nombre de méthodes différentes pour
    accéder à la nième marche d'un escalier.

    Version itérative.
    """
    u, v, w = 1, 2, 4

    for i in range(4, n + 1):
        z = u + v + w
        u = v
        v = w
        w = z

    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    else:
        return w
  1. Proposer une version récursive du calcul de unu_n.
def nbre_methodes_rec(n: int) -> int:
    """
    Calcul du nombre de méthodes différentes pour
    accéder à la nième marche d'un escalier.

    Version récursive.
    """
Réponse
def nbre_methodes_rec(n: int) -> int:
    """
    Calcul du nombre de méthodes différentes pour
    accéder à la nième marche d'un escalier.

    Version récursive.
    """
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4

    return (
        nbre_methodes_rec(n - 1) + nbre_methodes_rec(n - 2) + nbre_methodes_rec(n - 3)
    )
  1. Proposer une version récursive efficace du calcul de unu_n qui utilise la mémoïsation.
def nbre_methodes_memo(n: int) -> int:
    """
    Calcul du nombre de méthodes différentes pour
    accéder à la nième marche d'un escalier.

    Version qui utilise la mémoïsation.
    """
Réponse
def nbre_methodes_memo(n: int) -> int:
    """
    Calcul du nombre de méthodes différentes pour
    accéder à la nième marche d'un escalier.

    Version qui utilise la mémoïsation.
    """
    memo = {1: 1, 2: 2, 3: 4}

    def _nbre(n: int) -> int:
        if n in memo.keys():
            return memo[n]
        else:
            memo[n] = _nbre(n - 1) + _nbre(n - 2) + _nbre(n - 3)
        return memo[n]

    return _nbre(n)
Physique, Chimie et Informatique > Terminales Spé. NSI > Programmation dynamique

Problème du rendu de monnaie

É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.

Afin de minimiser le nombre de pièces à rendre, on peut suivre la stratégie suivante :

  • On commence par rendre la pièce de plus grande valeur possible ;
  • On déduit cette valeur de la somme (encore) à rendre ;
  • On recommence, jusqu’à obtenir une somme nulle.

En procédant ainsi, on résout le problème étape par étape et un choix optimal est effectué à chacune de ces étapes (la pièce de plus grande valeur). Cet algorithme fait parti de la catégorie des algorithmes gloutons : chercher la solution optimale à partir d’optima locaux.

  1. Préparer le code suivant et étudier sa structure :
if __name__ == "__main__":
    # valeurs des pièces
    pieces = [1, 2, 5, 10, 20, 50, 100]

    prix = int(input("Quel est le prix ? "))
    client = int(input("Combien le client donne-t-il ? "))

    a_rendre = somme_a_rendre(prix, client)
    comment = pieces_a_rendre(a_rendre, pieces)

    reponse = [f"{comment[i]} piece(s) de {pieces[i]}" for i in range(len(pieces))]
    print(f"Je dois rendre : {a_rendre}")
    print(f"Je donne donc : {reponse}")
  1. Définir la fonction somme_a_rendre dont la spécification est :
def somme_a_rendre(prix: int, montant_client: int) -> int:
    """
    Détermine la somme à rendre à partir du prix et du montant donné par
    le client.
    """
Réponse
def somme_a_rendre(prix: int, montant_client: int) -> int:
    """
    Détermine la somme à rendre à partir du prix et
    du montant donné par le client.
    """
    return montant_client - prix
  1. Définir la fonction pieces_a_rendre dont la spécification est :
def pieces_a_rendre(somme: int, pieces: list[int]) -> list[int]:
    """
    Détermine les pièces (et leur nombre) à choisir pour rendre la somme
    passée en argument.
    Utilise la division euclidienne et le modulo de façon à pouvoir
    traiter tous les cas.
    """
Réponse
def pieces_a_rendre(somme: int, pieces: list[int]) -> list[int]:
    """
    Détermine les pièces (et leur nombre) à choisir
    pour rendre la somme passée en argument.

    Utilise la division euclidienne et le modulo de
    façon à pouvoir traiter tous les cas.

    On reçoit : pieces = [1, 2, 5, 10, 20]
    On retourne : a_rendre = [x, z, y, a, b]
    """
    a_rendre = []

    for i in range(len(pieces) - 1, -1, -1):
        nbre = somme // pieces[i]
        somme = somme % pieces[i]
        a_rendre.append(nbre)

    return list(reversed(a_rendre))


def pieces_a_rendre_2(somme: int, pieces: list[int]):
    a_rendre = {}

    i = len(pieces) - 1
    while somme > 0:
        nbre = somme // pieces[i]
        somme = somme % pieces[i]
        a_rendre[pieces[i]] = nbre
        i = i - 1
    return a_rendre


def pieces_a_rendre_3(somme: int, pieces: list[int]) -> list[int]:
    a_rendre = [0] * len(pieces)

    i = len(pieces) - 1
    while somme > 0:
        nbre = somme // pieces[i]
        somme = somme % pieces[i]
        a_rendre[i] = nbre
        i = i - 1

    return list(reversed(a_rendre))
Code complet

Le code se trouve à : cette adresse

Algorithme de force brute

  1. On note nbnb le nombre de pièces à rendre, prises dans la liste des pièces p=[1,2,5,10,20,50,100,200,500]p = [1, 2, 5, 10, 20, 50, 100, 200, 500], lorsque la somme à rendre est xx.
    Écrire la relation de récurrence que doit vérifier nbnb.

    Réponse
    nb(x)={0 si x=01+nb(x−p[i]) si x−p[i]⩾0nb(x) = \begin{cases} 0 & \text{ si } x = 0\cr 1 + nb(x - p[i]) & \text{ si } x - p[i] \geqslant 0 \cr \end{cases}

  2. En fait, on cherche le nombre minimal de pièces à rendre pour la somme xx. Adapter la relation de récurrence.

    Réponse
    nb(x)={0 si x=01+min⁡(nb(x−p[i])) si x−p[i]⩾0 et i∈[0,len(p)[nb(x) = \begin{cases} 0 & \text{ si } x = 0\cr 1 + \min{(nb(x - p[i]))} & \text{ si } x - p[i] \geqslant 0 \text{ et } i \in [0, \text{len}(p)[ \cr \end{cases}

  3. Écrire le schéma des appels récursifs pour x=11x=11 et p=[2,5,10]p=[2,5,10].

    Réponse

  4. Indiquer l’avantage et l’inconvénient de l’algorithme par Brute Force.

    Réponse

    Cet algorithme retourne une solution optimale mais calcule plusieurs fois les mêmes valeurs. Il est donc inutilisable si la valeur à retourner est importante.

  5. Réfléchir au code de la fonction dont la spécification est :

def nb_rendre(a_rendre: int, pieces: list[int]) -> int:
    """
    Détermine le nombre minimal de pièces
    à rendre.

    Algorithme récursif.
    """

Écrire le code de cette fonction.

Réponse
def nb_rendre(a_rendre: int, pieces: list[int]) -> int:
    """
    Détermine le nombre minimal de pièces
    à rendre.

    Algorithme récursif.
    """
    if a_rendre == 0:
        return 0

    nb_min = float("inf")

    for i in range(len(pieces)):
        if pieces[i] <= a_rendre:
            nb = 1 + nb_rendre(a_rendre - pieces[i], pieces)
            if nb <= nb_min:
                nb_min = nb

    return nb_min

  1. Tester le code pour une somme à rendre de 13 puis de 130. Le résultat confirme-t-il la réponse à la question 4 ?
Code complet

Le code se trouve à : cette adresse

Compléments

  1. On souhaite maintenant écrire le code de la fonction pieces_a_rendre dont la spécification est :
def pieces_a_rendre(
    somme: int, pieces: tuple[int], serie: list[int], series: list[Tuple[int]]
) -> None:
    """
    Détermine toutes les combinaisons de pièces qui permettent de rendre la somme somme.
    pieces est le tuple des pièces disponibles.
    series est la liste des pièces à rendre.
    series est la liste des listes des pièces à rendre.
    """

Remarque

On peut bien sur créer une fonction enveloppe qui ne prendrait que la somme et la liste des pièces disponibles en argument et retournerait la liste des listes de pièces.

Réponse
def pieces_a_rendre(
    somme: int, pieces: tuple[int], serie: list[int], series: list[Tuple[int]]
) -> None:
    """
    Détermine toutes les combinaisons de pièces qui permettent de rendre la somme somme.
    """
    if somme == 0:
        series.append(serie)
        return None

    for piece in pieces:
        if piece > somme:
            continue

        # Sauvegarde de la liste des pièces pour le retour arrière
        serie_sauv = list(serie)

        serie.append(piece)
        pieces_a_rendre(somme - piece, pieces, serie, series)

        serie = serie_sauv
  1. Tester le code pour une somme à rendre de 13 puis de 130. Obtient-on rapidement un résultat pour cette dernière valeur ?

  2. Comment déterminer le nombre minimum de pièces à retourner ?

    Réponse

    Le nombre minimum de pièces est égal à la plus petite longueur des listes éléments de la liste series.

Programmation dynamique (mémoïsation)

  1. Rappeler quel est l’objectif de la programmation dynamique.

    Réponse
    À retenir

    La programmation dynamique, comme la méthode diviser-pour-régner, résout des problèmes en combinant des solutions de sous-problèmes.

    • Les algorithmes diviser-pour-régner partitionnent le problème en sous-problèmes indépendants qu’ils résolvent récursivement, puis combinent leurs solutions pour résoudre le problème initial.
    • La programmation dynamique, quant à elle, peut s’appliquer même lorsque les sous-problèmes ne sont pas indépendants, c’est-à-dire lorsque des sous-problèmes ont des sous-sous-problèmes communs. Dans ce cas, un algorithme diviser-pour-régner fait plus de travail que nécessaire, en résolvant plusieurs fois le sous-sous-problème commun. Un algorithme de programmation dynamique résout chaque sous-sous-problème une seule fois et mémorise sa réponse dans un tableau, évitant ainsi le recalcul de la solution chaque fois que le sous-sous-problème est rencontré.

    La programmation dynamique est, en général, appliquée aux problèmes d’optimisation. Dans ce type de problèmes, il peut y avoir de nombreuses solutions possibles. Chaque solution a une valeur, et on souhaite trouver une solution ayant la valeur optimale (minimale ou maximale). Une telle solution est une solution optimale au problème, et non pas la solution optimale, puisqu’il peut y avoir plusieurs solutions qui donnent la valeur optimale.

  2. Le manque d’efficacité de la méthode force brute a pour origine les multiples calculs redondants. Mettre en œuvre la méthode de mémoïsation afin d’améliorer l’efficacité du code de la fonction nb_rendre.

Réponse
def nb_rendre(a_rendre: int, pieces: list[int]) -> int:
    """
    Détermine le nombre minimal de pièces
    à rendre.

    Algorithme récursif avec mémoïsation.
    """
    dic_a_rendre = {0: 0}

    def _nb_rendre(a_rendre: int, pieces: list[int], dic: dict[int, int]) -> int:
        """
        Version mémoïsée de la fonction nb_rendre.
        """
        if a_rendre not in dic.keys():
            nb_min = float("inf")

            for i in range(len(pieces)):
                if pieces[i] <= a_rendre:
                    nb = 1 + _nb_rendre(a_rendre - pieces[i], pieces, dic)
                    if nb <= nb_min:
                        nb_min = nb

            dic[a_rendre] = nb_min

        return dic[a_rendre]

    return _nb_rendre(a_rendre, pieces, dic_a_rendre)
Code complet

Le code se trouve à : cette adresse

Programmation dynamique (méthode tabulaire)

  1. Rappeler quel est l’objectif de la programmation dynamique.
    Réponse
    À retenir

    La programmation dynamique, comme la méthode diviser-pour-régner, résout des problèmes en combinant des solutions de sous-problèmes.

    • Les algorithmes diviser-pour-régner partitionnent le problème en sous-problèmes indépendants qu’ils résolvent récursivement, puis combinent leurs solutions pour résoudre le problème initial.
    • La programmation dynamique, quant à elle, peut s’appliquer même lorsque les sous-problèmes ne sont pas indépendants, c’est-à-dire lorsque des sous-problèmes ont des sous-sous-problèmes communs. Dans ce cas, un algorithme diviser-pour-régner fait plus de travail que nécessaire, en résolvant plusieurs fois le sous-sous-problème commun. Un algorithme de programmation dynamique résout chaque sous-sous-problème une seule fois et mémorise sa réponse dans un tableau, évitant ainsi le recalcul de la solution chaque fois que le sous-sous-problème est rencontré.

    La programmation dynamique est, en général, appliquée aux problèmes d’optimisation. Dans ce type de problèmes, il peut y avoir de nombreuses solutions possibles. Chaque solution a une valeur, et on souhaite trouver une solution ayant la valeur optimale (minimale ou maximale). Une telle solution est une solution optimale au problème, et non pas la solution optimale, puisqu’il peut y avoir plusieurs solutions qui donnent la valeur optimale.

  1. Le manque d’efficacité de la méthode force brute a pour origine les multiples calculs redondants. Mettre en œuvre la méthode de ascendante afin d’améliorer l’efficacité du code de la fonction nb_rendre.
Réponse
def nb_rendre(a_rendre: int, pieces: list[int]) -> int:
    """
    Détermine le nombre minimal de pièces
    à rendre.

    Algorithme itératif, méthode ascendante.
    """
    nbres = [float("inf")] * (a_rendre + 1)  # Tableau des valeurs
    nbres[0] = 0

    for somme in range(1, len(nbres)):
        for piece in pieces:
            if (somme - piece) >= 0:
                nbres[somme] = min(nbres[sommes], 1 + nbres[somme - piece])

    return nbres[a_rendre]

En résumé

Rendu de monnaie - Nombre de pièces à rendre - Toutes les méthodes
"""
Les mille et unes façon de rendre la monnaie.
"""


def glouton(somme: int, pieces: list[int]) -> int:
    """
    Retourne le nombre de pièces nécessaires pour
    rendre la monnaie pour somme.

    Méthode gloutonne, pièces est censé être trié
    dans le sens décroissant.
    """
    nbre = 0  # nombre de pièces à rendre

    for piece in pieces:
        nbre += somme // piece
        somme = somme % piece

    return nbre


def force_brute(somme: int, pieces: list[int]) -> int:
    """
    Retourne le nombre de pièces nécessaires pour
    rendre la monnaie pour somme.

    Méthode force brute.
    """
    if somme == 0:
        return 0

    nbre_min = float("inf")
    for piece in pieces:
        if somme - piece >= 0:
            nbre_new = 1 + force_brute(somme - piece, pieces)
            if nbre_new < nbre_min:
                nbre_min = nbre_new

    return nbre_min


def memoisation(somme: int, pieces: list[int], memo: dict[int, int] = {0: 0}) -> int:
    """
    Retourne le nombre de pièces nécessaires pour
    rendre la monnaie pour somme.

    Programmation dynamique : mémoïsation.
    """
    if somme not in memo:
        nbre_min = float("inf")
        for piece in pieces:
            if somme - piece >= 0:
                nbre_new = 1 + memoisation(somme - piece, pieces, memo)
                if nbre_new < nbre_min:
                    nbre_min = nbre_new
        memo[somme] = nbre_min

    return memo[somme]


def tabulaire(somme: int, pieces: list[int]) -> int:
    """
    Retourne le nombre de pièces nécessaires pour
    rendre la monnaie pour somme.

    Programmation dynamique : méthode tabulaire.
    Fonction enveloppe.
    """
    nbre_pour_somme = [float("inf") for i in range(somme + 1)]
    nbre_pour_somme[0] = 0

    def _tabulaire(somme: int, pieces: List[int], nbre_pour_somme):
        """
        Mise en œuvre de la méthode tabulaire.
        """
        for somme_a_rendre in range(1, somme + 1):
            for piece in pieces:
                if somme_a_rendre - piece >= 0:
                    nbre = 1 + nbre_pour_somme[somme_a_rendre - piece]

                    if nbre < nbre_pour_somme[somme_a_rendre]:
                        nbre_pour_somme[somme_a_rendre] = nbre

        return nbre_pour_somme[somme]

    return _tabulaire(somme, pieces, nbre_pour_somme)


if __name__ == "__main__":
    somme_a_rendre = 60
    pieces = [25, 20, 1]

    nbres_pieces = glouton(somme_a_rendre, pieces)
    print(f"Méthode gloutonne pour rendre {somme_a_rendre} : {nbres_pieces} pieces.")

    nbres_pieces = force_brute(somme_a_rendre, pieces)
    print(f"Méthode force-brute pour rendre {somme_a_rendre} : {nbres_pieces} pieces.")

    nbres_pieces = memoisation(somme_a_rendre, pieces)
    print(f"Méthode mémoïsation pour rendre {somme_a_rendre} : {nbres_pieces} pieces.")

    nbres_pieces = tabulaire(somme_a_rendre, pieces)
    print(f"Méthode tabulaire pour rendre {somme_a_rendre} : {nbres_pieces} pieces.")