Блог

Главная - Вопросы по программированию - Python: Что не так с этой функцией Фибоначчи?

Python: Что не так с этой функцией Фибоначчи?

#python #iterator #fibonacci

#python #итератор #фибоначчи

Вопрос:

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

 def fib(a,b,n):
    f = a b
    if (f > n):
        return []
    return [f].extend(fib(b,f,n))

>>>fib(0,1,10)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "lvl2.py", line 35, in fib
    return [f].extend(fib(b,f,n))
  File "lvl2.py", line 35, in fib
    return [f].extend(fib(b,f,n))
  File "lvl2.py", line 35, in fib
    return [f].extend(fib(b,f,n))
  File "lvl2.py", line 35, in fib
    return [f].extend(fib(b,f,n))
TypeError: 'NoneType' object is not iterable

Ответ №1:

list.extend расширяет список на месте. Вы можете использовать оператор для объединения двух списков вместе.

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

 def fib(a,b,n):
    data = []
    f = a b
    if (f > n):
        return data
    data.append(f)
    data.extend(fib(b,f,n))
    return data

Пример использования генераторов для бесконечных последовательностей:

 def fibgen(a, b):
    while True:
        a, b = b, a   b
        yield b

Вы можете создать генератор с помощью fibgen() и извлечь следующее значение с помощью .next() .

Комментарии:

1. Спасибо, это сработало. Я предполагаю, что другое решение — создать отдельный список и установить для него значение extend () и вернуть этот новый список.

Ответ №2:

Возможно, вас заинтересует особенно аккуратная реализация Фибоначчи, хотя она работает только в Python 3.2 и выше:

 @functools.lru_cache(maxsize=None)
def fib(n):
    return fib(n-1)   fib(n-2) if n > 0 else 0

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

Все еще, вероятно, более эффективно выполнять 

 import itertools
def nth(iterable, n, default=None):
    "Returns the nth item or a default value"
    return next(islice(iterable, n, None), default)
nth(fibgen())

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