Числа Фибоначчи, с однострочником в Python 3?

Question

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

Я написал этот код, но мне он показался не лучшим образом:

>>> fib=lambda n:reduce(lambda x,y:(x[0]+x[1],x[0]),[(1,1)]*(n-2))[0]
>>> fib(8)
13

Как это может быть лучше и проще?

Answer 1

fib = lambda n:reduce(lambda x,n:[x[1],x[0]+x[1]], range(n),[0,1])[0]

(при этом поддерживается кортеж, сопоставленный с [a, b] на [b, a + b], инициализированный на [0,1], повторенный N раз, затем принимающий первый элемент кортежа)

>>> fib(1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051
89040387984007925516929592259308032263477520968962323987332247116164299644090653
3187938298969649928516003704476137795166849228875L

(обратите внимание, что в этой нумерации fib (0) = 0, fib (1) = 1, fib (2) = 1, fib (3) = 2 и т. Д.)

(также обратите внимание: reduce является встроенным в Python 2.7, но не в Python 3; вам нужно выполнить from functools import reduce в Python 3.)

Answer 2

Редко встречающийся трюк заключается в том, что лямбда-функция может ссылаться на себя рекурсивно:

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

Кстати, это редко можно увидеть, потому что это сбивает с толку, и в этом случае это также неэффективно. Гораздо лучше написать это в несколько строк:

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

Answer 3

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

[1, 1]
[1, 0]

и умножьте его на себя N раз, чтобы получить:

[F(N+1), F(N)]
[F(N), F(N-1)]

Этим утром, набрасываясь на пар на стене душа, я понял, что вы можете сократить время работы пополам, начав со второй матрицы и умножив ее на себя N / 2 раза, затем используя N, чтобы выбрать индекс из первой строки / столбца.

С небольшим сжатием я уложил его в одну строку:

import numpy

def mm_fib(n):
    return (numpy.matrix([[2,1],[1,1]])**(n//2))[0,(n+1)%2]

>>> [mm_fib(i) for i in range(20)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

Answer 4

Если мы считаем «самый питонский путь» изящным и эффективным, то:

def fib(nr):
    return int(((1 + math.sqrt(5)) / 2) ** nr / math.sqrt(5) + 0.5)

побеждает.Зачем использовать неэффективный алгоритм (и если вы начнете использовать запоминание, мы можем забыть об oneliner), когда вы можете просто решить задачу в O (1) путем аппроксимации результата с золотым отношением?Хотя на самом деле я бы, очевидно, написал это в следующем виде:

def fib(nr):
    ratio = (1 + math.sqrt(5)) / 2
    return int(ratio ** nr / math.sqrt(5) + 0.5)

Более эффективно и гораздо проще для понимания.

Answer 5

Это нерекурсивное (анонимное) запоминание одного вкладыша

fib = lambda x,y=[1,1]:([(y.append(y[-1]+y[-2]),y[-1])[1] for i in range(1+x-len(y))],y[x])[1]

Answer 6

fib = lambda n, x=0, y=1 : x if not n else fib(n-1, y, x+y)

время выполнения O (n), fib (0) = 0, fib (1) = 1, fib (2) = 1 ...

Answer 7

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

fib = lambda n:pow(2<<n,n+1,(4<<2*n)-(2<<n)-1)%(2<<n)

>> fib(1000)
4346655768693745643568852767504062580256466051737178
0402481729089536555417949051890403879840079255169295
9225930803226347752096896232398733224711616429964409
06533187938298969649928516003704476137795166849228875L

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

Он основан на genefib4 из http://fare.tunes.org/files/fun/fibonacci.lisp, который, в свою очередь, основан на менее эффективном целочисленном выражении моей замкнутой формы (см .: http://paulhankin.github.io/Fibonacci/)

Answer 8

Другой пример, взятый из ответа Марка Байерса:

fib = lambda n,a=0,b=1: a if n<=0 else fib(n-1,b,a+b)

Answer 9

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

nthfib () ниже - прямое решение исходной проблемы (если импорт разрешен)

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

from itertools import imap, islice, repeat

nthfib = lambda n: next(islice((lambda x=[0, 1]: imap((lambda x: (lambda setx=x.__setitem__, x0_temp=x[0]: (x[1], setx(0, x[1]), setx(1, x0_temp+x[1]))[0])()), repeat(x)))(), n-1, None))    

>>> nthfib(1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051
89040387984007925516929592259308032263477520968962323987332247116164299644090653
3187938298969649928516003704476137795166849228875L

from itertools import imap, islice, repeat

fibgen = lambda:(lambda x=[0,1]: imap((lambda x: (lambda setx=x.__setitem__, x0_temp=x[0]: (x[1], setx(0, x[1]), setx(1, x0_temp+x[1]))[0])()), repeat(x)))()

>>> list(islice(fibgen(),12))
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]

Answer 10

Я не знаю, является ли это наиболее питоническим методом, но это лучшее, что я мог бы придумать: ->

Fibonacci = lambda x,y=[1,1]:[1]*x if (x<2) else ([y.append(y[q-1] + y[q-2]) for q in range(2,x)],y)[1]

Приведенный выше код не использует рекурсию, просто список длясохранить значения.