Exercices - Langages et programmation¶
Récursivité¶
Exercice 1 - Fonctions récursives de base¶
Écrire les fonctions récursives suivantes :
a. somme(n) : renvoie la somme des entiers de 1 à n.
b. compter_chiffres(n) : renvoie le nombre de chiffres d'un entier positif n.
c. renverser(chaine) : renvoie la chaîne de caractères inversée.
d. pgcd(a, b) : calcule le PGCD de a et b par l'algorithme d'Euclide.
Solution
a.
b.
c.
def renverser(chaine):
if len(chaine) <= 1:
return chaine
return chaine[-1] + renverser(chaine[:-1])
d.
Exercice 2 - Analyse de fonctions récursives¶
Pour chaque fonction, déterminer : - le cas de base ; - le cas récursif ; - le variant (preuve de terminaison) ; - le résultat de l'appel indiqué.
a.
Appel :mystere(13)
b.
def f(chaine, c):
if chaine == "":
return 0
if chaine[0] == c:
return 1 + f(chaine[1:], c)
return f(chaine[1:], c)
f("abracadabra", "a")
Solution
a.
- Cas de base : n == 0 → renvoie 0
- Cas récursif : renvoie n % 2 + mystere(n // 2)
- Variant : n (divisé par 2 à chaque appel, converge vers 0)
- mystere(13) : 13 en binaire = 1101, donc la fonction compte le nombre de bits à 1. Résultat : 3.
b.
- Cas de base : chaine == "" → renvoie 0
- Cas récursif : avance dans la chaîne (chaine[1:])
- Variant : len(chaine) (décroît de 1 à chaque appel)
- f("abracadabra", "a") : compte les occurrences de "a" → 5.
Exercice 3 - Dessins récursifs (fractales)¶
Écrire un programme Python utilisant le module turtle pour dessiner un flocon de Koch de manière récursive.
Le principe : à chaque niveau de récursion, chaque segment est remplacé par quatre segments formant une pointe triangulaire.
Solution
import turtle
def koch(t, longueur, niveau):
if niveau == 0:
t.forward(longueur)
else:
koch(t, longueur / 3, niveau - 1)
t.left(60)
koch(t, longueur / 3, niveau - 1)
t.right(120)
koch(t, longueur / 3, niveau - 1)
t.left(60)
koch(t, longueur / 3, niveau - 1)
def flocon(t, longueur, niveau):
for _ in range(3):
koch(t, longueur, niveau)
t.right(120)
t = turtle.Turtle()
t.speed(0)
t.penup()
t.goto(-150, 90)
t.pendown()
flocon(t, 300, 4)
turtle.done()
Calculabilité et décidabilité¶
Exercice 4 - Programme comme donnée¶
a. Citer trois exemples de logiciels qui prennent un programme en entrée.
b. Expliquer pourquoi la calculabilité ne dépend pas du langage de programmation.
c. Qu'est-ce qu'un problème indécidable ? Donner un exemple.
Solution
a. Un compilateur (traduit du code source en code machine), un interpréteur (exécute le code ligne par ligne), un antivirus (analyse le comportement du programme).
b. Tous les langages de programmation « complets » (au sens de Turing) sont équivalents en puissance de calcul : ce qui peut être calculé dans un langage peut l'être dans tout autre. C'est la thèse de Church-Turing.
c. Un problème indécidable est un problème pour lequel il n'existe aucun algorithme capable de répondre correctement (oui ou non) dans tous les cas. Le problème de l'arrêt en est l'exemple principal : on ne peut pas écrire un programme qui détermine si tout programme termine.
Exercice 5 - Le problème de l'arrêt¶
Les programmes suivants s'arrêtent-ils ?
a.
Appel :pa(7)
b.
Appel :pb(6)
c. Expliquer pourquoi un programme ne pourrait pas répondre automatiquement à ces questions dans tous les cas.
Solution
a. pa(7) : 7 → 5 → 3 → 1 → -1 → -3 → ... La condition n <= 0 finit par être atteinte (pour n = -1). Oui, il s'arrête.
b. pb(6) : 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → sortie de boucle. Oui, il s'arrête.
(C'est la suite de Syracuse, mais on ne sait pas si elle s'arrête pour tout n.)
c. C'est le problème de l'arrêt : Turing a prouvé qu'aucun programme ne peut déterminer si tout programme termine. L'analyse au cas par cas est possible, mais un algorithme général n'existe pas.
Paradigmes et modularité¶
Exercice 6 - Identifier le paradigme¶
Pour chaque extrait de code, identifier le paradigme dominant (impératif, fonctionnel, objet) et justifier.
a.
b.
c.
class Bulletin:
def __init__(self, eleve, notes):
self.eleve = eleve
self.notes = notes
def moyenne(self):
return sum(self.notes) / len(self.notes)
Solution
a. Paradigme impératif : variable accumulatrice total modifiée par une boucle for, instructions séquentielles.
b. Paradigme fonctionnel : utilisation de filter et lambda, pas de variable modifiée, transformation de données.
c. Paradigme objet : définition d'une classe avec attributs et méthodes, encapsulation des données.
Exercice 7 - Créer un module¶
Créer un module statistiques.py contenant les fonctions suivantes, documentées avec des docstrings :
moyenne(liste): renvoie la moyenne d'une liste de nombres ;ecart_type(liste): renvoie l'écart-type ;mediane(liste): renvoie la médiane ;quartiles(liste): renvoie Q1 et Q3.
Le module doit pouvoir être testé directement (__name__ == "__main__").
Solution
"""Module de statistiques descriptives."""
def moyenne(liste):
"""Renvoie la moyenne d'une liste de nombres."""
assert len(liste) > 0, "La liste ne doit pas être vide"
return sum(liste) / len(liste)
def ecart_type(liste):
"""Renvoie l'écart-type d'une liste de nombres."""
moy = moyenne(liste)
variance = sum((x - moy) ** 2 for x in liste) / len(liste)
return variance ** 0.5
def mediane(liste):
"""Renvoie la médiane d'une liste de nombres."""
tri = sorted(liste)
n = len(tri)
if n % 2 == 1:
return tri[n // 2]
return (tri[n // 2 - 1] + tri[n // 2]) / 2
def quartiles(liste):
"""Renvoie (Q1, Q3) d'une liste de nombres."""
tri = sorted(liste)
n = len(tri)
q1 = mediane(tri[:n // 2])
q3 = mediane(tri[(n + 1) // 2:])
return (q1, q3)
if __name__ == "__main__":
donnees = [4, 7, 13, 2, 1, 9, 15, 12, 5, 8]
print(f"Moyenne : {moyenne(donnees):.2f}")
print(f"Écart-type : {ecart_type(donnees):.2f}")
print(f"Médiane : {mediane(donnees)}")
print(f"Quartiles : {quartiles(donnees)}")
Mise au point et bugs¶
Exercice 8 - Trouver et corriger les bugs¶
Chaque fonction contient un bug. Identifier le type de bug, l'expliquer et proposer une correction.
a.
b.
def inverser_liste(tab):
for i in range(len(tab)):
tab[i], tab[len(tab) - 1 - i] = tab[len(tab) - 1 - i], tab[i]
return tab
c.
def moyenne_notes(notes):
somme = 0
for i in range(1, len(notes)):
somme += notes[i]
return somme / len(notes)
Solution
a. Bug logique : maxi = 0 échoue si tous les nombres sont négatifs (ex : maximum([-3, -1, -5]) renvoie 0).
Correction : maxi = tab[0] et commencer la boucle à l'index 1, ou utiliser float('-inf').
b. Bug logique : la boucle parcourt tout le tableau, donc chaque échange est effectué deux fois, annulant l'inversion. Correction : boucler seulement sur la première moitié : range(len(tab) // 2).
c. Bug « off-by-one » : range(1, ...) saute le premier élément notes[0]. Correction : range(len(notes)) ou simplement sum(notes).
Activités¶
🧪 Activité 1 - Tours de Hanoï visuelles¶
Adapter le programme des tours de Hanoï pour afficher l'état des trois tiges après chaque déplacement, en utilisant des listes Python pour représenter les tiges.
Solution
def afficher_tiges(tiges):
for nom in ['A', 'B', 'C']:
print(f" {nom} : {tiges[nom]}")
print()
def hanoi(n, source, dest, inter, tiges):
if n == 1:
disque = tiges[source].pop()
tiges[dest].append(disque)
print(f"Déplacer disque {disque} de {source} vers {dest}")
afficher_tiges(tiges)
return
hanoi(n - 1, source, inter, dest, tiges)
disque = tiges[source].pop()
tiges[dest].append(disque)
print(f"Déplacer disque {disque} de {source} vers {dest}")
afficher_tiges(tiges)
hanoi(n - 1, inter, dest, source, tiges)
n = 3
tiges = {'A': list(range(n, 0, -1)), 'B': [], 'C': []}
print("État initial :")
afficher_tiges(tiges)
hanoi(n, 'A', 'C', 'B', tiges)
🧪 Activité 2 - Même algorithme, trois paradigmes¶
Implémenter le crible d'Ératosthène (trouver tous les nombres premiers jusqu'à n) dans les trois paradigmes : impératif, fonctionnel et objet.
Solution
Impératif :
def crible_imperatif(n):
premiers = []
est_premier = [True] * (n + 1)
for i in range(2, n + 1):
if est_premier[i]:
premiers.append(i)
for j in range(i * i, n + 1, i):
est_premier[j] = False
return premiers
Fonctionnel :
def crible_fonctionnel(n):
def filtrer(nombres, p):
return [x for x in nombres if x == p or x % p != 0]
nombres = list(range(2, n + 1))
p = 2
while p * p <= n:
nombres = filtrer(nombres, p)
p = nombres[nombres.index(p) + 1] if p in nombres and nombres.index(p) + 1 < len(nombres) else n + 1
return nombres
Objet :
class Crible:
def __init__(self, n):
self.n = n
self.premiers = []
self._calculer()
def _calculer(self):
est_premier = [True] * (self.n + 1)
for i in range(2, self.n + 1):
if est_premier[i]:
self.premiers.append(i)
for j in range(i * i, self.n + 1, i):
est_premier[j] = False
def est_premier(self, k):
return k in self.premiers
def compter(self):
return len(self.premiers)
Projet¶
🎯 Projet - Interpréteur de mini-langage¶
Créer un interpréteur pour un mini-langage de programmation supportant :
- les variables (
x = 5) ; - les opérations arithmétiques (
x + 3,x * y) ; - l'affichage (
afficher x) ; - les conditions (
si x > 0 alors afficher x) ; - les boucles (
tant que x > 0 faire x = x - 1).
Solution
class Interpreteur:
def __init__(self):
self.variables = {}
def evaluer_expression(self, expr):
expr = expr.strip()
for op in ['+', '-', '*', '/']:
if op in expr:
parties = expr.split(op, 1)
gauche = self.evaluer_expression(parties[0])
droite = self.evaluer_expression(parties[1])
if op == '+': return gauche + droite
if op == '-': return gauche - droite
if op == '*': return gauche * droite
if op == '/': return gauche / droite
try:
return float(expr)
except ValueError:
if expr in self.variables:
return self.variables[expr]
raise ValueError(f"Variable inconnue : {expr}")
def evaluer_condition(self, cond):
for op in ['>=', '<=', '!=', '>', '<', '==']:
if op in cond:
parties = cond.split(op)
g = self.evaluer_expression(parties[0])
d = self.evaluer_expression(parties[1])
if op == '>': return g > d
if op == '<': return g < d
if op == '>=': return g >= d
if op == '<=': return g <= d
if op == '==': return g == d
if op == '!=': return g != d
return False
def executer(self, ligne):
ligne = ligne.strip()
if ligne.startswith("afficher "):
val = self.evaluer_expression(ligne[9:])
print(val)
elif ligne.startswith("si "):
parties = ligne[3:].split(" alors ")
if self.evaluer_condition(parties[0]):
self.executer(parties[1])
elif "=" in ligne and not any(op in ligne.split("=")[0] for op in ['>', '<', '!']):
parties = ligne.split("=", 1)
nom = parties[0].strip()
valeur = self.evaluer_expression(parties[1])
self.variables[nom] = valeur
else:
print(f"Instruction non reconnue : {ligne}")
def executer_programme(self, code):
for ligne in code.strip().split("\n"):
if ligne.strip():
self.executer(ligne)
interp = Interpreteur()
interp.executer_programme("""
x = 10
y = 3
z = x + y
afficher z
si x > 5 alors afficher x
si y > 5 alors afficher y
""")