tab = [12, -3, 15, -9, 17, 7]
for val in tab:
print(val)
12
-3
15
-9
17
7
| Contenus | Capacités attendues | Commentaires |
|---|---|---|
| Parcours séquentiel d’un tableau | Écrire un algorithme de recherche d’un extremum, de calcul d’une moyenne. | On montre que le coût est linéaire |
Dans ce chapitre, nous allons étudier des algorithmes de parcours séquentiel d’un tableau pour:
Ces algorithmes «séquentiels» ne sont pas du tout efficace, on les appelle en anglais Brute force algorithms.
Comme vu dans le chapitre P3C2, on peut itérer sur les valeurs ou sur les index.
On fait une itération sur les valeurs du tableau en utilisant le mot-clé in.
tab = [12, -3, 15, -9, 17, 7]
for val in tab:
print(val)
12
-3
15
-9
17
7
C’est la méthode classique utilisée dans les langages impératifs.
for i in range(len(tab)):
val = tab[i]
print("indice:", i, "valeur:", val)
indice: 0 valeur: 12
indice: 1 valeur: -3
indice: 2 valeur: 15
indice: 3 valeur: -9
indice: 4 valeur: 17
indice: 5 valeur: 7
On initialise la valeur au premier élément du tableau puis on parcourt le tableau pour vérifier s’il existe un élément soit plus petit soit plus grand.
def maximum(liste):
# ne pas utiliser max pour le nom de variable
# car la fonction max existe en Python(on l'écraserait!)
maxi = liste[0]
for e in liste:
if e > maxi:
maxi = e
return maxi
# appel de la fonction sur tab
maximum(tab)
17
def minimum(liste):
mini = liste[0]
for e in liste:
if e < mini:
mini = e
return mini
# appel de la fonction avec la liste tab en argument
minimum(tab)
-9
On initialise une valeur accumulatrice à 0, puis on additionne tous les éléments du tableau. Enfin on divise la somme des éléments par le nombre d’éléments du tableau.
def moyenne(liste):
somme = 0
for e in liste:
somme = somme + e
# On divise la somme de tpus les éléments par leur nombre
moyenne = somme / len(liste)
return moyenne
# appel de la fonction
moyenne(tab)
6.5
Pour mesurer l’efficacité temporelle d’un algorithme, on introduit la notion de complexité.
La complexité d’un algorithme est le nombre d’opérations élémentaires(opération arithmétique, comparaison, affectation…) effectuées pour obtenir un résultat.
La complexité d’un algorithme dépend souvent de la taille des données d’entrée notée . Dans notre cas la taille du tableau dans lequel on recherche l’élément.
Pour comparer facilement les algorithmes on se place dans le pire des cas, dans les algorithmes présentés il faut toujours parcourir entièrement la liste pour trouver le maximum, le minimum ou la moyenne: il y a donc itérations.
On dit que le coût de l’algorithme est linéaire ou encore que c’est un algorithme de complexité .