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
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\).
def fibonacci_iter(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
Fn = 0
Fn1 = 1
for j in range(2, n+1):
Fn2 = Fn1 + Fn
Fn = Fn1
Fn1 = Fn2
return Fn2
print(fibonacci_iter(0))
print(fibonacci_iter(10))
0
55
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\)).
def fibonacci_rec(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci_rec(n-1) + fibonacci_rec(n-2)
print(fibonacci_rec(0))
print(fibonacci_rec(10))
0
55
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 ?
Réponse. L’explication est la suivante : pour calculer de manière récursive \(F_n\), la fonction fibonacci_rec s’appelle elle-même sur l’entrée \(n-1\) et l’entrée \(n-2\). Or pour calculer \(F_{n-1}\), on a également besoin de \(F_{n-2}\) et de \(F_{n-3}\). Par conséquent, la fonction fibonacci_rec est appelée deux fois sur l’entrée \(n-2\), alors qu’une seule suffirait.
Puis, ce « gâchis » est répété (et s’empire) pur calculer \(F_{n-3}\), \(F_{n-4}\), etc. Au bout du compte, le nombre d’appels à fibonacci_rec est immense : de l’ordre de \(7\) millions d’appels pour calculer \(F_{32}\)…
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.
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\) :
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]]
def triangle_pascal(N):
L = [[1]]
for n in range(1, N+1):
ligne = [1]
for k in range(1, n):
ligne.append(L[n-1][k-1] + L[n-1][k])
ligne.append(1)
L.append(ligne)
return L
triangle_pascal(6)
[[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]]
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
alors (en observant que \(A\) et \(B\) sont croissantes), la fusion ordonnée de \(A\) et \(B\) est
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).
def fusionne_iter(liste1, liste2):
i = 0
j = 0
n = len(liste1)
m = len(liste2)
L = []
while (i < n) and (j < m):
if liste1[i] < liste2[j]:
L.append(liste1[i])
i += 1
else:
L.append(liste2[j])
j += 1
if i == n:
for k in range(j, m):
L.append(liste2[k])
elif j == m:
for k in range(i, n):
L.append(liste1[k])
return L
print(fusionne_iter([1, 4, 5], [2, 4, 8]))
[1, 2, 4, 4, 5, 8]
Question 2 : Écrire une fonction récursive fusionne_rec(liste1, liste2) qui retourne la fusion ordonnée de deux listes croissantes liste1 et liste2.
def fusionne_rec(liste1, liste2):
if liste1 == []:
return liste2
elif liste2 == []:
return liste1
else:
x1 = liste1[0]
x2 = liste2[0]
if x1 <= x2:
liste1.pop(0)
return [x1] + fusionne_rec(liste1, liste2)
else:
liste2.pop(0)
return [x2] + fusionne_rec(liste1, liste2)
print(fusionne_rec([1, 4, 5], [2, 4, 8]))
[1, 2, 4, 4, 5, 8]
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]
Solution en récursif :
def fusionne_tout(L):
if len(L) == 0:
return []
if len(L) == 1:
return L[0]
if len(L) == 2:
return fusionne_rec(L[0], L[1])
liste = L.pop()
return fusionne_rec(liste, fusionne_tout(L))
print(fusionne_tout([[1, 4, 5], [], [7, 11, 11], [1, 2, 4, 7], [2, 4, 8]]))
[1, 1, 2, 2, 4, 4, 4, 5, 7, 7, 8, 11, 11]
En itératif :
def fusionne_tout(L):
resultat = []
for liste in L:
resultat = fusionne_iter(resultat, liste)
return resultat
print(fusionne_tout([[1, 4, 5], [], [7, 11, 11], [1, 2, 4, 7], [2, 4, 8]]))
[1, 1, 2, 2, 4, 4, 4, 5, 7, 7, 8, 11, 11]
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
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.
def maximum_rec(L):
if len(L) == 1:
return L[0]
else:
x = L.pop()
y = max(L)
if x > y:
return x
else:
return y
print(maximum_rec([1, 2, 5, 2, 3]))
print(maximum_rec([12]))
5
12