# TP 11 correction : Dichotomie
# BCPST1B 2025-2026
# Lycée Hoche, Versailles
# L.-C. LEFÈVRE

#%% exercice 1

from random import randint

def jeu():
    n = randint(1, 100)
    fini = False
    c = 0
    # print("réponse :", n)
    while not fini:
        x = int(input("Nombre ? "))
        c = c + 1
        if x < n:
            print("Plus grand !")
        elif x > n:
            print("Plus petit !")
        else:
            print("Trouvé en", c, "coups")
            fini = True

# test
jeu()

#%% exercice 4.1

def racine2(n):
    a = 1
    b = 2
    for i in range(n):
        m = (a+b) / 2
        if m**2 > 2:
            b = m
        else:
            a = m
        print(a, b)

# test
racine2(10)

#%% exercice 4.2

def racine2_seuil(s):
    a = 1
    b = 2
    while b-a >= s:
        m = (a+b) / 2
        if m**2 > 2:
            b = m
        else:
            a = m
    return (a, b)

# test
print(racine2_seuil(1e-6))

#%% exercice 4.3

def racine2_rec(s, a, b):
    if b-a < s:
        return (a, b)
    else:
        m = (a+b) / 2
        if m**2 > 2:
            return racine2_rec(s, a, m)
        else:
            return racine2_rec(s, m, b)

# test
print(racine2_rec(1e-6, 1, 2))

#%% exercice 5.1
# exécuter, observer et zoomer !

import numpy as np
import matplotlib.pyplot as plt

X = np.linspace(-5, 5, 100)
Y = X**3 - 5*X - 3
Z = 0 * X
plt.grid(True)
plt.xlim(-5, 5)
plt.ylim(-10, 10)
plt.title("Exercice 5")
plt.plot(X, Y, color="blue", label="$f(x)$")
plt.plot(X, Z, color="red", label="$y=0$")
plt.legend()
plt.show()

#%% exercice 5.2

def solution1(s):
    # entre -2 et -1
    a = -2
    b = -1
    while b-a >= s:
        m = (a+b) / 2
        if m**3 - 5*m - 3 > 0:
            b = m
        else:
            a = m
    return (a, b)

def solution2(s):
    # entre -1 et 0, mais décroissante
    a = -1
    b = 0
    while b-a >= s:
        m = (a+b) / 2
        # attention c'est dans l'ordre inverse : f(a) > 0 et f(b) < 0
        if m**3 - 5*m - 3 > 0:
            a = m
        else:
            b = m
    return (a, b)

def solution3(s):
    # entre 2 et 3
    a = 2
    b = 3
    while b-a >= s:
        m = (a+b) / 2
        if m**3 - 5*m - 3 > 0:
            b = m
        else:
            a = m
    return (a, b)

# test
print(solution1(1e-6))
print(solution2(1e-6))
print(solution3(1e-6))

#%% exercice 6.1
# exécuter et observer en faisant varier t
t = 1

import numpy as np
import matplotlib.pyplot as plt

X = np.linspace(-8, 4, 100)
Y = np.exp(X)
T = 3 + t*X
plt.grid(True)
plt.xlim(-8, 4)
plt.ylim(-1, 10)
plt.title("Exercice 6")
plt.plot(X, Y, color="blue", label="$e^x$")
plt.plot(X, T, color="red", label="$3+tx$")
plt.legend()
plt.show()

#%% exercice 6.2

import math

def borne_x(t):
    n = 0
    while math.exp(n) < 3 + t*n:
        n = n + 1
    return n

# test
print(borne_x(1))
print(borne_x(5))
print(borne_x(10))
print(borne_x(100))

#%%

def solution_x(t, s):
    a = 0
    b = borne_x(t)
    while b-a >= s:
        m = (a+b) / 2
        if math.exp(m) >= 3 + t*m:
            b = m
        else:
            a = m
    return (a, b)

# test
print(solution_x(1, 1e-6))
print(solution_x(5, 1e-6))
print(solution_x(10, 1e-6))
print(solution_x(100, 1e-6))

#%%

def borne_y(t):
    n = 0
    while math.exp(n) < 3 + t*n:
        n = n - 1
    return n

# test
print(borne_y(2))
print(borne_y(1))
print(borne_y(0.5))
print(borne_y(0.1))

#%%

def solution_y(t, s):
    a = borne_y(t)
    b = 0
    while b-a >= s:
        m = (a+b) / 2
        if math.exp(m) >= 3 + t*m:
            a = m
        else:
            b = m
    return (a, b)

# test
print(solution_y(2, 1e-6))
print(solution_y(1, 1e-6))
print(solution_y(0.5, 1e-6))

#%% exercice 7

def est_croissante(L):
    for i in range(len(L)-1):
        if L[i] > L[i+1]:
            return False
    return True

# test
print(est_croissante([1, 6, 8, 10]))
print(est_croissante([7, 3, 4, 6]))
print(est_croissante([1, 8, 3, 9]))

#%% exercice 8

def cherche_iteratif(L, x):
    for i in range(len(L)):
        if L[i] == x:
            return i
    return None

# test
L = [1, 5, 12, 13, 16, 18, 25, 30]
print(cherche_iteratif(L, 12))
print(cherche_iteratif(L, 1))
print(cherche_iteratif(L, 30))
print(cherche_iteratif(L, 14))
print(cherche_iteratif(L, -10))
print(cherche_iteratif(L, 45))

#%% exercice 9

def cherche_dichotomie(L, x):
    n = len(L)
    a = 0
    b = n - 1
    if x == L[a]:
        return a
    elif x == L[b]:
        return b
    elif x < L[a] or x > L[b]:
        return None
    while b-a > 1:
        m = (a+b) // 2
        if x == L[m]:
            return m
        elif x > L[m] :
            a = m
        else:
            b = m
    return None

# tests
L = [1, 5, 12, 13, 16, 18, 25, 30]
print(cherche_dichotomie(L, 12))
print(cherche_dichotomie(L, 1))
print(cherche_dichotomie(L, 30))
print(cherche_dichotomie(L, 14))
print(cherche_dichotomie(L, -10))
print(cherche_dichotomie(L, 45))

#%% exercice 10
# exécuter une fois pour charger le fichier

with open("dictionnaire.txt", "r", encoding="utf-8") as f:
    dictionnaire = [s.strip() for s in f]
    dictionnaire.sort()
    print("longueur du dictionnaire:", len(dictionnaire))
    # extrait : un mot tous les 50000
    print(dictionnaire[::50000])

# la variable dictionaire est une liste de mots

#%% tests
# doit renvoyer True, sinon appeler à l'aide...
print(est_croissante(dictionnaire))

#%% tests

x = "python"
print(cherche_iteratif(dictionnaire, x))
print(cherche_dichotomie(dictionnaire, x))
x = "mathématiques"
print(cherche_iteratif(dictionnaire, x))
print(cherche_dichotomie(dictionnaire, x))
x = "ortaugraffe"
print(cherche_iteratif(dictionnaire, x))
print(cherche_dichotomie(dictionnaire, x))
# à vous ...

#%% un calcul

import math
print(math.log(len(dictionnaire)) / math.log(2))

#%% exercice 11

import timeit
# choisir un mot
x = "mathématiques"
# la fonction à chronométrer ne doit pas contenir de print !!!
# la réponse est en secondes
#%%
print(timeit.timeit("cherche_iteratif(dictionnaire, x)", number=1000, globals=globals()))
#%%
print(timeit.timeit("cherche_dichotomie(dictionnaire, x)", number=1000, globals=globals()))
#%%