Numérique et sciences informatiques (spécialité) · Première

Algorithmes gloutons : cours de NSI en Première

Publié le 6 novembre 2026 · Mis à jour le 6 novembre 2026 · Signaler une erreur

L'essentiel

Un algorithme glouton construit sa solution étape par étape, en prenant à chaque fois le meilleur choix local, sans jamais revenir en arrière.³
Exemple type : le rendu de monnaie. On répète le choix de la plus grande pièce qui ne dépasse pas la somme restante, jusqu'à obtenir un reste nul.³²
L'avantage principal est la facilité de mise en œuvre, mais le résultat n'est pas toujours optimal.²
Avec le système (1, 3, 4), le glouton rend 6 par 4+1+1 alors que 3+3 est meilleur : un seul contre-exemple suffit à montrer qu'un glouton n'est pas optimal.³
Quand le glouton peut échouer, on parle d'heuristique gloutonne.³

Introduction : choisir sans regarder trop loin

Tu es à la caisse d'une boulangerie et tu dois rendre 37 centimes. Sans y réfléchir, tu prends la plus grosse pièce possible, puis la plus grosse pièce possible avec ce qui reste, et ainsi de suite. Cette façon de faire est celle d'un algorithme glouton. D'ailleurs, sans s'en rendre compte, presque tout le monde applique un algorithme glouton dans la vie courante.²

Dans ce cours, tu vas voir ce qu'est exactement un algorithme glouton, comment l'écrire en Python, et surtout pourquoi il faut se méfier : il est simple à écrire, mais il ne donne pas toujours la meilleure solution.²

Ce chapitre s'appuie sur ce que tu connais déjà : le parcours séquentiel d'un tableau, que tu utiliseras pour balayer la liste des pièces, et les tris par insertion et par sélection. Les tris par sélection ressemblent d'ailleurs à un esprit glouton : à chaque tour, on choisit le plus petit élément restant. Tu reverras aussi l'idée de terminaison d'une boucle, utile pour justifier qu'un algorithme s'arrête.

Le principe : un choix local à chaque étape

Cet algorithme est itératif : il répète une même action dans une boucle. À chaque tour de boucle, il fait un choix localement optimal, en espérant qu'après de nombreux tours la solution obtenue soit globalement la meilleure.³ Le mot « espérer » est important : rien ne garantit que cet espoir se réalise.²

« un choix localement optimal, dans l'espoir d'atteindre après de multiples itérations une solution globalement optimale »³

Un choix localement optimal

Pour comprendre la différence entre local et global, imagine que tu montes une colline dans le brouillard. À chaque pas, tu choisis la direction qui monte le plus. C'est un choix local. Mais tu peux arriver au sommet d'une petite bosse, alors qu'une montagne bien plus haute se trouve ailleurs. Le choix local ne voit jamais l'ensemble du paysage. Les algorithmes gloutons fonctionnent de cette manière : ils ne regardent pas en arrière, ils ne comparent pas toutes les solutions possibles.

Le problème du rendu de monnaie

Trier le systèmeClasse les valeurs de la plus grande à la plus petite
ChoisirPrends la plus grande valeur qui ne dépasse pas le reste
RetrancherAjoute la pièce à la liste et soustrais sa valeur du reste
RecommencerRépète jusqu'à ce que le reste soit nul

Les étapes du rendu de monnaie glouton · Déroulé de l'algorithme glouton du rendu de monnaie.

ExempleRendre 37 centimes avec le système européen

Les pièces européennes, comptées en centimes, valent 1, 2, 5, 10, 20, 50, 100 et 200.³ Déroulons l'algorithme pour 37.

Étape	Somme restante	Plus grande pièce possible	Reste après
1	37	20	17
2	17	10	7
3	7	5	2
4	2	2	0

Le résultat est $37 = 20 + 10 + 5 + 2$ , soit 4 pièces.³ Les pièces de 200, 100 et 50 ont été écartées dès la première étape parce qu'elles dépassent 37.

Écrire l'algorithme en Python

On veut écrire une fonction qui prend en entrée la somme à rendre ainsi que le système de pièces, puis qui retourne, sous forme de liste, les pièces retenues par le glouton.² Le système est fourni sous forme d'une liste triée par ordre décroissant. C'est ici que tu utilises ton parcours séquentiel de tableau.

