Aller au contenu
FR

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

Algorithmes gloutons : exercices corrigés de Première NSI

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

L'essentiel

  • Un algorithme glouton répète un choix localement optimal à chaque étape, dans l'espoir d'obtenir un résultat optimal global 3.
  • Pour le rendu de monnaie, on choisit à chaque fois la plus grande pièce qui ne dépasse pas la somme restante, jusqu'à obtenir une somme nulle 23.
  • Le résultat dépend du système de pièces : optimal avec 1, 2, 5, 10, 20, 50, 100, 200 ; non optimal avec 1, 3, 4 3.
  • Quand le résultat n'est pas toujours optimal, on parle d'heuristique gloutonne 3.

Comment utiliser ces exercices

Ces exercices s'appuient sur une idée simple : à chaque étape, on prend le choix qui paraît le meilleur tout de suite. Un algorithme glouton suit ce principe : il réalise, étape par étape, un choix optimal local pour obtenir un résultat optimal global 3. C'est un algorithme itératif : on répète la même règle de choix à chaque tour de boucle 3. Essaie chaque exercice sur papier avant d'ouvrir les indices, puis compare ta démarche avec la correction, étape par étape.

Deux questions à se poser à chaque exercice

Devant un problème d'optimisation, distingue toujours deux questions. La première : que fait l'algorithme glouton ? Elle demande seulement d'appliquer la règle, sans chercher mieux. La seconde : est-ce le meilleur résultat possible ? Elle demande de comparer avec d'autres solutions. Dans la vie courante, chacun applique souvent sans s'en rendre compte une stratégie gloutonne 2 : on remplit d'abord le plus gros sac, on choisit le trajet qui semble le plus court au prochain carrefour. Ce réflexe est pratique, mais il ne garantit rien.

Au-delà de la monnaie

Le rendu de monnaie n'est qu'un exemple. L'idée gloutonne sert aussi à décomposer un entier strictement positif en somme d'éléments d'un ensemble contenant le nombre 1 : on retire à chaque fois le plus grand élément possible 3. Le système de numération de Zeckendorf en est un cas particulier, où l'ensemble utilisé est celui des nombres de Fibonacci 3. Les derniers exercices de la page explorent ce prolongement, puis une autre application : la décomposition d'un nombre rationnel en fractions unitaires 4.

Les exercices

Exercice 1 Rendre 37 centimes

★☆☆Environ 5 min

On utilise le système de pièces en centimes : 1, 2, 5, 10, 20, 50, 100, 200. Un client doit recevoir 37 centimes. Applique l'algorithme glouton et donne le nombre de pièces rendues.

Indice 1

À chaque étape, prends la plus grande pièce qui ne dépasse pas la somme restante.

Indice 2

Après la première pièce, il reste 17 centimes.

Voir la correction pas à pas

  1. Plus grande pièce inférieure ou égale à 37 : 20. Il reste 37 − 20 = 17.

  2. Plus grande pièce inférieure ou égale à 17 : 10. Il reste 7.

  3. Plus grande pièce inférieure ou égale à 7 : 5. Il reste 2.

  4. Plus grande pièce inférieure ou égale à 2 : 2. Il reste 0, on s'arrête.

  5. Pièces rendues : 20 + 10 + 5 + 2, soit 4 pièces.

Le rendu est 20 + 10 + 5 + 2, soit 4 pièces. Ce résultat est optimal, car dans ce système de pièces l'algorithme glouton donne toujours une solution optimale 3.

Exercice 2 Rendre 6 avec le système (1, 3, 4)

★☆☆Environ 5 min

Le système de pièces est (1, 3, 4). On doit rendre 6.

  1. Donne le rendu produit par l'algorithme glouton.
  2. Donne un rendu qui utilise moins de pièces.
  3. Que peux-tu en conclure ?
Indice 1

Pour la question 2, cherche deux pièces identiques dont la somme vaut 6.

