J'avais initialement mal codé le programme. Au lieu de renvoyer les nombres de Fibonacci entre une plage (c'est-à-dire. StartNumber 1, endNumber 20 devrait = uniquement les nombres entre 1 et 20), j'ai écrit pour que le programme affiche tous les nombres de Fibonacci entre une plage (c'est-à-dire. StartNumber 1, endNumber 20) affiche = 20 premiers nombres de Fibonacci). Je pensais avoir un code infaillible. Je ne vois pas non plus pourquoi cela se produit.

startNumber = int(raw_input("Enter the start number here "))
endNumber = int(raw_input("Enter the end number here "))

def fib(n):
    if n < 2:
        return n
    return fib(n-2) + fib(n-1)

print map(fib, range(startNumber, endNumber))

Quelqu'un a souligné dans ma partie II (qui a été fermée pour être un double - /programming/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii ) que je besoin de passer le startNumber et endNumber à travers un générateur en utilisant une boucle while. Quelqu'un peut-il s'il vous plaît m'indiquer comment faire cela? Toute aide est la bienvenue.

Je suis un programmeur en apprentissage et je me suis heurté à un fouillis. On me demande d'écrire un programme qui calculera et affichera la séquence de Fibonacci par un numéro de début et un numéro de fin saisis par l'utilisateur (c'est-à-dire. StartNumber = 20 endNumber = 100 et il n'affichera que les nombres compris entre cette plage). L'astuce est de l'utiliser de manière inclusive (ce que je ne sais pas faire en Python? - Je suppose que cela signifie utiliser une plage inclusive?).

Ce que j'ai jusqu'à présent, ce n'est pas de codage réel mais plutôt:

• Ecrire la formule de séquence Fib à l'infini
• Afficher startNumber à endNumber uniquement à partir de la séquence Fib.

Je n'ai aucune idée par où commencer et je demande des idées ou un aperçu de la façon d'écrire ceci. J'ai aussi essayé d'écrire la séquence Fib forumla mais je m'y perds aussi.

Il y a beaucoup d'informations sur la séquence de Fibonacci sur wikipedia et sur wolfram . Beaucoup plus que ce dont vous pourriez avoir besoin. Quoi qu'il en soit, c'est une bonne chose d'apprendre à utiliser ces ressources pour trouver (rapidement si possible) ce dont vous avez besoin.

Ecrire la formule de séquence Fib à l'infini

En maths, c'est donné sous une forme récursive:

En programmation, l' infini n'existe pas. Vous pouvez utiliser une forme récursive traduisant la forme mathématique directement dans votre langage, par exemple en Python cela devient:

def F(n):
    if n == 0: return 0
    elif n == 1: return 1
    else: return F(n-1)+F(n-2)

Essayez-le dans votre langue préférée et voyez que ce formulaire prend beaucoup de temps à mesure que n grossit. En fait, il s'agit de O (2 ⁿ ) dans le temps.

Continuez sur les sites que je vous ai liés et vous verrez ceci (sur wolfram ):

Celui-ci est assez facile à implémenter et très, très rapide à calculer, en Python:

from math import sqrt
def F(n):
    return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))

Une autre façon de le faire est de suivre la définition (de wikipedia ):

Le premier numéro de la séquence est 0, le deuxième nombre est 1 et chaque numéro suivant est égal à la somme des deux nombres précédents de la séquence elle-même, ce qui donne la séquence 0, 1, 1, 2, 3, 5, 8 , etc.

Si votre langage prend en charge les itérateurs, vous pouvez faire quelque chose comme:

def F():
    a,b = 0,1
    while True:
        yield a
        a, b = b, a + b

Afficher startNumber à endNumber uniquement à partir de la séquence Fib.

Une fois que vous savez comment générer des nombres de Fibonacci, il vous suffit de parcourir les nombres et de vérifier s'ils vérifient les conditions données.

Supposons maintenant que vous écriviez af (n) qui renvoie le n-ième terme de la séquence de Fibonacci (comme celui avec sqrt (5))

