Correction Détaillée — Série : Algorithmes d'Approximation
Niveau : 4ème Sciences de l'Informatique | 2024–2025
Exercice 1 — Approximation de π : Formule de Wallis
Rappel de la formule
π/2 = (2/1) × (2/3) × (4/3) × (4/5) × (6/5) × (6/7) × ... × (2n/(2n−1)) × (2n/(2n+1))
On remarque que chaque terme de rang n est composé de deux facteurs :
• Facteur gauche : 2n / (2n − 1)
• Facteur droit : 2n / (2n + 1)
Le produit partiel P(n) = (2/1)(2/3)(4/3)(4/5)...(2n/(2n-1))(2n/(2n+1))
On arrête quand |P(n) − P(n−1)| ≤ ε, alors π ≈ 2 × P(n).
Algorithme (Langage algorithmique)
Fonction wallis(ε : Réel) : Réel
Variables :
n : Entier
produit : Réel { produit courant de la série }
prodPrec : Réel { produit de l'itération précédente }
Début
n ← 1
produit ← 1
Répéter
prodPrec ← produit
produit ← produit × (2×n / (2×n − 1)) × (2×n / (2×n + 1))
n ← n + 1
Jusqu'à |produit − prodPrec| ≤ ε
Retourner 2 × produit
Fin
Explication pas à pas
Analyse de l'algorithme
1. On initialise produit = 1 (élément neutre de la multiplication).
2. À chaque itération de rang n, on multiplie produit par les deux fractions :
(2n / (2n-1)) et (2n / (2n+1))
3. On compare produit avec sa valeur précédente prodPrec.
4. On s'arrête quand la variation |produit - prodPrec| ≤ ε.
5. On retourne 2 × produit car la formule donne π/2, pas π directement.
Exemple avec ε = 0.001 :
n=1 : produit = 1 × (2/1) × (2/3) = 4/3 ≈ 1.3333
n=2 : produit = (4/3) × (4/3) × (4/5) = 64/45 ≈ 1.4222
... le produit converge vers π/2 ≈ 1.5708
Exercice 2 — Approximation de π : Formule de Leibniz
Rappel de la formule
π/8 = 1/(1×3) + 1/(5×7) + 1/(9×11) + ...
Terme général de rang n (en commençant à n=0) :
T(n) = 1 / ((4n+1) × (4n+3))
Remarque : les dénominateurs se construisent ainsi :
n=0 : (1)(3) → 4×0+1=1, 4×0+3=3
n=1 : (5)(7) → 4×1+1=5, 4×1+3=7
n=2 : (9)(11) → 4×2+1=9, 4×2+3=11
Algorithme (Langage algorithmique)
Fonction leibniz(ε : Réel) : Réel
Variables :
n : Entier
somme : Réel { somme partielle courante }
terme : Réel { terme T(n) courant }
Début
n ← 0
somme ← 0
Répéter
terme ← 1 / ((4×n + 1) × (4×n + 3))
somme ← somme + terme
n ← n + 1
Jusqu'à terme ≤ ε
Retourner 8 × somme
Fin
Explication pas à pas
Analyse de l'algorithme
1. somme s'accumule terme après terme.
2. Chaque terme T(n) = 1/((4n+1)(4n+3)) est strictement positif et décroissant.
3. La condition d'arrêt est : terme ≤ ε
(on arrête quand le dernier terme ajouté est suffisamment petit).
4. On retourne 8 × somme car la formule donne π/8.
Exemple avec ε = 0.001 :
n=0 : terme = 1/(1×3) = 0.3333 → somme = 0.3333
n=1 : terme = 1/(5×7) = 0.0286 → somme = 0.3619
n=2 : terme = 1/(9×11) = 0.0101 → somme = 0.3720
... π ≈ 8 × somme
Exercice 3 — Aire maximale d'un triangle variable
Rappel et analyse du problème
Aire du triangle AB'C' = (45 − x) × (20 + x) / 2
x varie dans ]0, min(45, ∞)[ → on prend x ∈ ]0, 45[
Le pas appartient à [0, 1]
Stratégie : on fait varier x de 0 à 44 (car si x ≥ 45 la hauteur devient nulle ou négative),
par incréments de 'pas', et on garde la valeur de x qui maximise l'aire.
Question 1 — Algorithme de la fonction aire_max(pas)
Fonction aire_max(pas : Réel) : Réel
Variables :
x : Réel { valeur courante de x }
aire : Réel { aire courante }
aireMax : Réel { meilleure aire trouvée }
xMax : Réel { valeur de x donnant aireMax }
Début
x ← pas
aireMax ← 0
xMax ← 0
TantQue x < 45 Faire
aire ← (45 − x) × (20 + x) / 2
Si aire > aireMax Alors
aireMax ← aire
xMax ← x
FinSi
x ← x + pas
FinTantQue
Retourner xMax
Fin
Explication et vérification mathématique
Vérification analytique
Aire(x) = (45 − x)(20 + x) / 2 = (900 + 45x − 20x − x²) / 2 = (900 + 25x − x²) / 2
Pour trouver le maximum, on dérive et on égale à zéro :
Aire'(x) = (25 − 2x) / 2 = 0 → x = 12.5
Donc la valeur exacte est x = 12.5
Aire maximale = (45 − 12.5)(20 + 12.5) / 2 = 32.5 × 32.5 / 2 = 528.125
L'algorithme doit retourner une valeur proche de 12.5 selon le pas choisi.
Avec pas = 0.01 : xMax ≈ 12.50 (très bonne approximation)
Avec pas = 0.1 : xMax ≈ 12.5 (approximation acceptable)
Exercice 4 — Surface maximale : Piste d'athlétisme & terrain de football
Rappel des formules
Périmètre piste : P = 2·L + π·D
Surface terrain : S = L × D
En exprimant D en fonction de L : D = (P − 2·L) / π
→ S(L) = L × (P − 2·L) / π
Contrainte : L ∈ ]0, P/2[ (L > 0 et D > 0)
Question 1 — Saisie des données
Répéter
Lire P
Jusqu'à 350 ≤ P ≤ 450
Répéter
Lire ε
Jusqu'à 0.001 ≤ ε ≤ 0.1
Question 2 — Algorithme : trouver L optimal et S maximale
Fonction stade(P : Réel, ε : Réel) : Réel
Variables :
L : Réel { longueur courante }
S : Réel { surface courante }
Smax : Réel { surface maximale }
Lopt : Réel { longueur optimale }
Début
L ← ε
Smax ← 0
Lopt ← 0
TantQue L < P/2 Faire
S ← L × (P − 2×L) / π
Si S > Smax Alors
Smax ← S
Lopt ← L
FinSi
L ← L + ε
FinTantQue
Écrire 'Longueur optimale L = ', Lopt
Écrire 'Surface maximale S = ', Smax
Retourner Lopt
Fin
Question 3 — Programme principal
Programme principal
Variables :
P, eps : Réel
Début
{ Saisie de P }
Répéter
Écrire 'Entrez le périmètre P (350 à 450 m) : '
Lire P
Jusqu'à 350 ≤ P ≤ 450
{ Saisie de ε (le pas) }
Répéter
Écrire 'Entrez le pas ε (0.001 à 0.1) : '
Lire eps
Jusqu'à 0.001 ≤ eps ≤ 0.1
{ Appel de la fonction et affichage }
stade(P, eps)
Fin
Vérification mathématique
Optimisation analytique
S(L) = L × (P − 2L) / π
Pour trouver le maximum :
S'(L) = (P − 4L) / π = 0 → L = P/4
Exemple avec P = 400 m :
L_opt = 400/4 = 100 m
D = (400 − 2×100) / π = 200/π ≈ 63.66 m
S_max = 100 × 63.66 ≈ 6366 m²
L'algorithme avec ε = 0.01 devrait retourner L ≈ 100 m et S ≈ 6366 m².
Tableau de synthèse — Récapitulatif des 4 exercices
Ex. Problème Formule Condition d'arrêt
1 Approx. π (Wallis) π/2 = Π(2n/(2n-1))(2n/(2n+1)) |produit − prodPrec| ≤ ε
2 Approx. π (Leibniz) π/8 = Σ 1/((4n+1)(4n+3)) terme courant T(n) ≤ ε
3 Aire max triangle Aire = (45−x)(20+x)/2 x balayé de 0 à 45 par pas
4 Surface max stade S(L) = L(P−2L)/π L balayé de 0 à P/2 par pas ε
Correction réalisée avec rigueur algorithmique — Bonne étude ! ✓