Devoir de contrôle n°2 : suites récurrentes, racine carrée par dichotomie, méthode des trapèzes, matrice récurrente

Exercice 1 : une suite récurrente d'ordre 2 (5 pts)

On définit la suite U par U0 = 2, U1 = 3 et, pour n ≥ 2, Un = Un-1 + 2 × Un-2.

• 1) Calculer à la main U2, U3 et U4 (1 pt).
• 2) Écrire la fonction Terme(n) qui renvoie Un sans utiliser de tableau (1,5 pt).
• 3) Écrire la fonction Rang(m) qui renvoie le plus petit n tel que Un > m (1,5 pt).
• 4) Écrire le programme qui lit n ≥ 0 et m ≥ 0 (saisies contrôlées) et affiche Un puis le rang (1 pt).

Pour n = 4 et m = 100, le programme affiche :

U4 = 27
Premier rang où U dépasse 100 : 6

Exercice 2 : racine carrée par dichotomie (6 pts)

Pour un réel a ≥ 1, la racine carrée de a est dans l'intervalle [1, a]. La méthode de dichotomie coupe l'intervalle en deux à chaque étape et garde la moitié qui contient la racine, jusqu'à ce que sa largeur soit inférieure à une précision eps.

• 1) Expliquer comment choisir la moitié à garder, à l'aide du milieu m (1 pt).
• 2) Écrire la fonction Racine(a, eps) qui renvoie une valeur approchée de √a : le milieu du dernier intervalle (2,5 pts).
• 3) Écrire le programme qui lit a ≥ 1 (saisie contrôlée), calcule Racine(a, 0.0001) et affiche le résultat arrondi à 3 chiffres après la virgule (1,5 pt).
• 4) Combien d'étapes faut-il environ pour a = 100 et eps = 0,0001 ? (1 pt)

Pour a = 2, le programme affiche : Racine ≈ 1.414

Exercice 3 : aire par la méthode des trapèzes (5 pts)

On veut une valeur approchée de l'aire sous la courbe de f(x) = x² + 1 entre a et b (a < b). La méthode des trapèzes découpe [a, b] en n bandes de même largeur h = (b - a) / n, et remplace chaque bande par un trapèze dont l'aire est h × (f(x) + f(x + h)) / 2.

• 1) Écrire la fonction F(x) (0,5 pt).
• 2) Écrire la fonction Trapezes(a, b, n) qui renvoie la somme des aires des n trapèzes (2,5 pts).
• 3) Écrire le programme qui lit a, b (a < b, saisie contrôlée) et n (n ≥ 1, saisie contrôlée), et affiche l'aire arrondie à 4 chiffres après la virgule (1,5 pt).
• 4) La valeur exacte entre 0 et 1 est 4/3. Que se passe-t-il quand n augmente ? (0,5 pt)

Pour a = 0, b = 1 et n = 4, le programme affiche : Aire ≈ 1.3438

Exercice 4 : une matrice définie par récurrence (4 pts)

Une matrice carrée M de n lignes et n colonnes (2 ≤ n ≤ 10) est définie par récurrence : M[0][j] = 1 pour toute colonne j, M[i][0] = 1 pour toute ligne i, et, pour i ≥ 1 et j ≥ 1, M[i][j] = M[i - 1][j] + M[i][j - 1] (la case du dessus plus la case de gauche).

• 1) Donner à la main la matrice M pour n = 3 (1 pt).
• 2) Écrire la procédure Construire(M, n) qui remplit la matrice (2 pts).
• 3) Écrire le programme qui lit n (saisie contrôlée), construit M, l'affiche ligne par ligne puis affiche sa dernière case M[n - 1][n - 1] (1 pt).

Pour n = 4, le programme affiche :

1 1 1 1
1 2 3 4
1 3 6 10
1 4 10 20
Dernière case : 20