如何更快地产生斐波那契

问题描述

我是一名CSE学生，正在为编程竞赛做准备。现在，我正在从事斐波那契数列。我有一个输入文件，大小约为一些包含正整数的千字节。输入甲酸盐

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

3 5 6 7 8 0

零表示文件结尾。输出应为

A zero means the end of file. Output should like

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;
}

该代码适用于示例输入并提供准确的结果，但问题是我的实际的输入设置比我的时间限制花费更多的时间。任何人都可以帮帮我。

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.

推荐答案

您可以简单地使用函数的尾部递归版本，该函数将返回最后两个斐波那契数字，如果您对内存有限制。

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;
}

这是 O（n），并且需要一个恒定的空间。

This is O(n) and needs a constant space.

这篇关于如何更快地产生斐波那契的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！