C语言 如何更快地生成斐波那契数列
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3337455/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to generate Fibonacci faster
提问by Mehedi
I am a CSE student and preparing myself for programming contest.Now I am working on Fibonacci series. I have a input file of size about some Kilo bytes containing positive integers. Input formate looks like
我是一名 CSE 学生，正在为编程比赛做准备。现在我正在研究斐波那契数列。我有一个大小约为一些 Kilo 字节的输入文件，其中包含正整数。输入格式看起来像
3 5 6 7 8 0
A zero means the end of file. Output should like
零表示文件结束。输出应该像
2
5
8
13
21
my code is
我的代码是
#include<stdio.h>
int fibonacci(int n) {
if (n==1 || n==2)
return 1;
else
return fibonacci(n-1) +fibonacci(n-2);
}
int main() {
int z;
FILE * fp;
fp = fopen ("input.txt","r");
while(fscanf(fp,"%d", &z) && z)
printf("%d \n",fibonacci(z));
return 0;
}
The code works fine for sample input and provide accurate result but problem is for my real input set it is taking more time than my time limit. Can anyone help me out.
该代码适用于样本输入并提供准确的结果，但问题是对于我的真实输入集，它花费的时间超过了我的时间限制。谁能帮我吗。
回答by Kru
You could simply use a tail recursion version of a function that returns the two last fibonacci numbers if you have a limit on the memory.
如果您对内存有限制，您可以简单地使用返回最后两个斐波那契数的函数的尾递归版本。
int fib(int n)
{
int a = 0;
int b = 1;
while (n-- > 1) {
int t = a;
a = b;
b += t;
}
return b;
}
This is O(n)and needs a constant space.
这是O(n)并且需要一个恒定的空间。
回答by Xzhsh
You should probably look into memoization.
您可能应该研究记忆。
http://en.wikipedia.org/wiki/Memoization
http://en.wikipedia.org/wiki/Memoization
It has an explanation and a fib example right there
它有一个解释和一个 fib 例子就在那里
回答by Teodor Pripoae
You can do this by matrix multiplictation, raising the matrix to power n and then multiply it by an vector. You can raise it to power in logaritmic time.
您可以通过矩阵乘法来实现，将矩阵提升到 n 次方，然后将其乘以一个向量。您可以在对数时间内将其提升到幂。
I think you can find the problem here. It's in romanian but you can translate it with google translate. It's exactly what you want, and the solution it's listed there.
我想你可以在这里找到问题。它是罗马尼亚语，但您可以使用谷歌翻译进行翻译。这正是您想要的，并且在那里列出了解决方案。
回答by sukru
Your algorithm is recursive, and approximately has O(2^N) complexity.
您的算法是递归的，并且大约具有 O(2^N) 复杂度。
This issue has been discussed on stackoverflow before: Computational complexity of Fibonacci Sequence
这个问题之前已经在stackoverflow上讨论过： Fibonacci Sequence的计算复杂度
There is also a faster implementation posted in that particular discussion.
在该特定讨论中还发布了一个更快的实现。
回答by David Brunelle
回答by dcp
Use memoization. That is, you cache the answers to avoid unnecessary recursive calls.
使用记忆。也就是说，您可以缓存答案以避免不必要的递归调用。
Here's a code example:
这是一个代码示例：
#include <stdio.h>
int memo[10000]; // adjust to however big you need, but the result must fit in an int
// and keep in mind that fibonacci values grow rapidly :)
int fibonacci(int n) {
if (memo[n] != -1)
return memo[n];
if (n==1 || n==2)
return 1;
else
return memo[n] = fibonacci(n-1) +fibonacci(n-2);
}
int main() {
for(int i = 0; i < 10000; ++i)
memo[i] = -1;
fibonacci(50);
}
回答by BlakBat
Nobody mentioned the 2 value stack array version, so I'll just do it for completeness.
没有人提到 2 值堆栈数组版本，所以我只是为了完整性而这样做。
// do not call with i == 0
uint64_t Fibonacci(uint64_t i)
{
// we'll only use two values on stack,
// initialized with F(1) and F(2)
uint64_t a[2] = {1, 1};
// We do not enter loop if initial i was 1 or 2
while (i-- > 2)
// A bitwise AND allows switching the storing of the new value
// from index 0 to index 1.
a[i & 1] = a[0] + a[1];
// since the last value of i was 0 (decrementing i),
// the return value is always in a[0 & 1] => a[0].
return a[0];
}
This is a O(n) constant stack space solution that will perform slightly the same than memoization when compiled with optimization.
这是一个 O(n) 常量堆栈空间解决方案，当优化编译时，它的性能与记忆化略有相同。
// Calc of fibonacci f(99), gcc -O2
Benchmark Time(ns) CPU(ns) Iterations
BM_2stack/99 2 2 416666667
BM_memoization/99 2 2 318181818
The BM_memoization used here will initialize the array only once and reuse it for every other call.
此处使用的 BM_memoization 将只初始化数组一次，并在每次其他调用时重用它。
The 2 value stack array version performs identically as a version with a temporary variable when optimized.
2 值堆栈数组版本在优化时的性能与带有临时变量的版本相同。
回答by Neha
You can also use the fast doubling method of generating fibonacci series Link- http://vinayakgarg.wordpress.com/2012/11/07/fastest-way-to-compute-fibonacci-number/
您也可以使用生成斐波那契数列链接的快速加倍方法- http://vinayakgarg.wordpress.com/2012/11/07/fastest-way-to-compute-fibonacci-number/
It is actually derived from results of matrix exponentiation method.
它实际上是从矩阵求幂方法的结果中推导出来的。
回答by Anurag
回答by Mark Peters
Are you guaranteed that, as in your example, the input will be given to you in ascending order? If so, you don't even need memoization; just keep track of the last two results, start generating the sequence but only display the Nth number in the sequence if N is the next index in your input. Stop when you hit index 0.
您是否保证，如在您的示例中，输入将按升序提供给您？如果是这样，你甚至不需要记忆；只需跟踪最后两个结果，开始生成序列，但如果 N 是输入中的下一个索引，则仅显示序列中的第 N 个数字。当您点击索引 0 时停止。
Something like this:
像这样的东西：
int i = 0;
while ( true ) {
i++; //increment index
fib_at_i = generate_next_fib()
while ( next_input_index() == i ) {
println fib_at_i
}
I leave exit conditions and actually generating the sequence to you.
我留下退出条件并实际为您生成序列。
