Favicon
NSI Première

Algorithmes sur les tableaux - Correction

1. Recherche d'une valeur dans un tableau

1.1. 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...

2. 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...

3. Extremum ( maximum ou minimum ), moyenne

3.1. 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

3.2. 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

3.3. 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)

4. Applications

4.1. Mot le plus long


def mot_le_plus_long(tab):

    longueur_max = len(tab[0])  # la taille du premier élément du tableau

    mot_max = tab[0]     # le premier élément du tableau

    for mot in tab :  # pour chaque mot dans le tableau

        if len(mot) > longueur_max :  # si le mot est plus long que le plus grand actuel

            longueur_max = len(mot) # alors on stocke sa longueur
            mot_max = mot     # et le mot lui mĂŞme

    return mot_max, longueur_max    # renvoi des résultats


print(mot_le_plus_long(['chaton', 'licorne', 'ratatouille', 'bip'])) # ('ratatouille', 11)
print(mot_le_plus_long(['chatons', 'licorne', 'or', 'car', 'etoile'])) # ('chatons', 7) 
print(mot_le_plus_long(['licorne', 'chatons', 'or', 'car', 'etoile'])) # ('licorne', 7)

4.2. Deux plus grandes valeurs


def deux_max(tab):
    """
    Renvoie les deux premiers maximum ( = les deux plus grandes valeurs )
    dans un tableau.
    Entrée : un tableau d'entiers ( list de int ou de float )
    Sortie : les deux plus grandes valeurs ( tuple de int ou de float )
    """
    max1 = 0 
    max2 = 0
    for valeur in tab:
        if valeur > max1:
            max2 = max1
            max1 = valeur
        elif valeur > max2:
            max2 = valeur
    return max1, max2

4.3. Face au Soleil


def building_sunset(buildings):
    """
    Renvoie le nombre de buildings qui verront le soleil.
    Entrée : un tableau dont chaque élément est la taille d'un building ( list de int)
    Sortie : le nombre de buildings qui voient le soleil ( int )
    """
    c = 1
    mini = buildings[0]
    for b in buildings:
        if b > mini:
            c += 1
            mini = b 
    return c			


def building_sunset_v2(buildings):
    """
    Renvoie les indices des buildings qui verront le soleil.
    Entrée : un tableau dont chaque élément est la taille d'un building ( list de int)
    Sortie : le tableau des indices des de buildings qui voient le soleil ( list de int )
    """
    mini = buildings[0]
    c = [0]
    for i in range(len(buildings)):
        if buildings[i] > mini:
            c.append(i)
            mini = buildings[i]
    return c		
    
    
b1 = [4, 2, 5, 4, 6]
print(building_sunset_v2(b1))	# renvoie 3
print(building_sunset_v2(b1))	# renvoie [0, 2, 4]

4.4. Plus grande période de gel

On a besoin ici de déterminer DEUX valeurs différentes :


def longueur_gel(temperatures):
    """
    Renvoie la durée de la plus grande période de gel,
    c'est à dire le plus grand nombre de jours consécutifs 
    où la température est restée inférieure ou égale à 0°C.
    Entrée : le tableau des températures des jours successifs ( list de int )
    Sortie : la durée de la plus longue période de gel ( int )
    """
    maxi = 0 # durée de la PLUS GRANDE période de gel
    l = 0 # durée d'une période de gel QUELCONQUE
    for t in temperatures: # pour chaque température dans le tableau,
        if t <=0 :  # si la température est négative,
            l += 1 # on incrémente la durée de la période actuelle.
            if l > maxi: # a-t-on trouvé une longueur plus grande que la maximum déterminé jusque là ?
                maxi = l # dans ce cas, la longueur de la période actuelle devient le nouveau maximum.
        else: # sinon  ( sous-entendu : si la température n'est pas inféireure ou égale à 0 ),
            l = 0 # alors on réinitialise le comptage de la durée de la période à 0.
    return maxi

4.5. Suivi par un GPS de sport

4.5.1. Meilleur 100m

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

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

4.5.2. 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):
    
    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