Feuille d’exercices 2 – avancé

Avertissement

Ces exercices sont prévus pour les étudiant·e·s ayant déjà réussi la feuille d’exercices « classiques ».

Exercice 7 : suite récurrente d’ordre 2

On considère la suite récurrente d’ordre \(2\), dite de Fibonacci, définie par

\[ F_0 = 0, \; F_1 = 1 \quad \text{ et } \quad F_{n+2} = F_{n+1} + F_n, \; \forall n \ge 0 \]

Question 1. Écrire une fonction fibonacci_iter(n) qui calcule la valeur de \(F_n\) de manière itérative (c’est-à-dire, sans que la fonction s’appelle elle-même).

On vérifiera entre autres que \(F_{10} = 55\).

# Votre réponse ici

Question 2. Écrire une fonction fibonacci_rec(n) qui calcule la valeur de \(F_n\) de manière récursive (attention, ne tester cette fonction qu’avec de petites valeurs, typiquement inférieures à \(25\)).

# Votre réponse ici

Question 3 (plus difficile). Pour \(n = 32\), la fonction fibonacci_rec(n) devrait prendre quelques secondes à être évaluée. Ce n’est pas du tout le cas de fibonacci_iter, qui calcule même \(F_{10000}\) instantanément. Avez-vous une explication pour ce phénomène ?

Exercice 8 : triangle de Pascal

Le triangle de Pascal est la donnée de tous les coefficients binomiaux \(\binom{n}{k}\), pour \(0 \le k \le n \le N\) où l’entier \(N\) est appelé l’ordre du triangle. Usuellement, on dispose l’ensemble des coefficients binomiaux sous la forme d’un triangle, d’où le nom. Le coefficient binomial \(\binom{0}{0} = 1\) est placé en haut à gauche. Puis, sur la ligne suivante on dispose \(\binom{1}{0} = 1\) et \(\binom{1}{1} = 1\). À la troisième ligne \(\binom{2}{0} = 1\), \(\binom{2}{1} = 2\), \(\binom{2}{2} = 1\), etc.

\[\begin{split} \begin{array}{cccc} \binom{0}{0} & & & \\ \binom{1}{0} & \binom{1}{1} & & \\ \binom{2}{0} & \binom{2}{1} & \binom{2}{2} & \\ \binom{3}{0} & \binom{3}{1} & \binom{3}{2} & \binom{3}{3}\\ \end{array}~\;~=~\;~ \begin{array}{cccc} 1 & & & \\ 1 & 1 & & \\ 1 & 2 & 1& \\ 1 & 3 & 3& 1 \\ \end{array} \end{split}\]

Pour calculer le triangle, l’idée de commencer à calculer le coefficient binomial pour \(n = 0\), puis d’utiliser la formule de Pascal (une nouvelle fois, d’où le nom), valable pour tout \(n \ge 0\) et tout \(k \ge 1\) en admettant que \(\binom{i}{j} = 0\) si \(j > i\) :

\[ \binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}\,. \]

Pour calculer \(\binom{n+1}{k}\), on peut donc sommer \(\binom{n}{k-1}\) et \(\binom{n}{k}\), qui sont deux valeurs précédemment calculées. Cela permet d’économiser un grand nombre de calculs de factorielles.

Question 1 : Implanter une fonction triangle_pascal(N) qui retourne le triangle de Pascal d’ordre N, sous la forme d’une liste L comportant N+1 sous-listes, telle que la \(j\)-ème liste contient l’ensemble des binomiaux de la forme \(\binom{j}{i}\) pour \(0 \le i \le j\).

Par exemple, pour N = 6, la fonction triangle_pascal(N) doit retourner :

[[1],
 [1, 1],
 [1, 2, 1],
 [1, 3, 3, 1],
 [1, 4, 6, 4, 1],
 [1, 5, 10, 10, 5, 1],
 [1, 6, 15, 20, 15, 6, 1]]

# Votre réponse ici

Exercice 9 : Fusion de listes ordonnées

On appelle fusion ordonnée de deux listes ordonnées \(A = [a_1, \dots, a_n]\) et \(B = [b_1, \dots, b_m]\) la liste des éléments de \(A\) et \(B\) ordonnée selon l’ordre de \(A\) et \(B\). Par exemple, si les listes \(A\) et \(B\) sont

\[ A = [ 1, 7, 7, 13 ] \quad \text{ et } \quad B = [ 0, 3, 6, 13, 15 ] \]

alors (en observant que \(A\) et \(B\) sont croissantes), la fusion ordonnée de \(A\) et \(B\) est

\[ [0, 1, 3, 6, 7, 7, 13, 13, 15 ] \]

Question 1 : Écrire une fonction itérative fusionne_iter(liste1, liste2) qui retourne la fusion ordonnée de deux listes croissantes liste1 et liste2. On supposera que les deux listes en entrée sont croissantes (on ne le vérifiera pas).

# Votre réponse ici

Question 2 : Écrire une fonction récursive fusionne_rec(liste1, liste2) qui retourne la fusion ordonnée de deux listes croissantes liste1 et liste2.

# Votre réponse ici

Question 3 : On suppose que L est une liste de listes. Écrire une fonction fusionne_tout(L) qui retourne la fusion ordonnée de toutes les listes présentes dans L (qui sont supposées toutes croissantes).

Par exemple, avec les listes suivantes :

[1, 4, 5]
[]
[7, 11, 11]
[1, 2, 4, 7]
[2, 4, 8]

on doit obtenir la liste fusionnée

[1, 1, 2, 2, 4, 4, 4, 5, 7, 7, 8, 11, 11]

# Votre réponse ici

Exercice 10 : maximum d’une liste par fonction récursive

Soit \(v = (v_1, \dots, v_n) \in \mathbb{R}^n\). Alors, la valeur maximale des coordonnées de \(v\) vérifie

\[ \mathrm{max}(v) = \mathrm{max}(v_1, \dots, v_n) = \mathrm{max}(\mathrm{max}(v_1, \dots, v_{n-1}), v_n) \]

Ainsi, on obtient une relation de récurrence pour calculer le maximum d’une liste.

Question 1 : Utiliser la relation ci-dessus pour écrire une fonction récursive maximum_rec(L), qui prend en entrée une liste L, et qui retourne le maximum de la liste L. Votre fonction devra être récursive.

# Votre réponse ici