Ich hatte das Programm ursprünglich falsch codiert. Anstatt die Fibonacci-Zahlen zwischen einem Bereich zurückzugeben (dh startNumber 1, endNumber 20 sollte = nur die Zahlen zwischen 1 und 20 sein), habe ich für das Programm geschrieben, dass alle Fibonacci-Zahlen zwischen einem Bereich angezeigt werden (dh startNumber 1, endNumber 20) Anzeigen = Erste 20 Fibonacci-Zahlen). Ich dachte, ich hätte einen sicheren Code. Ich verstehe auch nicht, warum das passiert.

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

Jemand wies in meinem Teil II (der geschlossen wurde, weil er ein Duplikat war - /programming/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii ) darauf hin, dass ich StartNumber und EndNumber müssen mithilfe einer while-Schleife durch einen Generator geleitet werden. Kann mir bitte jemand die Richtung zeigen, wie das geht? Jede Hilfe ist willkommen.

Ich bin ein lernender Programmierer und bin ein bisschen durcheinander geraten. Ich werde gebeten, ein Programm zu schreiben, das die Fibonacci-Sequenz anhand einer vom Benutzer eingegebenen Start- und Endnummer berechnet und anzeigt (dh startNumber = 20 endNumber = 100 und nur die Zahlen zwischen diesem Bereich anzeigt). Der Trick besteht darin, es inklusiv zu verwenden (was ich in Python nicht weiß? - Ich gehe davon aus, dass dies bedeutet, einen inklusiven Bereich zu verwenden?).

Was ich bisher habe, ist keine eigentliche Codierung, sondern:

• Schreiben Sie die Fib-Sequenzformel auf unendlich
• Zeigen Sie startNumber bis endNumber nur aus der Fib-Sequenz an.

Ich habe keine Ahnung, wo ich anfangen soll, und ich frage nach Ideen oder Einsichten, wie ich das schreiben soll. Ich habe auch versucht, das Fib-Sequenzforum zu schreiben, aber ich verliere mich auch darin.

Es gibt viele Informationen über die Fibonacci-Sequenz auf Wikipedia und auf Wolfram . Viel mehr als Sie vielleicht brauchen. Auf jeden Fall ist es eine gute Sache zu lernen, wie man diese Ressourcen verwendet, um (wenn möglich schnell) zu finden, was Sie brauchen.

Schreiben Sie die Fib-Sequenzformel auf unendlich

In der Mathematik wird es in rekursiver Form angegeben:

In der Programmierung existiert unendlich nicht. Sie können ein rekursives Formular verwenden, das das mathematische Formular direkt in Ihre Sprache übersetzt. In Python wird es beispielsweise zu:

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

Probieren Sie es in Ihrer Lieblingssprache aus und stellen Sie fest, dass dieses Formular viel Zeit benötigt, wenn n größer wird. Tatsächlich ist dies zeitlich O (2 ⁿ ).

Gehen Sie auf die Websites, die ich mit Ihnen verlinkt habe, und sehen Sie dies (auf Wolfram ):

Dieser ist in Python ziemlich einfach zu implementieren und sehr, sehr schnell zu berechnen:

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

Eine andere Möglichkeit besteht darin, der Definition (aus Wikipedia ) zu folgen :

Die erste Nummer der Sequenz ist 0, die zweite Nummer ist 1 und jede nachfolgende Nummer ist gleich der Summe der beiden vorherigen Nummern der Sequenz selbst, was die Sequenz 0, 1, 1, 2, 3, 5, 8 ergibt , etc.

Wenn Ihre Sprache Iteratoren unterstützt, können Sie Folgendes tun:

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

Zeigen Sie startNumber bis endNumber nur aus der Fib-Sequenz an.

Sobald Sie wissen, wie man Fibonacci-Zahlen generiert, müssen Sie nur noch die Zahlen durchlaufen und prüfen, ob sie die angegebenen Bedingungen bestätigen.

Angenommen, Sie haben jetzt af (n) geschrieben, das den n-ten Term der Fibonacci-Sequenz zurückgibt (wie den mit sqrt (5)).

In den meisten Sprachen können Sie Folgendes tun:

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

In Python würde ich das Iteratorformular verwenden und mich für Folgendes entscheiden:

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

Mein Tipp ist zu lernen, zu lesen, was Sie brauchen. Project Euler (google for it) schult Sie dazu: P Viel Glück und viel Spaß!

Effizienter Pythonic-Generator der Fibonacci-Sequenz

