import math
from time import time


# =============================================
# Exercice 1 : Suite récurrente u_n
# =============================================

def suite(n):
    """Renvoie u_n avec u0=1 et u_{n+1}=3*u_n -1"""
    u = 1                     # u0 = 1
    if n == 0:
        return u
    for i in range(1, n+1):   # on fait n étapes
        u = 3 * u - 1
    return u


# Question 2 : Nombre de calculs
# Pour suite(n) : n multiplications, n soustractions et n affectations environ


def suitee(n):
    """Version plus économique : on calcule directement avec une boucle"""
    u = 1
    if n == 0:
        return u
    for i in range(n):        # boucle plus simple
        u = 3 * u - 1
    return u


def suiteee(n):
    """Renvoie la liste contenant u0, u1, ..., un"""
    L = []
    u = 1
    L.append(u)               # on ajoute u0
    
    for i in range(n):        # on ajoute les suivants
        u = 3 * u - 1
        L.append(u)
    
    return L


# Tests
print("u_5 =", suite(5))
print("Liste jusqu'à u_5 :", suiteee(5))


# =============================================
# Exercice 2 : Méthode de la dichotomie
# =============================================

def f1(x):
    """f(x) = cos(x) - x"""
    return math.cos(x) - x


def dicho(f, a, b, epsilon):
    """Applique la dichotomie pour trouver x tel que f(x) ≈ 0"""
    while abs(f(a)) >= epsilon and abs(f(b)) >= epsilon:
        m = (a + b) / 2          # milieu de l'intervalle
        
        if f(a) * f(m) < 0:      # le zéro est entre a et m
            b = m
        else:                    # le zéro est entre m et b
            a = m
    
    # On retourne le milieu de l'intervalle final
    return (a + b) / 2


# Application : point fixe de cosinus (solution de cos(x) = x)
print("\nApproximation du point fixe de cos(x) à 0.01 près :")
x_approx = dicho(f1, 0, 1, 0.01)
print("x ≈", round(x_approx, 4))


def dicho2(L, m):
    """Dichotomie sur une liste triée L pour chercher m"""
    debut = 0
    fin = len(L) - 1
    
    while debut <= fin:
        milieu = (debut + fin) // 2
        
        if L[milieu] == m:
            return True
        elif L[milieu] < m:
            debut = milieu + 1
        else:
            fin = milieu - 1
    
    return False


# Test de dicho2
L_test = []
for i in range(50):
    L_test.append(2 * i)   # liste des 50 premiers nombres pairs : 0,2,4,...,98

print("10 est dans L_test ?", dicho2(L_test, 10))
print("11 est dans L_test ?", dicho2(L_test, 11))


# =============================================
# Exercice 3 : Fibonacci et suites
# =============================================

def fibo(n):
    """Renvoie v_n (Fibonacci avec v0=1, v1=1) en utilisant un dictionnaire"""
    if n == 0 or n == 1:
        return 1
    
    d = {}                    # dictionnaire pour stocker les valeurs
    d[0] = 1
    d[1] = 1
    
    for k in range(2, n+1):
        d[k] = d[k-1] + d[k-2]
    
    return d[n]


# Question 2 : Environ n additions et n affectations


def fiboDiv(M):
    """Renvoie le plus petit n tel que v_n >= M"""
    if M <= 1:
        return 0
    
    d = {}
    d[0] = 1
    d[1] = 1
    n = 1
    
    while d[n] < M:
        n = n + 1
        d[n] = d[n-1] + d[n-2]
    
    return n


print("\nPlus petit n tel que fibo(n) >= 100 :", fiboDiv(100))


def suite2(n):
    """Renvoie z_n avec z0=1 et z_n = z0 + 2z1 + 4z2 + ... + 2^{n-1} z_{n-1}"""
    if n == 0:
        return 1
    
    d = {}
    d[0] = 1
    
    for k in range(1, n+1):
        somme = 0
        for i in range(k):               # somme des termes précédents
            somme = somme + (2 ** i) * d[i]
        d[k] = somme
    
    return d[n]


print("z_4 =", suite2(4))


# =============================================
# Exercice 4 : Convergence de suites
# =============================================

def converge(u, epsilon):
    """Renvoie le premier n tel que |u(n+1) - u(n)| < epsilon"""
    n = 0
    while n < 5000:                      # sécurité contre boucle infinie
        diff = abs(u(n+1) - u(n))
        if diff < epsilon:
            print("La suite semble converger à partir de n =", n)
            return n
        n = n + 1
    print("Aucune convergence détectée avant n=5000")
    return False


# Fonctions sommes
def somme1(n):
    """Somme de 1/k^2 de k=1 à n"""
    if n == 0:
        return 0
    s = 0.0
    for k in range(1, n+1):
        s = s + 1.0 / (k * k)
    return s


def somme2(n):
    """Somme de 1/k (harmonique)"""
    if n == 0:
        return