import random

def liste_alea(n : int) -> list:
    """
    Renvoie une liste de n entiers aléatoires entre 0 et n
    """
    return # à compléter

# Affichons le début de la liste L :
print(liste_alea(10))

L = liste_alea(10)
e1 = L[0] # un élément de L !
e2 = -1 # un élément qui n'est pas dans L
print(e1 in L)
print(e2 in L)

def test_recherche_sequentielle():
    # à compléter...
    #   
    print("Tous les tests sont passés")

test_recherche_sequentielle()

def recherche_sequentielle(L : list,e : int) -> bool :
    """reçoit une liste d'entier L et un entier e, et renvoie :
    -> True si e appartient à L
    -> False si e n'appartient pas à L"""
    
    # à compléter

# on teste :
test_recherche_sequentielle()

def recherche_dichotomie(L : list, e : int) -> bool :
    a,b = 0,len(L)-1 # les indices gauche et droite
    
    while a<=b :
        m = (a+b)//2 # division entiere
        if e == L[m]:
            return # à compélter
        else :
            if e < L[m] :
                # à compléter
            else:
                # à compléter
    return False

from random import randint
def test_recherche_dichotomie():
    assert recherche_dichotomie([1,2,3],1) == True
    assert recherche_dichotomie([1,2,3],4) == False
    assert recherche_dichotomie([],1) == False # avec liste vide
    print("Tous les tests sont passés")

test_recherche_dichotomie()

from time import time

taille = 1000

# à compléter

print("Le temps d'exécution dans le pire des cas avec la fonction 'recherche_sequentielle' est :", t1-t0)


# à compléter

print("Le temps d'exécution dans le pire des cas avec la fonction 'recherche_dichotomie' est :", t1-t0)

from time import time
import matplotlib.pyplot as plt

liste_n = [2**i for i in range(13)]
tdic = []
tseq = []

for taille in liste_n :
   # à compléter

# dessin :
X = liste_n
Y = [tdic[i]/tseq[i] for i in range(len(tdic))]
plt.clf()
plt.plot(X,Y,'o')
plt.show()

def f(x) :
    return x*x-2

def dichotomie(f,a,b,eps):
    assert f(a)*f(b)<0
    while (b-a)>eps:
        m = (b+a)/2
        if f(a)*f(m)<0:
            b=m
        else:
            a=m
    return (a,b)

a,b = dichotomie(f,0,2,0.001)
print(f"Une solution de f(x)=0 est comprise entre {a:.3f} et {b:.3f}")

def read_datas():
    """ récupère les données du fichier 'Provence_10km_trie.txt' dont les données
    sont stockées en deux colonnes séparées par un ':' 
    NOM : PLACE
    La fonction renvoie deux listes : la première avec les noms des particpants,
    la deuxième avec leurs places respectives
    """
    
    noms = []
    places = [] 
    
    with open('Provence_10km_trie.txt') as f :
        for line in f :
            if line == '\n' : break
            nom,place = # à compléter
            noms.append(nom.strip())
            places.append(place.strip())
            
    return noms, places

# on teste
n,p = read_datas()
print(len(n))
print(n[:10])
print(p[:10])

def find_friend(names : list, ranks : list, friend : str) -> int :
    """ reçoit la liste des noms, la liste des places correspondantes
    ainsi que le nom d'un ami (écrit en majuscules sans accents) et
    qui renvoie la place de cet ami dans la course (et 0 s'il n'y était pas !)"""
    
    a,b = 0, len(names)-1
    while b-a >=0 :
        # à copmpléter

names, ranks = read_datas()
friends = ['MURAGA', 'ZUFFO', 'GRIEZMANN' ]
for f in friends :
    rk = find_friend(names,ranks,f)
    if rk == 0 :
        print(f"{f} non trouvé dans la liste")
    else :
        print(f"Place de {f} : {rk}")

TD M1 : Dichotomie, complexité¶

I. Méthode naïve : recherche séquentielle¶

II. Algorithme dichotomique¶

III. Rappels du cours de mathématiques¶

IV. Un cas concret¶