找出第n个斐波纳契数字为非常大的“n”
我想知道如何find斐波纳契数列的第n项来表示一个非常大的n值，例如1000000.使用等级recursion方程fib(n)=fib(n-1)+fib(n-2) ，find第50个学期需要2-3分钟！
Googlesearch后，我开始了解Binet的公式，但是这里不适合n> 79的值
有没有像我们一样寻找素数的algorithm呢？
您可以使用matrix求幂法（线性递推法）。 你可以在这个博客中find详细的解释和程序。 运行时间是O （log n ）。
我不认为有这样做的更好的方法。
使用记忆function可以节省很多时间。 例如，比较以下两个版本（在JavaScript中）：
版本1 ：正常recursion
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分钟，而第二个版本只需要不到5ms！ 你可以在jsFiddle中检查这个。
如果我们知道版本1的时间复杂度是指数（ O （2 N / 2 ）），而版本2是线性的（ O （ N ）），这并不奇怪。
版本3 ：matrix乘法
而且，通过计算N个matrix的乘法，我们甚至可以把时间复杂度降低到O （log（ N ））。
其中F n表示斐波纳契数列的第n项。
使用重复标识http://en.wikipedia.org/wiki/Fibonacci_number#Other_identities在;log(n)步骤中查找第n个数字。 你将不得不使用任意的精度整数。 或者，您可以通过在每个步骤中使用模块化algorithm来计算精确的答案。
注意到3n+3 == 3(n+1) ，我们可以devise一个单recursion函数来计算两个连续的斐波纳契数，每一步除以3，并根据余数select合适的公式。 IOW从一对@(n,n+1)中计算一对@(3n+r,3n+r+1), r=0,1,2 ，所以没有双recursion，不需要记忆。
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
似乎导致更快的代码。 使用“卢卡斯序列身份”可能是最快的（ 这是由于用户： primo ，谁引用这个实现 ）。
大多数人已经给你链接，解释了第N个斐波纳契数的发现，顺便说一下，Poweralgorithm和小的变化一样工作。
反正这是我的O（日志N）解决scheme。
public class algFibonacci { // author Orel Eraki // Fibonacci algorithm // O(log2 n) public static int Fibonacci(int n) { int num = Math.abs(n); if (num == 0) { return 0; } else if (num <= 2) { return 1; } int[][] number = { { 1, 1 }, { 1, 0 } }; int[][] result = { { 1, 1 }, { 1, 0 } }; while (num > 0) { if (num%2 == 1) result = MultiplyMatrix(result, number); number = MultiplyMatrix(number, number); num/= 2; } return result[1][1]*((n < 0) ? -1:1); } public static int[][] MultiplyMatrix(int[][] mat1, int[][] mat2) { return new int[][] { { mat1[0][0]*mat2[0][0] + mat1[0][1]*mat2[1][0], mat1[0][0]*mat2[0][1] + mat1[0][1]*mat2[1][1] }, { mat1[1][0]*mat2[0][0] + mat1[1][1]*mat2[1][0], mat1[1][0]*mat2[0][1] + mat1[1][1]*mat2[1][1] } }; } public static void main(String[] args) { System.out.println(Fibonacci(-8)); } }
为了计算斐波纳契数，recursionalgorithm是最糟糕的方法之一。 通过简单地在一个for循环中添加前两个数字（称为迭代方法）将不需要2-3分钟，来计算第50个元素。
为了计算斐波那契数列的任意大的元素，你将不得不使用封闭forms的解决scheme-Binet的公式，并使用任意精度的math来提供足够的精度来计算答案。
然而，只要使用recursion关系， 就不需要2-3分钟来计算第50期 – 在任何现代机器上，您都应该能够在几秒钟内计算出几十亿的期限。 这听起来像是在使用完全recursion公式，这会导致recursion计算的组合式爆炸。 简单的迭代公式要快得多。
即：recursion解决scheme是：
int fib(int n) { if (n < 2) return 1; return fib(n-1) + fib(n-2) }
…并坐下来看堆栈溢出。
迭代解决scheme是：
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_1和n_2项计算下一项n_new ，然后在下一次迭代中“洗牌”所有项。 对于n的运行时间是线性的，对于现代gigahertz机器来说，数十亿（在中间variables的整数溢出之后） n是几秒钟的问题。
首先，你可以从最大的已知斐波纳契项形成一个最高项的概念 。 也看到recursion斐波那契函数的演示 。 这篇文章是关于这个主题的感兴趣的方法。 另外，尝试阅读世界上最糟糕的algorithm呢？ 。
我有一个在C源代码来计算甚至第3500次斐波那奇数： – 更多细节访问
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); } } }
我解决了一个UVA问题：495 – 斐波纳契冷冻
它生成所有斐波纳契数字5000th和打印输出给定input（范围第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; }
这里有一个Python版本来计算O（log（n））中的第n个斐波那契数
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]
这里是一个简短的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]
如果您使用的是C＃，请查看Lync和BigInteger。 我尝试了1000000（实际上是1000001，因为我跳过了第一个1000000），并且低于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(); }
在Python中更优雅的解决scheme
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
#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），因为我们在每个recursion调用中将问题分成一半。
我已经写了一个小的代码来计算斐波那契数量大于会话recursion的方式。
我正在使用记忆技术来获取最后的斐波纳契数，而不是重新计算它。
public class FabSeries { private static Map<BigInteger, BigInteger> memo = new TreeMap<>(); public static BigInteger fabMemorizingTech(BigInteger n) { BigInteger ret; if (memo.containsKey(n)) return memo.get(n); else { if (n.compareTo(BigInteger.valueOf(2)) <= 0) ret = BigInteger.valueOf(1); else ret = fabMemorizingTech(n.subtract(BigInteger.valueOf(1))).add( fabMemorizingTech(n.subtract(BigInteger.valueOf(2)))); memo.put(n, ret); return ret; } } public static BigInteger fabWithoutMemorizingTech(BigInteger n) { BigInteger ret; if (n.compareTo(BigInteger.valueOf(2)) <= 0) ret = BigInteger.valueOf(1); else ret = fabWithoutMemorizingTech(n.subtract(BigInteger.valueOf(1))).add( fabWithoutMemorizingTech(n.subtract(BigInteger.valueOf(2)))); return ret; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.println("Enter Number"); BigInteger num = scanner.nextBigInteger(); // Try with memorizing technique Long preTime = new Date().getTime(); System.out.println("Stats with memorizing technique "); System.out.println("Fibonacci Value : " + fabMemorizingTech(num) + " "); System.out.println("Time Taken : " + (new Date().getTime() - preTime)); System.out.println("Memory Map: " + memo); // Try without memorizing technique.. This is not responsive for large // value .. can 50 or so.. preTime = new Date().getTime(); System.out.println("Stats with memorizing technique "); System.out.println("Fibonacci Value : " + fabWithoutMemorizingTech(num) + " "); System.out.println("Time Taken : " + (new Date().getTime() - preTime)); } }
input号码
40
统计与记忆技术
斐波纳契值：102334155
所用时间：5
存储器映射：{1 = 1,2 = 1,3 = 2,4 = 3,5 = 5,6 = 8,7 = 13,8 = 21,9 = 34,10 = 55,11 = 89,12 = 144,13 = 233,14 = 377,15 = 610,16 = 987,17 = 1597,18 = 2584,19 = 4181,20 = 6765,21 = 10946,22 = 17711,23 = 28657,24 = 46368， 25 = 75025,26 = 121393,27 = 196418,28 = 317811,29 = 514229,30 = 832040,31 = 1346269,32 = 2178309,33 = 3524578,34 = 5702887,35 = 9227465,36 = 14930352,37 = 24157817，38 = 39088169，39 = 63245986,40 = 102334155}
统计不记忆技术
斐波纳契值：102334155
拍摄时间：11558
计算斐波那契数（使用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 !! n得到第n斐波那契fibs !! n fibs !! n其中n是索引。
版本3 ：使用matrix乘法技术。 （更快的版本）：
-- 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)
我做了一个程序。 计算值不需要很长时间，但可以显示的最大期限是第1477次（因为双倍的最大范围）。 结果几乎立即出现。 该系列从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; }
这个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
