On désire mettre en place d’un algorithme permettant de déterminer si une valeur est présente ou non dans une liste de nombres aléatoires rangée par ordre croissant.
1. Générer une liste aléatoire de n nombres entiers différents d’une valeur k
Ecrire une fonction répondant à sa docstring :
def liste_alea(n,k):
'''
génère une liste aléatoire de n entiers compris entre
0 et n différents de k
'''
2. Tester un premier algorithme
Compléter la fonction suivante
def presence(liste,val):
'''
déterminer si une valeur est présente dans une liste
>>>presence([1,2,3],5)
False
>>>presence([1,2,3],2)
True
'''
for i in .......:
if .....==.....:
return .......
return ........
3. Mesurer le temps d’exécution et déterminer si il est linéaire ou quadratique
Ajouter les lignes suivantes dans votre programme
import time
l=liste_alea(100000,8)
l=sorted(l)
t0 = time.time()
presence(l,8)
t1 = time.time()
temps=t1-t0
print(temps)
Déterminer si le temps d’exécution de la fonction presence() est linéaire ou quadratique
4. Un algorithme plus performant : la dichotomie
def recherche_dichotomique(v, T):
"""
T : tableau d’entiers trié dans l’ordre croissant
v : nombre entier
La fonction renvoie True si T contient v et False sinon
"""
debut = 0
fin = len(T) - 1
while debut <= fin:
m = ...
if v == T[m]:
return ...
elif v > T[m]:
debut = m + 1
else:
fin = ...
return ...Tester le temps d’exécution de ce nouvel algorithme