Wie schreibe ich die Fibonacci-Sequenz?

140

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.

SD.
quelle

Antworten:

257

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:

Fibonacci aus Wikipedia

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

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

Fibonacci-Gleichung

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ß!

Andrea Ambu
quelle
1
Sie müssen eine while-Schleife verwenden, keine Zuordnung. Versuchen Sie es selbst herauszufinden und kommen Sie dann mit dem Code zurück, wenn Sie es nicht können. Ich bin nicht faul (der Code ist kürzer als dieser Kommentar). Ich mache das für dich, probiere es mit dem "while" -Hinweis aus;) Wenn du ein Problem damit hast, komm wieder zurück;)
Andrea Ambu
Ich bin zurück, lol. Ich habe die Map (Range) -Funktion entfernt und verwende nur eine Range (StartNumber, EndNumber) -Funktion. Jetzt habe ich das Problem, wo ich die while-Anweisung verwenden soll. Ich versuche es am Anfang der Funktion, aber natürlich gibt es eine Rechnung und eine Fehlerzeile. Wo soll ich es hinstellen? Thx
SD.
Versuchen Sie, von Hand ein Beispiel für die Eingabe / Ausgabe Ihres Programms (mit kurzer Reichweite) zu erstellen. Versuchen Sie dann herauszufinden, wo Ihr Programm falsch ist. Versuchen Sie, die "by-hand-Methode" in Code umzuwandeln. Dies ist für Übung, um zu lernen. Ich könnte zwei Codezeilen aufschreiben, aber ich glaube nicht, dass Sie etwas daraus lernen werden.
Andrea Ambu
1
Wir sollten int(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5)))irgendwelche Ideen verwenden? @AndreaAmbu
lord63. j
3
@ lord63.j, Sie sollten diese Formel nur verwenden, wenn Sie wissen, dass sie vom tatsächlichen Wert abweicht, wenn sie nüber 70 liegt, und mit einem OverflowError Zeitpunkt explodiert, der netwas über 600 liegt. Andere Ansätze können eine nvon 1000 oder mehr verarbeiten, ohne zu blasen Präzision verlieren oder verlieren.
CDLAN
66

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
Aaron Hall
quelle
Über die letzte Option "Mach das nicht" verstehe ich nicht, warum es sich vor setdefault selbst aufrufen würde. Soll setdefault den Wert nicht zurückgeben, wenn n ein gültiger Schlüssel ist? Doc sagt: "Wenn sich der Schlüssel im Wörterbuch befindet, geben Sie seinen Wert zurück. Wenn nicht, fügen Sie den Schlüssel mit dem Standardwert ein und geben Sie den Standardwert zurück. Der Standardwert ist" Keine "." Was vermisse ich ?
Binithb
@binithb Der Ausdruck innerhalb des setdefaultAufrufs wird ausgewertet, bevor setdefault is.
Aaron Hall
23

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))
Thomas Spycher
quelle
21

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.

James Thompson
quelle
Dies ist kein Hausaufgabenproblem, aber wow, danke für die Antwort! Ich verstehe, was ich tun muss, aber das Starten und Implementieren ist das, woran ich jetzt festhalte (insbesondere beim Implementieren von Benutzereingabewerten). Können Sie einen Einblick geben? Ich erhalte immer wieder den Fehler <function fib at 0x0141FAF0>.
SD.
Ich verstehe, dass Sie sich sehr bemühen, ein Programm zu implementieren, das möglicherweise über Ihre derzeitigen Fähigkeiten hinausgeht. Es hilft Ihnen nicht, wenn ich mehr Code schreibe. Sie sollten versuchen, mit meinem Code herumzuhacken, bis er funktioniert, und weitere Python-Tutorials lesen. Leerzeichen können ein Problem sein, aber ich kenne diesen Fehler nicht.
James Thompson
Ich verstehe. Gibt es eine andere Idee, von der du denkst, dass ich vermisst werde? Ich verstehe, wenn Sie jedoch nicht helfen können. Ich danke Ihnen für Ihre Zeit.
SD.
Ihr Fehler <function fib at 0x0141FAF0> kann das Ergebnis von "fib" (das sich auf die Funktion selbst bezieht) anstelle von "fib ()" sein, das die Funktion aufruft. Viel Glück.
Kiv
8
Denken Sie daran, dass diese naive rekursive Methode zur Berechnung von Fibonacci-Zahlen sehr schnell in einen Stapelüberlauf (nicht die Site) geraten kann. Generieren Sie aus praktischen Gründen iterativ oder verwenden Sie eine Art Memo oder ähnliches.
David Thornley
12

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:

Geben Sie hier die Bildbeschreibung ein

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()
Akash Rana
quelle
9

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]
Paul Hankin
quelle
1
Die erste und dritte Technik sind gut. Die zweite Technik ist um 1 versetzt; es muss effektiv n -= 1richtig funktionieren und es funktioniert auch nicht mit n = 0. Auf jeden Fall würde es mir wirklich helfen, wenn viel Kontext hinzugefügt würde, um zu erklären, wie diese funktionieren, insbesondere die erste Technik. Ich sehe, Sie haben einen Beitrag bei paulhankin.github.io/Fibonacci
Acumenus
6

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
DaVinci
quelle
4

Wir wissen das

Geben Sie hier die Bildbeschreibung ein

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

Geben Sie hier die Bildbeschreibung ein

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

Geben Sie hier die Bildbeschreibung ein

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

Giuseppe Lanza
quelle
3

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.

Aziz Alto
quelle
3

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)
user2095044
quelle
2

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

sanooj
quelle
1

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
Timmy
quelle
2
Dynamische Programmierung FTW! Fibonacci (100000000000000000000000000000000000000000000000000000000000000000000000000) reagiert fast sofort
Hans
6
Irgendwie bezweifle ich es.
Lanaru
Was ist mit dem Starten der Liste als [0, 1] (dh List.append (0); List.append (1)), um den Befehl remove nach dem else zu vermeiden? ... und die Fibonacci-Zahl sollte besser indiziert werden, da Fibonacci (10) die Fibonacci-Zahlen unter 10 zurückgibt, nicht die 10-te.
SeF
1

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
Haroon Rashedu
quelle
1

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

Adongo
quelle
1

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]
R__raki__
quelle
1
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

Nathan Rogers
quelle
1

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]
xgqfrms
quelle
Eine einfache Möglichkeit, Fibonacci-Serien nur mit dem Iterator ohne komplexe Rekursionsdatenstruktur zu realisieren!
xgqfrms
1

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
J. Jai
quelle
1

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.

Eugene Yarmash
quelle
0

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.

Jonas
quelle
0
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)
AlexB
quelle
3
eval(input())wird hier nicht benötigt; Ich denke int(input())in dem Fall ist besser.
GingerPlusPlus
0

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)
Dateityp
quelle
0
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
jdsantiagojr
quelle
0

Vielleicht hilft das

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

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])
Kadmillos
quelle
0

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
the_marcelo_r
quelle
0

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

...

Matthew Smith
quelle
0
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
JayL
quelle
0

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
Sysuser
quelle
0

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.

Jared Mackey
quelle