← Retour au sommaire

Chapitre 17 – Calcul et algorithmique

Exercices par capacités · BTS

Dernière mise à jour : 21 juin 2026

Capacités travaillées

C1 — Lire et dérouler un algorithme

Exercice 1

On exécute les instructions suivantes. Donner la valeur finale de chaque variable.

a ← 5
b ← 3
a ← a + b
b ← a - b
a ← a - b

Ligne 3 : \(a = 5+3 = 8\). Ligne 4 : \(b = 8-3 = 5\). Ligne 5 : \(a = 8-5 = 3\).

Valeurs finales : \(a = 3\), \(b = 5\). Cet algorithme échange les valeurs de \(a\) et \(b\) sans variable temporaire.

Exercice 2

Dérouler la boucle suivante : donner la valeur de somme à la fin.

somme ← 0
POUR i DE 1 A 5 FAIRE
    somme ← somme + i * i
FIN POUR

On ajoute les carrés : \(1^2 + 2^2 + 3^2 + 4^2 + 5^2 = 1+4+9+16+25 = 55\).

\(\texttt{somme} = 55\). (On retrouve \(\frac{n(n+1)(2n+1)}{6} = \frac{5\cdot6\cdot11}{6} = 55\).)

Exercice 3

Un technicien métrologue contrôle un diamètre de cote nominale 50 mm, tolérance ±0,05 mm. L'algorithme affiche « ACCEPTÉE » si \(49{,}95 \le d \le 50{,}05\). Pour les mesures \(d = 49{,}93\) ; \(d = 50{,}00\) ; \(d = 50{,}07\) mm, donner l'affichage.

\(d = 49{,}93 \lt 49{,}95\) : « REJETÉE — sous-dimensionnée ».

\(d = 50{,}00\) : \(49{,}95 \le 50{,}00 \le 50{,}05\) : « ACCEPTÉE ».

\(d = 50{,}07 \gt 50{,}05\) : « REJETÉE — sur-dimensionnée ».

Exercice 4

Dérouler cette boucle TANT QUE et donner la valeur affichée de n.

n ← 0
v ← 100
TANT QUE v > 1 FAIRE
    v ← v / 2
    n ← n + 1
FIN TANT QUE
Afficher(n)

Valeurs de \(v\) : 100 → 50 → 25 → 12,5 → 6,25 → 3,125 → 1,5625 → 0,78125.

On divise par 2 tant que \(v \gt 1\). Le test devient faux quand \(v = 0{,}78125\). On a effectué 7 divisions.

