Exercice 1 sur 9
QCMQu’est-ce qui caractérise un algorithme glouton ?
Aide d’ULU pour cet exerciceNumérique et sciences informatiques (NSI) · Première
Exercices : les algorithmes gloutons
23 exercices avec correction détaillée, en 3 séries. Aucune inscription : ta progression reste sur ton appareil.
ULUMINE · Numérique et sciences informatiques (NSI) · Première
Les algorithmes gloutons — S’entraîner
Feuille d’exercices
Prénom : ……………………………Date : ……………………Score : ……… / 9
Rendu de monnaie et sac à dos avec la stratégie gloutonne.
Exercice 1 — Coche la bonne réponse.
Qu’est-ce qui caractérise un algorithme glouton ?
- Il essaie toutes les solutions possibles
- Il fait à chaque étape le meilleur choix immédiat, sans revenir en arrière
- Il trie toujours les données par ordre croissant
- Il donne toujours la solution optimale
Exercice 2
Avec le système de l’euro (200, 100, 50, 20, 10, 5, 2, 1), combien de pièces et billets l’algorithme glouton rend-il pour 87 € ?
Écris tes calculs :
Réponse : ………………
Exercice 3
Que renvoie rendu_monnaie(8, [5, 2, 1]) ? (Écris la liste comme Python l’affiche.)
def rendu_monnaie(somme, pieces): """pieces : valeurs disponibles, triées par ordre décroissant.""" rendu = [] for p in pieces: while somme >= p: rendu.append(p) somme = somme - p return rendu euros = [200, 100, 50, 20, 10, 5, 2, 1]Python Exercice 4
Avec des pièces de 4, 3 et 1, combien de pièces l’algorithme glouton rend-il pour la somme 6 ?
Écris tes calculs :
Réponse : ………………
Exercice 5
Avec les mêmes pièces (4, 3 et 1), quel est le nombre minimal de pièces pour rendre 6 ?
Écris tes calculs :
Réponse : ………………
Exercice 6 — Coche « Vrai » ou « Faux ».
Un algorithme glouton fournit toujours une solution optimale.
VraiFaux
Exercice 7
Sac de 10 kg ; objets A (7 kg, 42 €), B (3 kg, 12 €), C (4 kg, 40 €), D (5 kg, 25 €). Quelle valeur totale obtient le glouton qui prend les objets par rapport valeur/poids décroissant ?
Écris tes calculs :
Réponse : ……………… €
Exercice 8
Quel est le rapport valeur/poids de l’objet C (4 kg, 40 €), en euros par kilogramme ?
Écris tes calculs :
Réponse : ……………… €/kg
Exercice 9 — Complète les trous.
Complète la définition.
Un algorithme glouton fait à chaque étape le choix optimal et ne revient jamais en .
ulumine.com — exercices corrigés gratuits
ULUMINE · Numérique et sciences informatiques (NSI) · Première
Les algorithmes gloutons — S’entraîner
Corrigé détaillé — pour les parents et les enseignants
Exercice 1
Réponse : Il fait à chaque étape le meilleur choix immédiat, sans revenir en arrière
Le choix est localement optimal et définitif. C’est ce qui rend la méthode rapide, mais pas toujours optimale.
Exercice 2
Réponse : 5
87 = 50 + 20 + 10 + 5 + 2.
Exercice 3
Réponse : [5, 2, 1]
On rend 5 (reste 3), puis 2 (reste 1), puis 1 (reste 0).
Exercice 4
Réponse : 3
Il prend d’abord 4 (reste 2), puis 1 et 1 : 3 pièces.
Exercice 5
Réponse : 2
3 + 3 = 6 utilise 2 pièces : le glouton n’est donc pas optimal pour ce système.
Exercice 6
Réponse : Faux
C’est vrai pour certains problèmes (rendu en euros, planification d’activités), faux en général : le rendu avec 1, 3, 4 ou le sac à dos fournissent des contre-exemples.
Exercice 7
Réponse : 65 €
Ordre C, A, D, B : on prend C (4 kg), on refuse A (11 kg), on prend D (9 kg), on refuse B (12 kg).
- 40 + 25 = 65 €
Exercice 8
Réponse : 10 €/kg
40 ÷ 4 = 10 €/kg : c’est le meilleur rapport, donc le premier objet choisi.
Exercice 9
Réponse : localement · arrière
« Localement » : le meilleur choix à l’instant présent, sans vision d’ensemble.
Rendu de monnaie et sac à dos avec la stratégie gloutonne.
Exercices corrigés : 0 / 9
- Aide d’ULU pour cet exercice
Exercice 2 sur 9
CalculAvec le système de l’euro (200, 100, 50, 20, 10, 5, 2, 1), combien de pièces et billets l’algorithme glouton rend-il pour 87 € ?
Aide d’ULU pour cet exerciceExercice 3 sur 9
Réponse à écrireQue renvoie rendu_monnaie(8, [5, 2, 1]) ? (Écris la liste comme Python l’affiche.)
def rendu_monnaie(somme, pieces): """pieces : valeurs disponibles, triées par ordre décroissant.""" rendu = [] for p in pieces: while somme >= p: rendu.append(p) somme = somme - p return rendu euros = [200, 100, 50, 20, 10, 5, 2, 1]Python Aide d’ULU pour cet exerciceExercice 4 sur 9
CalculAvec des pièces de 4, 3 et 1, combien de pièces l’algorithme glouton rend-il pour la somme 6 ?
Aide d’ULU pour cet exerciceExercice 5 sur 9
CalculAvec les mêmes pièces (4, 3 et 1), quel est le nombre minimal de pièces pour rendre 6 ?
Aide d’ULU pour cet exerciceExercice 6 sur 9
Vrai ou fauxUn algorithme glouton fournit toujours une solution optimale.
Aide d’ULU pour cet exerciceExercice 7 sur 9
CalculSac de 10 kg ; objets A (7 kg, 42 €), B (3 kg, 12 €), C (4 kg, 40 €), D (5 kg, 25 €). Quelle valeur totale obtient le glouton qui prend les objets par rapport valeur/poids décroissant ?
Aide d’ULU pour cet exerciceExercice 8 sur 9
CalculQuel est le rapport valeur/poids de l’objet C (4 kg, 40 €), en euros par kilogramme ?
Aide d’ULU pour cet exerciceExercice 9 sur 9
Texte à trousComplète la définition.
Aide d’ULU pour cet exercice
À découvrir aussi
Première · Numérique et sciences informatiques (NSI)
Représenter les entiers : binaire, hexadécimal, complément à deux
Écrire un entier en base 2 et en base 16, passer d’une base à l’autre, coder les entiers relatifs en complément à deux : cours et exercices de NSI en Première.
Première · Numérique et sciences informatiques (NSI)
Les booléens et les expressions logiques
Valeurs booléennes, opérateurs and, or, not et ou exclusif, tables de vérité et évaluation paresseuse en Python : cours et exercices corrigés de NSI en Première.
Première · Numérique et sciences informatiques (NSI)
Les nombres flottants et l’encodage du texte
Pourquoi les flottants sont approchés, nombres à virgule en binaire, encodages ASCII, ISO-8859-1, Unicode et UTF-8 : cours et exercices de NSI en Première.