Exercices corrigés — Algorithmique et Python (Terminale)

a) On part de u = 2, la valeur de u₀, et l'on applique n fois la relation de récurrence :

def terme(n):
    u = 2
    for k in range(n):
        u = 3 * u - 1
    return u

L'invariant de boucle est : après k passages dans la boucle, u vaut u_k. Comme range(n) provoque exactement n passages, la fonction renvoie u_n.
b) Déroulement de terme(3) : au départ u = 2 ; premier passage, u = 3 * 2 - 1 = 5 ; deuxième passage, u = 3 * 5 - 1 = 14 ; troisième passage, u = 3 * 14 - 1 = 41. La fonction renvoie 41 = u₃, ce qui correspond aux termes calculés au chapitre sur les suites.
Erreur fréquente : écrire range(n + 1), qui ferait un passage de trop et renverrait u_n+1. Tester la fonction sur terme(0), qui doit renvoyer 2, et sur terme(1), qui doit renvoyer 5, permet de le détecter.

range(n + 1) fait prendre à k les valeurs 0, 1, …, n, soit n + 1 valeurs. À chaque passage, on ajoute à s le nombre 2*k + 1, c'est-à-dire le (k + 1)-ième nombre impair.
Pour mystere(5), k prend les valeurs 0 à 5 et s vaut successivement 1, puis 1 + 3 = 4, puis 4 + 5 = 9, 9 + 7 = 16, 16 + 9 = 25 et enfin 25 + 11 = 36. La fonction renvoie 36.
Les valeurs intermédiaires 1, 4, 9, 16, 25, 36 sont les carrés parfaits : la somme des n + 1 premiers nombres impairs vaut (n + 1)². Preuve : 1 + 3 + … + (2n + 1) = 2(0 + 1 + … + n) + (n + 1) = 2 × nn + 12 + (n + 1) = (n + 1)(n + 1). La fonction mystere(n) renvoie donc toujours (n + 1)².

a) Avant la boucle, u = 1 et n = 0. La condition u < 100 est testée avant chaque passage.

le code comporte trois erreurs.
1. range(1, n) parcourt les entiers de 1 à n − 1 : la borne droite est exclue. Pour aller jusqu'à n inclus, il faut range(1, n + 1).
2. k/3 == 0 teste si le quotient k/3 vaut 0, ce qui n'arrive que pour k = 0 : la divisibilité se teste avec le reste de la division euclidienne, k % 3 == 0.
3. La variable compteur est incrémentée sans avoir été créée : il faut l'initialiser à 0 avant la boucle, puis la renvoyer.
Fonction corrigée :

def multiples_de_3(n):
    compteur = 0
    for k in range(1, n + 1):
        if k % 3 == 0:
            compteur += 1
    return compteur

Test : multiples_de_3(10) renvoie 3, pour les entiers 3, 6 et 9 ; multiples_de_3(9) renvoie aussi 3, ce qui vérifie la borne incluse. Le résultat attendu est la partie entière de n3, soit n // 3 en Python.

a) sum(L) vaut 12 + 15 + 9 + 14 = 50 et len(L) vaut 4 : la fonction renvoie 50 / 4, soit 12.5. Le résultat est un flottant, même quand la division tombe juste.
b) La variance est la moyenne des carrés des écarts à la moyenne. On calcule la moyenne une seule fois, puis la liste des carrés des écarts par compréhension :

def variance(L):
    m = moyenne(L)
    return sum([(x - m) ** 2 for x in L]) / len(L)

Pour [12, 15, 9, 14], les écarts à 12,5 sont −0,5 ; 2,5 ; −3,5 ; 1,5, leurs carrés 0,25 ; 6,25 ; 12,25 ; 2,25, de somme 21 : la variance vaut 214 = 5,25 et l'écart type √5,25 ≈ 2,29.
c) Si L est vide, len(L) vaut 0 et la division déclenche une erreur ZeroDivisionError. On se protège en testant ce cas au début de la fonction, par exemple if len(L) == 0: return None, ou en signalant explicitement l'erreur avec raise ValueError("liste vide"). Préciser ce comportement fait partie de la spécification de la fonction.

on fait évoluer une variable u qui vaut 1,05ⁿ après n passages, en s'arrêtant dès que le seuil 2 est atteint :

def doublement():
    n = 0
    u = 1
    while u < 2:
        u *= 1.05
        n += 1
    return n

Invariant : à chaque test de la condition, u vaut 1,05ⁿ exactement pour la valeur courante de n. La boucle continue tant que 1,05ⁿ < 2 et s'arrête au premier n tel que 1,05ⁿ ≥ 2, qui est bien la valeur renvoyée.
Terminaison : 1,05 > 1, donc 1,05ⁿ tend vers +∞ et finit par dépasser 2 ; la boucle s'arrête à coup sûr.
Résultat : 1,05¹⁴ ≈ 1,980 < 2 et 1,05¹⁵ ≈ 2,079 ≥ 2, la fonction renvoie 15. Vérification par le logarithme : n ≥ ln 2ln 1,05 ≈ 14,21, dont le premier entier supérieur est 15. Un capital placé à 5 % par an double en 15 ans. La fonction se généralise en doublement(taux) avec u *= 1 + taux.

a) La fonction simule 10 000 fois une série de 8 épreuves de Bernoulli de paramètre 0,4 et compte la proportion de séries comportant exactement 3 succès. Le nombre 0,2804 est une fréquence observée : c'est une estimation de P(X = 3), pas sa valeur exacte.
b) P(X = 3) = C(8,3) × 0,4³ × 0,6⁵ = 56 × 0,064 × 0,077 76 ≈ 0,2787.
c) Non. La fréquence obtenue est elle-même une variable aléatoire : chaque exécution utilise de nouveaux nombres pseudo-aléatoires et donne une valeur un peu différente. Les deux résultats, 0,2804 et 0,2761, encadrent la valeur exacte 0,2787 et s'en écartent de moins de 0,003 : c'est la fluctuation d'échantillonnage normale.
d) La fréquence sur N = 10 000 répétitions indépendantes a pour écart type √[p1 − pN] avec p = 0,2787 : √0,2787 × 0,721310 000 ≈ √2,01 × 10⁻⁵ ≈ 0,0045. Les écarts observés (0,0017 et 0,0026) sont inférieurs à un écart type : rien d'anormal. Pour gagner une décimale de précision, il faudrait multiplier le nombre de répétitions par 100. La simulation donne une valeur approchée ; la formule donne la valeur exacte.

la fonction random() renvoie un réel choisi uniformément dans l'intervalle [0 ; 1[ : la probabilité que le résultat tombe dans un sous-intervalle est égale à la longueur de ce sous-intervalle, indépendamment de sa position.
La condition random() < p est vraie exactement lorsque le nombre tiré appartient à [0 ; p[, intervalle de longueur p. La probabilité d'un succès est donc p, et celle d'un échec, correspondant à l'intervalle [p ; 1[, vaut 1 − p.
Exemple : avec p = 0,3, environ 30 % des tirages sont inférieurs à 0,3. Utiliser <= à la place de < ne change rien en pratique, car la probabilité d'obtenir exactement la valeur p est nulle.
Cette construction est à la base de toutes les simulations du chapitre : une variable de Bernoulli s'obtient par 1 if random() < p else 0, et une loi binomiale par la somme de n telles variables indépendantes.