Informatique & NSI · 04 / 06
Boucles et recherche : suivre l’algorithme
Première · Exemple résolu et 4 exercices corrigés, à ton rythme.
Le principe, simplement
Une boucle répète des opérations avec un état et une condition de poursuite. Une recherche linéaire parcourt les éléments jusqu’au résultat ou à la fin. Une recherche dichotomique divise un intervalle de recherche mais exige une organisation adaptée, généralement une liste triée. Un invariant décrit une propriété conservée ; une grandeur qui diminue peut aider à prouver la terminaison.
- 01Entrées
- 02État et invariant
- 03Progression
- 04Sortie et cas limites
EXEMPLE RÉSOLU
Du cours au raisonnement
Dans [2,5,9,12], chercher 9 linéairement compare 2, puis 5, puis 9. Pour une somme, initialise total à 0 et ajoute chaque élément exactement une fois. Une trace note indice, valeur courante, total et condition.
Résoudre un problème dans cette matière
- Préciser le contrat
Définis entrées, types, sorties et cas interdits. Pour un algorithme de recherche, précise s’il attend une liste triée.
- Suivre un petit exemple
Fais un tableau avec valeur des variables, condition testée et action. Choisis un exemple court que tu peux vérifier à la main.
- Tester les frontières
Teste entrée vide, un élément, doublons, valeur absente et limites numériques selon le contrat. Le résultat doit être défini ou l’erreur expliquée.
- Justifier
Explique pourquoi la méthode termine et répond au problème. Distingue nombre d’opérations, temps observé et mémoire utilisée.
À TOI DE JOUER
01 · Une tentative avant la correction
Pourquoi une boucle while avec une condition toujours vraie peut-elle ne jamais finir ?
Un indice
Quelle variable rapproche la condition de false ?
Voir et comprendre la correction
Sans mise à jour appropriée ou sortie prévue, aucun état ne mène à la fin. Il faut une progression justifiée, pas seulement une condition écrite.
Compare la méthode, les conditions et le résultat ; indique précisément ce que tu dois reprendre.
PROGRESSER PAR LA PRATIQUE
Trois défis supplémentaires, avec correction
Commence par le premier défi. Écris ta démarche avant d’ouvrir un indice ; utilise la correction pour retrouver la première étape qui bloque.
Combien d’itérations effectue range(2,6) en Python ?
Un indice pour démarrer
La borne finale est exclue.
Correction étape par étape
- Les valeurs sont 2,3,4,5.
- Il y a quatre itérations.
- 6 n’appartient pas à cet intervalle.
Quelle étape avais-tu oubliée ? Refais cet exercice sans aide, puis explique pourquoi la méthode fonctionne.
Une recherche linéaire parcourt [3,8,2,9] pour trouver 2. Combien de comparaisons si elle s’arrête au premier succès ?
Un indice pour démarrer
Commence au premier élément.
Correction étape par étape
- Compare à 3, puis à 8, puis à 2.
- La troisième comparaison réussit.
- Le programme s’arrête : il n’a pas besoin de tester 9.
Quelle étape avais-tu oubliée ? Refais cet exercice sans aide, puis explique pourquoi la méthode fonctionne.
Pourquoi une recherche dichotomique exige-t-elle une liste triée ?
Un indice pour démarrer
Éliminer une moitié suppose un ordre fiable.
Correction étape par étape
- La comparaison au milieu indique de quel côté chercher seulement si l’ordre est connu.
- Sans tri, la moitié supprimée peut contenir la cible.
- Sur une liste triée, la zone restante est approximativement divisée par deux à chaque étape.
Quelle étape avais-tu oubliée ? Refais cet exercice sans aide, puis explique pourquoi la méthode fonctionne.
L’erreur à éviter
La dichotomie n’est pas directement applicable à une liste non triée. Une boucle correcte doit aussi traiter les cas limites.
Sans tes notes, peux-tu…
- Expliquer le principe avec tes mots ?
- Reconstruire le schéma et ses liens ?
- Résoudre l’exercice et justifier la méthode ?
Choisir un état le conserve dans ce navigateur. C’est ton auto-évaluation, pas une note.