Voir la correction pas à pas

  1. Glouton : la plus grande pièce qui ne dépasse pas 6 est 4, il reste 2.

  2. Pour le reste 2, la plus grande pièce possible est 1 (car 3 > 2), il reste 1, puis encore 1. Rendu : 4 + 1 + 1, soit 3 pièces.

  3. Autre rendu : 3 + 3, soit 2 pièces.

  4. Comme 2 < 3, l'algorithme glouton n'est pas optimal pour ce système.

L'algorithme glouton donne 4 + 1 + 1 (3 pièces) alors que 3 + 3 (2 pièces) est meilleur 3. Un seul contre-exemple suffit pour affirmer que le glouton n'est pas optimal avec le système (1, 3, 4). Nombre de pièces du rendu glouton : 3.

Exercice 3 Un système non canonique

★★☆Environ 10 min

Le système de pièces est (1, 3, 6, 12, 24, 30). On doit rendre 49.

  1. Déroule l'algorithme glouton.
  2. Trouve un rendu avec moins de pièces.
  3. Que dire de ce système ?
Indice 1

Le glouton commence par 30.

Indice 2

Pour la question 2, pense à 24 + 24 + 1.

Voir la correction pas à pas

  1. Plus grande pièce ≤ 49 : 30, il reste 19.

  2. Plus grande pièce ≤ 19 : 12, il reste 7.

  3. Plus grande pièce ≤ 7 : 6, il reste 1.

  4. Plus grande pièce ≤ 1 : 1, il reste 0. Rendu glouton : 30 + 12 + 6 + 1, soit 4 pièces.

  5. Autre rendu : 24 + 24 + 1 = 49, soit 3 pièces.

  6. 3 < 4 : le glouton n'est pas optimal.

Le glouton donne 30 + 12 + 6 + 1, soit 4 pièces 2. Or 24 + 24 + 1 n'en utilise que 3 : ce système n'est pas canonique, l'algorithme glouton n'y répond pas de manière optimale 2. Écart entre le glouton et le meilleur rendu : 1 pièce.

Exercice 4 Trouver la plus petite somme qui piège le glouton

★★☆Environ 10 min

Avec le système (1, 3, 4), on cherche la plus petite somme pour laquelle l'algorithme glouton n'est pas optimal. Teste les sommes 1, 2, 3, 4, 5, 6 dans l'ordre.

Indice 1

Pour chaque somme, compare le rendu glouton avec le meilleur rendu que tu trouves à la main.

Indice 2

Les sommes 1 à 4 se rendent avec une seule pièce ou avec des pièces de 1.

Voir la correction pas à pas

  1. 1 : une pièce de 1. Glouton optimal.

  2. 2 : 1 + 1, deux pièces, et il n'y a pas mieux. Glouton optimal.

  3. 3 : une pièce de 3. Glouton optimal.

  4. 4 : une pièce de 4. Glouton optimal.

  5. 5 : glouton 4 + 1, deux pièces. Aucun rendu à une seule pièce n'existe : optimal.

  6. 6 : glouton 4 + 1 + 1, trois pièces, alors que 3 + 3 en utilise deux. Le glouton échoue.

La plus petite somme qui met le glouton en défaut est 6, le contre-exemple donné par le système (1, 3, 4) 3. Tester les petites sommes dans l'ordre croissant est une bonne méthode pour trouver un contre-exemple.

Exercice 5 Écrire la fonction de rendu

★★☆Environ 15 min

On représente un système de pièces par une liste triée par ordre décroissant, par exemple [200, 100, 50, 20, 10, 5, 2, 1].

Écris une fonction rendu(somme, pieces) qui renvoie la liste des pièces choisies par l'algorithme glouton. Teste-la mentalement avec rendu(37, [200, 100, 50, 20, 10, 5, 2, 1]).

Indice 1

Utilise une boucle for sur les pièces, puis une boucle while interne.

Indice 2

Tant que la pièce courante ne dépasse pas la somme restante, on l'ajoute et on retranche sa valeur.

