Parcours séquentiel d'un tableau

Algorithme de recherche d'une occurrence

Rechercher une occurrence, c'est rechercher dans un tableau si une valeur est présente ou pas.

Soit l'algorithme suivant :

tableau ← [25 , 23, 12, 45, 26, 18, 20]
trouve ← FAUX
nbre ← 45
i ← 0
Tant que  i < longueur(tableau) et trouve = FAUX
    Si nbre = tableau[ i ] Alors
        trouve ←VRAI
    FinSi
    i ← i + 1
FinPour
Si trouve = VRAI Alors
    Ecrire "Le nombre est présent dans le tableau"
Sinon
    Ecrire "Le nombre n'est pas présent dans le tableau"

En faisant tourner l'algorithme à la main, quelle est la valeur de trouve une fois l'algorithme terminé ?

Que se passe t-il si nbre ← 19 à la place de nbre ← 45 ?

Complexité :

Est-ce que l'algorithme doit parcourir nécessairement toutes les valeurs du tableau ?

Pyhton :

Réaliser en python le programme correspondant et lancez-le afin de vérifier le résultat.

Algorithme de recherche d'un extremum

Soit l'algorithme suivant :

tableau ← [25 , 23, 12, 45, 26, 18, 20]
nbre ← 0
Pour i ← 0 à longueur(tableau)-1
    Si nbre<tableau[ i ] Alors
        nbre ← tableau[ i ]
    FinSi
    i Suivant
FinPour

En faisant tourner l'algorithme à la main, quelle est la valeur de nbre une fois l'algorithme terminé ?

A quoi sert cet algorithme ?

Complexité :

Compte tenu des explications de l'activité précédente on ne retiendra pas les 2 premières lignes de l'algorithme.

Combien d'opération élémentaires faut-il si le tableau ne contenait que 1 valeurs ?
Combien d'opération élémentaires faut-il si le tableau ne contenait que 2 valeurs ?
Combien d'opération élémentaires faut-il si le tableau ne contenait que 3 valeurs ?
Combien d'opération élémentaires faut-il si le tableau ne contenait que n valeurs ?

En déduire la complexité de l'algorithme compte tenu des explications de simplification données dans l'activité précédente.

Python :

Réaliser en python le programme correspondant et lancez-le afin de vérifier le résultat.

Algorithme de calcul de la moyenne

Soit le tableau tableau ← [25 , 23, 12, 45, 26, 18, 20]

A l'aide d'une boucle Pour ... Suivant ... FinPour proposer l'algorithme qui calcule la moyenne des valeurs du tableau.

Une fois calculé, la valeur de la moyenne sera affichée.

Vous pourrez vérifier votre travail à l'aide de l'exercice 6.14.

Complexité :

Compte tenu des explications de l'activité précédente on ne retiendra que les opérations de la boucle de l'algorithme.

En déduire la complexité de l'algorithme.

Pyhton :

Réaliser en python le programme correspondant et lancez-le afin de vérifier le résultat.

CONCLUSION

Dans un parcours séquentiel de tableau la complexité est toujours linéaire :

lorsque le tableau est grand elle est d'ordre n

Exercices d'application

Recherche d'une valeur dans un tableau - variante 1

Le programme python de recherche doit être écrit dans une fonction rechValeur(valeur,tableau) qui retourne un nombre.

L'objectif est de rechercher une valeur donnée dans un tableau et de retourner l'indice de sa position dans le tableau.

S'il n'est pas présent, la valeur -1 doit être retournée pour indiquer que la valeur recherchée n'est pas présente.

Voici une base de départ comme programme :

#Données de départ
tableau= [25 , 23, 12, 45, 26, 18, 20]
valeur=12
#Recherche de valeur dans tableau
trouve=-1
i=0
while i<len(tableau):
    if valeur==tableau[i]:
        trouve=1
    i=i+1
print("valeur trouvée :",trouve)

Ce programme est à modifier pour créer une fonction et pour retourner l'indice.

Vous tester au fur et à mesure, c'est plus simple !

A prévoir ensuite une amélioration pour tester si la valeur retournée par la fonction est -1, auquel cas afficher un message différents du genre "la valeur recherchée n'est pas dans le tableau".

Recherche d'une valeur dans un tableau - variante 2

Le programme de recherche doit être écrit dans une fonction rechValeur(valeur,tableau) qui retourne un nombre.

L'objectif est de rechercher une valeur donnée dans un tableau et de retourner le nombre de fois qu'il est présent dans le tableau.

S'il n'est pas présent, la valeur -1 doit être retournée pour indiquer que la valeur recherchée n'est pas présente.

Bien évidemment il faut le tester.

A prévoir ensuite une amélioration pour tester si la valeur retournée par la fonction est -1, auquel cas afficher un message différents du genre "la valeur recherchée n'est pas dans le tableau".

Recherche d'une valeur dans un tableau - variante 3

Le programme de recherche doit être écrit dans une fonction rechValeur(valeur,tableau) qui retourne un tableau.

L'objectif est de rechercher une valeur donnée dans un tableau et de retourner un tableau contenant les indices des positions de la valeur recherchée dans le tableau.

S'il n'est pas présent, un tableau avec la valeur -1 doit être retournée pour indiquer que la valeur recherchée n'est pas présente.

Bien évidemment il faut le tester.

A prévoir ensuite une amélioration pour tester si la valeur retournée par la fonction est -1, auquel cas afficher un message différents du genre "la valeur recherchée n'est pas dans le tableau".

Calcul de moyenne et recherche du min et du max

Le programme doit permettre de calculer la moyenne des notes contenues dans un tableau et de trouver en même temps (donc une seule boucle) la note la plus basse et la plus élevée.

On suppose que le tableau de notes contient des notes (valeur décimale) comprises entre 0 et 20.

La fonction moyenneNotes(tableau) à créer doit donc retourner 3 nombres : moyenne, min et max

C'est donc un mixe de 2 algorithmes vus précédemment.

A prévoir ensuite, au tout début de la fonction, de tester si le tableau n'est pas vide, car tab[0] provoque une erreur python si c'est le tableau est vide. Auquel cas retourner la valeur -1 pour la moyenne. Le message des informations sera alors modulé en indiquant que le tableau de note ne doit pas être vide

Détails: Mis à jour : 3 Décembre 2023