wake-up-neo.com

Effiziente Berechnung der Fibonacci-Serie

Ich arbeite an einem Project Euler Problem: das über die Summe der geraden Fibonacci-Zahlen. 

Mein Code:

def Fibonacci(n):
    if n == 0:
        return 0
    Elif n == 1:
        return 1
    else:
        return Fibonacci(n-1) + Fibonacci(n-2)

list1 = [x for x in range(39)]
list2 = [i for i in list1 if Fibonacci(i) % 2 == 0]

Die Lösung des Problems kann leicht durch Drucken der Summe (list2) gefunden werden. Es dauert jedoch viel Zeit, um mit der Liste2 zu kommen, schätze ich. Gibt es eine Möglichkeit, dies schneller zu machen? Oder ist es auch so in Ordnung ... 

(das Problem: Durch die Berücksichtigung der Terme in der Fibonacci-Sequenz, deren Werte vier Millionen nicht überschreiten, ermitteln Sie die Summe der geradzahligen Terme.) 

34
user65165

Ja. Die primitive rekursive Lösung benötigt viel Zeit. Der Grund dafür ist, dass für jede berechnete Zahl alle vorherigen Zahlen mehr als einmal berechnet werden müssen. Schauen Sie sich das folgende Bild an.

Tree representing fibonacci calculation

Es repräsentiert das Berechnen von Fibonacci(5) mit Ihrer Funktion. Wie Sie sehen, wird der Wert von Fibonacci(2) dreimal und der Wert von Fibonacci(1) fünfmal berechnet. Das wird immer schlimmer, je höher die Zahl ist, die Sie berechnen möchten.

Was macht es gerade schlimmer ist, dass Sie mit jeder Fibonacci-Zahl, die Sie in Ihrer Liste berechnen, nicht die vorherigen Zahlen verwenden, die Sie kennen, um die Berechnung zu beschleunigen - Sie berechnen jede Zahl "von Grund auf neu". "

Es gibt einige Möglichkeiten, dies zu beschleunigen:


1. Erstellen Sie eine Liste "von unten nach oben"

Am einfachsten ist es, eine Liste mit Fibonacci-Zahlen zu erstellen, bis zu der von Ihnen gewünschten Zahl. Wenn du das tust, baust du sozusagen "von unten nach oben" und kannst frühere Zahlen wiederverwenden, um die nächste zu erstellen. Wenn Sie eine Liste der Fibonacci-Zahlen [0, 1, 1, 2, 3] haben, können Sie die letzten beiden Zahlen in dieser Liste verwenden, um die nächste Zahl zu erstellen.

Dieser Ansatz würde ungefähr so ​​aussehen:

>>> def fib_to(n):
...     fibs = [0, 1]
...     for i in range(2, n+1):
...         fibs.append(fibs[-1] + fibs[-2])
...     return fibs
...

Dann können Sie die ersten 20 Fibonacci-Zahlen erhalten, indem Sie tun

>>> fib_to(20)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

Oder Sie können die 17. Fibonacci-Zahl von einer Liste der ersten 40 erhalten, indem Sie tun

>>> fib_to(40)[17]
1597

2. Memoisierung (relativ fortgeschrittene Technik)

Es gibt eine andere Alternative, um es schneller zu machen, aber sie ist auch etwas komplizierter. Da Ihr Problem darin besteht, dass Sie bereits berechnete Werte neu berechnen, können Sie stattdessen die bereits berechneten Werte in einem Diktat speichern und versuchen, sie daraus zu erhalten, bevor Sie sie neu berechnen. Dies nennt man Auswendiglernen. Es könnte ungefähr so ​​aussehen:

>>> def fib(n, computed = {0: 0, 1: 1}):
...     if n not in computed:
...         computed[n] = fib(n-1, computed) + fib(n-2, computed)
...     return computed[n]

Auf diese Weise können Sie im Handumdrehen große Fibonacci-Zahlen berechnen:

>>> fib(400)
176023680645013966468226945392411250770384383304492191886725992896575345044216019675

Dies ist in der Tat eine so verbreitete Technik, dass Python 3 einen Dekorateur enthält, der dies für Sie erledigt. Ich präsentiere Ihnen automatische Memoisierung!

import functools

@functools.lru_cache(None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

Dies macht so ziemlich das Gleiche wie die vorherige Funktion, aber mit all den computed Sachen, die vom lru_cache Dekorateur behandelt werden.


3. Einfach hochzählen (eine naive iterative Lösung)

Eine dritte Methode, wie von Mitch vorgeschlagen, ist das einfache Hochzählen, ohne die Zwischenwerte in einer Liste zu speichern. Das könnte man sich vorstellen

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

Ich empfehle diese beiden letzten Methoden nicht, wenn es Ihr Ziel ist, eine Liste von Fibonacci-Zahlen zu erstellen. fib_to(100) wird viel schneller sein als [fib(n) for n in range(101)], weil Sie bei letzterem immer noch das Problem haben, jede Zahl in der Liste von Grund auf neu zu berechnen.

84
kqr

Dies ist ein sehr schneller Algorithmus, der die n-te Fibonacci-Zahl viel schneller finden kann als der einfache iterative Ansatz, der in anderen Antworten dargestellt wird. Er ist jedoch ziemlich fortgeschritten:

def fib(n):
    v1, v2, v3 = 1, 1, 0    # initialise a matrix [[1,1],[1,0]]
    for rec in bin(n)[3:]:  # perform fast exponentiation of the matrix (quickly raise it to the nth power)
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec=='1':    v1, v2, v3 = v1+v2, v1, v2
    return v2

Sie können mehr über die involvierte Mathematik hier erfahren.


43
Piotr Dabkowski

Python optimiert die Schwanzrekursion nicht. Daher schlagen die meisten hier vorgestellten Lösungen mit Error: maximum recursion depth exceeded in comparison fehl, wenn n zu groß ist (und im Großen und Ganzen meine ich 1000).

Das Rekursionslimit kann erhöht werden, aber Python stürzt beim Stapelüberlauf im Betriebssystem ab.

Beachten Sie den Unterschied in der Leistung zwischen fib_memo/fib_local und fib_lru/fib_local_exc: LRU-Cache ist viel langsamer und wurde nicht einmal abgeschlossen, da er bereits für n = ~ 500 einen Laufzeitfehler erzeugt:

import functools
from time import clock
#import sys
#sys.setrecursionlimit()

@functools.lru_cache(None)
def fib_lru(n):
    if n < 2:
        return n
    return fib_lru(n-1) + fib_lru(n-2)

def fib_memo(n, computed = {0: 0, 1: 1}):
    if n not in computed:
        computed[n] = fib_memo(n-1, computed) + fib_memo(n-2, computed)
    return computed[n]

def fib_local(n):
    computed = {0: 0, 1: 1}
    def fib_inner(n):
        if n not in computed:
            computed[n] = fib_inner(n-1) + fib_inner(n-2)
        return computed[n]
    return fib_inner(n)

def fib_local_exc(n):
    computed = {0: 0, 1: 1}
    def fib_inner_x(n):
        try:
            computed[n]
        except KeyError:
            computed[n] = fib_inner_x(n-1) + fib_inner_x(n-2)
        return computed[n]

    return fib_inner_x(n)

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

def benchmark(n, *args):
    print("-" * 80)
    for func in args:
        print(func.__name__)
        start = clock()
        try:
            ret = func(n)
            #print("Result:", ret)
        except RuntimeError as e:
            print("Error:", e)
        print("Time:", "{:.8f}".format(clock() - start))
        print()

benchmark(500, fib_iter, fib_memo, fib_local, fib_local_exc, fib_lru)

Ergebnisse:

fib_iter
Time: 0.00008168

fib_memo
Time: 0.00048622

fib_local
Time: 0.00044645

fib_local_exc
Time: 0.00146036

fib_lru
Error: maximum recursion depth exceeded in comparison
Time: 0.00112552

Die iterative Lösung ist bei weitem die schnellste und beschädigt den Stack selbst für n=100k (0,162 Sekunden) nicht. Es gibt in der Tat nicht die mittleren Fibonacci-Zahlen zurück.

Wenn Sie die nth sogar Fibonacci-Zahl berechnen möchten, können Sie den iterativen Ansatz folgendermaßen anpassen:

def fib_even_iter(n):
    a, b = 0, 1
    c = 1
    while c < n:
        a, b = b, a + b
        if a % 2 == 0:
            c += 1
    return a

Oder wenn Sie sich für jede gerade Zahl auf dem Weg interessieren, verwenden Sie einen Generator :

def fib_even_gen(n):
    a, b = 0, 1
    c = 1
    yield a
    while c < n:
        a, b = b, a + b
        if a % 2 == 0:
            yield a
            c += 1
    return a

for i, f in enumerate(fib_even_gen(100), 1):
    print("{:3d}.  {:d}".format(i, f))

Ergebnis:

  1.  0
  2.  2
  3.  8
  4.  34
  5.  144
  6.  610
  7.  2584
  8.  10946
  9.  46368
 10.  196418
 11.  832040
 12.  3524578
 13.  14930352
 14.  63245986
 15.  267914296
 16.  1134903170
 17.  4807526976
 18.  20365011074
 19.  86267571272
 20.  365435296162
 21.  1548008755920
 22.  6557470319842
 23.  27777890035288
 24.  117669030460994
 25.  498454011879264
 26.  2111485077978050
 27.  8944394323791464
 28.  37889062373143906
 29.  160500643816367088
 30.  679891637638612258
 31.  2880067194370816120
 32.  12200160415121876738
 33.  51680708854858323072
 34.  218922995834555169026
 35.  927372692193078999176
 36.  3928413764606871165730
 37.  16641027750620563662096
 38.  70492524767089125814114
 39.  298611126818977066918552
 40.  1264937032042997393488322
 41.  5358359254990966640871840
 42.  22698374052006863956975682
 43.  96151855463018422468774568
 44.  407305795904080553832073954
 45.  1725375039079340637797070384
 46.  7308805952221443105020355490
 47.  30960598847965113057878492344
 48.  131151201344081895336534324866
 49.  555565404224292694404015791808
 50.  2353412818241252672952597492098
 51.  9969216677189303386214405760200
 52.  42230279526998466217810220532898
 53.  178890334785183168257455287891792
 54.  757791618667731139247631372100066
 55.  3210056809456107725247980776292056
 56.  13598018856492162040239554477268290
 57.  57602132235424755886206198685365216
 58.  244006547798191185585064349218729154
 59.  1033628323428189498226463595560281832
 60.  4378519841510949178490918731459856482
 61.  18547707689471986212190138521399707760
 62.  78569350599398894027251472817058687522
 63.  332825110087067562321196029789634457848
 64.  1409869790947669143312035591975596518914
 65.  5972304273877744135569338397692020533504
 66.  25299086886458645685589389182743678652930
 67.  107168651819712326877926895128666735145224
 68.  453973694165307953197296969697410619233826
 69.  1923063428480944139667114773918309212080528
 70.  8146227408089084511865756065370647467555938
 71.  34507973060837282187130139035400899082304280
 72.  146178119651438213260386312206974243796773058
 73.  619220451666590135228675387863297874269396512
 74.  2623059926317798754175087863660165740874359106
 75.  11111460156937785151929026842503960837766832936
 76.  47068900554068939361891195233676009091941690850
 77.  199387062373213542599493807777207997205533596336
 78.  844617150046923109759866426342507997914076076194
 79.  3577855662560905981638959513147239988861837901112
 80.  15156039800290547036315704478931467953361427680642
 81.  64202014863723094126901777428873111802307548623680
 82.  271964099255182923543922814194423915162591622175362
 83.  1152058411884454788302593034206568772452674037325128
 84.  4880197746793002076754294951020699004973287771475874
 85.  20672849399056463095319772838289364792345825123228624
 86.  87571595343018854458033386304178158174356588264390370
 87.  370959230771131880927453318055001997489772178180790104
 88.  1571408518427546378167846658524186148133445300987550786
 89.  6656593304481317393598839952151746590023553382130993248
 90.  28197781736352815952563206467131172508227658829511523778
 91.  119447720249892581203851665820676436622934188700177088360
 92.  505988662735923140767969869749836918999964413630219877218
 93.  2143402371193585144275731144820024112622791843221056597232
 94.  9079598147510263717870894449029933369491131786514446266146
 95.  38461794961234640015759308940939757590587318989278841661816
 96.  162926777992448823780908130212788963731840407743629812913410
 97.  690168906931029935139391829792095612517948949963798093315456
 98.  2923602405716568564338475449381171413803636207598822186175234
 99.  12384578529797304192493293627316781267732493780359086838016392
100.  52461916524905785334311649958648296484733611329035169538240802

Time: 0.00698620

Das sind die ersten 100 geraden Fibonacci-Zahlen in ~ 7ms und umfassen den Overhead des Druckens auf das Terminal (unter Windows leicht zu unterschätzen).

8
CoDEmanX

Basierend auf der Tatsache, dass fib(n) = fib(n-1)+fib(n-2), ist die unkomplizierte Lösung

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

das Problem hierbei ist jedoch, dass einige Werte mehrmals berechnet werden und daher sehr ineffizient sind. Der Grund ist in dieser Skizze zu sehen:

 Fibonacci

Im Wesentlichen muss jeder rekursive Aufruf der fib-Funktion alle vorherigen Fibonacci-Zahlen für seine eigene Verwendung berechnen. Der am meisten berechnete Wert ist fib (1), da er in allen Blattknoten des Baums erscheinen muss, der als Antwort von @kqr angezeigt wird. Die Komplexität dieses Algorithmus ist die Anzahl der Knoten des Baums, also $ O (2 ^ n) $.

Jetzt ist es besser, zwei Zahlen zu verfolgen, den aktuellen Wert und den vorherigen Wert, so dass nicht jeder Aufruf alle vorherigen Werte berechnen muss. Dies ist der zweite Algorithmus in der Skizze und kann wie folgt implementiert werden

def fib(n):
   if (n==0):
       return(0,1)
   Elif (n==1):
       return(1,1)
   else:
       a,b = fib(n-1)
       return(b,a+b)

Die Komplexität dieses Algorithmus ist linear $ O (n) $, und einige Beispiele werden es geben

>>> fib(1)
(1, 1)
>>> fib(2)
(1, 2)
>>> fib(4)
(3, 5)
>>> fib(6)
(8, 13)
5
Vahid Mir

Lösung in R, Benchmark berechnet 1 bis 1000. Fibonacci-Zahlenreihe in 1,9 Sekunden. In C++ oder Fortran wäre ich viel schneller, da ich den ersten Beitrag geschrieben hatte, schrieb ich eine gleichwertige Funktion in C++, die in beeindruckenden 0,0033 Sekunden abgeschlossen wurde, sogar Python in 0,3 Sekunden.

#Calculate Fibonnaci Sequence
fib <- function(n){
  if(n <= 2)
    return(as.integer(as.logical(n)))
  k = as.integer(n/2)
  a = fib(k + 1)
  b = fib(k)
  if(n %% 2 == 1)
    return(a*a + b*b)
  return(b*(2*a - b))
}

#Function to do every fibonacci number up to nmax
doFib <- function(nmax = 25,doPrint=FALSE){
    res = sapply(0:abs(nmax),fib)
    if(doPrint)
        print(paste(res,collapse=","))
    return(res)
}

#Benchmark
system.time(doFib(1000))

#user  system elapsed 
#  1.874   0.007   1.892 
3

Ich stützte mich auf einen Artikel über Fibonacci-Zahlen in Wikipedia. Die Idee ist, Schleifen und Rekursion zu vermeiden und den Wert einfach nach Bedarf zu berechnen. 

Da Sie kein mathematischer Assistent sind, wählen Sie eine der Formeln aus, rendern Sie sie in Code und passen Sie sie an, bis die Werte richtig sind. 

import cmath

def getFib(n):
    #Given which fibonacci number we want, calculate its value
    lsa = (1 / cmath.sqrt(5)) * pow(((1 + cmath.sqrt(5)) / 2), n)
    rsa = (1 / cmath.sqrt(5)) * pow(((1 - cmath.sqrt(5)) / 2), n)
    fib = lsa-rsa
    #coerce to real so we can round the complex result
    fn = round(fib.real) 
    return fn 

#Demo using the function
s = ''
for m in range(0,30):
    s = s + '(' + str(m) + ')' + str(getFib(m)) + ' '

print(s)
3
Dan Rhea

kqr s Lösung Nr. 2 ist mein absoluter Favorit.
In diesem speziellen Fall verlieren wir jedoch alle unsere Berechnungen zwischen aufeinanderfolgenden Aufrufen innerhalb des Listenverständnisses:

list2 = [i for i in list1 if fib(i) % 2 == 0]

Also entschied ich mich, noch einen Schritt weiter zu gehen und es wie folgt zwischen die einzelnen Schritte zu notieren:

def cache_fib(ff):
    comp = {0: 0, 1: 1}

    def fib_cached(n, computed=comp):
        return ff(n, computed)
    return fib_cached


@cache_fib
def fib(n, computed={0: 0, 1: 1}):
    if n not in computed:
        computed[n] = fib(n - 1, computed) + fib(n - 2, computed)
    return computed[n]
2
Lukasz

Die rekursive Berechnung von Fibonacci ist am ineffizientesten als das iterative Vorgehen. Meine Empfehlung ist:

Nehmen Sie sich die Zeit, um eine Fibonacci-Klasse als Iterator zu erstellen, und führen Sie die Berechnungen für jedes Element im Index unabhängig durch. Möglicherweise verwenden Sie einen beliebigen @memoize-Dekorator (und auch here ), um alle vorherigen Berechnungen zwischenzuspeichern.

Hoffe das hilft!

1
Paulo Bu

Dies ist eine verbesserte Version von Fibonacci, bei der wir Fibonacci von number nur einmal berechnen:

dicFib = { 0:0 ,1 :1 }
iterations = 0
def fibonacci(a):
    if  (a in dicFib):      
        return dicFib[a]    
    else :
        global iterations               
        fib = fibonacci(a-2)+fibonacci(a-1)
        dicFib[a] = fib
        iterations += 1
        return fib

print ("Fibonacci of 10 is:" , fibonacci(10))
print ("Fibonacci of all numbers:" ,dicFib)
print ("iterations:" ,iterations)

# ('Fibonacci of 10 is:', 55)
# ('Fibonacci of all numbers:', {0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55})
# ('iterations:', 9)

Hier speichern wir Fibonacci von jeder Zahl im Wörterbuch. Sie können also sehen, dass es für jede Iteration nur einmal berechnet wird, und für Fibonacci (10) nur neunmal.

1
Girish Gupta

Um die Summe der ersten n geradzahligen Fibonacci-Zahlen direkt zu finden, geben Sie 3n + 2 in Ihre bevorzugte Methode ein, um effizient eine einzelne Fibonacci-Zahl zu berechnen, um eins zu erniedrigen und durch zwei zu teilen (fib((3*n+2) - 1)/2)). Wie haben Mathe-Dummys vor OEIS überlebt?

1
greybeard

Eine O(1) Lösung

Es stellt sich heraus, dass es eine Nice-Rekursivformel für die Summe der geraden Fibonacci-Zahlen gibt. Der n-te Term in der Folge der Summen von geraden Fibonacci-Zahlen lautet S_{n} = 4*S_{n-1} + S_{n-2} + 2. Der Beweis bleibt dem Leser überlassen, es gilt jedoch zu beweisen, dass 1) gerade Fibo-Zahlen alle drei sind, 2) die obige Formel mit Induktion unter Verwendung von beweisen Definition von Fibo-Zahlen. Aus der Logik von hier können wir mit etwas Aufwand eine geschlossene Formel ableiten:

S_{n} = -1/2 + (1/4 + 3*sqrt(5)/20)*(2+sqrt(5))**n + (1/4 - 3*sqrt(5)/20)*(2-sqrt(5))**n

Trotz des sqrt ist dies ein Integral für das Integral n, sodass dies bequem mithilfe der praktischen Funktionen aus meiner vorherigen Antwort oder mithilfe eines Pakets wie sympy berechnet werden kann die Wurzeln genau.

import sympy as sp
one = sp.sympify(1) #to force casting to sympy types
k1 = -one/2
k2 = one/4 + 3*sp.sqrt(5)/20
k3 = one/4 - 3*sp.sqrt(5)/20
r1 = one
r2 = 2 + sp.sqrt(5)
r3 = 2 - sp.sqrt(5)
def even_sum_fibo(n):
  #get the nth number in the sequence of even sums of Fibonacci numbers.  If you want the sum of Fibos up to some number m, use n = m/3 (integer division)
  return sp.simplify(k1*r1**n + k2*r2**n + k3*r3**n)
1
Scott

Es gibt eine O(1) - Lösung: https://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding

import math

PHI = (1 + math.sqrt(5)) / 2
SQRT5 = math.sqrt(5)


def fast_fib(n):
    if n < 0:
        raise ValueError('Fibs for negative values are not defined.')
    return round(math.pow(PHI, n) / SQRT5)
1
Bastian Venthur
import time


def calculate_fibonacci_1(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return calculate_fibonacci_1(n - 1) + calculate_fibonacci_1(n - 2)


def calculate_fibonacci_2(n):
    fib = [0] * n
    fib[0] = 1
    fib[1] = 1
    for i in range(2, n):
        fib[i] = fib[i - 1] + fib[i - 2]
    return fib[n-1]


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


def calculate_fibonacci_4(n):
    v1, v2, v3 = 1, 1, 0
    for rec in bin(n)[3:]:
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec == '1':
            v1, v2, v3 = v1+v2, v1, v2
    return v2


def calculate_fibonacci_5(n):
    if n == 0:
        return (0, 1)
    else:
        a, b = calculate_fibonacci_5(n // 2)
        c = a * (b * 2 - a)
        d = a * a + b * b
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, c + d)

    n = 30

    start = time.time()
    calculate_fibonacci_1(n)
    end = time.time()
    print(end - start)

    start = time.time()
    calculate_fibonacci_2(n)
    end = time.time()
    print(end - start)

    start = time.time()
    calculate_fibonacci_3(n)
    end = time.time()
    print(end - start)

    start = time.time()
    calculate_fibonacci_4(n)
    end = time.time()
    print(end - start)

    start = time.time()
    calculate_fibonacci_5(n)
    end = time.time()
    print(end - start)

zum n=30:

0.264876127243
6.19888305664e-06
8.10623168945e-06
7.15255737305e-06
4.05311584473e-06

zum n=300:

>10s
3.19480895996e-05
1.78813934326e-05
7.15255737305e-06
6.19888305664e-06

zum n=3000:

>10s
0.000766038894653
0.000277996063232
1.78813934326e-05
1.28746032715e-05

zum n=30000:

>10s
0.0550990104675
0.0153529644012
0.000290870666504
0.000216007232666

zum n=300000:

>10s
3.35211610794
0.979753017426
0.012097120285
0.00845909118652

zum n=3000000:

>10s
>10s
>10s
0.466345071793
0.355515003204

zum n=30000000:

>100s
>100s
>100s
16.4943139553
12.6505448818

haftungsausschluss: Funktionscodes nr. 4 und 5 wurden nicht von mir geschrieben

1
SantaXL

Haskell 1 Liner: -

fibs = 0 : (f 1 1) where f a b = a : f b (a+b)

Dieser Code ist äußerst effizient und berechnet Fibonacci-Zahlen bis (10^1000) in weniger als einer Sekunde! Dieser Code wird auch für dieses Problem in Project Euler nützlich sein.

1
rohansumant

Sie können die Gleichung mit Quadratwurzeln verwenden, um dies zu berechnen, wenn Sie keine Gleitkomma-Arithmetik verwenden, sondern die Koeffizienten auf andere Weise verfolgen. Dies ergibt einen im Wesentlichen konstanten zeitgenauen Algorithmus für Fibonacci-Zahlen:

def rootiply(a1,b1,a2,b2,c):
    ''' multipy a1+b1*sqrt(c) and a2+b2*sqrt(c)... return a,b'''
    return a1*a2 + b1*b2*c, a1*b2 + a2*b1

def rootipower(a,b,c,n):
    ''' raise a + b * sqrt(c) to the nth power... returns the new a,b and c of the result in the same format'''
    ar,br = 1,0
    while n != 0:
        if n%2:
            ar,br = rootiply(ar,br,a,b,c)
        a,b = rootiply(a,b,a,b,c)
        n /= 2
    return ar,br

def fib(k):
    ''' the kth fibonacci number'''
    a1,b1 = rootipower(1,1,5,k)
    a2,b2 = rootipower(1,-1,5,k)
    a = a1-a2
    b = b1-b2
    a,b = rootiply(0,1,a,b,5)
    # b should be 0!
    assert b == 0
    return a/2**k/5

if __== "__main__":
    assert rootipower(1,2,3,3) == (37,30) # 1+2sqrt(3) **3 => 13 + 4sqrt(3) => 39 + 30sqrt(3)
    assert fib(10)==55
1
Scott

Jedes Problem wie dieses wird bei einer großen Rekursion sehr lange dauern. Die rekursive Definition eignet sich gut, um das Problem auf eine leicht zu verstehende Weise zu codieren. Wenn Sie es jedoch benötigen, um eine iterative Lösung wie die Antwort in diesem Thread schneller auszuführen, ist dies viel schneller.

1
ChrisProsser

Eine schnelle Methode ist die rekursive Berechnung der fib (n/2) -Zahl:

fibs = {0: 0, 1: 1}
def fib(n):
    if n in fibs: return fibs[n]
    if n % 2 == 0:
        fibs[n] = ((2 * fib((n / 2) - 1)) + fib(n / 2)) * fib(n / 2)
        return fibs[n]
    else:
        fibs[n] = (fib((n - 1) / 2) ** 2) + (fib((n+1) / 2) ** 2)
        return fibs[n]

from time import time
s=time()
print fib(1000000)
print time()-s
1

O(1) LÖSUNG

Die Formel wird auch als Binets Formel bezeichnet ( Lesen Sie mehr )

Grundsätzlich können wir es in python so schreiben:

def fib(n):
    a = ((1 + (5 ** 0.5)) / 2)**int(n)
    b = ((1 - (5 ** 0.5)) / 2)**int(n)
    return round((a - b) / (5 ** 0.5))

Aufgrund des relativ niedrigen Werts von b können wir ihn jedoch ignorieren und die Funktion kann so einfach wie sein

def fib(n):
    return round((((1+(5**0.5))/2)**int(n))/(5**0.5))
0
Tatsu

Hier ist eine optimierte Lösung mit dem Wörterbuch 

def Fibonacci(n):
    if n<2 : return n
    Elif not n in fib_dict :
            fib_dict[n]= Fibonacci(n-1) + Fibonacci(n-2)
    return fib_dict[n]

#dictionary which store Fibonacci values with the Key
fib_dict = {}
print(Fibonacci(440))
0
vishwaraj

Vorgabe der Startnummer und der maximalen Anzahl; Ich denke, die folgende Lösung für Fibonacci wäre interessant. Das Gute ist, dass es keine Rekursion enthält - und somit den Speicheraufwand reduziert.

# starting number is a
# largest number in the fibonacci sequence is b

def fibonacci(a,b):
    fib_series = [a, a]

    while sum(fib_series[-2:]) <=b:
        next_fib = sum(fib_series[-2:])
        fib_series.append(next_fib)

    return fib_series

print('the fibonacci series for the range %s is %s'
      %([3, 27], fibonacci(3, 27)))

the fibonacci series for the range [1, 12] is [3, 3, 6, 9, 15, 24]
0
everestial007

Zwar eine späte Antwort, aber es könnte hilfreich sein

fib_dict = {}

def fib(n): 
    try:
        return fib_dict[n]
    except:
        if n<=1:
            fib_dict[n] = n
            return n
        else:
            fib_dict[n] = fib(n-1) + fib (n-2)
            return fib(n-1) + fib (n-2)

print fib(100)

Dies ist viel schneller als auf herkömmliche Weise 

0
Abx

Spoiler-Alarm: Lesen Sie dies nicht, wenn Sie die Projekt-Euler-Frage 2 ausführen, bis Sie selbst einen Sprung hatten.

Abgesehen von Closed-Form-Ansätzen, die auf Reihensummen basieren, scheint dies effizienter zu sein als die meisten/alles, was ich gesehen habe, da nur eine recht billige Loop-Iteration pro gerade Fibonacci-Nummer erforderlich ist, also nur 12 Iterationen 4.000.000 bekommen.

def sumOfEvenFibonacciNumbersUpTo(inclusiveLimit):
    even = 0
    next = 1
    sum  = 0
    while even<=inclusiveLimit:
        sum  += even
        even += next<<1
        next  = (even<<1)-next
    return sum
0
egyik

Hier ist eine einfache ohne Rekursion und O (n)

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