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.
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 :
deffact_env(n:int)->int:"""
Retourne la factorielle de n.
Algorithme : récursivité enveloppée
"""
Réponse
deffact_env(n:int)->int:"""
Retourne la factorielle de n.
Algorithme : récursivité enveloppée
"""ifn==0:return1returnn*fact_env(n-1)if__name__=="__main__":assertfact_env(0)==1assertfact_env(1)==1assertfact_env(5)==120assertfact_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
Définir la fonction fact_term qui calcule la factorielle d’un entier naturel n, sans oublier le jeu de tests.
La spécification de la fonction est :
deffact_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
deffact_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.
"""ifn==0:returnaccreturn_fact(n-1,acc*n)return_fact(n,1)if__name__=="__main__":assertfact_term(0)==1assertfact_term(1)==1assertfact_term(5)==120assertfact_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−2
Résolutions du problème sans programmation dynamique
Définir la fonction fibo_iter qui calcule le terme de rang n 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 :
deffibo_iter(n:int)->int:"""
Retourne le terme de rang n de la suite de Fibonacci.
Algorithme : itératif
"""
Réponse
deffibo_iter(n:int)->int:"""
Retourne le terme de rang n de la suite de Fibonacci.
Algorithme : itératif
"""u=0v=1foriinrange(2,n+1):w=u+vu=vv=wifn==0:return0else:returnvif__name__=="__main__":# fibo_iterassertfibo_iter(0)==0assertfibo_iter(1)==1assertfibo_iter(10)==55assertfibo_iter(16)==987
Quelle est la complexité de l’algorithme itératif ?
Réponse
L’algorithme comporte une boucle, la complexité est donc en O(n).
Définir la fonction fibo_head qui calcule le terme de rang n 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 :
deffibo_head(n:int)->int:"""
Retourne le terme de rang n de la suite de Fibonacci.
Algorithme : récursif (enveloppé)
"""
Réponse
deffibo_head(n:int)->int:"""
Retourne le terme de rang n de la suite de Fibonacci.
Algorithme : récursif (enveloppé)
"""ifn==0:return0elifn==1:return1fibo1=fibo_head(n-1)fibo2=fibo_head(n-2)returnfibo1+fibo2if__name__=="__main__":assertfibo_head(0)==0assertfibo_head(1)==1assertfibo_head(10)==55assertfibo_head(16)==987
Écrire l’arbre des appels récursifs pour n=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−1.
Si chaque étape est en O(1), le nombre de calculs effectués est donc 20+21+22+23+…+2n−1=2n.
La complexité est donc en O(2n).
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 n de la suite de Fibonacci à l’aide d’un algorithme récursif terminal.
La spécification de la fonction fib_tail est :
deffibo_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
deffibo_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):ifn==0:returnaelifn==1:returnbreturn_fibo_tail(n-1,b,a+b)return_fibo_tail(n)if__name__=="__main__":assertfibo_tail(0)==0assertfibo_tail(1)==1assertfibo_tail(10)==55assertfibo_tail(16)==987
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). On a donc T(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 n 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éestocke 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
Quel est l’intérêt des structures de données tableau ou dictionnaire pour le stockage des valeurs des sous-problèmes ?
Écrire l’arbre des appels récursifs pour n=5, lorsque la technique de mémoïsation est mise en œuvre. Le comparer à l’arbre obtenu à la question 6.
Réponse
Définir la fonction fibo_memo qui calcule le terme de rang n 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
deffibo_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:ifnindic.keys():returndic[n]else:dic[n]=_fibo(n-1,dic)+_fibo(n-2,dic)returndic[n]return_fibo(n,dic)
ou
deffibo_memo2(n:int,tab:list[int]=[0,1])->int:"""
Version mémoïsée de Fibonacci.
Utilisation d'une liste.
"""ifn<len(tab):returntab[n]calcul=fibo_memo2(n-1,tab)+fibo_memo2(n-2,tab)tab.append(calcul)returncalcul
Quelle est la complexité de l’algorithme avec mémoïsation ?
Réponse
Définir la fonction fibo_up qui calcule le terme de rang n 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
deffibo_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]foriinrange(2,n+1):valeur=tab[i-2]+tab[i-1]tab.append(valeur)returntab[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.
Déterminer la relation de récurrence, sachant que l’on note un le nombre de méthodes permettant d’atteindre la nième marche.
Réponse
un=⎩⎨⎧u1u2u3un=1=2=4=un−1+un−2+un−3
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.
Proposer une version itérative du calcul de un.
defnbre_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
defnbre_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,4foriinrange(4,n+1):z=u+v+wu=vv=ww=zifn==1:return1elifn==2:return2elifn==3:return4else:returnw
Proposer une version récursive du calcul de un.
defnbre_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
defnbre_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.
"""ifn==1:return1elifn==2:return2elifn==3:return4return(nbre_methodes_rec(n-1)+nbre_methodes_rec(n-2)+nbre_methodes_rec(n-3))
Proposer une version récursive efficace du calcul de un qui utilise la mémoïsation.
defnbre_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
defnbre_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:ifninmemo.keys():returnmemo[n]else:memo[n]=_nbre(n-1)+_nbre(n-2)+_nbre(n-3)returnmemo[n]return_nbre(n)
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.
Préparer le code suivant et étudier sa structure :
if__name__=="__main__":# valeurs des piècespieces=[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]}"foriinrange(len(pieces))]print(f"Je dois rendre : {a_rendre}")print(f"Je donne donc : {reponse}")
Définir la fonction somme_a_rendre dont la spécification est :
defsomme_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
defsomme_a_rendre(prix:int,montant_client:int)->int:"""
Détermine la somme à rendre à partir du prix et
du montant donné par le client.
"""returnmontant_client-prix
Définir la fonction pieces_a_rendre dont la spécification est :
defpieces_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
defpieces_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=[]foriinrange(len(pieces)-1,-1,-1):nbre=somme//pieces[i]somme=somme%pieces[i]a_rendre.append(nbre)returnlist(reversed(a_rendre))defpieces_a_rendre_2(somme:int,pieces:list[int]):a_rendre={}i=len(pieces)-1whilesomme>0:nbre=somme//pieces[i]somme=somme%pieces[i]a_rendre[pieces[i]]=nbrei=i-1returna_rendredefpieces_a_rendre_3(somme:int,pieces:list[int])->list[int]:a_rendre=[0]*len(pieces)i=len(pieces)-1whilesomme>0:nbre=somme//pieces[i]somme=somme%pieces[i]a_rendre[i]=nbrei=i-1returnlist(reversed(a_rendre))
On note nb le nombre de pièces à rendre, prises dans la liste des pièces p=[1,2,5,10,20,50,100,200,500], lorsque la somme à rendre est x.
Écrire la relation de récurrence que doit vérifier nb.
Réponse
nb(x)={01+nb(x−p[i]) si x=0 si x−p[i]⩾0
En fait, on cherche le nombre minimal de pièces à rendre pour la somme x.
Adapter la relation de récurrence.
Réponse
nb(x)={01+min(nb(x−p[i])) si x=0 si x−p[i]⩾0 et i∈[0,len(p)[
Écrire le schéma des appels récursifs pour x=11 et p=[2,5,10].
Réponse
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.
Réfléchir au code de la fonction dont la spécification est :
defnb_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
defnb_rendre(a_rendre:int,pieces:list[int])->int:"""
Détermine le nombre minimal de pièces
à rendre.
Algorithme récursif.
"""ifa_rendre==0:return0nb_min=float("inf")foriinrange(len(pieces)):ifpieces[i]<=a_rendre:nb=1+nb_rendre(a_rendre-pieces[i],pieces)ifnb<=nb_min:nb_min=nbreturnnb_min
Tester le code pour une somme à rendre de 13 puis de 130. Le résultat confirme-t-il la réponse à la question 4 ?
On souhaite maintenant écrire le code de la fonction pieces_a_rendre dont la spécification est :
defpieces_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
defpieces_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.
"""ifsomme==0:series.append(serie)returnNoneforpieceinpieces:ifpiece>somme:continue# Sauvegarde de la liste des pièces pour le retour arrièreserie_sauv=list(serie)serie.append(piece)pieces_a_rendre(somme-piece,pieces,serie,series)serie=serie_sauv
Tester le code pour une somme à rendre de 13 puis de 130. Obtient-on rapidement un résultat pour cette dernière valeur ?
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)
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.
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
defnb_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.
"""ifa_rendrenotindic.keys():nb_min=float("inf")foriinrange(len(pieces)):ifpieces[i]<=a_rendre:nb=1+_nb_rendre(a_rendre-pieces[i],pieces,dic)ifnb<=nb_min:nb_min=nbdic[a_rendre]=nb_minreturndic[a_rendre]return_nb_rendre(a_rendre,pieces,dic_a_rendre)
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.
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
defnb_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 valeursnbres[0]=0forsommeinrange(1,len(nbres)):forpieceinpieces:if(somme-piece)>=0:nbres[somme]=min(nbres[sommes],1+nbres[somme-piece])returnnbres[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.
"""defglouton(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 à rendreforpieceinpieces:nbre+=somme//piecesomme=somme%piecereturnnbredefforce_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.
"""ifsomme==0:return0nbre_min=float("inf")forpieceinpieces:ifsomme-piece>=0:nbre_new=1+force_brute(somme-piece,pieces)ifnbre_new<nbre_min:nbre_min=nbre_newreturnnbre_mindefmemoisation(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.
"""ifsommenotinmemo:nbre_min=float("inf")forpieceinpieces:ifsomme-piece>=0:nbre_new=1+memoisation(somme-piece,pieces,memo)ifnbre_new<nbre_min:nbre_min=nbre_newmemo[somme]=nbre_minreturnmemo[somme]deftabulaire(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")foriinrange(somme+1)]nbre_pour_somme[0]=0def_tabulaire(somme:int,pieces:List[int],nbre_pour_somme):"""
Mise en œuvre de la méthode tabulaire.
"""forsomme_a_rendreinrange(1,somme+1):forpieceinpieces:ifsomme_a_rendre-piece>=0:nbre=1+nbre_pour_somme[somme_a_rendre-piece]ifnbre<nbre_pour_somme[somme_a_rendre]:nbre_pour_somme[somme_a_rendre]=nbrereturnnbre_pour_somme[somme]return_tabulaire(somme,pieces,nbre_pour_somme)if__name__=="__main__":somme_a_rendre=60pieces=[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.")