NSI (terminale) · Chapitre 8 · Exercice de TD
Système canonique ?
Les algorithmes gloutons · niveau 3 (difficile)
Énoncé
Système canonique ?
Écrire une fonction qui teste si, pour toutes les sommes de à , le rendu glouton est optimal (c'est-à-dire utilise autant de pièces que la solution par programmation dynamique).
Corrigé
On compare la fonction gloutonne nombre_pieces et la fonction minimum_pieces obtenue par programmation dynamique sur chaque somme.
def est_canonique(systeme, N):
systeme_desc = sorted(systeme, reverse=True)
for s in range(1, N + 1):
if nombre_pieces(systeme_desc, s) != minimum_pieces(systeme, s):
return False, s # premier contre-exemple
return True, None
print(est_canonique([1, 2, 5, 10], 100)) # (True, None)
print(est_canonique([1, 3, 4], 10)) # (False, 6)100 % gratuit
Essaie le suivant avec le tuteur
- L'exercice suivant avec le tuteur, sans compte : il guide pas à pas, sans donner la réponse
- 8 autres exercices corrigés dans ce chapitre
- Les 2 QCM du chapitre, le premier sans compte
- Le podcast et la vidéo du chapitre : 2 minutes d'écoute sans compte
Sans compte : le cours, le premier QCM, 2 minutes de podcast et de vidéo et un exercice avec le tuteur. Pour tout le reste : inscription gratuite en 30 secondes, sans carte bancaire.