Puissances de matrices et Fibonacci

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 5 — Algorithmes dichotomiques

Énoncé

En admettant la fonction matmul(A, B) multipliant deux matrices $2 \times 2$ , adapter l'exponentiation rapide pour calculer $F_{100}$ (le 100e terme de la suite de Fibonacci) via la relation : $(1110)^{n} = (F_{n + 1} F_{n} F_{n} F_{n - 1})$

Corrigé

def matmul(A, B):
    return [[A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
            [A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]]]

def matpow(A, n: int):
    R = [[1, 0], [0, 1]] # Matrice identité (neutre)
    B, m = A, n
    while m > 0:
        # Invariant : R @ B**m == A**n
        if m % 2 == 1:
            R = matmul(R, B)
        B = matmul(B, B)
        m = m // 2
    return R

F = matpow([[1, 1], [1, 0]], 100)
# F[0][1] contient la valeur exacte de F_100
assert F[0][1] == 354224848179261915075

La complexité de ce calcul est de $O (lo g n)$ multiplications de matrices.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.