Dans la plupart des langues, vous pouvez faire quelque chose comme:

def SubFib(startNumber, endNumber):
    n = 0
    cur = f(n)
    while cur <= endNumber:
        if startNumber <= cur:
            print cur
        n += 1
        cur = f(n)

En python, j'utiliserais la forme d'itérateur et je choisirais:

def SubFib(startNumber, endNumber):
    for cur in F():
        if cur > endNumber: return
        if cur >= startNumber:
            yield cur

for i in SubFib(10, 200):
    print i

Mon conseil est d' apprendre à lire ce dont vous avez besoin. Project Euler (google pour cela) vous apprendra à le faire: P Bonne chance et amusez-vous!

Générateur pythonique efficace de la séquence de Fibonacci

J'ai trouvé cette question en essayant d'obtenir la génération pythonique la plus courte de cette séquence (réalisant plus tard que j'en avais vu une similaire dans une proposition d'amélioration de Python ), et je n'ai remarqué personne d'autre proposer ma solution spécifique (bien que la première réponse se rapproche, mais encore moins élégant), alors le voici, avec des commentaires décrivant la première itération, car je pense que cela peut aider les lecteurs à comprendre:

def fib():
    a, b = 0, 1
    while True:            # First iteration:
        yield a            # yield 0 to start with and then
        a, b = b, a + b    # a will now be 1, and b will also be 1, (0 + 1)

et utilisation:

for index, fibonacci_number in zip(range(10), fib()):
     print('{i:3}: {f:3}'.format(i=index, f=fibonacci_number))

imprime:

  0:   0
  1:   1
  2:   1
  3:   2
  4:   3
  5:   5
  6:   8
  7:  13
  8:  21
  9:  34
 10:  55

(À des fins d'attribution, j'ai récemment remarqué une implémentation similaire dans la documentation Python sur les modules, même en utilisant les variables aet b, que je me souviens maintenant d'avoir vu avant d'écrire cette réponse. Mais je pense que cette réponse démontre une meilleure utilisation du langage.)

Implémentation définie de manière récursive

L' Encyclopédie en ligne des séquences entières définit la séquence de Fibonacci de manière récursive comme

F (n) = F (n-1) + F (n-2) avec F (0) = 0 et F (1) = 1

La définition succincte de cela de manière récursive en Python peut être effectuée comme suit:

def rec_fib(n):
    '''inefficient recursive function as defined, returns Fibonacci number'''
    if n > 1:
        return rec_fib(n-1) + rec_fib(n-2)
    return n

Mais cette représentation exacte de la définition mathématique est incroyablement inefficace pour les nombres bien supérieurs à 30, car chaque nombre en cours de calcul doit également calculer pour chaque nombre en dessous. Vous pouvez démontrer sa lenteur en utilisant ce qui suit:

for i in range(40):
    print(i, rec_fib(i))

Récursivité mémorisée pour plus d'efficacité

Il peut être mémorisé pour améliorer la vitesse (cet exemple tire parti du fait qu'un argument de mot-clé par défaut est le même objet à chaque fois que la fonction est appelée, mais normalement vous n'utiliseriez pas un argument par défaut mutable pour exactement cette raison):

def mem_fib(n, _cache={}):
    '''efficiently memoized recursive function, returns a Fibonacci number'''
    if n in _cache:
        return _cache[n]
    elif n > 1:
        return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
    return n

Vous constaterez que la version mémorisée est beaucoup plus rapide et dépassera rapidement votre profondeur de récursivité maximale avant même de pouvoir penser à vous lever pour prendre un café. Vous pouvez voir à quel point il est visuellement plus rapide en faisant ceci:

for i in range(40):
    print(i, mem_fib(i))

