TP-Cours ITC 02 : Recherche séquentielle dans un tableau unidimensionnel [semaine 06]

TP-Cours ITC 02

Recherche séquentielle dans un tableau unidimensionnel

I. Recherche d'un élément

I.1 Algorithme : boucle conditionnelle (while) ou inconditionnelle (for) ?

On souhaite écrire la fonction

recherche(a:list,x:int)➞bool
recherche(a:list,x:int)➞bool permettant de déterminer si un entier x est présent ou non dans le tableau a. Le résultat renvoyé par cette fonction sera donc un booléen (True/False). Bien sûr, on s’interdit d’utiliser l’expression
x in a
x in a qui est spécifique à Python et qui peut cacher un algorithme que l’on ne maîtrise pas.

L’idée la plus simple consiste à considérer a priori que x n’est pas dans a  pour ensuite parcourir tout le tableau et modifier la valeur d’une variable booléenne en conséquence SI on rencontre x en parcourant a. Voici cet algorithme mis en œuvre :

Retenez bien cet algorithme, il peut vous être demandé dans de nombreux problèmes ! Nous allons voir toutefois qu’il peut être amélioré, et le programme indique que vous devez connaître les variantes à venir …

À présent, nous allons modifier la fonction précédente en utilisant une propriété de l’instruction

return
return: lorsque le flux d’exécution du code rencontre sur une instruction
return
return, la fonction contenant cette instruction renvoie un résultat et le flux d’exécution se poursuit à la suite de l’appel de cette fonction En particulier, les instructions suivant un
return
return à l’intérieur d’une fonction ne sont pas exécutées !

Il est possible d’utiliser cette propriété de

return
return ceci à notre avantage : par exemple, pour sortir d’une boucle for contenue dans une fonction avant d’avoir accompli toutes les itérations de cette boucle.

Ici, la fonction

recherche
recherche s’achève avec
return True
return True dès lors qu’un élément de la liste
a
a vaut
x
x et si le flux d’exécution arrive sur l’instruction
return False
return False, cela signifie que la boucle for s’est déroulée entièrement en testant tous les éléments de 
a
a mais sans avoir trouvé un élément de
a
a de valeur
x
x: la fonction
recherche
recherche renvoie bien le résultat attendu.

Boucle while ?

D’aucuns pensent que l’utilisation d’un

return
return pour forcer l’arrêt d’une boucle
for
for est une (mauvaise) habitude qui doit être évitée si c’est possible.

Nous allons donc modifier cette boucle pour effectuer des tests successifs sur les éléments de

a
a tant que c’est possible (on utilisera pour ces  tests un indice
i
i qui devra rester strictement inférieur à
len(a)
len(a)à l’intérieur de la boucle) et tant que l’élément observé dans
a
a n’a pas comme valeur
x
x. Notre nouvelle version de la fonction
recherche
recherche utilisera donc une boucle
while
while et testera en fin de boucle si tous les éléments de
a
a ont été testés ou non pour déterminer si
x
x est dans
a
a (ou non).

Mémorisez cet algorithme classique  ! Nous allons voir qu’il sert de base à des questions plus pointues sur le sujet.

I.2 Première occurrence, liste des occurrences

Exercice 1

Votre premier travail consiste à modifier la fonction précédente (celle avec la boucle while) pour créer une version de la fonction recherche qui retourne l’indice la première occurrence de x dans a si sa présence est avérée et -1 sinon.

Toutefois, la boucle

while
while n’est pas toujours recommandée ! Tout dépend de la question posée et pour répondre à certaines questions classiques sur les tableaux, il faut parfois parcourir la totalité de ce tableau. Par exemple, lorsqu’on souhaite obtenir le nombre d’occurrences de
x
x dans
a
a (La valeur renvoyée par cette fonction est donc un entier de [[0;
len(a)
len(a)]]. Entraînez-vous à écrire fonction qui fournit une réponse à ce problème, il s’agit d’un algorithme classique ! Vous pouvez faire cela dans Pyzo. Dans le prochain exercice, vous devrez parcourir tous les éléments de la liste
a
a pour écrire votre fonction.

Exercice 2

Écrire une version de la fonction recherche qui retourne la liste des indices des occurrences de x dans a. Si x n’est pas dans a, votre fonction devra renvoyer une liste vide.

II. Recherche du maximum et du second maximum

II.1 Recherche du maximum d'un tableau, nombre de maximums

On suppose ici qu’on travaille sur un tableau (représenté par la liste

a
a) d’entiers. On se propose de trouver le plus grand entier du tableau appelé maximum du tableau/de
a
a. L’algorithme accomplissant cette tâche est très simple. La variable
max
max est initialisée à
a[0]
a[0] car on envisage la possibilité que le maximum de
a
a soit le premier élément de
a
a. On parcourt ensuite la totalité du tableau et lorsqu’on/si on rencontre un entier strictement plus grand que
max
max, on fait évoluer la valeur de
max
max.

Exercice 3

Écrire la fonction

maxNBmax(a:list)➞(int,int)
maxNBmax(a:list)➞(int,int) qui renvoie un tuple formé du plus grand élément de la liste d’entiers
a
a et du nombre d’occurrences de ce maximum dans la liste
a
a.

II.2 Recherche du maximum et du second maximum

On souhaite écrire une fonction qui détermine les deux plus grands éléments d’un tableau d’entiers (représenté par une  liste) ainsi que leurs indices de première occurrence respectifs dans ce tableau. Avant d’aller plus loin, songez bien que ces deux plus grands éléments peuvent être égaux !

Exercice 4

Écrire la fonction

maximums(a:list)➞(int,int),(int,int)
maximums(a:list)➞(int,int),(int,int) qui renvoie deux tuples formés du plus grand élément de la liste d’entiers
a
a et de l’indice de sa première occurrence dans
a
a, du second plus grand élément de la liste d’entiers
a
a et de l’indice de sa première occurrence dans
a
a. Vous suivrez l’algorithme précédent en vous assurant bien d’avoir compris le rôle des différents blocs d’instructions de la fonction
maximums
maximums.

Traitez sérieusement ces quatre exercices  ! Ces algorithmes sont des « classiques » au sens où vous devez être capables de mobiliser rapidement ces connaissances dans un DS. La recherche linéaire dans un tableau est une question habituelle des DS de début d’année … i