Algorithmes gloutons en 1ère
Algorithmes gloutons, c'est une notion de nsi du chapitre « Algorithmique et programmation », au programme de 1ère. Voici le cours, un exemple et de quoi t'entraîner.
Algorithmes gloutons : le cours
Stratégie qui fait le meilleur choix à chaque étape sans revenir en arrière, en espérant obtenir une bonne solution globale. On prend toujours ce qui semble optimal maintenant.
Exemple
Rendre la monnaie avec le moins de pièces : tu utilises d'abord les plus grandes pièces possibles, puis les plus petites. Tu ne reviens jamais en arrière.
À retenir
Un algorithme glouton est rapide mais ne garantit pas toujours la meilleure solution possible.
S'entraîner sur algorithmes gloutons
Fais l'exercice, puis demande au tuteur de te corriger pas à pas.
Exercice 1
Écris une fonction `recherche_max(tableau)` qui parcourt séquentiellement un tableau et retourne l'indice de l'élément maximum. Teste ta fonction avec l'assertion suivante : `assert recherche_max([3, 7, 2, 9, 1]) == 3`
Corrige cet exercice avec le tuteur →Exercice 2
Implémente l'algorithme de tri par insertion pour trier un tableau en ordre croissant. Explique le principe en 3-4 lignes, puis fournis le code avec des assertions de test.
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Algorithmique et programmation (NSI 1ère).