1000000 などの非常に大きな値の n に対して、フィボナッチ数列の n 番目の項をどのように見つけることができるか疑問に思っていましたfib(n)=fib(n-1)+fib(n-2)。
グーグルで調べたところ、Binetの式について知りましたが、ここで言われているように、n> 79の値には適切ではありません
素数を見つけるのと同じように、そうするアルゴリズムはありますか?
質問する
92576 次
23 に答える
62
行列累乗法（線形再帰法）を使用できます。詳細な説明と手順については、このブログを参照してください。実行時間はO (log n ) です。
これを行うより良い方法はないと思います。
于 2013-02-02T12:08:14.533 に答える
39
メモ化を使用すると、時間を大幅に節約できます。たとえば、次の2つのバージョン（JavaScript）を比較します。
バージョン1：通常の再帰
var fib = function(n) {
return n < 2 ? n : fib(n - 1) + fib(n - 2);
};
バージョン2：メモ化
A.アンダースコアライブラリを利用する
var fib2 = _.memoize(function(n) {
return n < 2 ? n : fib2(n - 1) + fib2(n - 2);
});
B.ライブラリフリー
var fib3 = (function(){
var memo = {};
return function(n) {
if (memo[n]) {return memo[n];}
return memo[n] = (n <= 2) ? 1 : fib3(n-2) + fib3(n-1);
};
})();
最初のバージョンはn=50（Chromeの場合）で3分以上かかりますが、2番目のバージョンは5ミリ秒未満しかかかりません！これはjsFiddleで確認できます。
バージョン1の時間計算量が指数関数的（ O（2 N / 2））であるのに対し、バージョン2の時間計算量は線形（O（N ））であることがわかっていれば、それほど驚くことではありません。
バージョン3：行列の乗算
さらに、 N個の行列の乗算を計算することにより、時間計算量をO（log（N））に削減することもできます。
ここで、 Fnはフィボナッチ数列のn番目の項を示します。
于 2013-02-02T12:55:56.203 に答える
14
反復 ID http://en.wikipedia.org/wiki/Fibonacci_number#Other_identitiesnを使用して、段階的に - 番目の番号を見つけlog(n)ます。そのためには、任意精度の整数を使用する必要があります。または、各ステップで剰余演算を使用して、ある係数を法として正確な答えを計算できます。
に注目すると、各ステップでを 3 で割り、剰余値に従って適切な式を選択する2 つの連続するフィボナッチ数を計算する単一再帰関数を3n+3 == 3(n+1)考案できます。IOW は 1 つのステップでペアからペアを計算するため、二重再帰はなく、メモ化も必要ありません。n@(3n+r,3n+r+1), r=0,1,2@(n,n+1)
Haskell コードはこちらです。
F(2n-1) = F(n-1)^2 + F(n)^2 === a' = a^2 + b^2
F(2n) = 2 F(n-1) F(n) + F(n)^2 === b' = 2ab + b^2
より高速なコードにつながるようです。「Lucas sequence identities」を使用 するのが最も速いかもしれません (これは、この実装を引用しているユーザー: primoによるものです)。
于 2013-02-02T12:26:50.260 に答える
6
ほとんどの人は、N 番目のフィボナッチ数の発見を説明するリンクを既に提供しています。Power アルゴリズムは小さな変更で同じように機能します。
とにかく、これは私の O(log N) ソリューションです。
package algFibonacci;
import java.math.BigInteger;
public class algFibonacci {
// author Orel Eraki
// Fibonacci algorithm
// O(log2 n)
public static BigInteger Fibonacci(int n) {
int num = Math.abs(n);
if (num == 0) {
return BigInteger.ZERO;
}
else if (num <= 2) {
return BigInteger.ONE;
}
BigInteger[][] number = { { BigInteger.ONE, BigInteger.ONE }, { BigInteger.ONE, BigInteger.ZERO } };
BigInteger[][] result = { { BigInteger.ONE, BigInteger.ONE }, { BigInteger.ONE, BigInteger.ZERO } };
while (num > 0) {
if (num%2 == 1) result = MultiplyMatrix(result, number);
number = MultiplyMatrix(number, number);
num/= 2;
}
return result[1][1].multiply(BigInteger.valueOf(((n < 0) ? -1:1)));
}
public static BigInteger[][] MultiplyMatrix(BigInteger[][] mat1, BigInteger[][] mat2) {
return new BigInteger[][] {
{
mat1[0][0].multiply(mat2[0][0]).add(mat1[0][1].multiply(mat2[1][0])),
mat1[0][0].multiply(mat2[0][1]).add(mat1[0][1].multiply(mat2[1][1]))
},
{
mat1[1][0].multiply(mat2[0][0]).add(mat1[1][1].multiply(mat2[1][0])),
mat1[1][0].multiply(mat2[0][1]).add(mat1[1][1].multiply(mat2[1][1]))
}
};
}
public static void main(String[] args) {
System.out.println(Fibonacci(8181));
}
}
于 2013-02-02T13:23:22.973 に答える
4
フィボナッチ数列の任意に大きな要素を計算するには、閉じた形式のソリューション (Binet の公式) を使用し、任意精度の数学を使用して、答えを計算するのに十分な精度を提供する必要があります。
ただし、再帰関係を使用するだけで、50 番目の項を計算するのに 2 ～ 3 分かかることはありません。最新のマシンでは、数秒以内に数十億の項を計算できるはずです。完全再帰式を使用しているように聞こえますが、これは再帰計算の組み合わせ爆発につながります。単純な反復式ははるかに高速です。
つまり、再帰的な解決策は次のとおりです。
int fib(int n) {
if (n < 2)
return 1;
return fib(n-1) + fib(n-2)
}
...座って、スタック オーバーフローを監視します。
反復ソリューションは次のとおりです。
int fib(int n) {
if (n < 2)
return 1;
int n_1 = 1, n_2 = 1;
for (int i = 2; i <= n; i += 1) {
int n_new = n_1 + n_2;
n_1 = n_2;
n_2 = n_new;
}
return n_2;
}
n_new基本的に、前の項n_1およびから次の項を計算n_2し、次の反復のためにすべての項を「シャッフル」していることに注意してください。の値に線形の実行時間では、最新のギガヘルツ マシンでは、数十億 (中間変数の整数オーバーフローのかなり後) でn数秒の問題です。n
于 2013-02-02T12:00:01.300 に答える
3
フィボナッチ数を計算する場合、再帰アルゴリズムは最悪の方法の 1 つです。前の 2 つの数値を for サイクル (反復法と呼ばれる) で加算するだけで、50 番目の要素を計算するのに 2 ～ 3 分かかりません。
于 2013-02-02T12:01:49.490 に答える
3
これは、O(log(n)) で n 番目のフィボナッチ数を計算する Python バージョンです。
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
def matmul(M1, M2):
a11 = M1[0][0]*M2[0][0] + M1[0][1]*M2[1][0]
a12 = M1[0][0]*M2[0][1] + M1[0][1]*M2[1][1]
a21 = M1[1][0]*M2[0][0] + M1[1][1]*M2[1][0]
a22 = M1[1][0]*M2[0][1] + M1[1][1]*M2[1][1]
return [[a11, a12], [a21, a22]]
def matPower(mat, p):
if p == 1:
return mat
m2 = matPower(mat, p//2)
if p % 2 == 0:
return matmul(m2, m2)
else:
return matmul(matmul(m2, m2),mat)
Q = [[1,1],[1,0]]
q_final = matPower(Q, n-1)
return q_final[0][0]
于 2017-11-02T13:23:53.067 に答える
2
まず、既知の最大のフィボナッチ項から最高項のアイデアを形成できます。再帰的なフィボナッチ関数のプレゼンテーションのステップ実行も参照してください。このテーマに関する興味深いアプローチは、この記事にあります。また、世界で最悪のアルゴリズムでそれについて読んでみてください。.
于 2013-02-02T13:56:53.263 に答える
2
UVA の問題を解決しました: 495 - フィボナッチ フリーズ
5000 番目までのすべてのフィボナッチ数を生成し、指定された入力 (1 番目から 5000 番目の範囲) の出力を出力します。
ランタイム 00.00 秒で受け入れられます。
5000 のフィボナッチ数は次のとおりです。
3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125
#include<stdio.h>
#include<string.h>
#define LIMIT 5001
#define MAX 1050
char num[LIMIT][MAX];
char result[MAX];
char temp[MAX];
char* sum(char str1[], char str2[])
{
int len1 = strlen(str1);
int len2 = strlen(str2);
int minLen, maxLen;
int i, j, k;
if (len1 > len2)
minLen = len2, maxLen = len1;
else
minLen = len1, maxLen = len2;
int carry = 0;
for (k = 0, i = len1 - 1, j = len2 - 1; k<minLen; k++, i--, j--)
{
int val = (str1[i] - '0') + (str2[j] - '0') + carry;
result[k] = (val % 10) + '0';
carry = val / 10;
}
while (k < len1)
{
int val = str1[i] - '0' + carry;
result[k] = (val % 10) + '0';
carry = val / 10;
k++; i--;
}
while (k < len2)
{
int val = str2[j] - '0' + carry;
result[k] = (val % 10) + '0';
carry = val / 10;
k++; j--;
}
if (carry > 0)
{
result[maxLen] = carry + '0';
maxLen++;
result[maxLen] = '\0';
}
else
{
result[maxLen] = '\0';
}
i = 0;
while (result[--maxLen])
{
temp[i++] = result[maxLen];
}
temp[i] = '\0';
return temp;
}
void generateFibonacci()
{
int i;
num[0][0] = '0'; num[0][1] = '\0';
num[1][0] = '1'; num[1][1] = '\0';
for (i = 2; i <= LIMIT; i++)
{
strcpy(num[i], sum(num[i - 1], num[i - 2]));
}
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int N;
generateFibonacci();
while (scanf("%d", &N) == 1)
{
printf("The Fibonacci number for %d is %s\n", N, num[N]);
}
return 0;
}
于 2016-05-04T06:40:28.400 に答える
1
Python でのよりエレガントなソリューション
def fib(n):
if n == 0:
return 0
a, b = 0, 1
for i in range(2, n+1):
a, b = b, a+b
return b
于 2014-02-14T11:09:46.663 に答える
0
3500 番目のフィボナッチ数を計算するための C 言語のソース コードがあります:- 詳細については、こちらをご覧ください。
http://codingloverlavi.blogspot.in/2013/04/fibonacci-series.html
Cのソースコード:-
#include<stdio.h>
#include<conio.h>
#define max 2000
int arr1[max],arr2[max],arr3[max];
void fun(void);
int main()
{
int num,i,j,tag=0;
clrscr();
for(i=0;i<max;i++)
arr1[i]=arr2[i]=arr3[i]=0;
arr2[max-1]=1;
printf("ENTER THE TERM : ");
scanf("%d",&num);
for(i=0;i<num;i++)
{
fun();
if(i==num-3)
break;
for(j=0;j<max;j++)
arr1[j]=arr2[j];
for(j=0;j<max;j++)
arr2[j]=arr3[j];
}
for(i=0;i<max;i++)
{
if(tag||arr3[i])
{
tag=1;
printf("%d",arr3[i]);
}
}
getch();
return 1;
}
void fun(void)
{
int i,temp;
for(i=0;i<max;i++)
arr3[i]=arr1[i]+arr2[i];
for(i=max-1;i>0;i--)
{
if(arr3[i]>9)
{
temp=arr3[i];
arr3[i]%=10;
arr3[i-1]+=(temp/10);
}
}
}
于 2013-05-03T08:44:06.090 に答える
0
フィボナッチ数の計算 (Haskell を使用):
バージョン 1 : 定義をコードに直接変換 (非常に遅いバージョン):
fib :: Integer -> Integer
fib 0 = 1
fib 1 = 1
fib n =
fib (n - 1) + fib (n - 2)
バージョン 2 : F_{n - 1}とF_{n - 2} (高速バージョン)を計算するために行った作業を使用します。
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fibs !! nwhere nis the indexを実行するだけで、n 番目のフィボナッチを取得できます。
バージョン 3 : 行列乗算法を使用します。(さらに高速なバージョン):
-- declaring a matrix
data Matrix = Matrix
( (Integer, Integer)
, (Integer, Integer)
)
deriving (Show, Eq)
-- creating it an instance of Num
-- so that if we implement (*) we get (^) for free
instance Num Matrix where
(*) = mMult
-- don't need these
(+) = undefined
negate = undefined
fromInteger = undefined
abs = undefined
signum = undefined
-- 2-d matrix multiplication
mMult :: Matrix -> Matrix -> Matrix
mMult (Matrix ((a11, a12), (a21, a22))) (Matrix ((b11, b12), (b21, b22))) =
Matrix
( (a11 * b11 + a12 * b21, a11 * b12 + a12 * b22)
, (a21 * b11 + a22 * b21, a21 * b12 + a22 * b22)
)
-- base matrix for generating fibonacci
fibBase :: Matrix
fibBase =
Matrix ((1,1), (1,0))
-- get the large fibonacci numbers
fastFib :: Int -> Integer
fastFib n =
let
getNth (Matrix ((_, a12), _)) = a12
in
getNth (fibBase ^ n)
于 2016-08-13T16:50:16.070 に答える
0
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
const long long int MAX = 10000000;
// Create an array for memoization
long long int f[MAX] = {0};
// Returns n'th fuibonacci number using table f[]
long long int fib(int n)
{
// Base cases
if (n == 0)
return 0;
if (n == 1 || n == 2)
return (f[n] = 1);
if (f[n])
return f[n];
long long int k = (n & 1)? (n+1)/2 : n/2;
f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1)) %MOD
: ((2*fib(k-1) + fib(k))*fib(k))%MOD;
return f[n];
}
int main()
{
long long int n = 1000000;
printf("%lld ", fib(n));
return 0;
}
時間計算量: 再帰呼び出しごとに問題を半分に分割するため、O(Log n)。
于 2016-06-28T18:39:46.490 に答える
0
これは短いpythonコードで、7桁までうまく機能します。3要素の配列が必要です
def fibo(n):
i=3
l=[0,1,1]
if n>2:
while i<=n:
l[i%3]= l[(i-1) % 3] + l[(i-2) % 3]
i+=1
return l[n%3]
于 2013-08-26T18:52:04.667 に答える
-1
C# を使用している場合は、Lync と BigInteger をご覧ください。1000000 (最初の 1000000 をスキップしたため、実際には 1000001) でこれを試したところ、2 分 (00:01:19.5765) 未満でした。
public static IEnumerable<BigInteger> Fibonacci()
{
BigInteger i = 0;
BigInteger j = 1;
while (true)
{
BigInteger fib = i + j;
i = j;
j = fib;
yield return fib;
}
}
public static string BiggerFib()
{
BigInteger fib = Fibonacci().Skip(1000000).First();
return fib.ToString();
}
于 2014-08-12T21:44:40.900 に答える
-1
この JavaScript 実装は nthFibonacci(1200) を問題なく処理します:
var nthFibonacci = function(n) {
var arr = [0, 1];
for (; n > 1; n--) {
arr.push(arr.shift() + arr[0])
}
return arr.pop();
};
console.log(nthFibonacci(1200)); // 2.7269884455406272e+250
于 2015-03-01T02:01:50.977 に答える
-1
参考までに：
次の式は正常に機能しているように見えますが、使用される数値の正確さに依存します-
[((1+√5)/2)ⁿ- ((1-√5)/2)ⁿ]/√5
注:より正確にするために、数字を四捨五入しないでください。
JS サンプル コード:
let n = 74,
const sqrt5 = Math.sqrt(5);
fibNum = Math.round((Math.pow(((1+sqrt5)/2),n)- Math.pow(((1-sqrt5)/2),n))/sqrt5) ;
Number Precisionに従って、n=74までの Chrome コンソールで正常に動作します。
どんな提案もお待ちしております！
別の解決策
手順に従います-
- フィボナッチ数列のインデックスと値、および過去の値のセットを一定間隔で作成します。たとえば、各 50 または各 100。
- step-1
nのセットから目的の数値の最も近い下位インデックスを見つけます。 - 後続の各値に前の値を追加することにより、従来の方法で続行します。
注:良くないように思えますが、時間の複雑さを本当に気にしている場合は、このソリューションがヒットします。最大反復回数は、 step-1の間隔と等しくなります。
結論：
- フィボナッチ数は黄金比と強く関係しています: Binet の公式は n 番目のフィボナッチ数を n と黄金比で表し、n が増加するにつれて連続する 2 つのフィボナッチ数の比が黄金比になる傾向があることを意味します。
- 純粋数学では、Binet の公式から毎回正確な結果が得られます。実際のコンピューティングでは、必要な精度が使用される精度を超えるため、エラーが発生します。すべての実際のソリューションには、ある時点で精度を超えるという同じ問題があります。
于 2019-03-01T06:43:50.807 に答える
-1
私はプログラムをしました。値を計算するのにそれほど時間はかかりませんが、表示できる最大項は 1477 番目です (double の最大範囲のため)。結果はほぼ瞬時に表示されます。シリーズは0から始まります。改善が必要な場合は、お気軽に編集してください。
#include<iostream>
using namespace std;
void fibseries(long int n)
{
long double x=0;
double y=1;
for (long int i=1;i<=n;i++)
{
if(i%2==1)
{
if(i==n)
{
cout<<x<<" ";
}
x=x+y;
}
else
{
if(i==n)
{
cout<<x<<" ";
}
y=x+y;
}
}
}
main()
{
long int n=0;
cout<<"The number of terms ";
cin>>n;
fibseries(n);
return 0;
}
于 2017-06-04T03:50:16.670 に答える