Détecter l'échec du glouton
Exercice de TD · niveau 2 · NSI (terminale), chapitre 8 — Les algorithmes gloutons
Énoncé
Détecter l'échec du glouton.
Pour un système de pièces donné et une somme, on veut comparer le nombre de pièces du glouton avec le nombre minimal réel. Écrire minimum_pieces(systeme, somme) par programmation dynamique, puis tester sur le système avec .
Corrigé
On construit un tableau dp où dp[k] est le nombre minimal de pièces pour rendre .
def minimum_pieces(systeme, somme):
INF = float("inf")
dp = [0] + [INF] * somme
for k in range(1, somme + 1):
for v in systeme:
if v <= k and dp[k - v] + 1 < dp[k]:
dp[k] = dp[k - v] + 1
return dp[somme]
print(minimum_pieces([1, 3, 4], 6)) # 2 (3 + 3)
# Le glouton donnerait 3 pieces (4 + 1 + 1)Les autres exercices de ce chapitre Le cours du chapitre
Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.