(Il peut sembler que nous pouvons simplement faire ce qui suit, mais cela ne nous permet pas de profiter du cache, car il s'appelle lui-même avant que setdefault ne soit appelé.)

def mem_fib(n, _cache={}):
    '''don't do this'''
    if n > 1:  
        return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
    return n

Générateur défini récursivement:

En apprenant Haskell, je suis tombé sur cette implémentation dans Haskell:

fib@(0:tfib) = 0:1: zipWith (+) fib tfib

Le plus proche que je pense pouvoir arriver à cela en Python pour le moment est:

from itertools import tee

def fib():
    yield 0
    yield 1
    # tee required, else with two fib()'s algorithm becomes quadratic
    f, tf = tee(fib()) 
    next(tf)
    for a, b in zip(f, tf):
        yield a + b

Cela le démontre:

[f for _, f in zip(range(999), fib())]

Il ne peut cependant aller que jusqu'à la limite de récursivité. Habituellement, 1000, alors que la version Haskell peut aller jusqu'à des centaines de millions, bien qu'elle utilise les 8 Go de mémoire de mon ordinateur portable pour ce faire:

> length $ take 100000000 fib 
100000000

Consommer l'itérateur pour obtenir le nième numéro de fibonacci

Un commentateur demande:

Question pour la fonction Fib () qui est basée sur l'itérateur: que faire si vous voulez obtenir le nième, par exemple le 10e numéro de fib?

La documentation itertools a une recette pour cela:

from itertools import islice

def nth(iterable, n, default=None):
    "Returns the nth item or a default value"
    return next(islice(iterable, n, None), default)

et maintenant:

>>> nth(fib(), 10)
55

Pourquoi ne pas simplement faire ce qui suit?

x = [1,1]
for i in range(2, 10):  
    x.append(x[-1] + x[-2]) 
print(', '.join(str(y) for y in x))

L'idée derrière la séquence de Fibonacci est illustrée dans le code Python suivant:

def fib(n):
   if n == 1:
      return 1
   elif n == 0:   
      return 0            
   else:                      
      return fib(n-1) + fib(n-2)         

Cela signifie que le fib est une fonction qui peut faire l'une des trois choses. Il définit fib (1) == 1, fib (0) == 0 et fib (n) comme:

fib (n-1) + fib (n-2)

Où n est un entier arbitraire. Cela signifie que fib (2), par exemple, se développe vers l'arithmétique suivante:

fib(2) = fib(1) + fib(0)
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(2) = 1 + 0
fib(2) = 1

Nous pouvons calculer fib (3) de la même manière avec l'arithmétique ci-dessous:

fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(2) = 1
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(3) = 1 + 1 + 0

La chose importante à réaliser ici est que fib (3) ne peut pas être calculé sans calculer fib (2), qui est calculé en connaissant les définitions de fib (1) et fib (0). Faire appeler une fonction comme le fait la fonction fibonacci s'appelle récursivité, et c'est un sujet important en programmation.

Cela ressemble à un devoir, donc je ne vais pas faire la partie début / fin pour vous. Python est un langage merveilleusement expressif pour cela, donc cela devrait avoir du sens si vous comprenez les mathématiques, et nous l'espérons, vous apprendra la récursivité. Bonne chance!

Edit: Une critique potentielle de mon code est qu'il n'utilise pas le rendement de la fonction Python super pratique, ce qui rend la fonction fib (n) beaucoup plus courte. Mon exemple est cependant un peu plus générique, car peu de langages en dehors de Python ont réellement du rendement.

Complexité temporelle:

La fonction de mise en cache réduit la manière normale de calculer les séries de Fibonacci de O (2 ^ n) à O (n) en éliminant les répétitions dans l'arbre récursif de la série de Fibonacci:

Code:

import sys

table = [0]*1000

def FastFib(n):
    if n<=1:
        return n
    else:
        if(table[n-1]==0):
            table[n-1] = FastFib(n-1)
        if(table[n-2]==0):
            table[n-2] = FastFib(n-2)
        table[n] = table[n-1] + table[n-2]
        return table[n]

def main():
    print('Enter a number : ')
    num = int(sys.stdin.readline())
    print(FastFib(num))

if __name__=='__main__':
    main()

C'est assez efficace, en utilisant des opérations arithmétiques de base O (log n).

def fib(n):
    return pow(2 << n, n + 1, (4 << 2*n) - (2 << n) - 1) % (2 << n)

Celui-ci utilise des opérations arithmétiques de base O (1), mais la taille des résultats intermédiaires est grande et n'est donc pas du tout efficace.

def fib(n):
    return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1)

