Projet récapitulatif : Fondamentaux 🎯

Bravo d'être arrivé jusqu'ici ! Cette leçon est un grand défi pour vérifier que tu as bien tout compris. Chaque exercice est expliqué simplement, avec la méthode et le pseudo-code avant le code Python.

💡 Avant de coder : essaie d'écrire la solution en pseudo-code sur une feuille, puis traduis-la en Python dans l'onglet Sandbox.

---

Exercices Étape 1 — Bases et logique 🧩

1. Factorielle — version itérative ET récursive 🔢

La factorielle de n (notée n!) c'est : n × (n-1) × (n-2) × … × 1. Exemple : 5! = 5 × 4 × 3 × 2 × 1 = 120

Méthode itérative (avec une boucle) : On multiplie les nombres de 1 à n dans une boucle.

Exécution pas à pas
pseudo
1/8
1FONCTION factorielle_iterative(n)2    resultat ← 13    POUR i ALLANT DE 1 À n FAIRE4        resultat ← resultat × i5    FIN POUR6    RETOURNER resultat7FIN FONCTION8 
🧩
FONCTION factorielle_iterative(n)
FONCTION factorielle_iterative(n)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "factorielle_iterative(n)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

Méthode récursive (la fonction s'appelle elle-même) :

• Cas de base : 0! = 1 et 1! = 1
• Appel récursif : n! = n × (n-1)!

Exécution pas à pas
pseudo
1/8
1FONCTION factorielle_recursive(n)2    SI n <= 1 ALORS              ⬅ Cas de base3        RETOURNER 14    SINON5        RETOURNER n × factorielle_recursive(n - 1)  ⬅ Appel récursif6    FIN SI7FIN FONCTION8 
🧩
FONCTION factorielle_recursive(n)
FONCTION factorielle_recursive(n)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "factorielle_recursive(n)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

def factorielle_iterative(n):
    resultat = 1
    for i in range(1, n + 1):
        resultat = resultat * i
    return resultat

def factorielle_recursive(n):
    if n <= 1:
        return 1
    return n * factorielle_recursive(n - 1)

print(factorielle_iterative(5))   # 120
print(factorielle_recursive(5))   # 120

🎯 Teste avec : 0! = 1, 3! = 6, 7! = 5040

---

2. Suite de Fibonacci — itératif ET récursif 🌀

Fibonacci : chaque nombre est la somme des deux précédents. Suite : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34…

• F(0) = 0, F(1) = 1
• F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5…

Méthode itérative : On garde les deux dernières valeurs en mémoire.

Exécution pas à pas
pseudo
1/14
1FONCTION fibonacci_iterative(n)2    SI n <= 1 ALORS3        RETOURNER n4    FIN SI5    a ← 0    ⬅ F(0)6    b ← 1    ⬅ F(1)7    POUR i ALLANT DE 2 À n FAIRE8        c ← a + b    ⬅ F(i) = F(i-1) + F(i-2)9        a ← b        ⬅ On décale10        b ← c11    FIN POUR12    RETOURNER b13FIN FONCTION14 
🧩
FONCTION fibonacci_iterative(n)
FONCTION fibonacci_iterative(n)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "fibonacci_iterative(n)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

Méthode récursive : Élégante mais plus lente.

Exécution pas à pas
pseudo
1/8
1FONCTION fibonacci_recursive(n)2    SI n <= 1 ALORS              ⬅ Cas de base3        RETOURNER n4    SINON5        RETOURNER fibonacci_recursive(n-1) + fibonacci_recursive(n-2)  ⬅ Somme des 2 précédents6    FIN SI7FIN FONCTION8 
🧩
FONCTION fibonacci_recursive(n)
FONCTION fibonacci_recursive(n)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "fibonacci_recursive(n)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

def fibonacci_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

print(fibonacci_iterative(10))   # 55
print(fibonacci_recursive(10))   # 55

🎯 Teste avec : F(0) = 0, F(1) = 1, F(6) = 8, F(20) = 6765

---

3. Vérifier si un nombre est premier 🔍

Un nombre premier est divisible seulement par 1 et par lui-même. Exemples : 2, 3, 5, 7, 11, 13… (1 n'est PAS premier)

Méthode : On teste tous les diviseurs de 2 à √n. Si aucun ne divise n, alors n est premier.

Exécution pas à pas
pseudo
1/12
1FONCTION est_premier(n)2    SI n <= 1 ALORS              ⬅ 1 n'est pas premier3        RETOURNER Faux4    FIN SI5    POUR i ALLANT DE 2 À √n FAIRE   ⬅ On ne teste que jusqu'à la racine carrée6        SI n % i == 0 ALORS       ⬅ Si n divisible par i → pas premier7            RETOURNER Faux8        FIN SI9    FIN POUR10    RETOURNER Vrai                ⬅ Aucun diviseur trouvé → premier11FIN FONCTION12 
🧩
FONCTION est_premier(n)
FONCTION est_premier(n)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "est_premier(n)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

import math

def est_premier(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

print(est_premier(7))   # True
print(est_premier(8))   # False
print(est_premier(97))  # True

💡 Pourquoi √n ? Si n = a × b, au moins un des deux facteurs est ≤ √n. Pas besoin de chercher plus loin !

---

4. Inverser une chaîne de caractères 🔄

"hello" à l'envers → "olleh"

Exécution pas à pas
pseudo
1/8
1FONCTION inverser_chaine(s)2    resultat ← ""3    POUR i ALLANT DE longueur(s)-1 À 0 (en descendant) FAIRE4        resultat ← resultat + s[i]5    FIN POUR6    RETOURNER resultat7FIN FONCTION8 
🧩
FONCTION inverser_chaine(s)
FONCTION inverser_chaine(s)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "inverser_chaine(s)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

def inverser_chaine(s):
    resultat = ""
    for i in range(len(s) - 1, -1, -1):   # On part de la fin
        resultat = resultat + s[i]         # On ajoute chaque caractère
    return resultat

print(inverser_chaine("hello"))   # "olleh"
print(inverser_chaine("12345"))   # "54321"

💡 Astuce : En Python, tu peux aussi écrire s[::-1] — mais le but ici est de comprendre la logique !

---

5. Vérifier un palindrome 🪞

Un palindrome se lit pareil dans les deux sens : "kayak", "radar", "été", "ressasser".

Exécution pas à pas
pseudo
1/13
1FONCTION est_palindrome(s)2    DEBUT ← 0                      ⬅ Premier index3    FIN ← longueur(s) - 1          ⬅ Dernier index4    TANT QUE DEBUT < FIN FAIRE5        SI s[DEBUT] != s[FIN] ALORS   ⬅ Si les caractères sont différents6            RETOURNER Faux             ⬅ Pas un palindrome7        FIN SI8        DEBUT ← DEBUT + 1           ⬅ On avance9        FIN ← FIN - 1               ⬅ On recule10    FIN TANT QUE11    RETOURNER Vrai                  ⬅ Tous les couples correspondent12FIN FONCTION13 
🧩
FONCTION est_palindrome(s)
FONCTION est_palindrome(s)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "est_palindrome(s)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

def est_palindrome(s):
    debut = 0
    fin = len(s) - 1
    while debut < fin:
        if s[debut] != s[fin]:
            return False
        debut = debut + 1
        fin = fin - 1
    return True

print(est_palindrome("kayak"))    # True
print(est_palindrome("hello"))    # False
print(est_palindrome("radar"))    # True

🎯 Défi : Peux-tu adapter la fonction pour ignorer les espaces et majuscules ? ("Esope reste ici et se repose" → palindrome !)

---

Exercices Étape 2 — Tableaux et complexité 📊

6. Trouver le max et le min d'un tableau 🏆

Exécution pas à pas
pseudo
1/20
1FONCTION trouver_max(tab)2    max ← tab[0]                  ⬅ On suppose que le premier est le max3    POUR CHAQUE valeur DANS tab FAIRE4        SI valeur > max ALORS5            max ← valeur6        FIN SI7    FIN POUR8    RETOURNER max9FIN FONCTION10 11FONCTION trouver_min(tab)12    min ← tab[0]                  ⬅ Pareil mais pour le min13    POUR CHAQUE valeur DANS tab FAIRE14        SI valeur < min ALORS15            min ← valeur16        FIN SI17    FIN POUR18    RETOURNER min19FIN FONCTION20 
🧩
FONCTION trouver_max(tab)
FONCTION trouver_max(tab)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "trouver_max(tab)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

def trouver_max(tab):
    max_val = tab[0]
    for val in tab:
        if val > max_val:
            max_val = val
    return max_val

def trouver_min(tab):
    min_val = tab[0]
    for val in tab:
        if val < min_val:
            min_val = val
    return min_val

notes = [15, 12, 18, 10, 14]
print(trouver_max(notes))  # 18
print(trouver_min(notes))  # 10

⏱ Complexité : O(n) — on parcourt le tableau une fois.

---

7. Trouver les doublons 👯

Trouve les nombres qui apparaissent plusieurs fois dans un tableau.

Exécution pas à pas
pseudo
1/15
1FONCTION trouver_doublons(tab)2    deja_vu ← []                 ⬅ Liste des nombres déjà rencontrés3    doublons ← []                ⬅ Liste des doublons trouvés4    POUR CHAQUE valeur DANS tab FAIRE5        SI valeur EST DANS deja_vu ALORS6            SI valeur PAS DANS doublons ALORS7                ajouter valeur À doublons8            FIN SI9        SINON10            ajouter valeur À deja_vu11        FIN SI12    FIN POUR13    RETOURNER doublons14FIN FONCTION15 
🧩
FONCTION trouver_doublons(tab)
FONCTION trouver_doublons(tab)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "trouver_doublons(tab)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

def trouver_doublons(tab):
    deja_vu = []
    doublons = []
    for valeur in tab:
        if valeur in deja_vu:
            if valeur not in doublons:
                doublons.append(valeur)
        else:
            deja_vu.append(valeur)
    return doublons

print(trouver_doublons([3, 1, 4, 1, 5, 3]))  # [1, 3]

🎯 Défi : Essaie de le faire avec un set ou un dictionnaire pour que ce soit plus rapide !

---

8. Two Sum — trouver deux nombres qui font une somme cible 🎯

Étant donné un tableau [2, 7, 11, 15] et une cible 9, trouve les deux nombres qui additionnés donnent 9 (ici 2 + 7 = 9).

Exécution pas à pas
pseudo
1/11
1FONCTION two_sum(tab, cible)2    POUR i ALLANT DE 0 À longueur(tab) - 1 FAIRE3        POUR j ALLANT DE i + 1 À longueur(tab) - 1 FAIRE4            SI tab[i] + tab[j] == cible ALORS5                RETOURNER [i, j]          ⬅ On retourne les indices6            FIN SI7        FIN POUR8    FIN POUR9    RETOURNER []                           ⬅ Aucune solution10FIN FONCTION11 
🧩
FONCTION two_sum(tab, cible)
FONCTION two_sum(tab, cible)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "two_sum(tab, cible)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

def two_sum(tab, cible):
    for i in range(len(tab)):
        for j in range(i + 1, len(tab)):
            if tab[i] + tab[j] == cible:
                return [i, j]
    return []

print(two_sum([2, 7, 11, 15], 9))   # [0, 1] (car 2 + 7 = 9)
print(two_sum([3, 2, 4], 6))        # [1, 2] (car 2 + 4 = 6)

⏱ Complexité : O(n²) — deux boucles imbriquées. Pour t'entraîner, cherche une version en O(n) avec un dictionnaire !

---

9. Rotation d'un tableau 🔄

Décale tous les éléments d'un tableau de k positions vers la droite. Exemple : [1, 2, 3, 4, 5] avec k = 2 → [4, 5, 1, 2, 3]

Exécution pas à pas
pseudo
1/11
1FONCTION rotation(tab, k)2    n ← longueur(tab)3    k ← k % n                      ⬅ Si k > n, on prend le reste (k = 7 pour n=5 revient à k=2)4    resultat ← []                  ⬅ Nouveau tableau vide5    POUR i ALLANT DE 0 À n - 1 FAIRE6        nouvel_index ← (i + k) % n   ⬅ On décale de k et on boucle avec le modulo7        resultat[nouvel_index] ← tab[i]8    FIN POUR9    RETOURNER resultat10FIN FONCTION11 
🧩
FONCTION rotation(tab, k)
FONCTION rotation(tab, k)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "rotation(tab, k)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

def rotation(tab, k):
    n = len(tab)
    k = k % n  # Si k est plus grand que n
    resultat = [0] * n
    for i in range(n):
        nouvel_index = (i + k) % n
        resultat[nouvel_index] = tab[i]
    return resultat

print(rotation([1, 2, 3, 4, 5], 2))  # [4, 5, 1, 2, 3]
print(rotation([1, 2, 3], 5))        # [2, 3, 1] (car 5%3=2)

💡 Le % (modulo) fait "reboucler" l'index : si on dépasse la fin, on revient au début.

---

10. Fusionner deux tableaux triés ➕

On a deux tableaux déjà triés, on veut les fusionner en un seul tableau trié. Exemple : [1, 3, 5] + [2, 4, 6] → [1, 2, 3, 4, 5, 6]

Exécution pas à pas
pseudo
1/22
1FONCTION fusionner_tries(tab1, tab2)2    i ← 0, j ← 0                  ⬅ On avance dans chaque tableau3    resultat ← []                  ⬅ Résultat fusionné4    TANT QUE i < longueur(tab1) ET j < longueur(tab2) FAIRE5        SI tab1[i] < tab2[j] ALORS6            ajouter tab1[i] À resultat7            i ← i + 18        SINON9            ajouter tab2[j] À resultat10            j ← j + 111        FIN SI12    FIN TANT QUE13    ⬅ On ajoute ce qui reste (un des deux tableaux est vide)14    POUR k ALLANT DE i À longueur(tab1) - 1 FAIRE15        ajouter tab1[k] À resultat16    FIN POUR17    POUR k ALLANT DE j À longueur(tab2) - 1 FAIRE18        ajouter tab2[k] À resultat19    FIN POUR20    RETOURNER resultat21FIN FONCTION22 
🧩
FONCTION fusionner_tries(tab1, tab2)
FONCTION fusionner_tries(tab1, tab2)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "fusionner_tries(tab1, tab2)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.

def fusionner_tries(tab1, tab2):
    i = j = 0
    resultat = []
    while i < len(tab1) and j < len(tab2):
        if tab1[i] < tab2[j]:
            resultat.append(tab1[i])
            i += 1
        else:
            resultat.append(tab2[j])
            j += 1
    # Ajouter les éléments restants
    while i < len(tab1):
        resultat.append(tab1[i])
        i += 1
    while j < len(tab2):
        resultat.append(tab2[j])
        j += 1
    return resultat

print(fusionner_tries([1, 3, 5], [2, 4, 6]))  # [1, 2, 3, 4, 5, 6]
print(fusionner_tries([1, 2, 3], [4, 5]))     # [1, 2, 3, 4, 5]

⏱ Complexité : O(n + m) — on parcourt chaque tableau une seule fois.

---

Vérification des acquis ✅

Avant de passer à la suite, assure-toi de savoir :

• ✅ Écrire une fonction itérative ET récursive (factorielle, Fibonacci)
• ✅ Reconnaître un nombre premier
• ✅ Inverser une chaîne / vérifier un palindrome
• ✅ Parcourir un tableau et trouver le max/min
• ✅ Fusionner deux tableaux triés

🎉 Bravo ! Si tu arrives à faire ces 10 exercices sans regarder les solutions, tu as un super niveau en algorithmique de base ! Passe à la leçon suivante pour découvrir la complexité algorithmique.