Informatique · Terminale · 1 exercice vérifié
S’entraîner : Programmation dynamique
Chapitre : Numérique et sciences informatiques (spécialité)
Ce que vous travaillez
Résoudre un problème en combinant les solutions de sous-problèmes qui se chevauchent, chacune calculée une seule fois et mémorisée (de haut en bas avec mémoïsation, ou de bas en haut en remplissant un tableau) ; exemples du rendu de monnaie optimal (nombre minimal de pièces) et de l'alignement de séquences ; coût en mémoire de la table.
À maîtriser avant de commencer
Ces notions sont utilisées ici. Relisez-les si l’une d’elles vous échappe.
- Programmes récursifs — Une fonction récursive s'appelle elle-même sur une donnée plus petite ; elle comporte au moins un cas de base, traité sans appel récursif, qui garantit l'arrêt ; analyser un appel par la pile des appels ou l'arbre des appels ; compter les appels effectués ; écrire une version récursive d'un calcul (factorielle, puissance, somme des chiffres).
- Algorithmes gloutons — Un algorithme glouton construit une solution pas à pas en faisant à chaque étape le choix qui paraît le meilleur sur le moment, sans revenir en arrière ; rendu de monnaie (rendre la plus grande pièce possible), problème du sac à dos ; la solution obtenue n'est pas toujours optimale : elle l'est pour le rendu de monnaie avec les pièces et billets en euros, pas avec un système comme (1, 3, 4).
- Dictionnaires par clés et valeurs — Un dictionnaire associe des valeurs à des clés uniques : lecture d'une valeur par sa clé, ajout ou modification d'une entrée, test d'appartenance d'une clé ; itération sur les clés, les valeurs ou les couples avec keys(), values() et items().
Comment se déroule la séance
Cette séance s’appuie sur 1 exercice vérifié. Chacun produit un nouvel énoncé à chaque ouverture, avec une solution calculée.
Formats de réponse : Réponse numérique (1). Difficulté 4 sur 5. Environ 6 minutes pour un premier passage.
Dans votre compte : aide graduée (indice, rappel de cours, aide au démarrage), corrigé pas à pas après chaque tentative, suivi de vos progrès.
Essayez un exercice, sans compte
Un exercice réel de cette séance, le même pour chaque visiteur. Répondez, puis vérifiez : la correction est calculée, et le corrigé s’affiche après votre tentative.
Difficulté 4 sur 5 · ≈ 6 minutes
Énoncé
La fonction ci-dessous calcule par programmation dynamique le nombre minimal de pièces nécessaires pour obtenir une somme s, chaque valeur de pièce étant disponible en quantité illimitée.
| n° | Instruction |
|---|---|
| 1 | def nb_min(s, pieces): |
| 2 | ····t = [0] |
| 3 | ····for x in range(1, s + 1): |
| 4 | ········meilleur = x |
| 5 | ········for p in pieces: |
| 6 | ············if p <= x and t[x - p] + 1 < meilleur: |
| 7 | ················meilleur = t[x - p] + 1 |
| 8 | ········t.append(meilleur) |
| 9 | ····return t[s] |
| 10 | print(nb_min(21, [1, 6, 9])) |
Chaque groupe de quatre points « ···· » marque un niveau d'indentation (quatre espaces en Python).
Quel nombre ce programme affiche-t-il ?
Votre réponse
Continuez dans votre compte
Créez votre compte gratuit pour faire toute la séance avec l’aide graduée, ou connectez-vous pour revenir directement ici.
L’accès gratuit comprend les cours et exercices de votre niveau choisi.