Celui-ci calcule X ^ n dans l'anneau polynomial Z [X] / (X ^ 2 - X - 1) en utilisant l'exponentiation par quadrillage. Le résultat de ce calcul est le polynôme Fib (n) X + Fib (n-1), à partir duquel le nième nombre de Fibonacci peut être lu.

Encore une fois, cela utilise des opérations arithmétiques O (log n) et est très efficace.

def mul(a, b):
        return a[0]*b[1]+a[1]*b[0]+a[0]*b[0], a[0]*b[0]+a[1]*b[1]

def fib(n):
        x, r = (1, 0), (0, 1)
        while n:
                if n & 1: r = mul(r, x)
                x = mul(x, x)
                n >>= 1
        return r[0]

Code Python canonique pour imprimer la séquence de Fibonacci:

a,b=1,1
while True:
  print a,
  a,b=b,a+b       # Could also use b=a+b;a=b-a

Pour le problème "Imprimer le premier numéro de Fibonacci supérieur à 1000 chiffres":

a,b=1,1
i=1
while len(str(a))<=1000:
  i=i+1
  a,b=b,a+b

print i,len(str(a)),a

Nous savons que

Et que la puissance n-ième de cette matrice nous donne:

Nous pouvons donc implémenter une fonction qui calcule simplement la puissance de cette matrice à la n-ième puissance -1.

comme tout ce que nous savons, la puissance a ^ n est égale à

Donc à la fin la fonction fibonacci serait O (n) ... rien de vraiment différent d'une implémentation plus facile si ce n'était du fait que nous savons aussi que x^n * x^n = x^2net l'évaluation de x^npeut donc se faire avec la complexité O (log n )

Voici mon implémentation fibonacci en utilisant le langage de programmation rapide:

struct Mat {
    var m00: Int
    var m01: Int
    var m10: Int
    var m11: Int
}

func pow(m: Mat, n: Int) -> Mat {
    guard n > 1 else { return m }
    let temp = pow(m: m, n: n/2)

    var result = matMultiply(a: temp, b: temp)
    if n%2 != 0 {
        result = matMultiply(a: result, b: Mat(m00: 1, m01: 1, m10: 1, m11: 0))
    }
    return result
}

func matMultiply(a: Mat, b: Mat) -> Mat {
    let m00 = a.m00 * b.m00 + a.m01 * b.m10
    let m01 = a.m00 * b.m01 + a.m01 * b.m11
    let m10 = a.m10 * b.m00 + a.m11 * b.m10
    let m11 = a.m10 * b.m01 + a.m11 * b.m11

    return Mat(m00: m00, m01: m01, m10: m10, m11: m11)
}

func fibonacciFast(n: Int) -> Int {

    guard n > 0 else { return 0 }
    let m = Mat(m00: 1, m01: 1, m10: 1, m11: 0)

    return pow(m: m, n: n-1).m00
}

Cela a la complexité O (log n). Nous calculons la puissance de Q avec l'exposant n-1 puis nous prenons l'élément m00 qui est Fn + 1 qui à l'exposant de puissance n-1 est exactement le n-ième nombre de Fibonacci que nous voulions.

Une fois que vous avez la fonction fibonacci rapide, vous pouvez itérer à partir du numéro de début et du numéro de fin pour obtenir la partie de la séquence de Fibonacci qui vous intéresse.

let sequence = (start...end).map(fibonacciFast)

bien sûr, effectuez d'abord quelques vérifications au début et à la fin pour vous assurer qu'ils peuvent former une plage valide.

