Как написать последовательность Фибоначчи?

142

Первоначально я неправильно написал программу. Вместо того, чтобы возвращать числа Фибоначчи между диапазоном (т.е. startNumber 1, endNumber 20 должны = только числа между 1 и 20), я написал для программы, чтобы отображать все числа Фибоначчи между диапазоном (например, startNumber 1, endNumber 20 отображает = Первые 20 чисел Фибоначчи). Я думал, что у меня есть надежный код. Я тоже не понимаю, почему это происходит.

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

Кто-то указал в моей части II (которая была закрыта как дубликат - /programming/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii ), что я необходимо передать startNumber и endNumber через генератор, используя цикл while. Может кто-нибудь указать мне, как это сделать? Любая помощь приветствуется.


Я обучающийся программист, и я наткнулся на небольшую путаницу. Меня просят написать программу, которая будет вычислять и отображать последовательность Фибоначчи по введенному пользователем начальному и конечному номерам (то есть startNumber = 20 endNumber = 100, и она будет отображать только числа между этим диапазоном). Уловка состоит в том, чтобы использовать его включительно (что я не знаю, как это сделать в Python? - Я предполагаю, что это означает использование включающего диапазона?).

Пока что у меня нет фактического кодирования, а скорее:

  • Запишите формулу последовательности Фибоначчи до бесконечности
  • Отображать startNumber в endNumber только из последовательности Фибоначчи.

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

SD.
источник

Ответы:

262

Есть много информации о последовательности Фибоначчи в Википедии и на вольфраме . Намного больше, чем вам может понадобиться. В любом случае полезно научиться использовать эти ресурсы, чтобы найти (если возможно, быстро) то, что вам нужно.

Запишите формулу последовательности Фибоначчи до бесконечности

В математике это дается в рекурсивной форме:

Фибоначчи из Википедии

В программировании бесконечности не существует. Вы можете использовать рекурсивную форму, переводя математическую форму прямо на ваш язык, например, в Python она становится:

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

Попробуйте на своем любимом языке и убедитесь, что эта форма требует много времени, поскольку n становится больше. Фактически, это время O (2 n ).

Зайдите на сайты, которые я связал с вами, и увидите это (на вольфраме ):

Уравнение Фибоначчи

Это довольно легко реализовать и очень, очень быстро вычислить на Python:

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

Другой способ сделать это - следовать определению (из Википедии ):

Первое число в последовательности - 0, второе число - 1, и каждое последующее число равно сумме двух предыдущих чисел самой последовательности, что дает последовательность 0, 1, 1, 2, 3, 5, 8. , так далее.

Если ваш язык поддерживает итераторы, вы можете сделать что-то вроде:

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

Отображать startNumber в endNumber только из последовательности Фибоначчи.

Как только вы знаете, как генерировать числа Фибоначчи, вам просто нужно циклически перебирать числа и проверять, подтверждают ли они заданные условия.

Предположим, теперь вы написали af (n), который возвращает n-й член последовательности Фибоначчи (например, с sqrt (5))

На большинстве языков вы можете сделать что-то вроде:

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

В python я бы использовал форму итератора и выбрал:

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

Мой совет - научитесь читать то, что вам нужно. Project Euler (Google для этого) научит вас этому: P Удачи и получайте удовольствие!

