Discussion :

[FATENMRABET]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[flapili]

Bonjour,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[FATENMRABET]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[flapili]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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)

[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)...

[flapili]

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)

[fred1599]

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,

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.

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.