Exercices corrigés Python (complexité)

FONCTION est_trie(T, n):
    SI n ≤ 1 ALORS
        RETOURNER Vrai
    SINON
        SI T[0] > T[1] ALORS
            RETOURNER Faux
        SINON
            RETOURNER est_trie(T[1:], n-1)
        FINSI
    FINSI

def binaire(N):
    """
    Affiche la représentation binaire de N.
    """
    if N > 1:
        binaire(N // 2)
    print(N % 2, end='')


def binaire_chaine(N):
    """
    Retourne la représentation binaire sous forme de chaîne.
    """
    if N == 0:
        return '0'
    if N == 1:
        return '1'
    return binaire_chaine(N // 2) + str(N % 2)


# Tests
print("Binaire de 13 : ", end='')
binaire(13)
print()
print(f"Binaire de 42 : {binaire_chaine(42)}")
print(f"Binaire de 255 : {binaire_chaine(255)}")

def fib_rec(n):
    """
    Version récursive naïve de Fibonacci.
    """
    if n <= 1:
        return n
    return fib_rec(n-1) + fib_rec(n-2)


def fib_memo(n, memo=None):
    """
    Version récursive avec mémoïsation.
    """
    if memo is None:
        memo = {}
    
    if n <= 1:
        return n
    
    if n not in memo:
        memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    
    return memo[n]


from functools import lru_cache

@lru_cache(maxsize=None)
def fib_cache(n):
    """
    Version avec décorateur lru_cache.
    """
    if n <= 1:
        return n
    return fib_cache(n-1) + fib_cache(n-2)


# Tests
print("Fib(10) (récursif) =", fib_rec(10))
print("Fib(40) (mémoïsation) =", fib_memo(40))
print("Fib(100) (cache) =", fib_cache(100))

def suite(n):
    """
    Version récursive naïve.
    """
    if n <= 2:
        return 1
    return 3 * suite(n-1) + suite(n-2)


def suite_memo(n, memo=None):
    """
    Version avec mémoïsation.
    """
    if memo is None:
        memo = {}
    
    if n <= 2:
        return 1
    
    if n not in memo:
        memo[n] = 3 * suite_memo(n-1, memo) + suite_memo(n-2, memo)
    
    return memo[n]


# Tests
print("U₅ (récursif) =", suite(5))
print("U₁₀ (mémoïsation) =", suite_memo(10))
print("U₂₀ (mémoïsation) =", suite_memo(20))

def pair(N):
    """
    Détermine si N est pair par récursivité mutuelle.
    """
    if N == 0:
        return True
    return impair(N-1)


def impair(N):
    """
    Détermine si N est impair par récursivité mutuelle.
    """
    if N == 0:
        return False
    return pair(N-1)


# Tests
for i in range(10):
    print(f"{i} est pair ? {pair(i)} - impair ? {impair(i)}")

def max_rec1(T, n):
    """
    Maximum récursif : max(T[0..n-1]) = max(T[n-1], max(T[0..n-2]))
    Complexité : O(n)
    """
    if n == 1:
        return T[0]
    
    max_prec = max_rec1(T, n-1)
    return max_prec if max_prec > T[n-1] else T[n-1]

def plus_longue_coupe(T, debut, fin):
    """
    Retourne la longueur de la plus longue séquence de 1 consécutifs
    dans T[debut:fin+1] (approche diviser pour régner).
    """
    if debut == fin:
        return 1 if T[debut] == 1 else 0
    
    milieu = (debut + fin) // 2
    
    # Cas 1 et 2 : séquence dans une moitié
    gauche = plus_longue_coupe(T, debut, milieu)
    droit = plus_longue_coupe(T, milieu + 1, fin)
    
    # Cas 3 : séquence à cheval
    # Longueur de la séquence de 1 se terminant à la fin de la moitié gauche
    longueur_gauche = 0
    i = milieu
    while i >= debut and T[i] == 1:
        longueur_gauche += 1
        i -= 1
    
    # Longueur de la séquence de 1 commençant au début de la moitié droite
    longueur_droit = 0
    j = milieu + 1
    while j <= fin and T[j] == 1:
        longueur_droit += 1
        j += 1
    
    cheval = longueur_gauche + longueur_droit
    
    return max(gauche, droit, cheval)


# Version alternative avec retour de plusieurs informations
def plus_longue_coupe_complet(T, debut, fin):
    """
    Retourne un triplet (max, prefixe, suffixe) où :
    - max : longueur max de 1 consécutifs dans l'intervalle
    - prefixe : longueur du préfixe de 1
    - suffixe : longueur du suffixe de 1
    """
    if debut == fin:
        if T[debut] == 1:
            return (1, 1, 1)
        else:
            return (0, 0, 0)
    
    milieu = (debut + fin) // 2
    g_max, g_pref, g_suff = plus_longue_coupe_complet(T, debut, milieu)
    d_max, d_pref, d_suff = plus_longue_coupe_complet(T, milieu + 1, fin)
    
    # Calcul du nouveau préfixe
    if g_pref == milieu - debut + 1:  # toute la gauche est remplie de 1
        pref = g_pref + d_pref
    else:
        pref = g_pref
    
    # Calcul du nouveau suffixe
    if d_suff == fin - milieu:  # toute la droite est remplie de 1
        suff = d_suff + g_suff
    else:
        suff = d_suff
    
    # Séquence à cheval
    cheval = g_suff + d_pref
    
    # Maximum global
    maxi = max(g_max, d_max, cheval)
    
    return (maxi, pref, suff)


# Test
T = [0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1]
print(f"Tableau : {T}")
print(f"Longueur max (version simple) : {plus_longue_coupe(T, 0, len(T)-1)}")
maxi, pref, suff = plus_longue_coupe_complet(T, 0, len(T)-1)
print(f"Longueur max (version complète) : {maxi}")

def multiplier_naif(a, b):
    """
    Multiplication par additions successives.
    a * b = a + a + ... + a (b fois)
    Complexité : O(b) additions
    """
    if b == 0:
        return 0
    return a + multiplier_naif(a, b-1)


def multiplier_opt(a, b):
    """
    Version optimisée : on prend le plus petit des deux comme compteur.
    Complexité : O(min(a,b)) additions
    """
    if a == 0 or b == 0:
        return 0
    
    if a < b:
        return multiplier_opt(b, a)  # inversion pour minimiser les appels
    
    return a + multiplier_opt(a, b-1)


# Test
print(f"5 × 3 = {multiplier_naif(5, 3)}")
print(f"100 × 2 = {multiplier_naif(100, 2)}")
print(f"3 × 5 (opt) = {multiplier_opt(3, 5)}")