Connexion élèves

Choisir le(s) module(s) à installer :

Algorithmes sur les tableaux - Correction

Recherche d'une valeur dans un tableau

Algorithme "naïf"

Parcours par valeur :


from random import randint

def recherche(tableau:list[int], valeur: int)->bool :			
	""" Fonction qui recherche la présence d'une valeur dans un tableau d'entiers
	Entrées :
		tableau = le tableau
		valeur = la valeur à rechercher
	Sortie :
		booléen True ou False selon la présence ou non de la valeur dans le tableau
	"""
	
	for element in tableau:
		if element == valeur:
			return True
	
	return False			
			
tableau = [randint(1,100) for i in range(50)]
print(recherche(tableau, 12) # par exemple...			
			

Parcours par indice :

On peut envisager un parcours par indice du tableau, ce qui permettra en plus de renvoyer l'indice à laquelle se trouve la valeur dans le tableau au cas où elle y est présente.


from random import randint

def recherche(tableau:list[int], valeur: int)->tuple[bool, int] :			
	""" Fonction qui recherche la présence d'une valeur dans un tableau d'entiers
	Entrées :
		tableau = le tableau
		valeur = la valeur à rechercher
	Sorties :
		booléen True ou False selon la présence ou non de la valeur dans le tableau
		l'indice de la valeur dans le tableau si elle y est présente, -1 sinon
	"""
	
	for i in range(len(tableau)) :
		if tableau[i] == valeur :
			return True, i
	
	return False, -1			
			
tableau = [randint(1,100) for i in range(50)]
print(recherche(tableau, 12) # par exemple...			
			

Comparaison avec l'algorithme utilisé par Python


from random import randint
from timeit import timeit

def recherche_naive(tableau:list[int], valeur: int)->bool :
    for element in tableau:
        if element == valeur:
            return True
    return False

def recherche_python(tableau:list[int], valeur: int)->bool :
    if valeur in tableau:
        return True
    else:
        return False


# Programme principal

tableau = [randint(1,100) for i in range(50)]

t1 = timeit(stmt = 'recherche_naive(tableau, 15)', globals=globals(), number = 1000)
print(t1)

t2 = timeit(stmt = 'recherche_python(tableau, 15)', globals=globals(), number = 1000)
print(t2)				
			

0.001952268999957596
0.0007598840002174256

>>> 		
			

→ on constate que les durées mesurées changent d'une exécution à l'autre, mais que celle de la version Python est toujours plus petite que la version "naïve" : l'algorithme utilisé par Python doit donc être plus efficace...

Extremum ( maximum ou minimum ), moyenne

Recherche du maximum


def maximum(tableau:list[int])->int:
    """
        Fonction renvoyant le maximum dans un tableau d'entiers
        Entrée :
        	tableau = tableau d'entiers
        Sortie :
        	la valeur maximale dans le tableau
    """
    maximum = tableau[0] # maximum initialisé à la valeur du premier élément du tableau
    for element in tableau:
        if element > maximum:
            maximum = element
    return maximum	
			

Recherche du minimum


def minimum(tableau:list[int])->int:
    """
        Fonction renvoyant le minimum dans un tableau d'entiers
        Entrée :
        	tableau = tableau d'entiers
        Sortie :
        	la valeur minimale dans le tableau
    """
    minimum = tableau[0] # initialisé avec la valeur du premier élément du tableau
    for element in tableau:
        if element < minimum:
            minimum = element
    return minimum		
			

Calcul d'une moyenne


def moyenne(tableau:list[int])->float:           
    """
        Fonction renvoyant la moyenne d'un tableau d'entiers
        Entrée :
        	tableau = tableau d'entiers
        Sortie :
        	la valeur moyenne du tableau
    """
    
    somme = 0
    
    for element in tableau:
        somme += element
        
    return somme / len(tableau)	
			

Application : suivi par un GPS de sport

Meilleur 100m

Il s'agit simplement d'une recherche de minimum dans un tableau :

			
def meilleur100m(L: list[float])->float:
    mini = L[0]
    for hecto in L:
        if hecto < mini:
            mini = hecto
    return mini			
			

Meilleur km

Plus délicat : c'est aussi une recherche de minimum, mais d'un minimum calculé à partir de 10 éléments successifs du tableau :


def meilleurkm(L: list[float])->float:
    
    minikm = 100**100 # valeur suffisamment grande pour qu'on trouve ensuite forcément une plus petite !
    
    for i in range (len(L)-9): # attention, il faut parcourir le tableau jusqu'à 9 éléments avant le dernier sinon 'Index out of range'....
        
        mkm = 0
        for j in range(10):    # boucle de calcul du temps au kilomètre, donc sur 10 éléments successifs à partir de l'indice i;
            mkm = mkm + L[i+j] # revient donc à calculer : L[i+0] + L[i+1] + L[i+2] +.... + L[i+9]
            
        if mkm < minikm:    # test si le temps calculé est un nouveau minimum
            minikm = mkm
    
    return minikm