Ich habe diese Frage gefunden, als ich versucht habe, die kürzeste Pythonic-Generation dieser Sequenz zu erhalten (später wurde mir klar, dass ich eine ähnliche in einem Python-Verbesserungsvorschlag gesehen hatte ), und ich habe nicht bemerkt, dass jemand anderes meine spezifische Lösung gefunden hat (obwohl die beste Antwort kommt näher, aber immer noch weniger elegant), also hier mit Kommentaren, die die erste Iteration beschreiben, weil ich denke, dass dies den Lesern helfen kann, Folgendes zu verstehen:

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)

und Verwendung:

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

Drucke:

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

(Zu Attributionszwecken habe ich kürzlich eine ähnliche Implementierung in der Python-Dokumentation zu Modulen festgestellt , sogar unter Verwendung der Variablen aund b, die ich jetzt vor dem Schreiben dieser Antwort gesehen habe. Ich denke jedoch, dass diese Antwort eine bessere Verwendung der Sprache demonstriert.)

Rekursiv definierte Implementierung

Die Online-Enzyklopädie ganzzahliger Sequenzen definiert die Fibonacci-Sequenz rekursiv als

F (n) = F (n-1) + F (n-2) mit F (0) = 0 und F (1) = 1

Die prägnante Definition in Python kann wie folgt erfolgen:

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

Diese genaue Darstellung der mathematischen Definition ist jedoch für Zahlen, die viel größer als 30 sind, unglaublich ineffizient, da jede zu berechnende Zahl auch für jede darunter liegende Zahl berechnet werden muss. Sie können anhand der folgenden Methoden demonstrieren, wie langsam es ist:

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

Gespeicherte Rekursion für Effizienz

Es kann zur Verbesserung der Geschwindigkeit gespeichert werden (in diesem Beispiel wird die Tatsache ausgenutzt, dass ein Standardschlüsselwortargument bei jedem Aufruf der Funktion dasselbe Objekt ist, aber normalerweise würden Sie aus genau diesem Grund kein veränderbares Standardargument verwenden):

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

Sie werden feststellen, dass die gespeicherte Version viel schneller ist und Ihre maximale Rekursionstiefe schnell überschreitet, bevor Sie überhaupt daran denken können, auf einen Kaffee aufzustehen. Sie können sehen, wie viel schneller es visuell ist, indem Sie dies tun:

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

(Es mag so aussehen, als könnten wir nur das Folgende tun, aber es lässt uns den Cache nicht nutzen, da er sich selbst aufruft, bevor setdefault aufgerufen wird.)

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

Rekursiv definierter Generator:

Als ich Haskell gelernt habe, bin ich in Haskell auf diese Implementierung gestoßen:

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

Das, was ich momentan in Python am ehesten erreichen kann, ist:

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

Dies zeigt es:

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

Es kann jedoch nur bis zur Rekursionsgrenze gehen. Normalerweise 1000, während die Haskell-Version bis zu 100 Millionen erreichen kann, obwohl sie alle 8 GB des Speichers meines Laptops verwendet, um dies zu tun:

> length $ take 100000000 fib 
100000000

Den Iterator verbrauchen, um die n-te Fibonacci-Zahl zu erhalten

Ein Kommentator fragt:

Frage für die Fib () -Funktion, die auf dem Iterator basiert: Was ist, wenn Sie die n-te, zum Beispiel die 10. Fib-Nummer erhalten möchten?

Die itertools-Dokumentation enthält ein Rezept dafür:

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)

und nun:

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

Warum nicht einfach folgendes tun?

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

Die Idee hinter der Fibonacci-Sequenz wird im folgenden Python-Code gezeigt:

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

Dies bedeutet, dass fib eine Funktion ist, die eines von drei Dingen ausführen kann. Es definiert fib (1) == 1, fib (0) == 0 und fib (n) als:

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

Wobei n eine beliebige ganze Zahl ist. Dies bedeutet, dass beispielsweise fib (2) auf die folgende Arithmetik erweitert wird:

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

Wir können fib (3) auf die gleiche Weise mit der unten gezeigten Arithmetik berechnen:

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

Das Wichtigste dabei ist, dass fib (3) nicht ohne Berechnung von fib (2) berechnet werden kann, was durch Kenntnis der Definitionen von fib (1) und fib (0) berechnet wird. Ein Funktionsaufruf selbst wie die Fibonacci-Funktion wird als Rekursion bezeichnet und ist ein wichtiges Thema bei der Programmierung.

