import math

# ==============================================================================
# PARTIE 1 : DÉFINITION DES FONCTIONS
# ==============================================================================

def f(x):
    """
    Fonction f(x) = 2 - x - e^x
    Correspond à l'équation (3) : 2 - x = e^x <=> f(x) = 0
    
    """
    return 2 - x - math.exp(x)

def df(x):
    """
    Dérivée f'(x) = -1 - e^x
    Utilisée pour la méthode de Newton.
    
    """
    return -1 - math.exp(x)

def g_lambda(x, lam=0.25):
    """
    Fonction g_lambda(x) pour la méthode du point fixe.
    Formule : lambda * ((2 - x) * e^(-x) - 1) + x
    Par défaut, lambda = 1/4.
    
    """
    return lam * ((2 - x) * math.exp(-x) - 1) + x

# ==============================================================================
# PARTIE 2 : ALGORITHMES DE RÉSOLUTION
# ==============================================================================

def methode_point_fixe(g, x0, epsilon, n_max_iter=1000):
    """
    Implémente l'algorithme du point fixe.
    Arrêt si |x_{n+1} - x_n| < epsilon.
    
    """
    x_old = x0
    print(f"{'Itération':<10} | {'x_n':<20} | {'Erreur est.'}")
    print("-" * 45)
    
    for n in range(1, n_max_iter + 1):
        x_new = g(x_old)
        erreur = abs(x_new - x_old)
        
        # Affichage pour suivre la convergence (optionnel mais pédagogique)
        if n <= 10 or erreur < epsilon * 100: # On n'affiche pas tout si c'est trop long
             print(f"{n:<10} | {x_new:<20.10f} | {erreur:.2e}")
        
        if erreur < epsilon:
            return x_new, n
        
        x_old = x_new
        
    print("La méthode n'a pas convergé après", n_max_iter, "itérations.")
    return x_old, n_max_iter

def methode_newton(f, df, x0, epsilon, n_max_iter=100):
    """
    Implémente l'algorithme de Newton.
    x_{n+1} = x_n - f(x_n)/f'(x_n)
    
    """
    x_old = x0
    print(f"{'Itération':<10} | {'x_n':<20} | {'Erreur est.'}")
    print("-" * 45)
    
    for n in range(1, n_max_iter + 1):
        deriv = df(x_old)
        if deriv == 0:
            print("Erreur : Dérivée nulle, division impossible.")
            return None, n
            
        x_new = x_old - f(x_old) / deriv
        erreur = abs(x_new - x_old)
        
        print(f"{n:<10} | {x_new:<20.10f} | {erreur:.2e}")
        
        if erreur < epsilon:
            return x_new, n
        
        x_old = x_new
        
    return x_old, n_max_iter

# ==============================================================================
# PARTIE 3 : PROGRAMME PRINCIPAL (MAIN)
# ==============================================================================

if __name__ == "__main__":
    # Paramètres communs
    x0 = 0
    epsilon = 1e-10  # 10^-10 

    print("=== EXERCICE 3 : RÉSOLUTION NUMÉRIQUE ===")
    
    # --- A. Méthode du Point Fixe ---
    print("\n--- A. Méthode du Point Fixe (lambda = 1/4) ---")
    
    # Calcul théorique du majorant n_max (Question 2c) 
    # k approx 0.816 (calculé dans la correction théorique)
    k = 0.816 
    x1 = g_lambda(x0)
    dist_init = abs(x1 - x0)
    
    # Formule : n >= (ln(epsilon*(1-k)/|x1-x0|)) / ln(k)
    # Attention aux signes : ln(k) est négatif car k < 1
    n_theorique = (math.log((epsilon * (1 - k)) / dist_init)) / math.log(k)
    print(f"Estimation théorique du nombre d'itérations nécessaire : {math.ceil(n_theorique)}")
    
    # Résolution numérique
    sol_pf, iter_pf = methode_point_fixe(g_lambda, x0, epsilon)
    print(f"\nSolution Point Fixe : {sol_pf:.10f}")
    print(f"Nombre d'itérations réel : {iter_pf}")
    print(f"Vérification n <= n_max : {iter_pf} <= {math.ceil(n_theorique)} -> {iter_pf <= math.ceil(n_theorique)}")

    # --- B. Méthode de Newton ---
    print("\n\n--- B. Méthode de Newton ---")
    # 
    
    sol_newton, iter_newton = methode_newton(f, df, x0, epsilon)
    print(f"\nSolution Newton : {sol_newton:.10f}")
    print(f"Nombre d'itérations : {iter_newton}")

    # --- Comparaison ---
    print("\n--- Conclusion ---")
    print(f"Newton est {iter_pf / iter_newton:.1f} fois plus rapide en nombre d'itérations.")