Voir la correction pas à pas

  1. Créer une liste vide resultat et garder la somme restante dans reste.

  2. Parcourir les pièces de la plus grande à la plus petite.

  3. Pour chaque pièce, tant que piece <= reste, ajouter piece à resultat et faire reste = reste - piece.

  4. À la fin, renvoyer resultat.

  5. Code : def rendu(somme, pieces): puis resultat = [], reste = somme, for p in pieces: puis while p <= reste: puis resultat.append(p) et reste = reste - p, enfin return resultat.

  6. Test : pour 37, la fonction renvoie [20, 10, 5, 2], ce qui est le résultat attendu 3.

La fonction répète le choix de la plus grande pièce possible jusqu'à obtenir une somme à rendre nulle 2. Elle ne renvoie un rendu complet que si la pièce de valeur 1 est dans le système. Pour 37, la liste renvoyée contient 4 pièces. Le tri décroissant de la liste est une condition indispensable : sans lui, la fonction ne choisirait plus la plus grande pièce en premier.

Exercice 6 Compter les pièces d'un rendu glouton

★★☆Environ 10 min

Avec le système européen en centimes (1, 2, 5, 10, 20, 50, 100, 200), combien de pièces l'algorithme glouton utilise-t-il pour rendre 388 centimes ?

Indice 1

Commence par la pièce de 200, puis regarde ce qui reste.

Voir la correction pas à pas

  1. 388 : une pièce de 200, il reste 188.

  2. 188 : une pièce de 100, il reste 88.

  3. 88 : une pièce de 50, il reste 38.

  4. 38 : une pièce de 20, il reste 18.

  5. 18 : une pièce de 10, il reste 8.

  6. 8 : une pièce de 5, il reste 3.

  7. 3 : une pièce de 2, il reste 1.

  8. 1 : une pièce de 1, il reste 0.

  9. Total : 8 pièces.

Le rendu est 200 + 100 + 50 + 20 + 10 + 5 + 2 + 1, soit 8 pièces. Comme le glouton est toujours optimal avec ce système 3, on ne peut pas faire mieux.

Exercice 7 Décomposer 50 avec les nombres de Fibonacci

★★★Environ 10 min

Les nombres de Fibonacci, du plus petit au plus grand, commencent par 1, 2, 3, 5, 8, 13, 21, 34, 55. Le système de numération de Zeckendorf utilise l'algorithme glouton avec cet ensemble 3. Décompose 50 en somme de nombres de cet ensemble en choisissant à chaque étape le plus grand nombre possible qui ne dépasse pas le reste. Combien de termes obtiens-tu ?

Indice 1

Le plus grand nombre de la liste qui ne dépasse pas 50 est 34.

Indice 2

Après 34, il reste 16.

Voir la correction pas à pas

  1. Plus grand nombre ≤ 50 : 34 (car 55 > 50). Il reste 50 − 34 = 16.

  2. Plus grand nombre ≤ 16 : 13. Il reste 3.

  3. Plus grand nombre ≤ 3 : 3. Il reste 0, on s'arrête.

  4. Décomposition : 50 = 34 + 13 + 3, soit 3 termes.

La décomposition gloutonne est 50 = 34 + 13 + 3, soit 3 termes 3. C'est la même démarche que pour le rendu de monnaie : l'ensemble contient 1, donc la décomposition aboutit toujours à un reste nul 3.

Exercice 8 Fractions égyptiennes : décomposer 5/6

★★★Environ 15 min

Une fraction unitaire est de la forme 1n\frac{1}{n}. L'algorithme glouton de décomposition en fractions égyptiennes choisit à chaque étape la plus grande fraction unitaire possible inférieure au nombre considéré 4.

Applique-le à 56\frac{5}{6} et vérifie le résultat.

Indice 1

Cherche le plus petit entier nn tel que 1n≤56\frac{1}{n} \le \frac{5}{6}.

Indice 2

Il reste ensuite 56−12\frac{5}{6} - \frac{1}{2}.