Je sais que la question a 8 ans, mais je me suis quand même amusé à y répondre. :)

La suite de Fibonacci est la suivante : 1, 1, 2, 3, 5, 8, ....

C'est f(1) = 1, f(2) = 1, f(3) = 2, ..., f(n) = f(n-1) + f(n-2).

Ma mise en œuvre préférée (la plus simple et pourtant atteint une vitesse de la lumière par rapport aux autres implémentations) est la suivante:

def fibonacci(n):
    a, b = 0, 1
    for _ in range(1, n):
        a, b = b, a + b
    return b

Tester

>>> [fibonacci(i) for i in range(1, 10)]
[1, 1, 2, 3, 5, 8, 13, 21, 34]

Horaire

>>> %%time
>>> fibonacci(100**3)
CPU times: user 9.65 s, sys: 9.44 ms, total: 9.66 s
Wall time: 9.66 s

Edit: un exemple de visualisation pour ces implémentations.

utiliser la récursivité:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
x=input('which fibonnaci do you want?')
print fib(x)

Une autre façon de faire:

a,n=[0,1],10
map(lambda i: reduce(lambda x,y: a.append(x+y),a[-2:]),range(n-2))

Assigner une liste à 'a', assigner un entier à 'n' Map et réduire sont 2 des trois fonctions les plus puissantes de python. Ici, la carte sert uniquement à itérer «n-2» fois. a [-2:] obtiendra les deux derniers éléments d'un tableau. a.append (x + y) ajoutera les deux derniers éléments et s'ajoutera au tableau

Tout cela a l'air un peu plus compliqué qu'il ne devrait l'être. Mon code est très simple et rapide:

def fibonacci(x):

    List = []
    f = 1
    List.append(f)
    List.append(f) #because the fibonacci sequence has two 1's at first
    while f<=x:
        f = List[-1] + List[-2]   #says that f = the sum of the last two f's in the series
        List.append(f)
    else:
        List.remove(List[-1])  #because the code lists the fibonacci number one past x. Not necessary, but defines the code better
        for i in range(0, len(List)):
        print List[i]  #prints it in series form instead of list form. Also not necessary

OK .. après avoir été fatigué de faire référence à toutes les longues réponses, trouvez maintenant le moyen ci-dessous pour implémenter Fibonacci en python. Vous pouvez l'améliorer comme vous le souhaitez en obtenant un argument ou en obtenant une entrée de l'utilisateur… ou en modifiant les limites de 10000. Selon vos besoins ……

def fibonacci():
    start = 0 
    i = 1 
    lt = []
    lt.append(start)
    while start < 10000:
        start += i
        lt.append(start)
        i = sum(lt[-2:])
        lt.append(i)
    print "The Fibonaccii series: ", lt

Cette approche fonctionne également bien. Trouvez les analyses d'analyse ci-dessous

In [10]: %timeit fibonacci
10000000 loops, best of 3: 26.3 ns per loop

c'est une amélioration de la réponse de mathew henry:

def fib(n):
    a = 0
    b = 1
    for i in range(1,n+1):
            c = a + b
            print b
            a = b
            b = c

le code doit imprimer b au lieu d'imprimer c

sortie: 1,1,2,3,5 ....

Utiliser la boucle for et n'imprimer que le résultat

def fib(n:'upto n number')->int:
    if n==0:
        return 0
    elif n==1:
        return 1
    a=0
    b=1
    for i in range(0,n-1):
        b=a+b
        a=b-a
    return b

Résultat

>>>fib(50)
12586269025
>>>>
>>> fib(100)
354224848179261915075
>>> 

Imprimer le listcontenant tous les nombres

def fib(n:'upto n number')->int:
    l=[0,1]
    if n==0:
        return l[0]
    elif n==1:
        return l
    a=0
    b=1
    for i in range(0,n-1):
        b=a+b
        a=b-a
        l.append(b)
    return l

Résultat

>>> fib(10)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

import time
start_time = time.time()



