47

適切な関数構造で書くことに問題がないことは知っていますが、ほとんどの Pythonic 方法で 1 行で n 番目のフィボナッチ数を見つける方法を知りたいです。

私はそのコードを書きましたが、最善の方法とは思えませんでした:

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

どうすればより良く、より簡単になるでしょうか?

4

23 に答える 23

61 
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 などであることに注意してください。)

(注: reducePython 2.7 では組み込みですが、Python 3 では組み込みではありません。Python 3 で実行する必要がありますfrom functools import reduce。)

于 2011-02-08T17:15:39.287 に答える
49

めったに見られないトリックは、ラムダ関数がそれ自体を再帰的に参照できることです。

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
于 2011-02-08T17:05:52.447 に答える
13

私は最近、行列の乗算を使用してフィボナッチ数を生成することについて学びました。これは非常にクールでした。あなたは基本行列を取ります：

[1, 1]
[1, 0]

それをN回掛けて、次を取得します。

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

今朝、シャワーの壁の湯気で落書きをしていて、2 番目の行列から始めて、それ自体を N/2 回乗算し、次に N を使用して最初の行列からインデックスを選択することで、実行時間を半分に短縮できることに気付きました。行/列。

少し絞って、1行にまとめました。

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]
于 2013-03-13T18:05:30.150 に答える
12

これは、整数演算を使用するフィボナッチ数列の閉じた式であり、非常に効率的です。

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/フィボナッチ/ )

于 2016-05-29T11:22:40.097 に答える
10

これは、非再帰的 (匿名) のメモ化ワンライナーです。

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]
于 2011-02-08T17:26:15.640 に答える
10

「最もPython的な方法」がエレガントで効果的であると考える場合：

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

勝ちます。黄金比で結果を近似することで O(1) の問題をうまく解決できるのに、なぜ非効率的なアルゴリズムを使用するのでしょうか (そして、メモ化を使用し始めると、ワンライナーのことを忘れることができます)。実際には、明らかに次の形式で記述します。

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

より効率的で、はるかに理解しやすくなります。

于 2011-02-08T17:14:11.247 に答える
7 
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 ...

于 2011-04-18T00:25:52.640 に答える
3

Mark Byersの回答からヒントを得た別の例：

fib = lambda n,a=0,b=1: a if n<=0 else fib(n-1,b,a+b)
于 2011-02-08T17:30:42.380 に答える
2 
def fib(n):
    x =[0,1]
    for i in range(n):
        x=[x[1],x[0]+x[1]]
    return x[0]

Jason S からヒントを得て、私のバージョンの方が理解が深まっていると思います。

于 2014-01-14T10:40:20.077 に答える
2

これは、再帰を使用せず、シーケンス履歴全体ではなく、最後の 2 つの値のみをメモする実装です。

以下の 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]
于 2011-06-10T22:23:39.660 に答える
1

リスト内包表記を使用しないのはなぜですか?

from math import sqrt, floor
[floor(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))) for n in range(100)]

数学のインポートはありませんが、あまりきれいではありません:

[int(((1+(5**0.5))**n-(1-(5**0.5))**n)/(2**n*(5**0.5))) for n in range(100)]
于 2017-01-17T21:22:28.700 に答える
1

私の2セント

# One Liner
def nthfibonacci(n):
    return long(((((1+5**.5)/2)**n)-(((1-5**.5)/2)**n))/5**.5)

また

# Steps
def nthfibonacci(nth):
    sq5 = 5**.5
    phi1 = (1+sq5)/2
    phi2 = -1 * (phi1 -1)
    n1 = phi1**(nth+1)
    n2 = phi2**(nth+1)
    return long((n1 - n2)/sq5)
于 2014-09-25T10:26:13.343 に答える
1

この問題を解決するために、Stackoverflow Single Statement Fibonacciの同様の質問に触発され、フィボナッチ数列のリストを出力できるこの単一行関数を取得しました。ただし、これは Python 2 スクリプトであり、Python 3 ではテストされていません。

(lambda n, fib=[0,1]: fib[:n]+[fib.append(fib[-1] + fib[-2]) or fib[-1] for i in range(n-len(fib))])(10)

このラムダ関数を変数に割り当てて再利用します。

fib = (lambda n, fib=[0,1]: fib[:n]+[fib.append(fib[-1] + fib[-2]) or fib[-1] for i in range(n-len(fib))])
fib(10)

出力はフィボナッチ数列のリストです:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
于 2013-06-03T01:30:17.877 に答える
0

再帰を使用した単純なフィボナッチ数ジェネレーター

fib = lambda x: 1-x if x < 2 else  fib(x-1)+fib(x-2)
print fib(100)

これは、私のコンピューターで計算するのに永遠にかかりますfib(100)。

閉じた形式のフィボナッチ数もあります。

fib = lambda n: int(1/sqrt(5)*((1+sqrt(5))**n-(1-sqrt(5))**n)/2**n)
print fib(50)

これは、精度の問題により、最大 72 個の数値までほぼ機能します。

于 2015-06-08T11:14:00.047 に答える
0

ここに私がそれを行う方法がありますが、関数はリストの内包線部分にNoneを返し、内部にループを挿入できるようにします..したがって、基本的には、2つの要素を超えるリスト内にfib seqの新しい要素を追加します

>>f=lambda list,x :print('The list must be of 2 or more') if len(list)<2 else [list.append(list[-1]+list[-2]) for i in range(x)]
>>a=[1,2]
>>f(a,7)
于 2016-05-29T09:54:20.403 に答える
0

論理演算子を使用したラムダ

fibonacci_oneline = lambda n = 10, out = []: [ out.append(i) or i if i <= 1 else out.append(out[-1] + out[-2]) or out[-1] for i in range(n)]
于 2016-03-09T07:10:27.040 に答える