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 qui recherche un nombre dans une liste triée en utilisant la recherche dichotomique. Teste-la avec assert pour vérifier qu'elle retourne l'index correct ou -1 si le nombre n'existe pas.
Corrige cet exercice avec le tuteur →Exercice 2
Crée une fonction tri_par_insertion(liste) qui trie une liste en utilisant le tri par insertion. Utilise des assertions pour vérifier que la liste retournée est bien triée et contient les mêmes éléments.
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Algorithmique et programmation (NSI 1ère).