Как написать последовательность Фибоначчи? - PullRequest
Новая
       187

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

130 голосов
/ 30 января 2009

Я изначально неправильно запрограммировал программу. Вместо того, чтобы возвращать числа Фибоначчи между диапазонами (т.е. 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 (которая была закрыта за дублирование - https://stackoverflow.com/questions/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii)), что мне нужно передать startNumber и endNumber через генератор, используя цикл while. Может кто-нибудь указать мне направление о том, как это сделать? Любая помощь приветствуется.

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

То, что я имею до сих пор, это не настоящее кодирование, а:

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

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

Ответы [ 43 ]

0 голосов
/ 17 декабря 2015

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

# 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
0 голосов
/ 07 июня 2019

Если вы поклонник рекурсии, вы можете легко кешировать результаты с помощью 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, кэш может расти без ограничений.

0 голосов
/ 31 декабря 2015

Я пытался избежать рекурсивной функции для решения этой проблемы, поэтому я выбрал итеративный подход. Первоначально я выполнял запомненную рекурсивную функцию, но продолжал достигать максимальной рекурсивной глубины. У меня также были строгие цели в отношении памяти, поэтому вы увидите, что я сохраняю массив настолько малым, насколько я могу, в процессе цикла, сохраняя в нем только 2-3 значения в любое время. 

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

Получение 6-миллионного числа Фибоначчи занимает около 282 секунд на моей машине, в то время как 600К Фибоначчи занимает всего 2,8 секунды. Мне не удалось получить такие большие числа Фибоначчи с помощью рекурсивной функции, даже запоминаемой.

Страница:
...