Polynésie – Bac NSI 2026 – Jour 1

📄 Sujet complet
🔥🔥🔥🔥🔥
Dans ce sujet, on calcule les termes d'une suite, itérativement et récursivement.

mots clés : Complexité, algorithmique, récursivité, programmation dynamique

🔎 Voir les exercices similaires ↓

📘 Sujet PDF

Polynésie – Bac NSI 2026 – Jour 1 Énoncé de l'exercice 1

Cet exercice porte sur la notion de complexité.

On définit une suite d’entiers Un de la façon suivante :

U0 = 0, U1 = 1, Un = Un-1 + Un-2 pour tout n ≥ 2.

Les premières valeurs de cette suite sont donc les suivantes : U0 = 0, U1 = 1, U2 = 1, U3 = 2, U4 = 3, U5 = 5.

On donne la fonction suivante permettant de calculer les termes de cette suite :

  1. Compléter la fonction récursive suite qui prend en paramètre un entier n et renvoie la valeur de Un.

1 def suite(n):
2     if n < 2:
3         valeur = ...
4     else:
5         valeur = suite(n - 1) + suite(...)
6     return ...

On appelle p la fonction donnant le nombre d’additions à effectuer pour calculer le terme d’indice n de la suite Un avec la fonction proposée ci-dessus. On peut montrer que cette fonction est la suivante :

p(0) = 0 ; p(1) = 0 ; p(n) = 1 + p(n − 1) + p(n − 2) pour tout n ≥ 2.

  1. Écrire une fonction nb_additions_suite prenant en paramètre un entier n et renvoyant la valeur de p(n) où p est la fonction définie ci-dessus.

  2. Calculer les valeurs p(2), p(4) et p(7).

On propose une nouvelle fonction pour calculer les termes de la suite Un :

1 def suite2(n, valeurs_calculees = [0, 1]):
2     if n < len(valeurs_calculees):
3         valeur = valeurs_calculees[n]
4     else:
5         valeurs_calculees.append(suite2(n - 1, valeurs_calculees)
6                                  + suite2(n - 2, valeurs_calculees))
7     return valeurs_calculees[n]

  1. Recopier et compléter le tableau ci-dessous avec le nombre d’additions effectuées par la fonction suite2 pour les calculs des premiers termes de la suite Un.

complexité de suite2
n nombre d’additions
2 1
3 2
4 3
5
6
7

On appelle q la fonction donnant le nombre d’additions à effectuer pour calculer le terme d’indice n de la suite Un avec la fonction suite2.

  1. Expliquer pourquoi suite2 est plus efficace que suite et donner le nom du procédé algorithmique utilisé pour obtenir cette efficacité.

  2. Proposer une version itérative, non récursive, suite3 du calcul des termes de la suite Un.

  3. Expliquer pourquoi la version itérative est préférable à la version récursive pour obtenir un terme quelconque de la suite Un.

▶✅ Correction (cliquer pour afficher) PDF

Polynésie – Bac NSI 2026 – Jour 1 Correction de l'exercice 1

1. Fonction récursive suite

def suite(n):
    if n < 2:
        valeur = n
    else:
        valeur = suite(n - 1) + suite(n - 2)
    return valeur

2. Fonction nb_additions_suite

def nb_additions_suite(n):
    if n < 2:
        return 0
    else:
        return 1 + nb_additions_suite(n - 1) + nb_additions_suite(n - 2)

3. Valeurs de p(2), p(4) et p(7)

n 0 1 2 3 4 5 6 7
p(n) 0 0 1 2 4 7 12 20

p(2) = 1 + 0 + 0 = 1, p(4) = 1 + p(3) + p(2) = 1 + 2 + 1 = 4, p(7) = 1 + p(6) + p(5) = 1 + 12 + 7 = 20.

4. Nombre d’additions de suite2

n nombre d’additions
2 1
3 2
4 3
5 4
6 5
7 6

Chaque terme de U₂ à Uₙ n’est calculé qu’une fois, avec une seule addition : q(n) = n − 1.

▶ Animation : l’arbre des appels de suite(n)

Chaque nœud est un appel suite(k). Les appels identiques ont la même couleur : on voit combien de fois les mêmes termes sont recalculés. Avec suite2, chaque terme n’est calculé qu’une fois (les appels déjà mémorisés sont barrés).

n =

5. Pourquoi suite2 est plus efficace

suite recalcule de nombreuses fois les mêmes termes (suite(5) appelle suite(3) deux fois, suite(2) trois fois…) : son coût est exponentiel. suite2 mémorise chaque terme calculé dans la liste valeurs_calculees et le réutilise : chaque terme est calculé une seule fois, le coût devient linéaire. Ce procédé s’appelle la mémoïsation (programmation dynamique).

6. Version itérative suite3

def suite3(n):
    a, b = 0, 1          # a = U_0, b = U_1
    for i in range(n):
        a, b = b, a + b
    return a

7. Pourquoi préférer la version itérative

La version itérative utilise une mémoire constante (deux variables) et fait n additions. Les versions récursives empilent un appel par terme : pour n grand, on dépasse la limite de récursion de Python (environ 1 000 appels) et le programme s’arrête avec une erreur RecursionError. De plus, chaque appel de fonction coûte du temps et de la mémoire.

Une erreur, un oubli ? Écrivez-moi : frederic.peuriere@lfcl.pt

💻 Console Python (cliquer pour afficher)

🔎 Exercices sur des thèmes similaires