Fiche de révision · Spé NSI Première

Algorithmes gloutons : principe et exemple du rendu de monnaie

Chapitre : Algorithmique

En 30 secondes

Un algorithme glouton construit sa solution étape par étape en faisant à chaque fois le choix qui semble le meilleur, sans revenir en arrière.
Rendu de monnaie glouton : à chaque étape, prendre la plus grande pièce inférieure ou égale à la somme à rendre, jusqu'à atteindre 0.
Simple et rapide, mais pas toujours optimal : avec le système 1, 3, 4, rendre 6 donne 4+1+1 (3 pièces) au lieu de 3+3 (2 pièces).

Comprendre le principe d'un algorithme glouton : faire à chaque étape le choix qui semble le meilleur sur le moment, sans revenir en arrière.
Dérouler l'algorithme glouton de rendu de monnaie en choisissant à chaque étape la plus grande pièce possible.
Savoir qu'un algorithme glouton est simple et rapide mais ne donne pas toujours la solution optimale.

Algorithme glouton: un algorithme qui construit sa solution étape par étape en faisant à chaque fois le choix qui semble le meilleur sur le moment, sans jamais revenir sur un choix déjà fait.
Choix glouton: le choix localement optimal fait à une étape : celui qui paraît le meilleur immédiatement, sans tenir compte des étapes suivantes.
Solution optimale: la meilleure solution possible à un problème selon un critère donné, par exemple le plus petit nombre de pièces pour rendre une somme.

Croire qu'un algorithme glouton donne toujours la solution optimale : selon le système de pièces, il peut utiliser plus de pièces que le minimum.

Glouton = à chaque étape, je prends le meilleur choix du moment et je ne reviens JAMAIS en arrière.

10 questions sur « Algorithmes gloutons », corrigées et expliquées. Sans compte.

Règles, méthode pas à pas, exemple corrigé, exercices et corrections : dans le pack Première, à toi pour l'année.

~10 questions du programme de Première, score immédiat, sans compte.