MéthodeUne première version

def rendu_glouton(somme, systeme):
    """Renvoie la liste des pièces choisies par le glouton.
    systeme : valeurs rangées de la plus grande à la plus petite."""
    pieces = []
    reste = somme
    for valeur in systeme:
        while reste >= valeur:
            pieces.append(valeur)
            reste = reste - valeur
    return pieces

Pour tester :

>>> rendu_glouton(37, [200, 100, 50, 20, 10, 5, 2, 1])
[20, 10, 5, 2]

Comment lire ce code ? La boucle for parcourt les valeurs de la plus grande à la plus petite. Pour chaque valeur, la boucle while ajoute autant de pièces de cette valeur qu'il est possible, tant que le reste le permet. Quand on passe à la valeur suivante, on ne revient plus en arrière : c'est la marque du choix glouton.

La variable reste est la somme encore à rendre. Elle diminue à chaque pièce ajoutée. Comme chaque valeur de pièce est un entier strictement positif, reste décroît strictement dans la boucle while, qui s'arrête donc forcément : c'est la terminaison.

RemarqueVariante avec division entière

On peut éviter la boucle while avec la division entière. Pour une valeur donnée, reste // valeur donne le nombre de pièces à prendre, et reste % valeur donne ce qui reste après :

def rendu_glouton_div(somme, systeme):
    pieces = []
    reste = somme
    for valeur in systeme:
        nombre = reste // valeur
        pieces.extend([valeur] * nombre)
        reste = reste % valeur
    return pieces

Ces versions donnent le même résultat. Choisis celle que tu comprends le mieux, l'essentiel est de savoir expliquer pourquoi elle fonctionne.

Un glouton n'est pas toujours optimal

Quand l'algorithme ne fournit pas systématiquement la solution optimale, on l'appelle une heuristique gloutonne.³ Une heuristique est une méthode qui donne souvent une bonne réponse, sans garantie d'obtenir la meilleure.

Glouton et solution optimale selon le système
Système	Somme	Résultat du glouton	Meilleure solution
1, 2, 5, 10, 20, 50, 100, 200	37	20 + 10 + 5 + 2 (4 pièces)	Identique : glouton optimal
1, 3, 4	6	4 + 1 + 1 (3 pièces)	3 + 3 (2 pièces)
1, 3, 6, 12, 24, 30	49	30 + 12 + 6 + 1 (4 pièces)	24 + 24 + 1 (3 pièces)

Glouton et solution optimale selon le système · Dans les deux derniers cas, le glouton n'est pas optimal.

Systèmes canoniques : quand le glouton réussit

Un autre exemple : les fractions égyptiennes

Le principe glouton ne sert pas qu'à rendre la monnaie. Il apparaît aussi en mathématiques, pour écrire un nombre rationnel comme somme de fractions unitaires (de numérateur 1) toutes différentes. Par exemple, $\frac{5}{6} = \frac{1}{2} + \frac{1}{3}$ .⁴

Cette méthode gloutonne a été redécouverte plusieurs fois par des mathématiciens modernes, d'abord par James Joseph Sylvester en 1880.⁴ Le résultat qu'elle produit porte le nom de développement égyptien glouton, ou développement de Sylvester.⁴ Tu n'as pas à connaître ces noms pour le programme, mais ils montrent qu'une idée algorithmique simple peut traverser les siècles.

Méthode : reconnaître et rédiger un glouton

Bilan et lien avec la suite

Dans la suite du programme, tu rencontreras l'algorithme des k plus proches voisins, qui repose lui aussi sur une boucle et sur des choix successifs, et tu approfondiras la notion de coût d'un algorithme, déjà vue avec les tris. Elle te permettra de comparer des algorithmes sur leur efficacité, pas seulement sur la qualité de leur résultat. Le glouton est justement un bon exemple de compromis : il est simple, mais pas toujours exact.

Exercices corrigés

Exercice 1 Rendre 88 centimes

★☆☆Environ 8 min

On utilise le système de pièces (en centimes) 1, 2, 5, 10, 20, 50. Déroule l'algorithme glouton pour rendre 88 centimes. Combien de pièces l'algorithme rend-il ?