#recursive solution
def fib(x, y, upperLimit):
    return [x] + fib(y, (x+y), upperLimit) if x < upperLimit else [x]

#To test :

print(fib(0,1,40000000000000))
print("run time: " + str(time.time() - start_time))

Résultats

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368 , 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 4334944320773, 701 , 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052789597512803, 2504730781961, 4052794587512803, 6542897597512883, 6528975965920881,

temps d'exécution: 0.04298138618469238

il existe une méthode très simple pour s'en rendre compte!

vous pouvez exécuter ce code en ligne librement en utilisant http://www.learnpython.org/

# Set the variable brian on line 3!

def fib(n):
"""This is documentation string for function. It'll be available by fib.__doc__()
Return a list containing the Fibonacci series up to n."""
result = []
a = 0
b = 1
while a < n:
    result.append(a)  # 0 1 1 2 3 5  8  (13) break
    tmp_var = b       # 1 1 2 3 5 8  13
    b = a + b         # 1 2 3 5 8 13 21
    a = tmp_var       # 1 1 2 3 5 8  13
    # print(a)
return result

print(fib(10))
# result should be this: [0, 1, 1, 2, 3, 5, 8]

Cela peut être fait de la manière suivante.

n = 0

nombres = [0]

pour i dans la plage (0,11):
    imprimer n,
    nombres.append (n)
    prev = nombres [-2]
    si n == 0:
        n = 1
    autre:
        n = n + précédent

Juste pour le plaisir, dans Python 3.8+, vous pouvez utiliser une expression d'assignation (alias l'opérateur morse) dans une compréhension de liste, par exemple:

>>> a, b = 0, 1
>>> [a, b] + [b := a + (a := b) for _ in range(8)]  # first 10 Fibonacci numbers
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Une expression d'affectation vous permet d'attribuer une valeur à une variable et de la renvoyer dans la même expression. Par conséquent, l'expression

b := a + (a := b)

équivaut à exécuter

a, b = b, a + b

et renvoyer la valeur de b.

15 minutes après le début d'un tutoriel que j'ai utilisé lors de l'apprentissage de Python, il a demandé au lecteur d'écrire un programme qui calculerait une séquence de Fibonacci à partir de 3 nombres d'entrée (premier numéro de Fibonacci, deuxième numéro et numéro auquel arrêter la séquence). Le tutoriel n'avait couvert que les variables, if / thens, et les boucles jusqu'à ce point. Pas encore de fonctions. J'ai trouvé le code suivant:

sum = 0
endingnumber = 1                

print "\n.:Fibonacci sequence:.\n"

firstnumber = input("Enter the first number: ")
secondnumber = input("Enter the second number: ")
endingnumber = input("Enter the number to stop at: ")

if secondnumber < firstnumber:

    print "\nSecond number must be bigger than the first number!!!\n"

else:

while sum <= endingnumber:

    print firstnumber

    if secondnumber > endingnumber:

        break

    else:

        print secondnumber
        sum = firstnumber + secondnumber
        firstnumber = sum
        secondnumber = secondnumber + sum

Comme vous pouvez le voir, c'est vraiment inefficace, mais cela fonctionne.

def fib():
    a,b = 1,1
    num=eval(input("Please input what Fib number you want to be calculated: "))
    num_int=int(num-2)
    for i in range (num_int):
        a,b=b,a+b
    print(b)

Je viens de passer par http://projecteuler.net/problem=2, c'était mon point de vue

# Even Fibonacci numbers
# Problem 2

def get_fibonacci(size):
    numbers = [1,2]
    while size > len(numbers):
        next_fibonacci = numbers[-1]+numbers[-2]
        numbers.append(next_fibonacci)

    print numbers

get_fibonacci(20)

def fib(x, y, n):
    if n < 1: 
        return x, y, n
    else: 
        return fib(y, x + y, n - 1)

print fib(0, 1, 4)
(3, 5, 0)

#
def fib(x, y, n):
    if n > 1:
        for item in fib(y, x + y, n - 1):
            yield item
    yield x, y, n

