私はプロジェクト オイラー問題に取り組んでいます: フィボナッチ数の偶数の合計に関する問題です。
私のコード:
def Fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return Fibonacci(n-1) + Fibonacci(n-2)
list1 = [x for x in range(39)]
list2 = [i for i in list1 if Fibonacci(i) % 2 == 0]
問題の解決策は、sum(list2) を出力することで簡単に見つけることができます。ただし、私が推測しているlist2を思い付くには多くの時間がかかります。これを速くする方法はありますか？それとも、このままでいいのでしょうか...
(問題: 値が 400 万を超えないフィボナッチ数列の項を考慮して、偶数値の項の合計を見つけます。)
Python は末尾再帰を最適化しないため、ここで紹介するほとんどのソリューションは、が大きすぎるError: maximum recursion depth exceeded in comparison場合(つまり 1000 という意味) で失敗します。n
再帰制限は増やすことができますが、オペレーティング システムのスタック オーバーフローで Python がクラッシュします。
fib_memo/fib_localとfib_lru/のパフォーマンスの違いに注意してくださいfib_local_exc: LRU キャッシュはかなり遅く、完了さえしませんでした。これは、n = ~500 で既に実行時エラーが発生するためです。
import functools
from time import clock
#import sys
#sys.setrecursionlimit()
@functools.lru_cache(None)
def fib_lru(n):
if n < 2:
return n
return fib_lru(n-1) + fib_lru(n-2)
def fib_memo(n, computed = {0: 0, 1: 1}):
if n not in computed:
computed[n] = fib_memo(n-1, computed) + fib_memo(n-2, computed)
return computed[n]
def fib_local(n):
computed = {0: 0, 1: 1}
def fib_inner(n):
if n not in computed:
computed[n] = fib_inner(n-1) + fib_inner(n-2)
return computed[n]
return fib_inner(n)
def fib_local_exc(n):
computed = {0: 0, 1: 1}
def fib_inner_x(n):
try:
computed[n]
except KeyError:
computed[n] = fib_inner_x(n-1) + fib_inner_x(n-2)
return computed[n]
return fib_inner_x(n)
def fib_iter(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
def benchmark(n, *args):
print("-" * 80)
for func in args:
print(func.__name__)
start = clock()
try:
ret = func(n)
#print("Result:", ret)
except RuntimeError as e:
print("Error:", e)
print("Time:", "{:.8f}".format(clock() - start))
print()
benchmark(500, fib_iter, fib_memo, fib_local, fib_local_exc, fib_lru)
結果：
fib_iter
Time: 0.00008168
fib_memo
Time: 0.00048622
fib_local
Time: 0.00044645
fib_local_exc
Time: 0.00146036
fib_lru
Error: maximum recursion depth exceeded in comparison
Time: 0.00112552
n=100k反復ソリューションは断然最速で、 (0.162 秒)の間でもスタックを破損しません。実際、中間のフィボナッチ数は返されません。
偶数番目のフィボナッチ数を計算したい場合は、n次のように反復アプローチを適用できます。
def fib_even_iter(n):
a, b = 0, 1
c = 1
while c < n:
a, b = b, a + b
if a % 2 == 0:
c += 1
return a
または、途中のすべての偶数に興味がある場合は、ジェネレーターを使用します。
def fib_even_gen(n):
a, b = 0, 1
c = 1
yield a
while c < n:
a, b = b, a + b
if a % 2 == 0:
yield a
c += 1
return a
for i, f in enumerate(fib_even_gen(100), 1):
print("{:3d}. {:d}".format(i, f))
結果：
1. 0
2. 2
3. 8
4. 34
5. 144
6. 610
7. 2584
8. 10946
9. 46368
10. 196418
11. 832040
12. 3524578
13. 14930352
14. 63245986
15. 267914296
16. 1134903170
17. 4807526976
18. 20365011074
19. 86267571272
20. 365435296162
21. 1548008755920
22. 6557470319842
23. 27777890035288
24. 117669030460994
25. 498454011879264
26. 2111485077978050
27. 8944394323791464
28. 37889062373143906
29. 160500643816367088
30. 679891637638612258
31. 2880067194370816120
32. 12200160415121876738
33. 51680708854858323072
34. 218922995834555169026
35. 927372692193078999176
36. 3928413764606871165730
37. 16641027750620563662096
38. 70492524767089125814114
39. 298611126818977066918552
40. 1264937032042997393488322
41. 5358359254990966640871840
42. 22698374052006863956975682
43. 96151855463018422468774568
44. 407305795904080553832073954
45. 1725375039079340637797070384
46. 7308805952221443105020355490
47. 30960598847965113057878492344
48. 131151201344081895336534324866
49. 555565404224292694404015791808
50. 2353412818241252672952597492098
51. 9969216677189303386214405760200
52. 42230279526998466217810220532898
53. 178890334785183168257455287891792
54. 757791618667731139247631372100066
55. 3210056809456107725247980776292056
56. 13598018856492162040239554477268290
57. 57602132235424755886206198685365216
58. 244006547798191185585064349218729154
59. 1033628323428189498226463595560281832
60. 4378519841510949178490918731459856482
61. 18547707689471986212190138521399707760
62. 78569350599398894027251472817058687522
63. 332825110087067562321196029789634457848
64. 1409869790947669143312035591975596518914
65. 5972304273877744135569338397692020533504
66. 25299086886458645685589389182743678652930
67. 107168651819712326877926895128666735145224
68. 453973694165307953197296969697410619233826
69. 1923063428480944139667114773918309212080528
70. 8146227408089084511865756065370647467555938
71. 34507973060837282187130139035400899082304280
72. 146178119651438213260386312206974243796773058
73. 619220451666590135228675387863297874269396512
74. 2623059926317798754175087863660165740874359106
75. 11111460156937785151929026842503960837766832936
76. 47068900554068939361891195233676009091941690850
77. 199387062373213542599493807777207997205533596336
78. 844617150046923109759866426342507997914076076194
79. 3577855662560905981638959513147239988861837901112
80. 15156039800290547036315704478931467953361427680642
81. 64202014863723094126901777428873111802307548623680
82. 271964099255182923543922814194423915162591622175362
83. 1152058411884454788302593034206568772452674037325128
84. 4880197746793002076754294951020699004973287771475874
85. 20672849399056463095319772838289364792345825123228624
86. 87571595343018854458033386304178158174356588264390370
87. 370959230771131880927453318055001997489772178180790104
88. 1571408518427546378167846658524186148133445300987550786
89. 6656593304481317393598839952151746590023553382130993248
90. 28197781736352815952563206467131172508227658829511523778
91. 119447720249892581203851665820676436622934188700177088360
92. 505988662735923140767969869749836918999964413630219877218
93. 2143402371193585144275731144820024112622791843221056597232
94. 9079598147510263717870894449029933369491131786514446266146
95. 38461794961234640015759308940939757590587318989278841661816
96. 162926777992448823780908130212788963731840407743629812913410
97. 690168906931029935139391829792095612517948949963798093315456
98. 2923602405716568564338475449381171413803636207598822186175234
99. 12384578529797304192493293627316781267732493780359086838016392
100. 52461916524905785334311649958648296484733611329035169538240802
Time: 0.00698620
これは、最初の 100 個の偶数フィボナッチ数であり、端末への印刷のオーバーヘッドが含まれています (Windows では過小評価されがちです)。
という事実に基づいてfib(n) = fib(n-1)+fib(n-2)、簡単な解決策は次のとおりです。
def fib(n):
if (n <=1):
return(1)
else:
return(fib(n-1)+fib(n-2))
ただし、ここでの問題は、一部の値が複数回計算されるため、非常に非効率的であるということです。その理由は、次のスケッチで確認できます。
基本的に、fib関数を再帰的に呼び出すたびに、それ自体で使用する前のすべてのフィボナッチ数を計算する必要があります。したがって、@kqr の回答によって示されるツリーのすべての葉ノードに表示される必要があるため、最も計算された値は fib(1) になります。このアルゴリズムの複雑さは、ツリーのノード数 ($O(2^n)$) です。
より良い方法は、現在の値と以前の値の 2 つの数値を追跡することです。これにより、各呼び出しで以前の値をすべて計算する必要がなくなります。これはスケッチの 2 番目のアルゴリズムであり、次のように実装できます。
def fib(n):
if (n==0):
return(0,1)
elif (n==1):
return(1,1)
else:
a,b = fib(n-1)
return(b,a+b)
このアルゴリズムの複雑さは線形 $O(n)$ で、いくつかの例は次のようになります。
>>> fib(1)
(1, 1)
>>> fib(2)
(1, 2)
>>> fib(4)
(3, 5)
>>> fib(6)
(8, 13)
偶数のフィボナッチ数の和を求める再帰的な公式があることがわかりました。偶数のフィボナッチ数の合計の数列の n 番目の項は です。S_{n} = 4*S_{n-1} + S_{n-2} + 2 証明は読者に委ねられていますが、1) 偶数の Fibo 数は 3 番目ごとに 1 であることの証明、2) Fibo 数の定義を使用した帰納法による上記の式の証明が含まれます。hereのロジックを使用すると、少しの努力でこれに対する閉形式の式を導き出すことができます。
S_{n} = -1/2 + (1/4 + 3*sqrt(5)/20)*(2+sqrt(5))**n + (1/4 - 3*sqrt(5)/20)*(2-sqrt(5))**n
にもかかわらずsqrt、これは Integral に不可欠であるため、これは以前の回答の便利な関数を使用するか、ルートを正確に処理するnなどのパッケージを使用して便利に計算できます。sympy
import sympy as sp
one = sp.sympify(1) #to force casting to sympy types
k1 = -one/2
k2 = one/4 + 3*sp.sqrt(5)/20
k3 = one/4 - 3*sp.sqrt(5)/20
r1 = one
r2 = 2 + sp.sqrt(5)
r3 = 2 - sp.sqrt(5)
def even_sum_fibo(n):
#get the nth number in the sequence of even sums of Fibonacci numbers. If you want the sum of Fibos up to some number m, use n = m/3 (integer division)
return sp.simplify(k1*r1**n + k2*r2**n + k3*r3**n)
kqrのソリューション nr 2 は私のお気に入りです。
ただし、この特定のケースでは、リスト内包表記内の後続の呼び出しの間にすべての計算が失われています。
list2 = [i for i in list1 if fib(i) % 2 == 0]
、そのため、さらに一歩進んで、次のようにループステップ間でメモ化することにしました。
def cache_fib(ff):
comp = {0: 0, 1: 1}
def fib_cached(n, computed=comp):
return ff(n, computed)
return fib_cached
@cache_fib
def fib(n, computed={0: 0, 1: 1}):
if n not in computed:
computed[n] = fib(n - 1, computed) + fib(n - 2, computed)
return computed[n]
R のソリューション、ベンチマークは 1.9 秒で 1 ～ 1000 番目のフィボナッチ数列を計算します。実際、C++ または Fortran でははるかに高速になります。最初の投稿を書いて以来、私は C++ で同等の関数を作成し、0.0033 秒という驚異的な速さで完了しました。Python でさえ 0.3 秒で完了しました。
#Calculate Fibonnaci Sequence
fib <- function(n){
if(n <= 2)
return(as.integer(as.logical(n)))
k = as.integer(n/2)
a = fib(k + 1)
b = fib(k)
if(n %% 2 == 1)
return(a*a + b*b)
return(b*(2*a - b))
}
#Function to do every fibonacci number up to nmax
doFib <- function(nmax = 25,doPrint=FALSE){
res = sapply(0:abs(nmax),fib)
if(doPrint)
print(paste(res,collapse=","))
return(res)
}
#Benchmark
system.time(doFib(1000))
#user system elapsed
# 1.874 0.007 1.892
ネタバレ注意: プロジェクト オイラーの質問 2 を実行している場合は、自分で問題を解決するまでこれを読まないでください。
閉じた形式の級数加算ベースのアプローチはさておき、これは私が投稿したもののほとんど/すべてよりも効率的であるように思われます.偶数のフィボナッチ数ごとにかなり安価なループ反復が1回しか必要ないため、4,000,000.
def sumOfEvenFibonacciNumbersUpTo(inclusiveLimit):
even = 0
next = 1
sum = 0
while even<=inclusiveLimit:
sum += even
even += next<<1
next = (even<<1)-next
return sum
Haskell 1 ライナー :-
fibs = 0 : (f 1 1) where f a b = a : f b (a+b)
このコードは非常に効率的で、() までのフィボナッチ数を10^10001 秒以内に計算します。このコードは、Project Eulerのこの問題にも役立ちます。
1 つの高速な方法は、fib(n/2) 数を再帰的に計算することです。
fibs = {0: 0, 1: 1}
def fib(n):
if n in fibs: return fibs[n]
if n % 2 == 0:
fibs[n] = ((2 * fib((n / 2) - 1)) + fib(n / 2)) * fib(n / 2)
return fibs[n]
else:
fibs[n] = (fib((n - 1) / 2) ** 2) + (fib((n+1) / 2) ** 2)
return fibs[n]
from time import time
s=time()
print fib(1000000)
print time()-s
これは古い質問であることは知っていますが、とにかくやってみようと思いました。
まず、いくつかの基本事項。3 つおきのフィボナッチ数は偶数です。F(1)+F(2)=F(3)、F(4)+F(5)=F(6) などなので、すべての偶数のフィボナッチ数は、 F(3X)。F(X) までのすべてのフィボナッチ数の合計を見つける簡単な方法は既にあります。答えは F(X+2)-1 です。その項を 2 で割るだけで、答えが得られます。
ここで、フィボナッチを O(log2(X)) 時間で解く方法について少し横道にそれます。ファイは非常に特別な数です。ファイ=(sqrt(5)+1)/2。ファイ^2=1+ファイ。実際、ファイ^X=F(X-1)+F(X)ファイです。高校の代数を思い出すと、Phi^2X=(Phi^X)^2 = (F(X-1)+F(X)Phi)^2 = F(X-1)^2+2F(X-1) )F(X)ファイ+(F(X)^2)(ファイ^2)。Φ^2 はわかっているので、代入して配布します。F(2X-1)+F(2X)ファイ=ファイ^2X=F(X-1)^2+F(X)^2+ファイ(2F(X-1)F(X)+F(X) ^2)。フィボナッチ数はファイを含まない整数であるため、F(2X-1)=F(X-1)^2+F(X)^2 であることがわかります。F(2X+1)=F(X)+F(X+1) という追加の事実により、F(2X)=F(X+1)^2-F(X-1)^2 を求めることができます。さあ、コーディングしましょう！
import math
def fibonacci(x):
a=1 #start at F(-1)
b=0 #start at F(0)
c=1 #start at F(1)
bits=int((math.log2(x)+1)//1) #number of bits in x
for i in range(bits,-1,-1):
#Times 2
d=b*b+a*a
e=c*c-a*a
f=d+e
a=d
b=e
c=f
bit=(x//(2**i))%2
#Plus 1
if bit==1:
a=b
b=c
c=a+b
return b
def fibsum(x):
y=x-(x%3)
return (fibonacci(y+2)-1)//2
print(fibsum(600))
浮動小数点演算を使用しない場合は、平方根を含む方程式を使用してこれを計算できますが、他の方法で係数を追跡します。これにより、O(log n)算術演算 (メモ化の演算とは対照的にO(n log n)) アルゴリズムが得られます。
def rootiply(a1,b1,a2,b2,c):
''' multipy a1+b1*sqrt(c) and a2+b2*sqrt(c)... return a,b'''
return a1*a2 + b1*b2*c, a1*b2 + a2*b1
def rootipower(a,b,c,n):
''' raise a + b * sqrt(c) to the nth power... returns the new a,b and c of the result in the same format'''
ar,br = 1,0
while n != 0:
if n%2:
ar,br = rootiply(ar,br,a,b,c)
a,b = rootiply(a,b,a,b,c)
n /= 2
return ar,br
def fib(k):
''' the kth fibonacci number'''
a1,b1 = rootipower(1,1,5,k)
a2,b2 = rootipower(1,-1,5,k)
a = a1-a2
b = b1-b2
a,b = rootiply(0,1,a,b,5)
# b should be 0!
assert b == 0
return a/2**k/5
if __name__ == "__main__":
assert rootipower(1,2,3,3) == (37,30) # 1+2sqrt(3) **3 => 13 + 4sqrt(3) => 39 + 30sqrt(3)
assert fib(10)==55
遅い回答ですが、参考になるかもしれません
fib_dict = {}
def fib(n):
try:
return fib_dict[n]
except:
if n<=1:
fib_dict[n] = n
return n
else:
fib_dict[n] = fib(n-1) + fib (n-2)
return fib(n-1) + fib (n-2)
print fib(100)
これは、従来の方法よりもはるかに高速です
これは、辞書を使用した最適化されたソリューションです
def Fibonacci(n):
if n<2 : return n
elif not n in fib_dict :
fib_dict[n]= Fibonacci(n-1) + Fibonacci(n-2)
return fib_dict[n]
#dictionary which store Fibonacci values with the Key
fib_dict = {}
print(Fibonacci(440))
Project Euler は、コーディングの練習に最適な場所です。
あなたの質問に来て...
フィボナッチ数列; 最後の数字の前の数字と最後の数字を加算し、結果の合計がシリーズの新しい数字です。
関数を定義しましたが、while ループを使用するのが最善です。
i = 0
x = [0,1,2]
y =[]
n = int(input('upper limit of fibonacci number is '))
while i< n:
z= x[-1]+x[-2]
x.append(z)
if z%2 == 0:
y.append(z)
i = x[-1]
print(i)
print('The sum of even fibbunacci num in given fibonacci number is ',sum(y)+2)
int count=0;
void fibbo(int,int);
void main()
{
fibbo(0,1);
getch();
}
void fibbo(int a,int b)
{
count++;
printf(" %d ",a);
if(count<=10)
fibbo(b,a+b);
else
return;
}