Discussion :

[jesse100]

J'essaie de trouver une réponse à ce problème sur un autre site Web de pratique. Je suis nouveau sur Python, et une série de Fibonacci de 1,2,3,5,8,13,21,34,55,89... Je veux calculer la somme des éléments pairs dans le. Suite de Fibonacci dont les valeurs ne dépassent pas N (par exemple, N=10).
De plus, la plus petite valeur supérieure à N.

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
N = 10
def fibonacci(n):
    if n in fibonacci_cashe: 
        return fibonacci_cashe[n]
    if n==1:
        value = 1
    elif n == 2:
        value = 1
    elif n>2:
        value = fibonacci(n-2)+fibonacci(n-1)
 
    fibonacci_cashe[n] = value
    return value 
for i in range(N):
    test = fibonacci(N)
    #I don't know what I should do here

La série est 1,2,3,5,8,13,21,34,55,89, 144, 144+89,... les moins de (N=10) sont : 2, 8, 34, et les le total est de 44. 13 est le plus petit plus grand que (N=10).
Pourriez-vous m'aider avec ce problème? J'ai vu un article sur la série de Fibonacci qui proposait de supprimer la mémorisation. Est-ce correct?
Merci beaucoup.

[Sve@r]

Bonjour à toi aussi, comme d'hab !!!

Est-ce correct?

Déjà ton code non. Tu utilises fibonacci_cashe qui n'est pas défini (semble que ce serait un dict). Et tu utilises la récursivité là où une simple itération fait le job en mille fois plus rapide (et utiliser le cache qui permet d'éviter des calculs inutiles ok mais quand le code est mal foutu dès le départ ça reste une béquille)

Code python :

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

1
2
3
4
5
6
7
8
9
10
def fibonacci(n):
	assert n > 0
	res=[1, 1]
	if n <= 2: return res[:n]
	for i in range(2, n):
		res.append(res[-2] + res[-1])
	return res
 
for i in range(1, 10):
	print(i, fibonacci(i))

Et ce n'est qu'une façon de faire parmis des dizianes (celle-ci crée d'abord les n chiffres mais on peut se contenter de calculer et renvoyer le dernier fib(n) ou autre générateur)

De plus, la plus petite valeur supérieure à N.

Ceci n'est pas une phrase, il n'y a pas de verbe.

les moins de (N=10) sont : 2, 8, 34, et les le total est de 44. 13 est le plus petit plus grand que (N=10).

Alors première info: 34 n'est pas inférieur à 10. Et si c'est la suite de chiffres d'une longueur inférieure à 10 alors il y a des chiffres intermédiaires entre 8 et 34. Et si tu veux parler des pairs, alors je ne vois pas ce que "13" vient faire ici.

J'ai vu un article sur la série de Fibonacci qui proposait de supprimer la mémorisation.

Mouais. Cet article est en effet très bien détaillé, mais il ne dit rien de prépondérant qui n'ait déjà été dit au collège en 5°. Et éviter la récursivité chaque fois que c'est possible est un des fondements de tous les cours de programmation quand ils abordent le chapitre de la récursivité.

[wiztricks]

Salut,

Pourriez-vous m'aider avec ce problème?

C'est un problème d'algorithme qui se traite en réfléchissant plus ou moins longtemps sur une feuille de papier à gribouiller avec un crayon.

J'ai vu un article sur la série de Fibonacci qui proposait de supprimer la mémorisation. Est-ce correct?

Si le but est de compter les N premiers entiers pairs de la suite, il suffit de compter combien on en a trouvé et d'arrêter à N. Ce qui se fait avec un compteur et une condition qui arrête la boucle. C'est le genre d'exercice proposé dans tous les tutos (parfois corrigés) et qu'on fait pour arriver à maîtriser boucles et conditions.

- W

[Pyramidev]

Je suis nouveau sur Python, et une série de Fibonacci de 1,2,3,5,8,13,21,34,55,89... Je veux calculer la somme des éléments pairs dans le. Suite de Fibonacci dont les valeurs ne dépassent pas N (par exemple, N=10).
De plus, la plus petite valeur supérieure à N.

Normalement, les deux premiers éléments d'une suite de Fibonacci sont 0 et 1. Mais bon, le résultat final sera le même.

Si on définit la suite de Fibonacci sous forme d'itérateur, par exemple avec un générateur (utilisation du mot-clef yield), alors on peut résoudre l'exercice ainsi, avec une complexité linéaire et sans mémoïsation :

Code Python :

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
def fibonacci():
    x = 1
    yield x
    y = 2
    yield y
    while True:
        x, y = y, x + y
        yield y
 
def exercise(N):
    numbers = fibonacci()
    x = next(numbers)
    sum_of_even_numbers = 0
    while x <= N:
        x = next(numbers)
        if x % 2 == 0:
            sum_of_even_numbers += x
    return sum_of_even_numbers, x

Dans le code de la fonction exercise, chaque appel à x = next(numbers) met dans x la valeur suivante de la suite de Fibonacci.

Pour résoudre l'exercice sans définir la suite de Fibonacci sous forme d'itérateur, mais en gardant la complexité linéaire et sans utiliser la mémoïsation, il faut fusionner comme il faut les codes des fonctions fibonacci et exercise. Cela ne devrait être assez simple. Bonne chance.

[wiztricks]

Salut,

Si on définit la suite de Fibonacci sous forme d'itérateur, par exemple avec un générateur (utilisation du mot-clef yield), alors on peut résoudre l'exercice ainsi, avec une complexité linéaire et sans mémoïsation :

Voilà une solution élégante...

Néanmoins, un algorithme digne de ce nom s'arrête au bout d'un certain temps => on va afficher les N premiers éléments de la suite et écrire dans tous les cas quelque chose comme:

Code :

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

1
2
3
4
5
6
7
8
9
a = 0
b = 1
n = int(input("nombre de termes a afficher: ")) - 2
print (a, b, end=" ")
while n:
    c = a + b
    a, b = b, c
    print(c, end=" ")
    n = n - 1

Et si on a su écrire çà, décrémenter n lorsque c est pair est assez trivial.

note: si on ajoute une fonction là dedans, ce n'est plus un exercice de débutant qui débute à peine.

- W