Numérique et sciences informatiques (spécialité) · Première
Algorithmes gloutons : quiz de NSI en Première
Publié le 6 novembre 2026 · Mis à jour le 6 novembre 2026 · Signaler une erreur
L'essentiel
- Un algorithme glouton fait, à chaque étape, le choix qui semble le meilleur sur le moment, dans l'espoir d'obtenir un bon résultat final. 3
- Pour rendre la monnaie, il retient la plus grosse pièce qui rentre dans ce qu'il reste à rendre, puis recommence jusqu'à zéro. 3 2
- Il est simple à programmer, mais son résultat n'est pas toujours optimal. 2
- Avec les pièces européennes il est optimal ; avec le système (1, 3, 4), le cas de 6 le met en échec. 3
- Un seul contre-exemple suffit pour prouver qu'un algorithme glouton n'est pas optimal sur un système donné.
Avant de commencer
Ce quiz couvre le chapitre sur les algorithmes gloutons, l'un des algorithmes au programme de NSI en Première, dans la continuité des tris et de la recherche dichotomique. Tu y croiseras la définition du principe glouton, le problème du rendu de monnaie, les systèmes de pièces où la méthode réussit ou échoue, et la manière de reconnaître un contre-exemple.
Quiz
14 questions · correction immédiate · ton score reste sur ton appareil.
-
Un algorithme glouton réalise, étape par étape, un choix localement optimal dans l'espoir d'atteindre une solution globalement optimale. 3 Tester toutes les solutions est une autre approche, plus coûteuse : elle ne fait aucun pari sur le choix local. Le découpage en moitiés évoque la recherche dichotomique, et le hasard n'a aucune place dans un algorithme glouton.
-
À chaque tour, on retient la plus grosse pièce qui rentre dans ce qu'il reste à rendre. 3 Prendre la plus petite pièce donnerait énormément de pièces. Prendre une pièce trop grosse est impossible : on rendrait plus que la somme due.
-
Le glouton décompose 37 en 20 + 10 + 5 + 2, soit 4 pièces. 3 On prend 20 (reste 17), puis 10 (reste 7), puis 5 (reste 2), puis 2 (reste 0). L'erreur fréquente est de compter les valeurs au lieu des pièces : la réponse est le nombre de pièces, pas la somme.
-
Le glouton prend d'abord 4, la plus grande pièce qui ne dépasse pas 6, puis il reste 2 : il faut alors 1 + 1. Il renvoie donc 4 + 1 + 1. 3 La décomposition 3 + 3 est meilleure, mais ce n'est pas celle que le glouton trouve. Une soustraction n'a pas de sens dans un rendu de monnaie.
-
La décomposition 3 + 3 utilise 2 pièces, alors que le glouton en utilise 3 avec 4 + 1 + 1. 3 Ce contre-exemple prouve que le glouton n'est pas optimal avec ce système. On ne peut pas descendre à une seule pièce, car aucune pièce ne vaut 6.
-
Lorsque l'algorithme ne donne pas toujours la solution optimale, on parle d'heuristique gloutonne. 3 Un algorithme exhaustif teste toutes les possibilités, ce qui est une tout autre idée. « Récursif » décrit la manière d'écrire un algorithme (il s'appelle lui-même), pas la qualité de son résultat.
-
Le glouton prend 30 (reste 19), puis 12 (reste 7), puis 6 (reste 1), puis 1 : soit 30 + 12 + 6 + 1, donc 4 pièces. 2 Si tu as trouvé moins, tu as probablement cherché une meilleure décomposition au lieu de dérouler l'algorithme : ici on te demande ce que fait le glouton.
-
La décomposition 24 + 24 + 1 vaut bien 49 et n'utilise que 3 pièces, alors que le glouton en utilise 4. 2 Deux pièces ne suffisent pas : aucune somme de deux valeurs du système ne donne 49. Ce système n'est donc pas de ceux où le glouton répond de façon optimale.
-
On recommence tant qu'il reste quelque chose à rendre et on s'arrête dès que la somme restante est égale à zéro. 2 Chaque pièce peut être reprise plusieurs fois, donc la liste des pièces ne se vide pas. Aucune limite de dix pièces n'existe, et la pièce de valeur 1 sert justement à finir le rendu.
-
On prend 50 (reste 13), puis 10 (reste 3), puis 2 (reste 1), puis 1. 3 La deuxième proposition n'applique pas la règle de la plus grande pièce, la troisième prend 5 alors que 10 convient encore, et la quatrième prend trois pièces de 1 au lieu d'une pièce de 2 puis une de 1.
-
La fraction 1 dépasse 5/6, donc elle est exclue. La plus grande fraction de numérateur 1 qui reste inférieure à 5/6 est 1/2. Il reste alors 5/6 − 1/2 = 1/3, d'où 5/6 = 1/2 + 1/3. 4 Choisir 1/3 ou 1/6 en premier ne respecterait pas la règle de la plus grande fraction possible.
-
C'est vrai : être optimal signifie l'être pour toutes les sommes, donc un seul contre-exemple suffit. C'est le rôle de la somme 6 avec le système (1, 3, 4) : le glouton donne 4 + 1 + 1, alors que 3 + 3 est meilleur. 3 À l'inverse, vérifier quelques sommes réussies ne prouve jamais l'optimalité.
Les questions qu'on se pose
Comment savoir si un algorithme glouton donne la solution optimale ?
On ne peut pas le deviner : cela dépend du problème et, pour le rendu de monnaie, du système de pièces. Avec le système européen, on peut montrer que le glouton est toujours optimal. 3 Avec les systèmes (1, 3, 4) ou {1, 3, 6, 12, 24, 30}, il ne l'est pas. 3 2 La démarche à retenir : cherche un contre-exemple, c'est-à-dire une somme pour laquelle une autre décomposition utilise moins de pièces.
Pourquoi utiliser un algorithme glouton s'il peut se tromper ?
Parce qu'il se programme facilement. 2 Quand le problème s'y prête, comme pour le rendu de monnaie avec les pièces européennes, il donne la meilleure solution sans calcul compliqué. Quand il ne la garantit pas, on parle d'heuristique gloutonne : le résultat reste souvent correct, mais sans garantie. 3
Quelle différence entre le choix « local » et le résultat « global » ?
Le choix local concerne une seule étape : prendre la plus grosse pièce possible sur la somme restante. Le résultat global concerne la solution complète : le nombre total de pièces rendues. Un algorithme glouton cherche l'optimum global en enchaînant des choix optimaux locaux. 3 Le piège est qu'un bon choix local peut mener à un mauvais total, comme 4 + 1 + 1 pour la somme 6 avec les pièces (1, 3, 4). 3
Sources
Programme visé : Programmes et ressources en numérique et sciences informatiques - Voie générale (Première) · Ministère de l'Éducation nationale (Éduscol)
- Programmes et ressources en numérique et sciences informatiques - Voie générale (Première), Ministère de l'Éducation nationale (Éduscol). Consulté le 6 novembre 2026.
- Algorithmes gloutons — Document Éduscol, Éduscol. Consulté le 6 novembre 2026.
- Algorithme glouton, Wikipédia. Consulté le 6 novembre 2026.
- Algorithme glouton pour la décomposition en fractions égyptiennes, Wikipédia. Consulté le 6 novembre 2026.
Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.