Algorithmique
En informatique, pour qu’un algorithme puisse être implémenté, il est nécessaire de s’assurer que la « suite finie et non ambiguë d’opérations ou d’instructions à réaliser » s’effectue en une durée finie .
Lorsqu’on élabore ou étudie un algorithme, il est donc nécessaire de vérifier :
[Lire]Recherche d'un élément dans un tableau : algorithmes itératifs et récursifs
Recherche d’un élément dans un tableau
La recherche d’éléments dans un tableau a déjà été évoquée en classe de première. Les deux algorithmes mis en œuvre à cette occasion, la recherche linéaire et la recherche dichotomique, utilisaient des boucles.
L’objectif de cette séance est de rapidement revoir ces algorithmes et de mettre en œuvres des algorithmes récursifs de même complexité. Quatre algorithmes de recherche vont donc être implémentés :
- La recherche linéaire itérative ;
- La recherche linéaire récursive ;
- La recherche dichotomique itérative ;
- La recherche dichotomique récursive.
Travail à faire
- Implémenter en Python les cinq algorithmes suivants et répondre aux questions.
Recherche séquentielle (ou linéaire)
Recherche séquentielle itérative
Algorithme 1
Fonction : recherche(tab, valeur)
Action : recherche la valeur « valeur » dans le tableau « tab »
Début
i ⟵ 0
i_val ⟵ -1
nb ⟵ Longueur(tab)
TantQue i < nb Faire
Si tab[i] = valeur Alors
i_val ⟵ i
FinSi
i ⟵ i + 1
FinTantQue
Renvoyer i_val
Fin