Das klingt nach einer Hausaufgabe, also werde ich den Start- / Endteil nicht für Sie erledigen. Python ist jedoch eine wunderbar ausdrucksstarke Sprache, daher sollte dies sinnvoll sein, wenn Sie Mathematik verstehen, und Sie hoffentlich über Rekursion unterrichten. Viel Glück!

Bearbeiten: Ein möglicher Kritikpunkt an meinem Code ist, dass er nicht die superhandliche Python-Funktionsausbeute verwendet, wodurch die fib (n) -Funktion viel kürzer wird. Mein Beispiel ist allerdings etwas allgemeiner, da nicht viele Sprachen außerhalb von Python tatsächlich Ertrag bringen.

Zeitliche Komplexität:

Die Caching-Funktion reduziert die normale Methode zur Berechnung von Fibonacci-Reihen von O (2 ^ n) auf O (n), indem die Wiederholungen im rekursiven Baum der Fibonacci-Reihen eliminiert werden:

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()

Dies ist sehr effizient, wenn O (log n) grundlegende arithmetische Operationen verwendet werden.

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

Dieser verwendet O (1) grundlegende arithmetische Operationen, aber die Größe der Zwischenergebnisse ist groß und daher überhaupt nicht effizient.

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

Dieser berechnet X ^ n im Polynomring Z [X] / (X ^ 2 - X - 1) unter Verwendung der Potenzierung durch Quadrieren. Das Ergebnis dieser Berechnung ist das Polynom Fib (n) X + Fib (n-1), aus dem die n-te Fibonacci-Zahl abgelesen werden kann.

Auch dies verwendet O (log n) arithmetische Operationen und ist sehr effizient.

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]

Kanonischer Python-Code zum Drucken der Fibonacci-Sequenz:

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

Für das Problem "Drucken Sie die erste Fibonacci-Zahl mit mehr als 1000 Stellen":

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

Wir wissen das

Und dass die n-te Potenz dieser Matrix uns gibt:

Wir können also eine Funktion implementieren, die einfach die Potenz dieser Matrix zur n-ten -1-Potenz berechnet.

nach allem, was wir wissen, ist die Kraft a ^ n gleich

Am Ende wäre die Fibonacci-Funktion also O (n) ... nichts wirklich anderes als eine einfachere Implementierung, wenn wir das nicht auch wissen x^n * x^n = x^2nund die Bewertung von x^ndaher mit der Komplexität O (log n) erfolgen kann )

Hier ist meine Fibonacci-Implementierung mit einer schnellen Programmiersprache:

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
}

Dies hat die Komplexität O (log n). Wir berechnen die Potenz von Q mit dem Exponenten n-1 und nehmen dann das Element m00, das Fn + 1 ist und am Leistungsexponenten n-1 genau die n-te Fibonacci-Zahl ist, die wir wollten.

Sobald Sie die schnelle Fibonacci-Funktion haben, können Sie von Startnummer und Endnummer iterieren, um den Teil der Fibonacci-Sequenz zu erhalten, an dem Sie interessiert sind.

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

Führen Sie natürlich zuerst eine Überprüfung von Anfang und Ende durch, um sicherzustellen, dass sie einen gültigen Bereich bilden können.

Ich weiß, dass die Frage 8 Jahre alt ist, aber ich hatte trotzdem Spaß beim Beantworten. :) :)

Die Fibonacci-Sequenz lautet : 1, 1, 2, 3, 5, 8, ....

Das heißt f(1) = 1, f(2) = 1, f(3) = 2, ..., f(n) = f(n-1) + f(n-2).

Meine Lieblingsimplementierung (am einfachsten und erreicht dennoch eine Lichtgeschwindigkeit im Vergleich zu anderen Implementierungen) ist folgende:

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

Prüfung

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

Zeitliche Koordinierung

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

Bearbeiten: Eine Beispielvisualisierung für diese Implementierungen.

Rekursion verwenden:

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)

Ein anderer Weg, es zu tun:

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

Das Zuweisen einer Liste zu 'a', das Zuweisen einer Ganzzahl zu 'n' Map und Reduzieren sind zwei der drei leistungsstärksten Funktionen in Python. Hier wird die Karte nur verwendet, um 'n-2' Mal zu iterieren. a [-2:] erhält die letzten beiden Elemente eines Arrays. a.append (x + y) fügt die letzten beiden Elemente hinzu und hängt an das Array an

