Parcours en profondeur : DFS en Terminale
Parcours en profondeur : DFS, c'est une notion de nsi du chapitre « Algorithmique avancée », au programme de Terminale. Voici le cours, un exemple et de quoi t'entraîner.
Parcours en profondeur : DFS : le cours
Le parcours en profondeur explore un graphe en allant aussi loin que possible dans une branche avant de revenir en arrière. Il utilise une pile (récursion ou structure).
Exemple
Explorer un labyrinthe : tu avances le plus loin possible dans un couloir, puis tu reviens en arrière pour essayer un autre chemin.
À retenir
DFS est utile pour détecter les cycles, trouver les composantes connexes et explorer tous les chemins possibles.
S'entraîner sur parcours en profondeur : dfs
Fais l'exercice, puis demande au tuteur de te corriger pas à pas.
Exercice 1
Soit la fonction récursive suivante : ```python def mystere(n): if n == 0: return 1 else: return n * mystere(n - 1) ``` 1. Identifiez le cas de base et le cas récursif. 2. Tracez l'exécution de mystere(4) en dessinant la pile d'appels. 3. Que calcule cette fonction ?
Corrige cet exercice avec le tuteur →Exercice 2
On souhaite implémenter la **recherche dichotomique** sur un tableau trié. 1. Écrivez une fonction récursive `recherche_dichotomique(tab, cible, gauche, droite)` qui retourne l'indice de `cible` dans `tab`, ou -1 si absent. 2. Analysez la complexité temporelle en fonction de la taille n du tableau. 3. Testez avec `tab = [1, 3, 5, 7, 9, 11]` et `cible = 7`.
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Algorithmique avancée (NSI Terminale).