Андреа Амбу
источник
1
Вам нужно использовать цикл while, а не карту. Попробуйте разобраться в этом самостоятельно, а затем вернитесь с кодом, если у вас не получится. Я не ленивый (код короче этого комментария). Я делаю это для вас, попробуйте с подсказкой «пока»;) Если у вас возникнут проблемы, вернитесь еще раз;)
Андреа Амбу
Я вернулся, лол. Я избавился от функции map (range) и использую только функцию range (startNumber, endNumber). Теперь у меня возникла проблема, где использовать оператор while. Я пробую в начале функции, но, конечно, есть строки с ошибками. Куда я должен его положить? Спасибо
SD.
Попробуйте своими руками сделать пример ввода-вывода вашей программы (с небольшим диапазоном). Затем попробуйте выяснить, в чем ошибка вашей программы. Попробуйте преобразовать "ручной метод" в код. Это для упражнений, для обучения. Я мог бы написать две строчки кода, но не думаю, что вы чему-нибудь из них научитесь.
Андреа Амбу
1
Мы должны использовать int(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5)))какие-нибудь идеи? @AndreaAmbu
lord63. j
3
@ lord63.j, вам следует использовать эту формулу только в том случае, если вы знаете, что она начинает отклоняться от фактического значения, когда nоно превышает 70, и взрывается, OverflowError когда значение nнемного превышает 600. Другие подходы могут обрабатывать n1000 или более без разрыва вверх или теряет точность.
cdlane
69

Эффективный питонический генератор последовательности Фибоначчи

Я нашел этот вопрос, пытаясь получить самую короткую Pythonic-генерацию этой последовательности (позже я понял, что видел подобное в предложении по расширению Python ), и я не заметил, чтобы кто-то еще предлагал мое конкретное решение (хотя главный ответ приближается, но все же менее элегантно), так что вот оно, с комментариями, описывающими первую итерацию, потому что я думаю, что это может помочь читателям понять:

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)

и использование:

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

печатает:

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

(Для целей атрибуции я недавно заметил аналогичную реализацию в документации Python по модулям, даже с использованием переменных aи b, которые, как я припоминаю, видел перед написанием этого ответа. Но я думаю, что этот ответ демонстрирует лучшее использование языка.)

Рекурсивно определенная реализация

Интернет Энциклопедия целочисленных последовательностей определяет последовательность Фибоначчи рекурсивно

F (n) = F (n-1) + F (n-2) с F (0) = 0 и F (1) = 1

Кратко определить это рекурсивно в Python можно следующим образом:

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

Но это точное представление математического определения невероятно неэффективно для чисел, намного превышающих 30, потому что каждое вычисляемое число должно также вычисляться для каждого числа ниже него. Вы можете продемонстрировать, насколько он медленный, используя следующее:

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

Мемоизированная рекурсия для эффективности

Его можно запоминать для повышения скорости (в этом примере используется тот факт, что аргумент ключевого слова по умолчанию является одним и тем же объектом каждый раз при вызове функции, но обычно вы не будете использовать изменяемый аргумент по умолчанию именно по этой причине):

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

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

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

(Может показаться, что мы можем просто сделать следующее, но на самом деле это не позволяет нам воспользоваться кешем, потому что он вызывает себя до вызова setdefault.)

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

Рекурсивно определенный генератор:

Изучая Haskell, я наткнулся на эту реализацию в Haskell:

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

На данный момент я думаю, что ближе всего к этому в Python я могу подойти:

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

Это демонстрирует:

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

Однако он может доходить только до предела рекурсии. Обычно 1000, тогда как версия Haskell может доходить до сотен миллионов, хотя для этого используются все 8 ГБ памяти моего ноутбука:

> length $ take 100000000 fib 
100000000

Использование итератора для получения n-го числа Фибоначчи

Комментатор спрашивает:

Вопрос к функции Fib (), основанной на итераторе: что делать, если вы хотите получить n-е, например 10-е число fib?

В документации itertools есть рецепт для этого:

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)

и сейчас:

>>> nth(fib(), 10)
55
Аарон Холл
источник
Что касается последней опции "не делайте этого" "", я не понимаю, почему она вызывается до setdefault. Разве setdefault не должен возвращать значение, если n - действительный ключ? Док говорит: «Если ключ находится в словаре, верните его значение. Если нет, вставьте ключ со значением по умолчанию и верните значение по умолчанию. По умолчанию по умолчанию нет». Что мне не хватает?
binithb
@binithb выражение внутри setdefaultвызова вычисляется раньше setdefault .
Аарон Холл
Как мемоизированная версия передает _cacheпеременную рекурсивным вызовам? Я не понимаю, почему тебе не нужно звонить setdefault(n, mem_fib(n-1, _cache) + mem_fib(n-2, _cache).
Натан Пирсон,
@NathanPierson аргумент ключевого слова является аргументом по умолчанию, и это тот же самый экземпляр словаря, который используется при каждом вызове, поэтому нам не нужно передавать его явно.
Аарон Холл
1
@NathanPierson, верно - это изменяемый аргумент по умолчанию, и он всегда одинаков и для будущих вызовов. Вот ответ, который я написал, который полностью исследует вопрос: stackoverflow.com/a/36968932/541136
Аарон Холл
25

Почему бы просто не сделать следующее?

x = [1,1]
for i in range(2, 10):  
    x.append(x[-1] + x[-2]) 
print(', '.join(str(y) for y in x))
Томас Спайчер
источник
22

Идея последовательности Фибоначчи показана в следующем коде Python:

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

Это означает, что fib - это функция, которая может делать одно из трех. Он определяет fib (1) == 1, fib (0) == 0 и fib (n) как:

фиб (п-1) + фиб (п-2)

Где n - произвольное целое число. Это означает, что, например, fib (2) расширяется до следующей арифметики:

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

Мы можем вычислить fib (3) таким же образом с помощью арифметики, показанной ниже:

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

Здесь важно понимать, что fib (3) не может быть вычислен без вычисления fib (2), которое вычисляется, зная определения fib (1) и fib (0). Сам вызов функции, такой как функция Фибоначчи, называется рекурсией, и это важная тема в программировании.

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

Изменить: одна из потенциальных критических замечаний по поводу моего кода заключается в том, что он не использует супер-удобную функцию Python yield, что делает функцию fib (n) намного короче. Однако мой пример немного более общий, поскольку не многие языки, кроме Python, действительно имеют yield.

Джеймс Томпсон
источник
Это не домашнее задание, но вау, спасибо за ответ! Я понимаю, что мне нужно сделать, но запуск и реализация - это то, на чем я сейчас застрял (особенно с реализацией значений пользовательского ввода). Можете ли вы немного разобраться в этом? Я продолжаю получать ошибку <function fib at 0x0141FAF0>.
SD.
Я понимаю, что вы очень стараетесь реализовать программу, которая может выходить за рамки ваших текущих возможностей. Если я напишу больше кода, вам не поможет. Вам следует попробовать взломать мой код, пока он не заработает, и прочитать больше руководств по Python. Пробелы могут быть проблемой, но я не знаю этой ошибки.
Джеймс Томпсон,
Я понимаю. Есть ли еще какая-нибудь идея, которую, по-вашему, я могу упустить? Я понимаю, если вы не можете помочь. Я благодарю вас за ваше время.
SD.
Ваша ошибка <function fib at 0x0141FAF0> может быть результатом того, что вы произнесли «fib» (который относится к самой функции) вместо «fib ()», который вызовет функцию. Удачи.
Kiv
9
Имейте в виду, что этот наивный рекурсивный метод вычисления чисел Фибоначчи может очень быстро попасть в переполнение стека (а не сайта). Для практических целей генерируйте итеративно или используйте какую-нибудь мемоизацию или что-то в этом роде.
Дэвид Торнли
13

Временная сложность:

Функция кэширования сокращает обычный способ вычисления рядов Фибоначчи с O (2 ^ n) до O (n) за счет исключения повторов в рекурсивном дереве рядов Фибоначчи:

введите описание изображения здесь

Код:

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()
Акаш Рана
источник
9

Это довольно эффективно, используя O (log n) основных арифметических операций.

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

Здесь используется O (1) базовых арифметических операций, но размер промежуточных результатов велик и поэтому неэффективен.

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

Этот вычисляет X ^ n в кольце многочленов Z [X] / (X ^ 2 - X - 1), используя возведение в степень возведением в квадрат. Результатом этого вычисления является полином Fib (n) X + Fib (n-1), из которого можно прочитать n-е число Фибоначчи.

Опять же, это использует O (log n) арифметических операций и очень эффективно.

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]
Пол Ханкин
источник
1
Первый и третий приемы хороши. Вторая техника отключена на 1; он эффективно должен n -= 1работать правильно, и он также не работает с n = 0. В любом случае, мне бы очень помогло, если бы было добавлено много контекста, чтобы объяснить, как они работают, особенно первый метод. Я вижу, у вас есть пост на paulhankin.github.io/Fibonacci
Acumenus
6

