求第n项斐波那契数的几种方法

递归

以前我们用递归的方法这样来求第n个斐波那契数

int Fib(int n)
{
    if (n < 3)
        return 1;
    return Fib(n - 1) + Fib(n - 2);
}

但是这个算法的效率太低，原因如下：

里面有太多的重复计算，时间复杂度过高，导致算法效率低下。

迭代

这算是一种较为优化的算法

long long Fib(long long first, long long second, int n)//first和second表示第一项和第二项
{
    if (n < 3)
        return 1;
    if (n == 3)
        return first + second;
    return Fib(second, first + second, n - 1);
}

写成非递归：

#include <stdio.h>
#include <windows.h>
long long Fib(int n)
{
    long long first = 1;//第一个斐波那契数
    long long second = 1;//第二个斐波那契数
    long long temp = 0;
    long long ret = 1;
    int i = 0;
    if (n <= 0)
        return 0;
    for (i = 3; i < n; i++)
    {
        temp = first + second;
        first = second;
        second = temp;
        ret = first + second;
    }
    return ret;
}
int main()
{
    int n = 0;
    printf("请输入n:\n");
    scanf_s("%d", &n);
    printf("%lld\n", Fib(n));
    system("pause");
    return 0;