\(n = 7\). (On a \(2^6 = 64 \lt 100 \le 128 = 2^7\), d'où \(\lceil\log_2 100\rceil = 7\).)

C2 — Écrire et utiliser fonctions et récursivité

Exercice 5

Soit la fonction récursive de factorielle vue en cours. Dérouler \(\texttt{FactoriellRec}(4)\) et donner le résultat.

\(\texttt{Rec}(4) = 4 \times \texttt{Rec}(3) = 4 \times 3 \times \texttt{Rec}(2) = 4\times3\times2\times\texttt{Rec}(1)\).

Cas de base : \(\texttt{Rec}(1) = 1\). Donc \(4\times3\times2\times1 = 24\). Soit \(4! = 24\).

Exercice 6

La suite de Fibonacci vérifie \(F_0 = 0\), \(F_1 = 1\), \(F_n = F_{n-1} + F_{n-2}\). Calculer \(F_2\) à \(F_8\).

\(F_2 = 1+0 = 1\) ; \(F_3 = 1+1 = 2\) ; \(F_4 = 2+1 = 3\) ; \(F_5 = 3+2 = 5\) ;

\(F_6 = 5+3 = 8\) ; \(F_7 = 8+5 = 13\) ; \(F_8 = 13+8 = 21\).

Suite : 0, 1, 1, 2, 3, 5, 8, 13, 21.

Exercice 7

Écrire en pseudo-code une fonction Maximum(T, n) qui renvoie le plus grand élément d'un tableau \(T[1..n]\).

Fonction Maximum(T : tableau ; n : entier) : réel
Début
    max ← T[1]
    POUR i DE 2 A n FAIRE
        SI T[i] > max ALORS
            max ← T[i]
        FIN SI
    FIN POUR
    RETOURNER max
Fin

On initialise avec le premier élément, puis on compare chaque élément suivant. Complexité \(O(n)\).

Exercice 8

Une fonction récursive doit posséder un cas de base et un cas récursif. Identifier ces deux éléments dans la fonction Puissance(x, n) ci-dessous, puis dérouler Puissance(2, 3).

Fonction Puissance(x : réel ; n : entier) : réel
Début
    SI n = 0 ALORS
        RETOURNER 1
    SINON
        RETOURNER x * Puissance(x, n - 1)
    FIN SI
Fin

Cas de base : \(n = 0\) renvoie 1 (pas d'appel récursif). Cas récursif : \(x \times \texttt{Puissance}(x, n-1)\), avec \(n\) strictement décroissant.

\(\texttt{Puissance}(2,3) = 2\times\texttt{Puissance}(2,2) = 2\times2\times\texttt{Puissance}(2,1) = 2\times2\times2\times\texttt{Puissance}(2,0) = 2\times2\times2\times1 = 8\). Soit \(2^3 = 8\).

C3 — Mettre en œuvre les algorithmes numériques

Exercice 9

Approcher \(\displaystyle I = \int_0^2 x^2\,\mathrm{d}x\) par la méthode des rectangles à gauche avec \(n = 4\) sous-intervalles.

\(h = \dfrac{2-0}{4} = 0{,}5\). Points de gauche : \(x = 0\,;\,0{,}5\,;\,1\,;\,1{,}5\).

\(f(x) = x^2\) : \(f(0) = 0\), \(f(0{,}5) = 0{,}25\), \(f(1) = 1\), \(f(1{,}5) = 2{,}25\).

\(I \approx h\,[0 + 0{,}25 + 1 + 2{,}25] = 0{,}5 \times 3{,}5 = 1{,}75\).

(Valeur exacte : \(\left[\frac{x^3}{3}\right]_0^2 = \frac{8}{3} \approx 2{,}667\) ; les rectangles à gauche sous-estiment ici.)

Exercice 10

Approcher \(\displaystyle I = \int_0^2 x^2\,\mathrm{d}x\) par la méthode des trapèzes avec \(n = 4\). Comparer à la valeur exacte \(\frac{8}{3}\).

\(h = 0{,}5\). \(I \approx \dfrac{h}{2}\big[f(0) + 2f(0{,}5) + 2f(1) + 2f(1{,}5) + f(2)\big]\).

\(f(0)=0\), \(f(0{,}5)=0{,}25\), \(f(1)=1\), \(f(1{,}5)=2{,}25\), \(f(2)=4\).

\(I \approx \dfrac{0{,}5}{2}\big[0 + 2(0{,}25+1+2{,}25) + 4\big] = 0{,}25\,[0 + 7 + 4] = 0{,}25 \times 11 = 2{,}75\).

Valeur exacte \(\approx 2{,}667\) : l'erreur est de 0,083 (bien plus précise que les rectangles).

Exercice 11

On cherche \(\sqrt2\) par Newton-Raphson sur \(f(x) = x^2 - 2\), avec \(f'(x) = 2x\) et \(x_0 = 1{,}5\). Calculer \(x_1\) et \(x_2\).

\(x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)} = x_n - \dfrac{x_n^2 - 2}{2x_n}\).

\(x_1 = 1{,}5 - \dfrac{2{,}25 - 2}{3} = 1{,}5 - \dfrac{0{,}25}{3} = 1{,}5 - 0{,}08333 = 1{,}41667\).

\(x_2 = 1{,}41667 - \dfrac{1{,}41667^2 - 2}{2\times1{,}41667} = 1{,}41667 - \dfrac{2{,}00695 - 2}{2{,}83333} \approx 1{,}41667 - 0{,}00245 = 1{,}41422\).

On retrouve \(\sqrt2 \approx 1{,}41421\) : convergence très rapide (quadratique).

Exercice 12

On résout \(f(x) = 0\) par dichotomie sur \([1\,;\,2]\) avec \(f(x) = x^2 - 2\). Vérifier l'hypothèse, puis calculer \(m_1\) (premier milieu) et indiquer le nouvel intervalle.

\(f(1) = -1 \lt 0\) et \(f(2) = 2 \gt 0\) : \(f(1)\cdot f(2) \lt 0\), il existe une racine dans \([1\,;\,2]\).

\(m_1 = \dfrac{1+2}{2} = 1{,}5\) ; \(f(1{,}5) = 0{,}25 \gt 0\).

Comme \(f(1)\) et \(f(1{,}5)\) sont de signes opposés, la racine est dans \([1\,;\,1{,}5]\). Nouvel intervalle : \([1\,;\,1{,}5]\).

Exercice 13

Combien d'itérations de dichotomie sont nécessaires pour atteindre une précision \(\varepsilon = 10^{-3}\) sur l'intervalle \([0\,;\,2]\) ?

Condition : \(n \ge \log_2\!\left(\dfrac{b-a}{\varepsilon}\right) = \log_2\!\left(\dfrac{2}{10^{-3}}\right) = \log_2(2000)\).

\(\log_2(2000) = \dfrac{\ln 2000}{\ln 2} = \dfrac{7{,}601}{0{,}693} \approx 10{,}97\).

Il faut \(n \ge 11\) itérations.

C4 — Dérouler un tri et évaluer la complexité

Exercice 14

Dérouler le tri à bulles sur le tableau \([4, 1, 3, 2]\). Donner l'état du tableau après chaque passage.

Passage 1 : [1, 3, 2, 4] (le 4 remonte en fin).

Passage 2 : [1, 2, 3, 4] (le 3 se place).

Passage 3 : [1, 2, 3, 4] — aucun échange → tableau trié, arrêt.

Exercice 15

Dérouler le tri par sélection sur \([5, 2, 8, 1]\). Donner le tableau après chaque sélection du minimum.

Étape 1 : min de [5,2,8,1] est 1 → échange avec position 1 : [1, 2, 8, 5].

Étape 2 : min de [2,8,5] est 2, déjà en place : [1, 2, 8, 5].

Étape 3 : min de [8,5] est 5 → échange : [1, 2, 5, 8]. Tableau trié.

Exercice 16

Associer chaque cas à sa complexité : accès \(T[k]\) par indice ; parcours d'un tableau ; recherche par dichotomie ; tri à bulles ; Fibonacci récursif naïf.

CasComplexité
Accès \(T[k]\) par indice\(O(1)\) — constante
Parcours d'un tableau\(O(n)\) — linéaire
Recherche par dichotomie\(O(\log n)\) — logarithmique
Tri à bulles\(O(n^2)\) — quadratique
Fibonacci récursif naïf\(O(2^n)\) — exponentielle
Exercice 17

Un tri quadratique \(O(n^2)\) traite \(n = 1\,000\) éléments en 0,1 s. Estimer le temps pour \(n = 10\,000\) éléments.

Le nombre d'opérations est proportionnel à \(n^2\). En multipliant \(n\) par 10, on multiplie \(n^2\) par \(10^2 = 100\).

Temps estimé : \(0{,}1 \times 100 = 10\) s.

Cela illustre pourquoi un tri \(O(n^2)\) est à éviter pour les grands jeux de données.

C5 — Traduire un algorithme en Python

Exercice 18

Traduire en Python l'algorithme qui calcule la somme des entiers de 1 à \(n\) (avec une boucle for).

n = int(input("Entrez n : "))
somme = 0
for i in range(1, n + 1):
    somme += i
print(somme)

Attention : range(1, n+1) génère 1, 2, …, n (la borne droite est exclue).

Exercice 19

Que renvoie ce code Python ? Justifier.

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

print(f(6))

C'est le calcul itératif de Fibonacci. \(b\) parcourt \(F_1, F_2, \ldots\) : après les 5 tours (\(range(1,6)\)) on obtient \(F_6\).

\(F_6 = 8\). Le code affiche 8.

Exercice 20

Écrire une fonction Python integrale_trapezes(f, a, b, n) qui approche \(\int_a^b f(x)\,dx\) par la méthode des trapèzes.

def integrale_trapezes(f, a, b, n):
    h = (b - a) / n
    somme = f(a) + f(b)
    for k in range(1, n):
        somme += 2 * f(a + k * h)
    return (h / 2) * somme

Traduction directe de la formule \(I \approx \frac{h}{2}\big[f(a) + 2\sum_{k=1}^{n-1}f(a+kh) + f(b)\big]\).

Exercice 21

On utilise NumPy. Que vaut la moyenne calculée par ce code ?

import numpy as np
t = np.array([18, 20, 22, 20])
print(np.mean(t))

\(\text{moyenne} = \dfrac{18 + 20 + 22 + 20}{4} = \dfrac{80}{4} = 20{,}0\).

Le code affiche 20.0.