Канонический код Python для печати последовательности Фибоначчи:

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

Для задачи «Выведите первое число Фибоначчи длиной более 1000 цифр»:

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
Да Винчи
источник
4

Мы знаем это

введите описание изображения здесь

И что n-я степень этой матрицы дает нам:

введите описание изображения здесь

Таким образом, мы можем реализовать функцию, которая просто вычисляет степень этой матрицы в степени n -1.

как все мы знаем, мощность a ^ n равна

введите описание изображения здесь

Итак, в конце функция фибоначчи была бы O (n) ... ничем не отличалось бы от более простой реализации, если бы не тот факт, что мы также это знаем, x^n * x^n = x^2nи x^nпоэтому оценка может быть выполнена со сложностью O (log n )

Вот моя реализация Фибоначчи с использованием быстрого языка программирования:

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
}

Это имеет сложность O (log n). Мы вычисляем степень Q с показателем n-1, а затем берем элемент m00, который представляет собой Fn + 1, который при показателе степени n-1 является в точности n-м числом Фибоначчи, которое мы хотели.

Когда у вас есть быстрая функция Фибоначчи, вы можете выполнять итерацию от начального числа до конечного числа, чтобы получить интересующую вас часть последовательности Фибоначчи.

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

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

Я знаю, что этому вопросу 8 лет, но мне все равно было весело отвечать. :)

Джузеппе Ланца
источник
3

Последовательность Фибоначчи: 1, 1, 2, 3, 5, 8, ....

То есть f(1) = 1, f(2) = 1, f(3) = 2, ..., f(n) = f(n-1) + f(n-2).

Моя любимая реализация (самая простая и, тем не менее, обеспечивает небольшую скорость по сравнению с другими реализациями):

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

Контрольная работа

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

Время

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

Изменить: пример визуализации для этой реализации.

Азиз Альто
источник
3

использовать рекурсию:

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
источник
2

Другой способ сделать это:

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

Назначение list для 'a', присвоение целого числа 'n' Map и сокращение - это 2 из трех самых мощных функций в python. Здесь карта используется только для повторения "n-2" раз. a [-2:] получит два последних элемента массива. a.append (x + y) добавит последние два элемента и добавит в массив

Sanooj
источник
1

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

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
Тимми
источник
2
Динамическое программирование FTW! fibonacci (10000000000000000000000000000000000000000000000000000000000000000000000000) отвечает почти мгновенно
Ганс
6
Как-то сомневаюсь.
Lanaru,
Как насчет того, чтобы начать список как [0, 1] (т.е. List.append (0); List.append (1)), чтобы избежать команды удаления после else? ... и число Фибоначчи должно быть лучше проиндексировано, поскольку fibonacci (10) возвращает числа Фибоначчи меньше 10, а не 10-е.
SeF
1

Хорошо ... после того, как вы устали ссылаться на все длинные ответы, теперь найдите ниже сортированный и приятный, довольно простой способ реализации Фибоначчи в python. Вы можете улучшить его так, как вы хотите, получив аргумент или введя данные пользователя… или изменив пределы с 10000. По мере необходимости ……

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

Этот подход тоже работает хорошо. Найдите аналитику пробега ниже

In [10]: %timeit fibonacci
10000000 loops, best of 3: 26.3 ns per loop
Харун Рашеду
источник
1

это улучшение ответа Мэтью Генри:

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

код должен печатать b вместо c