Voir la correction pas à pas

  1. Le plus petit nn tel que 1n≤56\frac{1}{n} \le \frac{5}{6} est n=2n = 2 (car 11=1>56\frac{1}{1} = 1 > \frac{5}{6}).

  2. On retranche : 56−12=56−36=26=13\frac{5}{6} - \frac{1}{2} = \frac{5}{6} - \frac{3}{6} = \frac{2}{6} = \frac{1}{3}.

  3. Le reste 13\frac{1}{3} est déjà une fraction unitaire, on s'arrête.

  4. Résultat : 56=12+13\frac{5}{6} = \frac{1}{2} + \frac{1}{3}.

On retrouve la décomposition 56=12+13\frac{5}{6} = \frac{1}{2} + \frac{1}{3} en fractions unitaires distinctes 4. Le reste après la première étape vaut 13\frac{1}{3}, soit environ 0,3333.

Exercice 9 Décomposer 7/15 en fractions unitaires

★★★Environ 15 min

Applique la même méthode gloutonne (plus grande fraction unitaire possible, inférieure au nombre considéré) 4 à 715\frac{7}{15}. Donne la décomposition et le dernier dénominateur.

Indice 1

12=0,5>715\frac{1}{2} = 0{,}5 > \frac{7}{15} : essaie 13\frac{1}{3}.

Voir la correction pas à pas

  1. 715≈0,467\frac{7}{15} \approx 0{,}467. 12\frac{1}{2} est trop grand, 13\frac{1}{3} convient : première fraction 13\frac{1}{3}.

  2. Reste : 715−13=715−515=215\frac{7}{15} - \frac{1}{3} = \frac{7}{15} - \frac{5}{15} = \frac{2}{15}.

  3. 215≈0,133\frac{2}{15} \approx 0{,}133. 17≈0,143\frac{1}{7} \approx 0{,}143 est trop grand, 18=0,125\frac{1}{8} = 0{,}125 convient : deuxième fraction 18\frac{1}{8}.

  4. Reste : 215−18=16120−15120=1120\frac{2}{15} - \frac{1}{8} = \frac{16}{120} - \frac{15}{120} = \frac{1}{120}, fraction unitaire : on s'arrête.

  5. Résultat : 715=13+18+1120\frac{7}{15} = \frac{1}{3} + \frac{1}{8} + \frac{1}{120}.

La décomposition gloutonne est 715=13+18+1120\frac{7}{15} = \frac{1}{3} + \frac{1}{8} + \frac{1}{120}. Le dernier dénominateur vaut 120 : les dénominateurs peuvent grossir très vite, même pour de petites fractions.

Les questions qu'on se pose

Comment prouver qu'un algorithme glouton n'est pas optimal ?

Il suffit d'exhiber un contre-exemple : une situation où une autre solution fait mieux. Avec le système (1, 3, 4) et la somme 6, le glouton donne 4 + 1 + 1 alors que 3 + 3 est meilleur 3. À l'inverse, vérifier quelques cas ne prouve jamais l'optimalité.

Pourquoi utiliser un algorithme glouton s'il n'est pas toujours optimal ?

Parce qu'il est facile à mettre en œuvre 2. Dans certains systèmes dits canoniques, il donne en plus un résultat optimal 2. Quand ce n'est pas garanti, on parle d'heuristique gloutonne 3.

Que se passe-t-il si la liste de pièces n'est pas triée dans l'ordre décroissant ?

La fonction ne choisit plus la plus grande pièce possible en premier : elle ne suit plus la règle gloutonne et peut rendre un résultat différent, voire moins bon. Trie toujours la liste par ordre décroissant avant de lancer la boucle.

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)

  1. 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.
  2. Algorithmes gloutons — Document Éduscol, Éduscol. Consulté le 6 novembre 2026.
  3. Algorithme glouton, Wikipédia. Consulté le 6 novembre 2026.
  4. 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

Je suis en…

Primaire

  • CP Bientôt
  • CE1 Bientôt
  • CE2 Bientôt
  • CM1 Bientôt
  • CM2 Bientôt

Collège

Lycée

Supérieur

  • BTS Bientôt
  • BUT Bientôt
  • Licence Bientôt
  • Prépas Bientôt

Sur cette page