我是一名 CSE 学生，正在为编程比赛做准备。现在我正在研究斐波那契数列。我有一个大小约为一些包含正整数的 Kilo 字节的输入文件。输入甲酸盐看起来像
3 5 6 7 8 0
零表示文件结束。输出应该像
2
5
8
13
21
我的代码是
#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;
}
该代码适用于样本输入并提供准确的结果，但问题是对于我的真实输入集，它花费的时间超过了我的时间限制。谁能帮我吗。
如果内存有限制，您可以简单地使用返回最后两个斐波那契数的函数的尾递归版本。
int fib(int n)
{
int a = 0;
int b = 1;
while (n-- > 1) {
int t = a;
a = b;
b += t;
}
return b;
}
这是O(n)并且需要一个恒定的空间。
查看维基百科，有一个公式可以给出斐波那契数列中的数字，根本没有递归
使用记忆。也就是说，您缓存答案以避免不必要的递归调用。
这是一个代码示例：
#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);
}
没有人提到 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];
}
这是一个 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
此处使用的 BM_memoization 将仅初始化数组一次，并将其用于其他所有调用。
2 值堆栈数组版本在优化时与具有临时变量的版本执行相同。
也可以使用快速倍增法生成斐波那契数列链接：fastest-way-to-compute-fibonacci-number
它实际上是从矩阵求幂法的结果推导出来的。
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.
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.
In C#:
static int fib(int n)
{
if (n < 2) return n;
if (n == 2) return 1;
int k = n / 2;
int a = fib(k + 1);
int b = fib(k);
if (n % 2 == 1)
return a * a + b * b;
else
return b * (2 * a - b);
}
矩阵乘法，无浮点运算，O(log N)时间复杂度假设整数乘法/加法是在恒定时间内完成的。
这是python代码
def fib(n):
x,y = 1,1
mat = [1,1,1,0]
n -= 1
while n>0:
if n&1==1:
x,y = x*mat[0]+y*mat[1], x*mat[2]+y*mat[3]
n >>= 1
mat[0], mat[1], mat[2], mat[3] = mat[0]*mat[0]+mat[1]*mat[2], mat[0]*mat[1]+mat[1]*mat[3], mat[0]*mat[2]+mat[2]*mat[3], mat[1]*mat[2]+mat[3]*mat[3]
return x
您可以发布 input.txt 文件和时间限制吗？顺便说一句：这个任务是众所周知的。您是否阅读了以下http://www.ics.uci.edu/~eppstein/161/960109.html？
构建一个数组 Answer[100]，在其中缓存 fibonacci(n) 的结果。检查您的斐波那契代码以查看您是否已预先计算出答案，并使用该结果。结果会让你大吃一惊。
在函数式编程中有一种特殊的计算斐波那契数的算法。该算法使用累积递归。累积递归用于最小化算法使用的堆栈大小。我认为这将帮助您减少时间。如果你愿意，你可以试试。
int ackFib (int n, int m, int count){
if (count == 0)
return m;
else
return ackFib(n+m, n, count-1);
}
int fib(int n)
{
return ackFib (0, 1, n+1);
}
您可以减少 if 语句的开销：Calculating Fibonacci Numbers Recursively in C
首先，您可以使用记忆化或相同算法的迭代实现。
考虑您的算法进行的递归调用的数量：
fibonacci(n) 调用 fibonacci(n-1) 和fibonacci(n-2)
fibonacci(n-1) 调用fibonacci(n-2)和fibonacci(n-3)
fibonacci(n-2) 调用fibonacci(n-3)和 fibonacci(n-4)
注意到一个模式了吗？您计算相同函数的次数比需要的次数多得多。
迭代实现将使用数组：
int fibonacci(int n) {
int arr[maxSize + 1];
arr[1] = arr[2] = 1; // ideally you would use 0-indexing, but I'm just trying to get a point across
for ( int i = 3; i <= n; ++i )
arr[i] = arr[i - 1] + arr[i - 2];
return arr[n];
}
这已经比你的方法快得多了。您可以按照相同的原则更快地完成它，只需构建一次数组直到最大值n，然后通过打印数组的元素在单个操作中打印正确的数字。这样您就不会为每个查询调用该函数。
如果您负担不起初始的预计算时间（但这通常仅在您被要求对结果取模时才会发生，否则他们可能不希望您实现大数算术并且预计算是最好的解决方案），请阅读其他方法的斐波那契维基页面。专注于矩阵方法，这是在比赛中很好了解的方法。
使用其中任何一个：递归的两个示例，一个使用 for 循环 O(n) 时间，一个使用黄金比例 O(1) 时间：
private static long fibonacciWithLoop(int input) {
long prev = 0, curr = 1, next = 0;
for(int i = 1; i < input; i++){
next = curr + prev;
prev = curr;
curr = next;
}
return curr;
}
public static long fibonacciGoldenRatio(int input) {
double termA = Math.pow(((1 + Math.sqrt(5))/2), input);
double termB = Math.pow(((1 - Math.sqrt(5))/2), input);
double factor = 1/Math.sqrt(5);
return Math.round(factor * (termA - termB));
}
public static long fibonacciRecursive(int input) {
if (input <= 1) return input;
return fibonacciRecursive(input - 1) + fibonacciRecursive(input - 2);
}
public static long fibonacciRecursiveImproved(int input) {
if (input == 0) return 0;
if (input == 1) return 1;
if (input == 2) return 1;
if (input >= 93) throw new RuntimeException("Input out of bounds");
// n is odd
if (input % 2 != 0) {
long a = fibonacciRecursiveImproved((input+1)/2);
long b = fibonacciRecursiveImproved((input-1)/2);
return a*a + b*b;
}
// n is even
long a = fibonacciRecursiveImproved(input/2 + 1);
long b = fibonacciRecursiveImproved(input/2 - 1);
return a*a - b*b;
}
using namespace std;
void mult(LL A[ 3 ][ 3 ], LL B[ 3 ][ 3 ]) {
int i,
j,
z;
LL C[ 3 ][ 3 ];
memset(C, 0, sizeof( C ));
for(i = 1; i <= N; i++)
for(j = 1; j <= N; j++) {
for(z = 1; z <= N; z++)
C[ i ][ j ] = (C[ i ][ j ] + A[ i ][ z ] * B[ z ][ j ] % mod ) % mod;
}
memcpy(A, C, sizeof(C));
};
void readAndsolve() {
int i;
LL k;
ifstream I(FIN);
ofstream O(FOUT);
I>>k;
LL A[3][3];
LL B[3][3];
A[1][1] = 1; A[1][2] = 0;
A[2][1] = 0; A[2][2] = 1;
B[1][1] = 0; B[1][2] = 1;
B[2][1] = 1; B[2][2] = 1;
for(i = 0; ((1<<i) <= k); i++) {
if( k & (1<<i) ) mult(A, B);
mult(B, B);
}
O<<A[2][1];
}
//1,1,2,3,5,8,13,21,33,...
int main() {
readAndsolve();
return(0);
}
#include<stdio.h>
int g(int n,int x,int y)
{
return n==0 ? x : g(n-1,y,x+y);}
int f(int n)
{
return g(n,0,1);}
int main (void)
{
int i;
for(i=1; i<=10 ; i++)
printf("%d\n",f(i)
return 0;
}
public static int GetNthFibonacci(int n)
{
var previous = -1;
var current = 1;
int element = 0;
while (1 <= n--)
{
element = previous + current;
previous = current;
current = element;
}
return element;
}
这类似于之前给出的答案，但有一些修改。正如其他答案中所述，记忆是另一种方法，但我不喜欢不会随着技术变化而扩展的代码（an 的大小unsigned int因平台而异），因此可以达到的序列中的最高值也可能变化，并且在我看来记忆是丑陋的。
#include <iostream>
using namespace std;
void fibonacci(unsigned int count) {
unsigned int x=0,y=1,z=0;
while(count--!=0) {
cout << x << endl; // you can put x in an array or whatever
z = x;
x = y;
y += z;
}
}
int main() {
fibonacci(48);// 48 values in the sequence is the maximum for a 32-bit unsigend int
return 0;
}
此外，如果您使用<limits>它可能编写一个编译时常量表达式，它将为您提供序列中任何整数数据类型可以达到的最大索引。
#include<stdio.h>
main()
{
int a,b=2,c=5,d;
printf("%d %d ");
do
{
d=b+c;
b=c;
c=d;
rintf("%d ");
}