выход: 1,1,2,3,5 ....

Адонго
источник
1

Использование цикла for и печать только результата

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

Результат

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

Выведите listсодержащий все числа

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

Результат

>>> fib(10)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
R__raki__
источник
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))

Полученные результаты

[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, 43334117167373, 701401107373 , 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 405273953700920, 2504730781961, 405277639537003107781961, 40527763953700351

время работы: 0.04298138618469238

Натан Роджерс
источник
1

есть очень простой способ понять это!

вы можете бесплатно запустить этот код в Интернете, используя http://www.learnpython.org/

# Set the variable brian on line 3!

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

print(fib(10))
# result should be this: [0, 1, 1, 2, 3, 5, 8]
xgqfrms
источник
простой способ реализовать ряды Фибоначчи, просто используя итератор, без сложной структуры данных Рекурсии!
xgqfrms
1

Сделать это можно следующим образом.

п = 0

числа = [0]

для i в диапазоне (0,11):
    напечатать n,
    numbers.append (n)
    пред = числа [-2]
    если n == 0:
        п = 1
    еще:
        n = n + пред.
J.Jai
источник
1

Если вы поклонник рекурсии, вы можете легко кэшировать результаты с помощью lru_cacheдекоратора (наименее использованный декоратор кеша)

from functools import lru_cache


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

Если вам нужно кэшировать более 128 значений, вы можете передать их maxsizeв качестве аргумента lru_cache(например, lru_cache(maxsize=500)если вы установите maxsize=Noneкеш может неограниченно расти.

Андреас Хатзивасилейадис
источник
1

Для развлечения в Python 3.8+ вы можете использовать выражение присваивания (также известное как оператор моржа) в понимании списка, например:

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

Выражение присваивания позволяет присвоить значение переменной и вернуть его в том же выражении. Следовательно, выражение

b := a + (a := b)

эквивалентно выполнению

a, b = b, a + b

и возвращает значение b.

Евгений Ярмаш
источник
0

15 минут в учебнике, который я использовал при изучении Python, он попросил читателя написать программу, которая будет вычислять последовательность Фибоначчи из 3 входных чисел (первое число Фибоначчи, второе число и число, на котором следует остановить последовательность). В руководстве были рассмотрены только переменные, if / thens и циклы до этого момента. Функций пока нет. Я придумал следующий код:

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

Как видите, это действительно неэффективно, но ДЕЙСТВИТЕЛЬНО работает.

Йонас
источник
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
источник
3
eval(input())здесь не нужен; Думаю int(input())по делу лучше.
GingerPlusPlus
0

Просто прохожу http://projecteuler.net/problem=2, это было мое мнение

# 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)
Филипе
источник
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
источник
0

Может это поможет

def fibo(n):
    result = []
    a, b = 0, 1
    while b < n:
            result.append(b)
            a, b = b, b + a
    return result
Ван Гог
источник
0

на основе классической последовательности Фибоначчи и просто ради однострочности

если вам просто нужно номер индекса, вы можете использовать уменьшить (даже если уменьшить это не лучше всего подходит для этого он может быть хорошим упражнением)

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]

и чтобы получить полный массив, просто удалите или (r.pop (0) и 0)

reduce(lambda r,v: r.append(r[-1]+r[-2]) or r , xrange(last_index), [0, 1])
Кадмиллос
источник
0

Как насчет этого? Я предполагаю, что это не так необычно, как другие предложения, потому что для получения ожидаемого результата требуется начальная спецификация предыдущего результата, но я считаю, что это очень удобочитаемый вариант, то есть все, что он делает, это предоставляет результат и предыдущий результат для рекурсия.

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

Вот результат:

0
1
1
2
3
5
8
13
21
34
done
the_marcelo_r
источник
0

В основном переведено с Ruby:

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

...

Мэтью Смит
источник
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
источник
0

Более подробное объяснение того, как работает мемоизация для последовательности Фибоначчи.

# 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
системный пользователь
источник