ご存知のように、フィボナッチ数列を生成する最も簡単なアルゴリズムは次のとおりです。
if(n<=0) return 0;
else if(n==1) return 1;
f(n) = f(n-1) + f(n-2);
ただし、このアルゴリズムには繰り返し計算が含まれます。たとえば、f(5) を計算すると、f(4) と f(3) が計算されます。f(4) を計算すると、f(3) と f(2) の両方が再度計算されます。誰かがより時間効率の良い再帰アルゴリズムを教えてくれませんか?
12076 次
9 に答える
2
簡単な方法の 1 つは、再帰的ではなく反復的に計算することです。これにより、線形時間で F(n) が計算されます。
def fib(n):
a,b = 0,1
for i in range(n):
a,b = a+b,a
return a
于 2012-06-07T00:27:46.200 に答える
2
効率的な時間計算量でフィボナッチを計算するためのいくつかの方法について読んだことがありますが、それらのいくつかは次のとおりです-
方法 1 - 動的プログラミング ここでは、サブ構造が一般的に知られているため、ソリューションに直接ジャンプします -
static int fib(int n)
{
int f[] = new int[n+2]; // 1 extra to handle case, n = 0
int i;
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++)
{
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
上記のスペース最適化バージョンは、次のように実行できます-
static int fib(int n)
{
int a = 0, b = 1, c;
if (n == 0)
return a;
for (int i = 2; i <= n; i++)
{
c = a + b;
a = b;
b = c;
}
return b;
}
方法 2- (行列 {{1,1},{1,0}} の累乗を使用)
これは O(n) であり、行列 M = {{1,1},{1,0}} をそれ自体に n 倍する (つまり、power(M, n ) を計算する) 場合、次の事実に依存します。結果の行列の行と列 (0, 0) の要素として (n+1) 番目のフィボナッチ数を取得します。このソリューションには O(n) 時間がかかります。
行列表現は、フィボナッチ数に対して次の閉じた式を与えます: fibonaccimatrix
static int fib(int n)
{
int F[][] = new int[][]{{1,1},{1,0}};
if (n == 0)
return 0;
power(F, n-1);
return F[0][0];
}
/*multiplies 2 matrices F and M of size 2*2, and
puts the multiplication result back to F[][] */
static void multiply(int F[][], int M[][])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
/*function that calculates F[][] raise to the power n and puts the
result in F[][]*/
static void power(int F[][], int n)
{
int i;
int M[][] = new int[][]{{1,1},{1,0}};
// n - 1 times multiply the matrix to {{1,0},{0,1}}
for (i = 2; i <= n; i++)
multiply(F, M);
}
これは、O(Logn) 時間の複雑さで動作するように最適化できます。前の方法でべき乗(M, n)を得るために、再帰的な乗算を行うことができます。
static int fib(int n)
{
int F[][] = new int[][]{{1,1},{1,0}};
if (n == 0)
return 0;
power(F, n-1);
return F[0][0];
}
static void multiply(int F[][], int M[][])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
static void power(int F[][], int n)
{
if( n == 0 || n == 1)
return;
int M[][] = new int[][]{{1,1},{1,0}};
power(F, n/2);
multiply(F, F);
if (n%2 != 0)
multiply(F, M);
}
方法 3 (O(log n) 時間) 以下は、O(log n) 時間で n 番目のフィボナッチ数を見つけるために使用できるもう 1 つの興味深い再帰式です。
n が偶数の場合、k = n/2: F(n) = [2*F(k-1) + F(k)]*F(k)
n が奇数の場合、k = (n + 1)/2 F(n) = F(k)*F(k) + F(k-1)*F(k-1) この式はどのように機能しますか? この式は、上記の行列式から導き出すことができます。フィボナッチマトリックス
行列式を両辺に取ると、(-1)n = Fn+1Fn-1 – Fn2 が得られます。さらに、任意の正方行列 A に対して AnAm = An+m であるため、次の恒等式を導き出すことができます (これらは、次の 2 つの異なる係数から得られます)。行列積)
FmFn + Fm-1Fn-1 = Fm+n-1
n = n+1 を置くことにより、
FmFn+1 + Fm-1Fn = Fm+n
m = n を置く
F2n-1 = Fn2 + Fn-12
F2n = (Fn-1 + Fn+1)Fn = (2Fn-1 + Fn)Fn (出典: Wiki)
式を証明するには、単に次のことを行う必要があります n が偶数の場合、k = n/2 と入力できます n が奇数の場合、k = (n+1)/2 と入力できます
public static int fib(int n)
{
if (n == 0)
return 0;
if (n == 1 || n == 2)
return (f[n] = 1);
// If fib(n) is already computed
if (f[n] != 0)
return f[n];
int k = (n & 1) == 1? (n + 1) / 2
: n / 2;
// Applyting above formula [See value
// n&1 is 1 if n is odd, else 0.
f[n] = (n & 1) == 1? (fib(k) * fib(k) +
fib(k - 1) * fib(k - 1))
: (2 * fib(k - 1) + fib(k))
* fib(k);
return f[n];
}
方法 4 - 数式を使用する この方法では、フィボナッチ数列の n 番目の項の数式を直接実装します。時間 O(1) 空間 O(1) Fn = {[(√5 + 1)/2] ^ n} / √5
static int fib(int n) {
double phi = (1 + Math.sqrt(5)) / 2;
return (int) Math.round(Math.pow(phi, n)
/ Math.sqrt(5));
}
参照: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html
于 2020-05-21T20:43:18.737 に答える
1
ヒント: より迅速に結果を得る方法の 1 つは、Binet の式を使用することです。
Pythonでそれを行う方法は次のとおりです。
from decimal import *
def fib(n):
return int((Decimal(1.6180339)**Decimal(n)-Decimal(-0.6180339)**Decimal(n))/Decimal(2.236067977))
于 2012-06-07T00:21:49.877 に答える
1
結果を保存して使用できます。
public static long[] fibs;
public long fib(int n) {
fibs = new long[n];
return internalFib(n);
}
public long internalFib(int n) {
if (n<=2) return 1;
fibs[n-1] = fibs[n-1]==0 ? internalFib(n-1) : fibs[n-1];
fibs[n-2] = fibs[n-2]==0 ? internalFib(n-2) : fibs[n-2];
return fibs[n-1]+fibs[n-2];
}
于 2013-01-05T08:02:58.933 に答える
0
F(n) = (φ^n)/√5 となり、最も近い整数に丸められます。ここで、φ は黄金比です....
φ^n は O(lg(n)) 時間で計算できるため、F(n) は O(lg(n)) 時間で計算できます。
于 2012-06-13T06:17:24.247 に答える
0
編集:実際には、Hynek Vychodil の回答は私の回答よりも優れていると思いますが、誰かが別の方法を探している場合に備えて、ここに残しておきます。
他の方法はすべて有効だと思いますが、最適ではありません。Binet の式を使用すると、原則として正しい答えが得られますが、最も近い整数に丸めると、n の値が大きい場合に問題が発生します。他のソリューションでは、関数を呼び出すたびに n までの値が不必要に再計算されるため、関数は繰り返し呼び出し用に最適化されていません。
私の意見では、グローバル配列を定義してから、必要に応じて配列に新しい値を追加するのが最善の方法です。Python の場合:
import numpy
fibo=numpy.array([1,1])
last_index=fibo.size
def fib(n):
global fibo,last_index
if (n>0):
if(n>last_index):
for i in range(last_index+1,n+1):
fibo=numpy.concatenate((fibo,numpy.array([fibo[i-2]+fibo[i-3]])))
last_index=fibo.size
return fibo[n-1]
else:
print "fib called for index less than 1"
quit()
当然、n>80 (概算) に対して fib を呼び出す必要がある場合は、Python で簡単に実行できる任意精度の整数を実装する必要があります。
于 2015-04-23T01:54:49.337 に答える
0
// D Programming Language
void vFibonacci ( const ulong X, const ulong Y, const int Limit ) {
// Equivalent : if ( Limit != 10 ). Former ( Limit ^ 0xA ) is More Efficient However.
if ( Limit ^ 0xA ) {
write ( Y, " " ) ;
vFibonacci ( Y, Y + X, Limit + 1 ) ;
} ;
} ;
// Call As
// By Default the Limit is 10 Numbers
vFibonacci ( 0, 1, 0 ) ;
于 2014-11-22T20:21:20.390 に答える
-1
これはより速く実行されます、O(n)
def fibo(n):
a, b = 0, 1
for i in range(n):
if i == 0:
print(i)
elif i == 1:
print(i)
else:
temp = a
a = b
b += temp
print(b)
n = int(input())
fibo(n)
于 2020-10-02T07:48:16.753 に答える