Informatique · Première · 2 exercices vérifiés
S’entraîner : Algorithmes gloutons
Chapitre : Numérique et sciences informatiques (spécialité)
Ce que vous travaillez
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).
À maîtriser avant de commencer
Ces notions sont utilisées ici. Relisez-les si l’une d’elles vous échappe.
- Parcours séquentiel d'un tableau — Parcourir un tableau élément par élément pour rechercher une occurrence, un extremum (maximum, minimum) ou calculer une moyenne ; le coût est linéaire : le nombre d'opérations est proportionnel à la longueur du tableau, et une recherche d'occurrence examine tout le tableau dans le pire cas.
Comment se déroule la séance
Cette séance s’appuie sur 2 exercices vérifiés. Chacun produit un nouvel énoncé à chaque ouverture, avec une solution calculée.
Formats de réponse : Réponse numérique (1), Vrai ou faux (1). Difficulté de 2 à 3 sur 5. Environ 8 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é 2 sur 5 · ≈ 4 minutes
Énoncé
La fonction ci-dessous rend la monnaie de façon gloutonne : elle prend toujours la plus grande pièce possible. Les pièces sont rangées par valeur décroissante.
| n° | Instruction |
|---|---|
| 1 | def rendu(somme, pieces): |
| 2 | ····n = 0 |
| 3 | ····for p in pieces: |
| 4 | ········while somme >= p: |
| 5 | ············somme = somme - p |
| 6 | ············n = n + 1 |
| 7 | ····return n |
| 8 | print(rendu(19, [10, 5, 2, 1])) |
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.