Accueil › Cours › Les algorithmes récurrents

Les leçons de ce chapitre

1. Les suites récurrentes
2. Fibonacci et le nombre d'or
3. Le triangle de Pascal

Leçon 22.1 : Les suites récurrentes

10 min

Une suite récurrente d'ordre 1 donne un premier terme U0, puis une règle pour passer d'un terme au suivant : par exemple U(n) = 2 × U(n − 1) + 1. Pour calculer U(n), on part de U0 et on applique la règle n fois.

• Une seule variable u suffit : u ← 2 × u + 1 remplace l'ancien terme par le nouveau.
• Si on doit garder tous les termes, on les range dans un tableau : U[i] ← 2 × U[i − 1] + 1.

Astuce : La boucle Pour i de 1 à n fait exactement n applications de la règle : après elle, u vaut U(n).

En Python

Les termes de U(n) = 2 × U(n − 1) + 1, avec U0 = 1.

n = int(input())
u = 1
print("U0 =", u)
for i in range(1, n + 1):
    u = 2 * u + 1
    print("U" + str(i), "=", u)

En algorithme

convch(i) colle le numéro du terme au nom U.

Algorithme Suite
Début
  Lire(n)
  u ← 1
  Ecrire("U0 = ", u)
  Pour i de 1 à n Faire
    u ← 2 * u + 1
    Ecrire("U" + convch(i), " = ", u)
  FinPour
Fin

TDO
Objet | Type/Nature
n, u, i | Entier

Leçon 22.2 : Fibonacci et le nombre d'or

11 min

La suite de Fibonacci est d'ordre 2 : chaque terme est la somme des deux précédents. F0 = 0, F1 = 1, puis F(n) = F(n − 1) + F(n − 2) : 0, 1, 1, 2, 3, 5, 8, 13…

• Il faut garder deux variables, a (l'avant-dernier) et b (le dernier).
• À chaque tour : c ← a + b, puis a ← b et b ← c (dans cet ordre).

Le quotient F(n) / F(n − 1) se rapproche du nombre d'or φ = 1.6180339… On s'arrête quand deux quotients successifs diffèrent de moins de eps.

Attention : Si tu écris a ← b puis b ← a + b, tu utilises le nouveau a : le résultat est faux. Passe par c.

En Python

Les n premiers termes de Fibonacci (n ≥ 2).

n = int(input())
a = 0
b = 1
print(a)
print(b)
for i in range(2, n):
    c = a + b
    a = b
    b = c
    print(c)

En algorithme

Trois variables, et l'ordre des affectations compte.

Algorithme Fibonacci
Début
  Lire(n)
  a ← 0
  b ← 1
  Ecrire(a)
  Ecrire(b)
  Pour i de 2 à n - 1 Faire
    c ← a + b
    a ← b
    b ← c
    Ecrire(c)
  FinPour
Fin

TDO
Objet | Type/Nature
n, a, b, c, i | Entier

Leçon 22.3 : Le triangle de Pascal

11 min

Le triangle de Pascal range les coefficients C(n, p) dans une matrice : la ligne i contient C(i, 0), C(i, 1), …, C(i, i). Chaque case est la somme de la case au-dessus et de celle au-dessus à gauche : M[i, j] ← M[i − 1, j] + M[i − 1, j − 1]. La première colonne et la diagonale valent 1.

Astuce : C'est une récurrence d'ordre 1 sur les lignes : chaque ligne se calcule à partir de la précédente.

En Python

Les n premières lignes du triangle (indices à partir de 0 en Python).

n = int(input())
M = [[0] * n for i in range(n)]
for i in range(n):
    M[i][0] = 1
    M[i][i] = 1
    for j in range(1, i):
        M[i][j] = M[i - 1][j] + M[i - 1][j - 1]
for i in range(n):
    ligne = ""
    for j in range(i + 1):
        ligne = ligne + str(M[i][j]) + " "
    print(ligne)

En algorithme

En algorithme, les lignes et les colonnes vont de 1 à n.

Algorithme Pascal
Début
  Lire(n)
  Pour i de 1 à n Faire
    M[i, 1] ← 1
    M[i, i] ← 1
    Pour j de 2 à i - 1 Faire
      M[i, j] ← M[i - 1, j] + M[i - 1, j - 1]
    FinPour
  FinPour
  Pour i de 1 à n Faire
    ligne ← ""
    Pour j de 1 à i Faire
      ligne ← ligne + convch(M[i, j]) + " "
    FinPour
    Ecrire(ligne)
  FinPour
Fin

TDO
Objet | Type/Nature
M | Matrice de 20 lignes et 20 colonnes d'entiers
n, i, j | Entier
ligne | Chaîne

S'entraîner gratuitement

Chaque leçon a 3 exercices gratuits avec indices pour appliquer ce chapitre avec Hannibot.

← Chapitre précédent : La récursivité · Chapitre suivant : Les fichiers →

Tous les chapitres · Voir les devoirs corrigés de 2ème TI

Cours écrit pour Mission Carthage d'après le programme officiel. Ton professeur reste la référence.