Indice 1

Commence par la plus grande valeur qui ne dépasse pas 88.

Indice 2

Note le reste après chaque pièce et recommence avec ce reste.

Voir la correction pas à pas

Reste 88 : la plus grande valeur permise est 50. Il reste $88 - 50 = 38$ .
Reste 38 : on prend 20. Il reste 18.
Reste 18 : on prend 10. Il reste 8.
Reste 8 : on prend 5. Il reste 3.
Reste 3 : on prend 2. Il reste 1.
Reste 1 : on prend 1. Il reste 0, l'algorithme s'arrête.
La liste obtenue est $50 + 20 + 10 + 5 + 2 + 1$ , soit 6 pièces.

Le glouton rend 88 centimes avec 6 pièces : 50, 20, 10, 5, 2 et 1. Chaque valeur n'a été utilisée qu'une fois, car aucune n'est contenue deux fois dans le reste au moment du choix.

Exercice 2 Un glouton qui se trompe

★★☆Environ 10 min

Le système de pièces est (1, 4, 6). On veut rendre la somme 8.

Déroule l'algorithme glouton et compte les pièces.
Trouve une meilleure décomposition de 8.
De combien de pièces le glouton dépasse-t-il l'optimum ?

Indice 1

Le glouton commence par 6. Que reste-t-il ensuite ?

Indice 2

Cherche une décomposition qui n'utilise que des pièces de 4.

Voir la correction pas à pas

Reste 8 : la plus grande valeur permise est 6. Il reste 2.
Reste 2 : ni 6 ni 4 ne conviennent, on prend 1. Il reste 1.
Reste 1 : on prend 1. Il reste 0. Le glouton rend $6 + 1 + 1$ , soit 3 pièces.
Autre décomposition : $4 + 4 = 8$ , soit 2 pièces.
Le glouton utilise donc $3 - 2 = 1$ pièce de plus que l'optimum.

Le glouton rend 3 pièces alors que 2 suffisent : c'est un contre-exemple. Le système (1, 4, 6) n'est donc pas canonique. Le glouton dépasse l'optimum d'une pièce.

Exercice 3 Décomposer 4/5 en fractions unitaires

★★☆Environ 12 min

Applique l'algorithme glouton de décomposition en fractions unitaires à $\frac{4}{5}$ . À chaque étape, tu choisis la plus grande fraction unitaire qui ne dépasse pas le reste. Quel est le dénominateur de la dernière fraction obtenue ?

Indice 1

La plus grande fraction unitaire qui ne dépasse pas $\frac{4}{5}$ est $\frac{1}{2}$ .

Indice 2

Compare le reste $\frac{3}{10}$ aux fractions $\frac{1}{3}$ et $\frac{1}{4}$ .

Voir la correction pas à pas

$\frac{1}{1}$ est trop grand ; $\frac{1}{2} \le \frac{4}{5}$ . On prend $\frac{1}{2}$ .
Le reste vaut $\frac{4}{5} - \frac{1}{2} = \frac{8}{10} - \frac{5}{10} = \frac{3}{10}$ .
Compare avec $\frac{1}{3}$ : $\frac{1}{3} \approx 0{,}333$ dépasse $\frac{3}{10} = 0{,}3$ . La fraction $\frac{1}{4} = 0{,}25$ convient. On prend $\frac{1}{4}$ .
Le reste vaut $\frac{3}{10} - \frac{1}{4} = \frac{6}{20} - \frac{5}{20} = \frac{1}{20}$ .
Ce reste est une fraction unitaire : on s'arrête. Vérification : $\frac{10}{20} + \frac{5}{20} + \frac{1}{20} = \frac{16}{20} = \frac{4}{5}$ .

On obtient $\frac{4}{5} = \frac{1}{2} + \frac{1}{4} + \frac{1}{20}$ . La dernière fraction a pour dénominateur 20.

Exercice 4 Écrire et tester une fonction

★★★Environ 15 min

