我想知道如何找到非常大的 n 值的斐波那契数列的第 n 项，例如 1000000。使用小学递归方程fib(n)=fib(n-1)+fib(n-2)，找到第 50 项需要 2-3 分钟！
谷歌搜索后，我开始了解 Binet 的公式，但它不适用于 n>79 的值，正如这里所说
有没有一种算法可以做到这一点，就像我们找到素数一样？
问问题
92576 次
23 回答
62
您可以使用矩阵求幂法（线性递归法）。您可以在此博客中找到详细的解释和过程。运行时间为O (log n )。
我认为没有更好的方法可以做到这一点。
于 2013-02-02T12:08:14.533 回答
39
使用memoization可以节省很多时间。例如，比较以下两个版本（在 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 多分钟，而第二个版本只需要不到 5 毫秒！您可以在jsFiddle中检查这一点。
如果我们知道版本 1 的时间复杂度是指数的（O (2 N /2 )），而版本 2 的时间复杂度是线性的（O ( N )），这并不奇怪。
版本 3：矩阵乘法
此外，我们甚至可以通过计算N个矩阵的乘法将时间复杂度降低到O (log( N ))。
其中F n表示斐波那契数列的第n项。
于 2013-02-02T12:55:56.203 回答
32
我同意Wayne Rooney 的回答，即最佳解决方案将在O(log n)步骤中完成，但是整体运行时复杂性将取决于所使用的乘法算法的复杂性。例如，使用Karatsuba 乘法，整体运行时复杂度将为O(n log 2 3 ) ≈ O(n 1.585 )。1
但是，矩阵求幂不一定是最好的方法。正如Nayuki 项目的开发人员所注意到的，矩阵求幂带有冗余计算，可以删除。从作者的描述中：
给定F k和F k+1，我们可以计算这些：
请注意，每次拆分只需要 3 次 BigInt 到 BigInt 乘法，而不是矩阵求幂需要 8 次。
不过，我们仍然可以做得比这稍好一些。最优雅的斐波那契恒等式之一与卢卡斯数有关：
其中L n是第n个 卢卡斯数。这个身份可以进一步概括为：
有一些或多或少等效的递归方式，但最合乎逻辑的似乎是在F n和L n上。下面的实现中使用的其他身份可以从Lucas Sequences列出的身份中找到或派生：
以这种方式进行每次拆分只需要两次 BigInt 到 BigInt 的乘法，而最终结果只需要一次。这比 Project Nayuki 提供的代码（测试脚本）快 20% 左右。注意：原始来源已稍作修改（改进）以进行公平比较。
def fibonacci(n):
def fib_inner(n):
'''Returns F[n] and L[n]'''
if n == 0:
return 0, 2
u, v = fib_inner(n >> 1)
q = (n & 2) - 1
u, v = u * v, v * v + 2*q
if (n & 1):
u1 = (u + v) >> 1
return u1, 2*u + u1
return u, v
u, v = fib_inner(n >> 1)
if (n & 1):
q = (n & 2) - 1
u1 = (u + v) >> 1
return v * u1 + q
return u * v
更新
灰胡子指出，Takahashi (2000) 2已经对上述结果进行了改进，指出 BigInt 平方通常（特别是对于 Schönhage-Strassen 算法）的计算成本低于 BigInt 乘法。作者建议使用以下身份进行迭代，拆分F n和L n：
以这种方式迭代每次拆分需要两个 BigInt 平方，而不是上面的 BigInt 平方和 BigInt 乘法。正如预期的那样，对于非常大的n ，运行时间明显快于上述实现，但对于较小的值（n < 25000）则慢一些。
但是，这也可以稍微改进。作者声称，“众所周知，卢卡斯数乘积算法使用最少的位运算来计算斐波那契数 F n。” 然后，作者选择采用当时已知最快的卢卡斯数乘积算法，在F n和L n上进行拆分。但是请注意，L n仅用于计算F n+1。如果考虑以下身份，这似乎有点浪费：
其中第一个直接取自高桥，第二个是矩阵求幂方法的结果（也由 Nayuki 指出），第三个是前两个相加的结果。这允许对F n和F n+1进行明显的拆分。结果需要少一次 BigInt 加法，重要的是，对于偶数n少一次除以 2 ；对于奇数n，收益翻倍。在实践中，这比 Takahashi 为小n提出的方法要快得多（快 10-15%），而对于非常大的n（测试脚本）则略快一些。
def fibonacci(n):
def fib_inner(n):
'''Returns F[n] and F[n+1]'''
if n == 0:
return 0, 1
u, v = fib_inner(n >> 1)
q = (n & 2) - 1
u *= u
v *= v
if (n & 1):
return u + v, 3*v - 2*(u - q)
return 2*(v + q) - 3*u, u + v
u, v = fib_inner(n >> 1)
# L[m]
l = 2*v - u
if (n & 1):
q = (n & 2) - 1
return v * l + q
return u * l
更新 2
自最初发布以来，我对之前的结果也略有改进。除了两个 BigInt 方格之外，在F n和F n+1上进行拆分还具有三个 BigInt 加法和每次拆分两个小的常数乘法的开销。通过拆分L n和L n+1几乎可以完全消除这种开销：
像以前一样，以这种方式拆分需要两个 BigInt 方格，但只需要一个 BigInt 加法。不过，这些值需要与相应的斐波那契数相关联。幸运的是，这可以通过一次除以 5 来实现：
因为商已知是整数，所以可以使用精确除法，例如 GMP mpz_divexact_ui。展开最外层的拆分允许我们使用单次乘法计算最终值：
正如在 Python 中实现的那样，这明显快于小n的先前实现（快 5-10%），而对于非常大的n（测试脚本）则稍微快一点。
def fibonacci(n):
def fib_inner(n):
'''Returns L[n] and L[n+1]'''
if n == 0:
return mpz(2), mpz(1)
m = n >> 1
u, v = fib_inner(m)
q = (2, -2)[m & 1]
u = u * u - q
v = v * v + q
if (n & 1):
return v - u, v
return u, v - u
m = n >> 1
u, v = fib_inner(m)
# F[m]
f = (2*v - u) / 5
if (n & 1):
q = (n & 2) - 1
return v * f - q
return u * f
1可以看出， F n ~ O(n)的位数（或位数）为：
使用 Karatsuba 乘法的运行时复杂度可以计算为：
2 Takahashi, D. (2000)，“计算大型斐波那契数的快速算法” (PDF)，信息处理快报 75，第 243-246 页。
于 2018-01-09T15:21:27.290 回答
14
使用重复标识http://en.wikipedia.org/wiki/Fibonacci_number#Other_identities在步骤中找到n第 - 个数字。log(n)为此，您将不得不使用任意精度的整数。或者您可以通过在每一步使用模运算来计算精确的答案模数。
注意到3n+3 == 3(n+1)，我们可以设计一个单递归函数，它在每一步计算两个连续的斐波那契数，除以n3 并根据余数选择适当的公式。IOW 它一步一步@(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
于 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 公式，并使用任意精度的数学来提供足够的精度来计算答案。
但是，仅使用递推关系不需要2-3 分钟来计算第 50 项——您应该能够在任何现代机器上在几秒钟内将项计算到数十亿。听起来您正在使用完全递归公式，这确实会导致递归计算的组合爆炸。简单的迭代公式要快得多。
也就是说：递归解决方案是：
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
对于计算斐波那契数，递归算法是最糟糕的方法之一。通过简单地将前两个数字相加在一个 for 循环（称为迭代方法）中，计算第 50 个元素不会花费 2-3 分钟。
于 2013-02-02T12:01:49.490 回答
3
这是一个 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]
于 2017-11-02T13:23:53.067 回答
3
我编写了一个C实现，它支持使用 GNU 的任何规模的输入数字gmp。
计算单个数字的 fib 的时间是O(n)，缓存空间是O(1)，（它实际上计算了 0 ~ n 的所有 fib）。
代码
fib_cached_gmp.c:
// fibonacci - cached algorithm - any scale of input with GMP,
#include <gmp.h>
#include <stdio.h>
#include <stdlib.h>
// a single step,
void fib_gmp_next(mpz_t *cache) {
mpz_add(cache[2], cache[0], cache[1]);
mpz_set(cache[0], cache[1]);
mpz_set(cache[1], cache[2]);
}
// figure fib for a single number, in O(n),
mpz_t *fib_gmp(int n, mpz_t *result) {
// init cache,
mpz_t cache[3]; // number: [fib(n-2), fib(n-1), fib(n)],
mpz_init(cache[0]);
mpz_init(cache[1]);
mpz_init(cache[2]);
mpz_set_si(cache[0], 0);
mpz_set_si(cache[1], 1);
while (n >= 2) {
fib_gmp_next(cache);
n--;
}
mpz_set(*result, cache[n]);
return result;
}
// test - print fib from 0 to n, tip: cache won't be reused between any 2 input numbers,
void test_seq(int n) {
mpz_t result;
mpz_init(result);
for (int i = 0; i <= n; i++) {
gmp_printf("fib(%2d): %Zd\n", i, fib_gmp(i, &result));
}
}
// test - print fib for a single num,
void test_single(int x) {
mpz_t result;
mpz_init(result);
gmp_printf("fib(%d): %Zd\n", x, fib_gmp(x, &result));
}
int main() {
// test sequence,
test_seq(100);
// test single,
test_single(12345);
return 0;
}
先安装gmp：
// for Ubuntu,
sudo apt-get install libgmp3-dev
编译：
gcc fib_cached_gmp.c -lgmp
执行：
./a.out
示例输出：
fib( 0): 0
fib( 1): 1
fib( 2): 1
fib( 3): 2
fib( 4): 3
fib( 5): 5
fib( 6): 8
fib( 7): 13
fib( 8): 21
fib( 9): 34
fib(10): 55
fib(11): 89
fib(12): 144
fib(13): 233
fib(14): 377
fib(15): 610
fib(16): 987
fib(17): 1597
fib(18): 2584
fib(19): 4181
fib(20): 6765
fib(21): 10946
fib(22): 17711
fib(23): 28657
fib(24): 46368
fib(25): 75025
fib(26): 121393
fib(27): 196418
fib(28): 317811
fib(29): 514229
fib(30): 832040
fib(31): 1346269
fib(32): 2178309
fib(33): 3524578
fib(34): 5702887
fib(35): 9227465
fib(36): 14930352
fib(37): 24157817
fib(38): 39088169
fib(39): 63245986
fib(40): 102334155
fib(41): 165580141
fib(42): 267914296
fib(43): 433494437
fib(44): 701408733
fib(45): 1134903170
fib(46): 1836311903
fib(47): 2971215073
fib(48): 4807526976
fib(49): 7778742049
fib(50): 12586269025
fib(51): 20365011074
fib(52): 32951280099
fib(53): 53316291173
fib(54): 86267571272
fib(55): 139583862445
fib(56): 225851433717
fib(57): 365435296162
fib(58): 591286729879
fib(59): 956722026041
fib(60): 1548008755920
fib(61): 2504730781961
fib(62): 4052739537881
fib(63): 6557470319842
fib(64): 10610209857723
fib(65): 17167680177565
fib(66): 27777890035288
fib(67): 44945570212853
fib(68): 72723460248141
fib(69): 117669030460994
fib(70): 190392490709135
fib(71): 308061521170129
fib(72): 498454011879264
fib(73): 806515533049393
fib(74): 1304969544928657
fib(75): 2111485077978050
fib(76): 3416454622906707
fib(77): 5527939700884757
fib(78): 8944394323791464
fib(79): 14472334024676221
fib(80): 23416728348467685
fib(81): 37889062373143906
fib(82): 61305790721611591
fib(83): 99194853094755497
fib(84): 160500643816367088
fib(85): 259695496911122585
fib(86): 420196140727489673
fib(87): 679891637638612258
fib(88): 1100087778366101931
fib(89): 1779979416004714189
fib(90): 2880067194370816120
fib(91): 4660046610375530309
fib(92): 7540113804746346429
fib(93): 12200160415121876738
fib(94): 19740274219868223167
fib(95): 31940434634990099905
fib(96): 51680708854858323072
fib(97): 83621143489848422977
fib(98): 135301852344706746049
fib(99): 218922995834555169026
fib(100): 354224848179261915075
fib(12345): 400805695072240470970514993214065752192289440772063392234116121035966330621821050108284603033716632771086638046166577665205834362327397885009536790892524821512145173749742393351263429067658996935575930135482780507243981402150702461932551227590433713277255705297537428017957026536279252053237729028633507123483103210846617774763936154673522664591736081039709294423865668046925492747583953758325850613548914282578320544573036249175099094644435323970587790740267131607004023987409385716162460955707793257532112771932704816713519196128834470721836094265012918046427449156654067195071358955104097973710150920536847877434256779886729555691213282504703193401739340461924048504866698176130757935914248753973087073009601101912877383634628929467608983980664185363370286731771712542583041365328648124549323878806758395652340861186334027392307091079257180835672989798524084534677252369585918458720952520972332496025465803523315515681084895362126005441170936820059518262349022456888758938672920855739736423917065122816343192172271301981007636070751378441363091187289522144227851382197807194256392294919912037019476582418451273767976783751999133072126657949249799858935787018952232743400610036315564885371356712960608966755186612620425868892621106627825137425386831657368826398245606147944273998498356443362170133234924531673939303668042878258282104212769625245680321344034442698232414181912301904509531018692483863038992377680591406376081935756597411807864832452421993121459549055042253305545594009110753730302061881025182053074077930494574304284381890534053065639084253641881363463311184024281835265103884539012874542416238100890688593076189105555658375552988619203325356676814545718066196038345684671830102920209857682912971565838896011294918349088792184108318689299230788355618638040186790724351073650210514429114905535411044888774713860041341593318365792673354888566799196442017231870631867558530906286613228902689695061557951752309687806567573290910909535395758148994377158637050112347651517847188123790794231572729345617619677555583207012253101701328971768827861922408064379891201972881554890367344239218306050355964382953279316318309272212482218232309006973312977359562553184608144571713073802285675503209229581312057259729362382786183100343961484090866057560474044189870633912200595478051573769889968342203512550302655117491740823696686983281784153050366346823513213598551985596176977626982962058849363351794302206703907577970065793839511591930741441079234179943480206539767561244271325923343752071038968002157889912694947204003637791271084190929058369801531787887444598295425899927970
尖端：
- 他
test_seq()不是很聪明，它没有重用两个输入数字之间的缓存。
虽然实际上一次调用fib_gmp()就足够了，但如果您在每个步骤中添加一个gmp_printf()tofib_gmp_next()并提供 i to 。 无论如何，这只是为了演示。fib_gmp_next()
于 2018-05-03T12:27:04.400 回答
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 回答
2
最简单的 Pythonic 实现可以如下给出
def Fib(n):
if (n < 0) :
return -1
elif (n == 0 ):
return 0
else:
a = 1
b = 1
for i in range(2,n+1):
a,b = b, a+b
return a
于 2017-12-22T17:33:57.697 回答
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 回答
1
借助一些离散数学知识，您可以在常数时间 O(1) 内找到任何斐波那契数。有一种叫做线性齐次递归关系的东西。
斐波那契数列就是一个著名的例子。
要找到第 n 个斐波那契数，我们需要找到
我们知道
在哪里
那么，特征方程为
在找到特征方程的根并代入第一个方程后
最后，我们需要找到 alpha 1 & alpha 2 的值
现在，您可以使用此等式在 O(1) 中找到任何斐波那契数。
于 2018-05-07T02:49:17.617 回答
0
我在 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);
}
}
}
于 2013-05-03T08:44:06.090 回答
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 回答
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
计算斐波那契数（使用 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您只需执行where nis 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 回答
-1
我编写了一个小代码来计算大数的斐波那契，这比会话递归方式更快。
我正在使用记忆技术来获取最后一个斐波那契数，而不是重新计算它。
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));
}
}
输入号码
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, 35=9227465, 3 24157817, 38=39088169, 39=63245986, 40=102334155}
无需记忆技术的统计数据
斐波那契值：102334155
所用时间：11558
于 2014-02-16T07:00:01.777 回答
-1
如果您使用 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();
}
于 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
我做了一个程序。计算值不需要很长时间，但可以显示的最大项是第 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 回答
-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，它可以在 chrome 控制台上正常工作，直到n=74
打开任何建议！
另一种解决方案
按照步骤-
- 以一定的时间间隔制作一组斐波那契数列的指数和值和前值。例如每 50 个或每 100 个。
- 从step-1
n的集合中找到所需数字的最接近的较低索引。 - 通过在每个后续值中添加先前的值，以传统方式进行。
注意：看起来不太好，但如果你真的关心时间复杂度，这个解决方案很受欢迎。根据step-1 ，最大迭代次数将等于间隔。
结论：
于 2019-03-01T06:43:50.807 回答