f = fib(0, 1, 12)
f.next()
(89, 144, 1)
f.next()[0]
55

Peut-être que cela aidera

def fibo(n):
    result = []
    a, b = 0, 1
    while b < n:
            result.append(b)
            a, b = b, b + a
    return result

basé sur la séquence classique de fibonacci et juste pour le plaisir des one-liners

si vous avez juste besoin du numéro de l'index, vous pouvez utiliser la réduction (même si réduire ce n'est pas le mieux adapté pour cela, cela peut être un bon exercice)

def fibonacci(index):
    return reduce(lambda r,v: r.append(r[-1]+r[-2]) or (r.pop(0) and 0) or r , xrange(index), [0, 1])[1]

et pour obtenir le tableau complet, supprimez simplement ou (r.pop (0) et 0)

reduce(lambda r,v: r.append(r[-1]+r[-2]) or r , xrange(last_index), [0, 1])

Celui-ci, ça va? Je suppose que ce n'est pas aussi sophistiqué que les autres suggestions car cela nécessite la spécification initiale du résultat précédent pour produire la sortie attendue, mais je pense que c'est une option très lisible, c'est-à-dire que tout ce qu'elle fait est de fournir le résultat et le résultat précédent à la récursivité.

#count the number of recursions
num_rec = 0

def fibonacci(num, prev, num_rec, cycles):

    num_rec = num_rec + 1

    if num == 0 and prev == 0:
        result  = 0;
        num = 1;
    else:
        result = num + prev

    print(result)

    if num_rec == cycles:
        print("done")
    else:
        fibonacci(result, num, num_rec, cycles)

#Run the fibonacci function 10 times
fibonacci(0, 0, num_rec, 10)

Voici le résultat:

0
1
1
2
3
5
8
13
21
34
done

Fondamentalement traduit de Ruby:

def fib(n):
    a = 0
    b = 1
    for i in range(1,n+1):
            c = a + b
            print c
            a = b
            b = c

...

def fib(lowerbound, upperbound):
    x = 0
    y = 1
    while x <= upperbound:
        if (x >= lowerbound):
            yield x
        x, y = y, x + y

startNumber = 10
endNumber = 100
for fib_sequence in fib(startNumber, endNumber):
    print "And the next number is... %d!" % fib_sequence

Une explication plus détaillée du fonctionnement de la mémorisation pour la séquence de Fibonacci.

# Fibonacci sequence Memoization

fib_cache = {0:0, 1:1}

def fibonacci(n):
    if n < 0:
        return -1
    if fib_cache.has_key(n):
        print "Fibonacci sequence for %d = %d cached" % (n, fib_cache[n])
        return fib_cache[n]
    else:
        fib_cache[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return fib_cache[n]

if __name__ == "__main__":
    print fibonacci(6)
    print fib_cache
    # fibonacci(7) reuses fibonacci(6) and fibonacci(5)
    print fibonacci(7)
    print fib_cache

J'essayais d'éviter une fonction récursive pour résoudre ce problème, j'ai donc adopté une approche itérative. Je faisais à l'origine une fonction récursive mémorisée mais j'ai continué à atteindre une profondeur récursive maximale. J'avais également des objectifs de mémoire stricts, donc vous me verrez garder le tableau aussi petit que possible pendant le processus de boucle en ne gardant que 2-3 valeurs dans le tableau à tout moment.

def fib(n):
    fibs = [1, 1] # my starting array
    for f in range(2, n):
        fibs.append(fibs[-1] + fibs[-2]) # appending the new fib number
        del fibs[0] # removing the oldest number
    return fibs[-1] # returning the newest fib

print(fib(6000000))

Obtenir le 6 millionième numéro de fibonacci prend environ 282 secondes sur ma machine tandis que le 600k fibonacci ne prend que 2,8 secondes. Je n'ai pas pu obtenir d'aussi grands nombres de fibonacci avec une fonction récursive, même mémorisée.