Diese sehen alle etwas komplizierter aus, als sie sein müssen. Mein Code ist sehr einfach und schnell:

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 .. Nachdem Sie es satt haben, alle langwierigen Antworten zu lesen, finden Sie jetzt die folgende sort & süße, ziemlich einfache Möglichkeit, Fibonacci in Python zu implementieren. Sie können es nach Ihren Wünschen verbessern, indem Sie ein Argument oder Benutzereingaben abrufen… oder die Grenzwerte von 10000 ändern. Nach Bedarf ……

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

Dieser Ansatz funktioniert auch gut. Hier finden Sie die Laufanalyse

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

Dies ist eine Verbesserung der Antwort von 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

Der Code sollte b anstatt c drucken

Ausgabe: 1,1,2,3,5 ....

Verwenden Sie for-Schleife und drucken Sie nur das Ergebnis

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

Ergebnis

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

Drucken Sie die listmit allen Zahlen

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

Ergebnis

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

Ergebnisse

[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, 43349443, 731807 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 40527380377807

Laufzeit: 0.04298138618469238

Es gibt eine sehr einfache Methode, um das zu realisieren!

Sie können diesen Code online frei ausführen, indem Sie http://www.learnpython.org/ verwenden.

# 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]

Dies kann folgendermaßen erfolgen.

n = 0

Zahlen = [0]

für i im Bereich (0,11):
    print n,
    numbers.append (n)
    prev = Zahlen [-2]
    wenn n == 0:
        n = 1
    sonst:
        n = n + prev

Nur zum Spaß können Sie in Python 3.8+ einen Zuweisungsausdruck (auch bekannt als Walross-Operator) in einem Listenverständnis verwenden, z.

>>> 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]

Mit einem Zuweisungsausdruck können Sie einer Variablen einen Wert zuweisen und ihn im selben Ausdruck zurückgeben. Daher der Ausdruck

b := a + (a := b)

entspricht der Ausführung

a, b = b, a + b

und Rückgabe des Wertes von b.

15 Minuten nach Beginn eines Tutorials, das ich beim Erlernen von Python verwendet habe, wurde der Leser gebeten, ein Programm zu schreiben, das eine Fibonacci-Sequenz aus 3 Eingabenummern berechnet (erste Fibonacci-Nummer, zweite Nummer und Nummer, an der die Sequenz gestoppt werden soll). Das Tutorial hatte nur Variablen behandelt, wenn / dann und Schleifen bis zu diesem Punkt. Noch keine Funktionen. Ich habe mir den folgenden Code ausgedacht:

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

Wie Sie sehen können, ist es wirklich ineffizient, aber es funktioniert.

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)

Ich habe gerade http://projecteuler.net/problem=2 durchgesehen, das war meine Meinung dazu

# 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

Vielleicht hilft das

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

basierend auf der klassischen Fibonacci-Sequenz und nur zum Wohle der Einzeiler

Wenn Sie nur die Nummer des Index benötigen, können Sie die Reduzierung verwenden (auch wenn die Reduzierung nicht am besten dafür geeignet ist, kann dies eine gute Übung sein).

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]

und um das komplette Array zu erhalten, entfernen Sie einfach das oder (r.pop (0) und 0)

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

Wie wäre es mit diesem? Ich denke, es ist nicht so ausgefallen wie die anderen Vorschläge, da es die anfängliche Spezifikation des vorherigen Ergebnisses erfordert, um die erwartete Ausgabe zu erzeugen, aber ich denke, es ist eine sehr lesbare Option, dh alles, was es tut, ist, das Ergebnis und das vorherige Ergebnis bereitzustellen die Rekursion.

#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)

Hier ist die Ausgabe:

0
1
1
2
3
5
8
13
21
34
done

Grundsätzlich übersetzt aus 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

Eine detailliertere Erklärung, wie Memoization für die Fibonacci-Sequenz funktioniert.

# 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

Ich habe versucht, eine rekursive Funktion zu vermeiden, um dieses Problem zu lösen, und habe daher einen iterativen Ansatz gewählt. Ich habe ursprünglich eine auswendig gelernte rekursive Funktion ausgeführt, aber immer wieder die maximale rekursive Tiefe erreicht. Ich hatte auch strenge Speicherziele, so dass Sie sehen werden, dass ich das Array während des Schleifenprozesses so klein wie möglich halte und immer nur 2-3 Werte im Array habe.

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

Das Erhalten der 6-millionsten Fibonacci-Zahl dauert auf meinem Computer ungefähr 282 Sekunden, während der 600k-Fibonacci nur 2,8 Sekunden dauert. Ich war nicht in der Lage, so große Fibonacci-Zahlen mit einer rekursiven Funktion zu erhalten, selbst einer auswendig gelernten.