m = 2
n =20
a,b = m,0
fib = [m]
while a <= n:
fib.append(a)
a,b = a+b, a
したがって、 から までの 2 つの変数が与えられた場合、 からm
までを含む (ただし、超えることはできません)n (and m < n)
フィボナッチ数列のすべての数値を含むリストを作成する必要があります。例: ifとthen should be .m
n
m = 2
n = 20
fib
[2,3,5,8,13]
途中でフィボナッチ数列を開始する方法がわからないので、考えられる最善の方法は、後で結果をフィルタリングすることです。
def f(low, high):
fib = [0]
a, b = 1, 0
while a <= n:
fib.append(a)
a,b = a+b, a
return filter(lambda x: x >= low and x =< high, fib)
フィボナッチ コードは自明です。ここで目にする新しいものは ですfilter
。これは、関数f
と iterableを取り、 trueでx
ある要素のすべてを含む新しい iterable を返します。x
f(x)
def fib(m,n):
a,b = 1,1
while a < m:
a,b = b, a+b
answer = [a]
while b < n:
a,b = b, a+b
answer.append(a)
return answer
In [2040]: fib(2,20)
Out[2040]: [2, 3, 5, 8, 13]
(nm) が比較的小さいと仮定すると、対数順序の解を得るために考慮すべき副問題がいくつかあります。(nm) が比較的大きくなる可能性がある場合は、すべての結果を事前に計算し、単純にバイナリ検索を実行するのが最善です。
最初の問題では、( http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form )を使用して i 番目のフィボナッチを見つけることができます。
2 番目の問題はバイナリ検索を使用して解決でき、最初の方法を使用してフィボナッチ数 >= m を見つけます。jがわかると、対数時間でj+1番目のフィボナッチ数を見つけることができ、これらを使用して <=n の他のすべての数を単純に生成できます。
私はグーグルでフィボナッチの第n項の式を見つけましたここ
したがって、コードは次のようになります。
def fibn(n):
Phi = (1+math.sqrt(5))/2
phi = (1-math.sqrt(5))/2
return round((math.pow(Phi, n) - math.pow(phi, n))/math.sqrt(5))
>>> fibn(0)
0.0
>>> fibn(1)
1.0
>>> fibn(2)
1.0
>>> fibn(3)
2.0
>>> fibn(4)
3.0
>>> fibn(5)
5.0
>>> fibn(6)
8.0
>>> fibn(7)
13.0
>>> fibn(8)
21.0
>>> fibn(9)
34.0
>>> fibn(10)
55.0
m = int(raw_input("Enter the start number : "))
n = int(raw_input("Enter the end number : "))
def fib(i):
if i == 0: return 0
elif i == 1: return 1
else: return f(i-1)+f(i-2)
print map(fib, range(m, n))
これがあなたが必要とするものであることを願っています。
フィボナッチ数を再帰的に計算したり、すべての数をリストに入れたりするのは簡単で明確です。ただし、数が多すぎる場合は、適切ではありません。ここにコードがあります、ところで
def main():
print fibo(100,600)
def fibo(m,n):
f0=2
f1=3
while f1<m:
tmp=f1
f1=f0+f1
f0=tmp
res=[f0]
while f1<n:
res.append(f1)
f1=res[-2]+res[-1]
return res[1:];
if __name__ == '__main__':
main()
ジェネレーターの使用:
import os,sys
def fib(num):
a=0
b=1
while 1:
a,b =b, b+a
yield a
low=2
high=200
for i in fib(range(1)):
if i <= high and i >= low :
print i
elif i > high:
break
O/P 2 3 5 8 13 21 34 55 89 144
次のようなことができます。
def fibs(low,high):
a, b = 0, 1
while 1:
a, b = b, a+b
if low <= a:
if a <= high:
yield a
else:
break
あなたはそれを次のように使うことができます
>>> for num in fibs(2,15):
... print num
...
2
3
5
8
13
しかし、フィボナッチ数の公式に頼らず、適切な丸めに頼らなければ、最初の数を計算せずに数をnth
取得する方法はありません。 nth
n-1
したがって、数式を使用したくない場合は、フィボナッチ数のリストを保持し、それを使用するのがlow
おそらく最善でしょうhigh
。不足している値を計算します。high > fib_nums[-1]
fib_nums[-1]
fib_nums[-2]
b
a