Bonjour, j'ai un problème concernant un exercice donné par ma professeure en informatique, je dois renvoyer les valeurs de la suite de fibonacci de 0 à n dans une liste en utilisant la récursivité (ex: tableFibonacci(0) = [1], tableFibonacci(5) = [1, 1, 2, 3, 5, 8]). Cependant j'ai un problème car pour obtenir tableFibonacci(0) = [1] et tableFibonacci(1) = [1, 1] j'ai fait 2 cas de base:
if n==0:
return [1]
if n==1:
return [1, 1]
Mais ça me pose problème après car avec ce code:
def tableFibonacci(n, liste=[1, 1]):
if n==0:
return [1]
if n==1:
return [1, 1]
return tableFibonacci(n-1, liste + [liste[-1] + liste[-2]]) + [liste[-1]+liste[-2]])
Je me retrouve avec une liste partiellement dans le mauvais sens et peu importe que j'inverse le
[liste[-1]+liste[-2]]
le résultat reste faux.
Voilà j'espère avoir été clair, merci d'avance pour votre aide.
PS: je pensais peut-être essayé quelque chose avec list.append() mais c'est encore pire qu'avant
Merci beaucoup pour la réponse je pensais pas du tout à faire comme ça j'ai encore des lacunes sur la récursivité
@PierrotLeFou: C'est pas plus efficace que de calculer le terme de la suite fn ? Puisque l'on ne rappelle pas plusieurs fois le calcul de fibonacci(k) pour un k plus petit que n
Peut-être que c'est ce que tu sous-entends quand tu dis qu'elle est linéaire sur la valeur de n
- Edité par hhheeellllllooo 12 février 2024 à 21:55:35
def tableFibonacci(n):
if n == 0:
return [0]
elif n == 1:
return [0, 1]
else:
prev = tableFibonacci(n-1)
return prev + [prev[-1] + prev[-2]]
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
moins de lignes mais fabriquer des listes à chaque appel est plus couteux en ressources
Que croyez vous faire sur cette ligne ?
u, v = L[-2:]
Et pour le L + ... je sais pas ce que donne la concaténation d'une liste, je l'utilise très peu à contrario de append.
Après la consommation mémoire on s'en ballec sur les PCs actuels et au niveau CPU, j'en sais rien...
D'ailleurs dans le meilleur des deux mondes, pourquoi pas
def tableFibonacci(n):
if n == 0:
return [0]
elif n == 1:
return [0, 1]
else:
prev = tableFibonacci(n-1)
prev.append(prev[-1] + prev[-2])
return prev
EDIT : Si on veut des performances on n'utilise pas la récursivité en python et au moins la forme itérative.
Si on veut des performances en récursif, on utilise au moins la mémoïzation
def tableFibonacci(n, memo=None):
if memo is None:
memo = {0: [0], 1: [0, 1]}
if n in memo:
return memo[n]
if n-1 not in memo:
tableFibonacci(n-1, memo)
if n-2 not in memo:
tableFibonacci(n-2, memo)
memo[n] = memo[n-1] + [memo[n-1][-1] + memo[n-2][-1]]
return memo[n]
et si la forme itérative ne suffit pas, alors on change de langage comme du C/C++
- Edité par fred1599 13 février 2024 à 15:04:12
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Je crois que ce qui coûte (encore que ça doive dépendre de l'implémentation, qui pourrait optimiser), c'est d'écrire
L = L + [x]
au lieu de
L.append(x)
parce que le premier cause probablement l'extension d'une copie de L, et que la copie, ça a un coût proportionnel à la longueur. Et dans une boucle qui fait n fois cet ajout, le coût total (en temps d'exécution) sera proportionnel au carré de n. Quadratique, on dit.
Certes, c'est mieux que de s'embarquer dans un truc exponentiel, mais quand même. Avec append, c'est seulement linéaire (proportionnel à n). Et donc à la taille de la liste à obtenir, on pourra pas faire mieux.
---
Après si le peuple (et le prof qui exige que les solutions correspondent à la question posée) insiste pour avoir un truc récursif, on peut remplacer
def allonger(liste, nb_fois):
for i in range(nb_fois):
liste.append(liste[-1] + liste[-2])
return liste
par
def allonger(liste, nb_fois):
if nb_fois > 0:
liste.append(liste[-1] + liste[-2])
allonger(liste, nb_fois - 1)
return liste
et - roule ma poule - la liste des n premiers nombres de la suite de fibo, c'est
Je ne peux que confirmer ce que dit Michel Billaud. Bien sûr, avec la limitation des appels récursifs, on ne peut pas tester l'inefficacité du code, mais si on dérécursifie en gardant la même gestion des listes, on voit tout de suite qu'une méthode est beaucoup plus rapide que l'autre :
def z(n):
if n == 1:
return [0]
elif n == 2:
return [0, 1]
prev=[0,1]
for k in range(n-2):
prev=prev + [prev[-1] + prev[-2]]
return prev
def f(n):
if n == 1:
return [0]
elif n == 2:
return [0, 1]
L=[0,1]
for k in range(n-2):
u, v = L[-2:]
L.append(u + v)
return L
from time import perf_counter
N=5*10**4
begin_perf = perf_counter()
# ---- Début de code à exécuter ----
z(N)
# ---- Fin de code à exécuter ----
delta = perf_counter() - begin_perf
print(f"Temps d'exécution de z : {delta:.2f}s")
begin_perf = perf_counter()
# ---- Début de code à exécuter ----
f(N)
# ---- Fin de code à exécuter ----
delta = perf_counter() - begin_perf
print(f"Temps d'exécution de f : {delta:.2f}s")
$ python3 fibo.py
Temps d'exécution de z : 13.02s
Temps d'exécution de f : 0.07s
fred1599 a écrit:
moins de lignes mais fabriquer des listes à chaque appel est plus couteux en ressources
Que croyez vous faire sur cette ligne ?
u, v = L[-2:]
Pour le coup, c'est assez astucieux car le tableau (de références) créé contient juste deux éléments, ce sera un tableau temporaire et il permet d'extraire efficacement u et v sans appel à la méthode spéciale getitem qui ralentit beaucoup. Si on remplace à la ligne d'après son code par L.append(L[-1]+L[-2]), le temps est équivalent.
Pendant que mes carottes et patates cuisent, je me suis dit que ça serait bien de vérifier expérimentalement l'histoire l'ajout par append ou concaténation.
Sujet du test, une fonction qui construit une liste [0,1, .... n-1] par une boucle, on va comparer les deux implémentations
def construction_par_concatenation(n):
liste = []
for i in range(n):
liste = liste + [i]
return liste
def construction_par_append(n):
liste = []
for i in range(n):
liste.append(i)
return liste
On se bricole une fonction qui affiche le temps d'exécution d'une fonction (reçue en paramètre) pour une taille donnée
from time import perf_counter
def mesurer(nom, fonction, taille):
debut = perf_counter()
fonction(taille)
fin = perf_counter()
print(f"{nom} {taille} éléments, durée {fin-debut:.4f}")
et on lance des tests, en multipliant la taille par 2.
2) que ça semble linéaire (2 fois plus d'éléments => 2 fois plus de temps)
La théorie c'est bien, mais vérifions en pratique qu'elle permet de prévoir. Si on multiplie par 10 la taille, ça devrait prendre 10 fois plus de temps
Conclusion : ça colle, on dirait. (modulo les incertitudes de mesure, qui ne donnent pas les mêmes temps à chaque fois).
-----
EDIT: après avoir savouré les délicieux légumes, voyons deux versions de la construction de fibo dans une liste par append, histoire de comparer les techniques d'accès aux derniers éléments
def liste_fib_indices(n):
liste = [1, 1]
if (n <= 2):
return liste[:n]
for i in range(n - 2):
liste.append(liste[-1] + liste[-2])
return liste
def liste_fib_destruct(n):
liste = [1, 1]
if (n <= 2):
return liste[:n]
for i in range(n - 2):
a, b = liste[-2:]
liste.append(a + b)
return liste
Résultat des courses (en relançant 3 fois les tests)
Pendant que mes carottes et patates cuisent, je me suis dit que ça serait bien de vérifier expérimentalement l'histoire l'ajout par append ou concaténation.
Si on écrit:
def construction_par_concatenation(n):
liste = []
for i in range(n):
liste = liste + [i]
return liste
on crée une nouvelle liste de plus en plus grosse (avec le n qui augmente).
Ecrire:
def construction_par_concatenation(n):
liste = []
for i in range(n):
liste += [i]
return liste
devrait donner des résultats comparables (à .append).
Pendant que mes carottes et patates cuisent, je me suis dit que ça serait bien de vérifier expérimentalement l'histoire l'ajout par append ou concaténation.
Si on écrit:
def construction_par_concatenation(n):
liste = []
for i in range(n):
liste = liste + [i]
return liste
on crée une nouvelle liste de plus en plus grosse (avec le n qui augmente).
Ecrire:
def construction_par_concatenation(n):
liste = []
for i in range(n):
liste += [i]
return liste
devrait donner des résultats comparables (à .append).
Des fois on croit des trucs, et quand on se donne la peine de vérifier, on a des surprises
def construction_par_extend(n):
liste = []
for i in range(n):
liste.extend([i])
return liste
def construction_par_extension(n):
liste = []
for i in range(n):
liste += [i]
return liste
def construction_par_append(n):
liste = []
for i in range(n):
liste.append(i)
return liste
Ps: dans la fonction de mesure, ai corrigé la prise du temps par
debut = time.process_time()
fonction(taille)
fin = time.process_time()
qui donne le temps CPU consommé, plutôt que temps réel écoulé, qui dépend de la charge de la machine.
C'est une bonne idée. Mais ma machine est trop rapide: il faut multiplier l'échantillon par 100 pour voir du temps passé et les pouièmes de temps passés ne sont pas trop cohérents:
Dans ce genre de test, faire N fois la même opération sur un "petit" échantillon vs. comparer le résultat d'une opération en fonction de la taille de l'échantillon sollicitera la machine (ici le sous système mémoire) différemment. Reste qu'il est bon de conforter ses idées aux réalités (sans oublier que le code Python vole bien haut dessus de la machine physique).
L+=[i] devrait plus lent que L. append(i) car il y a à chaque étape création d'une liste et d'après la doc elle-même concernant += :
when possible, the actual operation is performed in-place, meaning that rather than creating a new object and assigning that to the target, the old object is modified instead
en sorte que append et += se comportent pareil. Bien sûr, il faut que les données soient suffisamment volumineuses pour qu'on ne mesure pas des epsilons d'epsilon :
def a(n):
liste = []
for i in range(n):
liste.append(i)
return liste
def b(n):
liste = []
for i in range(n):
liste += [i]
return liste
from time import perf_counter
N=5*10**6
begin_perf = perf_counter()
a(N)
delta = perf_counter() - begin_perf
print(f"Temps d'exécution de a : {delta:.2f}s")
begin_perf = perf_counter()
b(N)
delta = perf_counter() - begin_perf
print(f"Temps d'exécution de b : {delta:.2f}s")
Temps d'exécution de a : 0.50s
Temps d'exécution de b : 0.63s
Par ailleurs, poser append=liste.append n'apporte qu'une amélioration mineure.
Si on veut des performances en récursif, on utilise au moins la mémoïzation
def tableFibonacci(n, memo=None):
if memo is None:
memo = {0: [0], 1: [0, 1]}
if n in memo:
return memo[n]
if n-1 not in memo:
tableFibonacci(n-1, memo)
if n-2 not in memo:
tableFibonacci(n-2, memo)
memo[n] = memo[n-1] + [memo[n-1][-1] + memo[n-2][-1]]
return memo[n]
Certes. Et dans ce cas, on utilise @cache de functools :
from functools import cache
@cache
def fibo(n):
if n == 0:
return 0
elif n == 1:
return 1
return fibo(n - 1) + fibo(n - 2)
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.