problème dans un exercice n-ième nombre de Fibonacci

Version imprimable

j'ai l'énoncé suivant:
Écrivez une fonction fibo(n) qui reçoit un nombre entier : n en paramètre, et qui, renvoie le n-ième nombre de Fibonacci Fi avec
F0 valant 0
F1 valant 1
Fi+1 valant F i+ F i - 1
Fn valant None si n<0 Par ailleurs, écrivez le code principal: votre programme lira une donnée entière x de type int et imprimera le résultat de l'exécution de fibo(i) pour i allant de 0 compris à x non compris avec chaque valeur sur une ligne séparée.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 def fibo(n): """fibo(n) qui reçoit un nombre entier : n en paramètre, et qui, renvoie le n-ième nombre de Fibonacci Fi avec F0 valant 0 F1 valant 1 Fi+1 valant Fi+F i - 1 Fn valant None si n<0""" prec,succ = 0,1 if (n == 0): return 0 elif (n == 1): return 1 elif (n < 1): return if(n>1): print(prec) print(succ) for i in range(n-2): prec, succ = succ, prec + succ print(succ) return succ x=int(input()) for i in range(x): print (fibo(i)) break
le code fonctionn ebien pour le 0, 1, -1 mais ne retourne pas des valeur pour
fail fibo(12) n'a pas retourné 144
fail fibo(12) n'a pas retourné 144
fail fibo(14) n'a pas retourné 377
fail fibo(14) n'a pas retourné 377
fail fibo(18) n'a pas retourné 2584

17/03/2019, 22h07
flapili
Bonjour,

votre algorithme me semble inutilement compliquer, voici ce que je vous propose
Code:

1 2 3 4 5 6 7 8 9 def f(n): if n<0: return None temp = 1 v = 0 for i in range(n): v = v + temp # ou v += temp temp = v - temp # or à ce stade v = v + temp, il faut donc soustraire temp return v
l'idée étant que à chaque itération on ajoute temp à v.
or on ne veux pas ajouter 1 à v mais la valeur précédente de v, il faut donc aussi ajouter notre dernière valeur v à temp et penser à retirer temp car on l'a déjà ajouté à v.

En espérant avoir été clair, bonne soirée à vous :)

ps: pour ce genre de calcul par récurrence je conseil l'utilisation de générateur (ou de liste si vous ne maitrisez pas python), avec un générateur on calcul les valeurs au fur et à mesure et on renvoie à chaque fois la valeur, et avec une liste on calcul l'ensemble de valeurs puis on retourne cette liste

merci flapili le problème était que j'avais oublié la soustraction, le code complet fonctionnant pour ce problème est alors:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 def fibo(n): if n<0: return None temp = 1 v = 0 for i in range(n): v = v + temp # ou v += temp temp = v - temp # or à ce stade v = v + temp, il faut donc soustraire temp return v x=int(input()) for i in range(x): print (fibo(i))
merci et bonne soirée

le "problème" ici est que vous recalculez les valeurs à chaque fois: vous avez le choix entre liste ou générateur, un exemple :

générateur :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
def f(n):
	if n<0:
		return None
	tmp = 1
	v = 0
	for i in range(n):
		v += tmp
		tmp = v - tmp
		yield v
 
for n in f(50):
	print(n)

liste:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
def f(n):
	if n<0:
		return None
	values = []
	tmp = 1
	v = 0
	for i in range(n):
		v += tmp
		tmp = v - tmp
		values.append(v)
 
	return values
 
liste_valeurs = f(50)
for n in liste_valeurs:
	print(n)

18/03/2019, 09h35
fred1599

Bonjour,

Voici sur cette page, un exemple pour fibo...

Cet exercice a été sujet à beaucoup de discussions pour améliorer les performances (interfaçages avec d'autres langages, générateurs -> itertools, ...).

On a pu démontrer que la récursivité était une catastrophe côté performance.

C'est hyper documenté sur le web ! et même sur ce forum (environ 150 résultats juste pour python)...
18/03/2019, 10h03
flapili

Citation:

Envoyé par fred1599

On a pu démontrer que la récursivité était une catastrophe côté performance.

il s'agit d'une suite pouvant se calculer par récurrence mathématique mais ici il n'est pas question de récursivité.

De plus hier en utilisant le générateur je me suis dit pourquoi ne pas calculer le le 10 000 000ième terme de la suite, de façon quasi instantané j'ai eu le résultat (le plus long dans tout ça a été l'affichage de ce nombre)
18/03/2019, 12h05
fred1599

Citation:

Envoyé par flapili

il s'agit d'une suite pouvant se calculer par récurrence mathématique mais ici il n'est pas question de récursivité.

Ma phrase concernant la récursivité était liée à la phrase précédente ci-dessous,

Citation:

Envoyé par fred1599

Cet exercice a été sujet à beaucoup de discussions pour améliorer les performances (interfaçages avec d'autres langages, générateurs -> itertools, ...).

et non au sujet du PO.

Citation:

Envoyé par flapili

le plus long dans tout ça a été l'affichage de ce nombre

Ce qui est normal, car tous les calculs se font via la mémoire vive (yield), et, on demande seulement après l'ensemble des calculs, son affichage.