Écris une fonction nombre_pieces(somme, systeme) qui renvoie le nombre de pièces utilisées par l'algorithme glouton (le système est une liste triée par ordre décroissant).
Écris une fonction glouton_optimal(somme, systeme) qui renvoie True si le glouton rend la somme avec un nombre de pièces minimal. Pour cela, compare avec une recherche exhaustive sur de petites sommes.
Explique pourquoi un test sur quelques sommes ne suffit pas à conclure qu'un système est canonique.

Indice 1

Tu peux réutiliser rendu_glouton et appliquer len à la liste renvoyée.

Indice 2

Pour la recherche du minimum, calcule pour chaque montant de 0 à somme le plus petit nombre de pièces, en testant chaque valeur du système.

Voir la correction pas à pas

Première fonction : def nombre_pieces(somme, systeme): return len(rendu_glouton(somme, systeme)).
Pour la seconde, on construit un tableau meilleur de taille somme + 1, avec meilleur[0] = 0.
Pour chaque montant m de 1 à somme, on prend le minimum de meilleur[m - v] + 1 pour chaque valeur v du système avec v <= m.
glouton_optimal renvoie nombre_pieces(somme, systeme) == meilleur[somme].
Ce test ne couvre que les sommes essayées. Pour le système (1, 3, 4), toutes les sommes de 1 à 5 sont bien rendues, et la première qui échoue est 6. Un test limité à de petites sommes aurait donc conclu à tort.

Une fonction qui compare le glouton à une recherche exhaustive trouve des contre-exemples, mais elle ne prouve l'optimalité que pour les sommes testées. Pour un système donné, il faut un argument général pour affirmer qu'il est canonique.

Les questions qu'on se pose

Pourquoi dit-on « glouton » ?

Parce que l'algorithme se jette à chaque étape sur la meilleure part immédiate, sans réfléchir à la suite. On parle aussi d'algorithme gourmand ou goulu, et en anglais de greedy algorithm.³ Le nom décrit le comportement : prendre le plus possible tout de suite.

Comment savoir si un glouton est optimal pour un problème donné ?

Il n'existe pas de réponse automatique : cela dépend du problème et des données. Pour un système de pièces, le système européen est un cas où le glouton est toujours optimal, tandis que (1, 3, 4) ne l'est pas.³ Dans un exercice, deux cas se présentent : soit tu cherches un contre-exemple, soit on t'indique que le système est canonique. Réussir sur quelques exemples ne prouve rien.

Quel est l'intérêt d'un glouton, s'il peut se tromper ?

Il est très facile à écrire et à comprendre.² Quand on ne sait pas trouver la meilleure solution simplement, il donne une solution acceptable, appelée heuristique gloutonne lorsque l'optimalité n'est pas garantie.³ Dans certains systèmes, comme le système européen, il donne même toujours la meilleure solution.³

Que peut-on te demander sur les algorithmes gloutons en NSI ?

Les sujets portent souvent sur le rendu de monnaie : écrire ou compléter une fonction en Python qui renvoie la liste des pièces choisies,² dérouler l'algorithme sur un exemple, ou trouver un contre-exemple qui montre que le résultat n'est pas toujours optimal.² Entraîne-toi à rédiger un contre-exemple complet : système, somme, résultat du glouton, meilleure solution.

Un glouton revient-il en arrière s'il se rend compte qu'il s'est trompé ?

Non. Un choix fait n'est jamais remis en cause : l'algorithme avance étape par étape avec des choix locaux.³ C'est ce qui le rend simple, mais c'est aussi la cause de ses échecs, comme pour 6 avec le système (1, 3, 4), où le choix de 4 conduit à 4 + 1 + 1.³

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.

Signaler une erreur sur cette page

Algorithmes gloutons : cours de NSI en Première

L'essentiel

Introduction : choisir sans regarder trop loin

Le principe : un choix local à chaque étape

Le problème du rendu de monnaie

Écrire l'algorithme en Python

Un glouton n'est pas toujours optimal

Systèmes canoniques : quand le glouton réussit

Un autre exemple : les fractions égyptiennes

Méthode : reconnaître et rédiger un glouton

Bilan et lien avec la suite

Exercices corrigés

Exercice 1 Rendre 88 centimes

Exercice 2 Un glouton qui se trompe

Exercice 3 Décomposer 4/5 en fractions unitaires

Exercice 4 Écrire et tester une fonction

Quiz

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur