Ответ 1

Да. Примитивно-рекурсивное решение занимает много времени. Причиной этого является то, что для каждого подсчитанного числа ему нужно рассчитать все предыдущие числа более одного раза. Посмотрите на следующее изображение.

Он представляет собой вычисление Fibonacci(5) с помощью вашей функции. Как вы можете видеть, он вычисляет значение Fibonacci(2) три раза, а значение Fibonacci(1) - пять раз. Это становится все хуже и хуже, чем выше число, которое вы хотите вычислить.

Что еще хуже, так это то, что с каждым номером фибоначчи, который вы вычисляете в своем списке, вы не используете предыдущие номера, о которых вы знаете, чтобы ускорить вычисление - вы вычисляете каждый номер "с нуля".

Есть несколько вариантов сделать это быстрее:

1. Создайте список "снизу вверх"

Самый простой способ - просто создать список номеров фибоначчи до нужного числа. Если вы это сделаете, вы строите "снизу вверх" или так сказать, и вы можете повторно использовать предыдущие номера для создания следующего. Если у вас есть список номеров фибоначчи [0, 1, 1, 2, 3], вы можете использовать последние два числа в этом списке, чтобы создать следующий номер.

Этот подход будет выглядеть примерно так:

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

Затем вы можете получить первые 20 номеров фибоначчи, выполнив

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

Или вы можете получить 17-й номер фибоначчи из списка первых 40, выполнив

>>> fib_to(40)[17]
1597

2. Запоминание (относительно продвинутая техника)

Еще одна альтернатива, чтобы сделать ее быстрее, но она немного сложнее. Поскольку ваша проблема заключается в том, что вы повторно вычисляете значения, которые вы уже вычислили, вместо этого вы можете сохранить значения, которые вы уже вычислили в dict, и попытаться их получить, прежде чем их пересчитать. Это называется memoization. Это может выглядеть примерно так:

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

Это позволяет вам вычислять большие числа фибоначчи на ветру:

>>> fib(400)
176023680645013966468226945392411250770384383304492191886725992896575345044216019675

Это на самом деле такая распространенная техника, что Python 3 включает в себя декоратор, чтобы сделать это для вас. Представляю вам, автоматическое напоминание!

import functools

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

Это почти то же самое, что и предыдущая функция, но со всеми элементами computed, обработанными декорером lru_cache.

3. Просто подсчитайте (наивное итерационное решение)

Третий метод, предложенный Митчем, состоит в том, чтобы просто подсчитать, не сохраняя значения промежуточного элемента в списке. Вы можете себе представить, что делать

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

Я не рекомендую эти последние два метода, если ваша цель - создать список чисел фибоначчи. fib_to(100) будет намного быстрее, чем [fib(n) for n in range(101)], потому что с последним вы все еще сталкиваетесь с проблемой вычисления каждого числа в списке с нуля.

Ответ 2

Это очень быстрый алгоритм, и он может найти n-е число Фибоначчи намного быстрее, чем простой итеративный подход, представленный в других ответах, он довольно продвинут, хотя:

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

Вы можете прочитать еще об участии в математике здесь.

Ответ 3

Python не оптимизирует хвостовую рекурсию, поэтому большинство представленных здесь решений не сработают с Error: maximum recursion depth exceeded in comparison, если n слишком большой (и большим, я имею в виду 1000).

Предел рекурсии может быть увеличен, но это приведет к сбою Python при переполнении стека в операционной системе.

Обратите внимание на разницу в производительности между fib_memo/fib_local и fib_lru/fib_local_exc: кеш LRU намного медленнее и даже не завершился, поскольку он вызывает ошибку времени выполнения для n = ~ 500

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)

Результаты:

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

Итеративное решение на сегодняшний день является самым быстрым и не повреждает стек даже для n=100k (0,162 секунды). Он действительно не возвращает промежуточные числа Фибоначчи.

Если вы хотите вычислить число n th даже Фибоначчи, вы можете адаптировать итеративный подход следующим образом:

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

Или, если вас интересует каждый четный номер на пути, используйте генератор :

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

Результат:

  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

То, что первые 100 даже чисел Фибоначчи в ~ 7 мс и включают в себя накладные расходы на печать на терминал (легко недооценивать в Windows).

Ответ 4

Основываясь на том факте, что fib(n) = fib(n-1)+fib(n-2), простым решением является

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

однако проблема здесь в том, что некоторые значения рассчитываются несколько раз, и поэтому это очень неэффективно. Причину можно увидеть на этом наброске:

По сути, каждый рекурсивный вызов функции fib должен вычислять все предыдущие числа Фибоначчи для своего собственного использования. Таким образом, наиболее вычисляемым значением будет fib (1), так как оно должно появиться во всех листовых узлах дерева, показанного ответом @kqr. Сложность этого алгоритма заключается в количестве узлов дерева, которое составляет $ O (2 ^ n) $.

Теперь лучший способ - отслеживать два числа, текущее значение и предыдущее значение, чтобы при каждом вызове не приходилось вычислять все предыдущие значения. Это второй алгоритм в эскизе и может быть реализован следующим образом

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)

Сложность этого алгоритма линейна $ O (n) $, и некоторые примеры будут

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

Ответ 5

Решение в R, benchmark вычисляет 1 - 1000-й ряд чисел Фибоначчи за 1,9 секунды. Было бы намного быстрее в С++ или Fortran, на самом деле, начиная с написания исходного сообщения, я написал эквивалентную функцию в С++, которая завершилась впечатляющим 0.0033 секундами, даже питон завершился за 0.3 секунды.

#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 

Ответ 6

Я основывал это на статье о числах Фибоначчи в Википедии. Идея состоит в том, чтобы избежать циклов и рекурсии и просто вычислить значение по мере необходимости.

Не будучи математическим wiz, выбрал одну из формул и перевел код на код и изменил его до тех пор, пока значения не выйдут правильно.

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)

Ответ 7

kqr решение № 2 - это мой любимый фаворит. Однако в этом конкретном случае мы теряем все наши вычисления между последовательными вызовами в понимании списка:

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

поэтому я решил сделать еще один шаг и запомнить его между шагами шага следующим образом:

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]

Ответ 8

Существует решение O (1): 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)

Ответ 9

Любые проблемы, подобные этому, потребуют много времени, если будет много уровней рекурсии. Рекурсивное определение полезно для кодирования проблемы таким образом, который может быть легко понят, но если вам нужно, чтобы он быстрее запускал итеративное решение, такое как ответ в этой теме будет намного быстрее.

Ответ 10

Рекурсивно вычислять Фибоначчи будет наиболее неэффективно, чем итеративно. Моя рекомендация:

Найдите время для создания класса Fibonacci как итератора и выполните вычисления независимо для каждого элемента в индексе, возможно, с помощью @memoize decorator (а также здесь) для кэширования всех предыдущих вычислений.

Надеюсь, это поможет!

Ответ 11

Один быстрый способ - вычислить числовое число (n/2) рекурсивно:

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

Ответ 12

Haskell 1 liner: -

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

Этот код чрезвычайно эффективен и вычисляет числа Фибоначчи до (10^1000) менее чем за секунду! Этот код также будет полезен для этой проблемы в Project Euler.

Ответ 13

Чтобы найти сумму первых n четнозначных чисел фибоначчи, положите 3n + 2 в свой любимый метод, чтобы эффективно вычислить одно число фибоначчи, уменьшиться на единицу и делить на два (fib((3*n+2) - 1)/2)). Как математические манекены выживали до OEIS?

Ответ 14

Вы можете использовать уравнение с квадратными корнями, чтобы вычислить это, если вы не используете арифметику с плавающей запятой, но отслеживайте коэффициенты по-другому. Это дает по существу постоянный точный алгоритм времени для чисел Фибоначчи:

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 __name__ == "__main__":
    assert rootipower(1,2,3,3) == (37,30) # 1+2sqrt(3) **3 => 13 + 4sqrt(3) => 39 + 30sqrt(3)
    assert fib(10)==55

Ответ 15

Это некоторая улучшенная версия Fibonacci, где мы вычисляем число Фибоначчи только один раз:

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)

Здесь мы храним Фибоначчи каждого числа в словаре. Таким образом, вы можете видеть, что он вычисляет только один раз для каждой итерации, а для Фибоначчи (10) - всего 9 раз.

Ответ 16

Решение O (1)

Оказывается, что существует хорошая рекурсивная формула для суммы четных чисел Фибоначчи. N-й член в последовательности сумм четных чисел Фибоначчи равен S_{n} = 4*S_{n-1} + S_{n-2} + 2 Доказательство остается читателю, но включает в себя доказательство 1) четные числа Фибо - каждый третий, 2) доказательство приведенной выше формулы с индукцией с использованием определения Fibo номера. Используя логику здесь, мы можем получить формулу с закрытой формой для этого с небольшим усилием:

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

Несмотря на sqrt, это интеграл для интеграла n, поэтому его можно удобно вычислить с помощью удобных функций из моего предыдущего ответа или с помощью пакета, такого как sympy, чтобы точно обрабатывать корни.

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)

Ответ 17

O (1) РЕШЕНИЕ

Формула также называется Формула Бине (подробнее)

По сути, мы можем написать это на python так:

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

Однако, из-за относительно низкого значения b, мы можем игнорировать его, и функция может быть настолько простой, как

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

Ответ 18

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)

для n=30:

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

для n=300:

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

для n=3000:

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

для n=30000:

>10s
0.0550990104675
0.0153529644012
0.000290870666504
0.000216007232666

для n=300000:

>10s
3.35211610794
0.979753017426
0.012097120285
0.00845909118652

для n=3000000:

>10s
>10s
>10s
0.466345071793
0.355515003204

для n=30000000:

>100s
>100s
>100s
16.4943139553
12.6505448818

отказ от ответственности: коды функций нет. 4 и 5 не были написаны мной

Ответ 19

Хотя поздний ответ, но может быть полезно

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)

Это намного быстрее, чем традиционный способ

Ответ 20

Учитывая стартовый номер и максимальное количество; Я думаю, что следующее решение для Фибоначчи было бы интересно. Хорошая вещь состоит в том, что это не включает рекурсию - таким образом уменьшая бремя памяти.

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

Ответ 21

Здесь простой без рекурсии и O (n)

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

Ответ 22

Оповещение о спойлере: не читайте это, если вы делаете Project Euler Question 2, пока не разберетесь сами.

За исключением подходов, основанных на суммировании рядов в замкнутой форме, это кажется более эффективным, чем большинство/все из того, что я видел опубликованным, так как для него требуется только одна довольно дешевая итерация цикла на четное число Фибоначчи, поэтому всего 12 итераций, чтобы добраться до 4 000 000.

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

Ответ 23

Вот оптимизированное решение со словарем

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

Ответ 24

Это намного быстрее, чем все выше

from sympy import fibonacci
%timeit fibonacci(10000)

262 ns ± 10.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Ответ 25

Мне нравится использовать это, чтобы найти n-й номер Фибоначчи, в Python:

def fib(n):
    a, b = 0, 1
    while n:
        a, b, n = b, a+b, n-1
    return a

Ответ 26

int count=0;
void fibbo(int,int);

void main()

{

fibbo(0,1);

    getch();
}

void fibbo(int a,int b)

{

 count++;

 printf(" %d ",a);

if(count<=10)

     fibbo(b,a+b);

else

      return;

}