C语言典型题——求菲波那切数列第N项

菲波那切数列*

1.引入
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

2.定义
斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368
........这个数列从第3项开始，每一项都等于前两项之和。
斐波那契数列的定义者，是意大利数学家列昂纳多·斐波那契（Leonardo Fibonacci），生于公元1170年，卒于1250年，籍贯是比萨。他被人称作“比萨的列昂纳多”。1202年，他撰写了《算盘全书》（Liber Abacci）一书。他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事，派驻地点于阿尔及利亚地区，列昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯等地研究数学。
3.求解

1. 递归方法

根据这个公式，应用递归调用可以很好的求解菲波那切数列第N项，以下为求解过程（源代码）：

#include<stdio.h>
#include<stdlib.h>
int fib(int n)
{
    if (n <= 2)
        return  1;
    else 
        return  fib(n - 1) + fib(n - 2);
}
int main()
{
    int n = 0;
    int ret = 0;

    scanf("%d",&n);
    ret = fib(n);
    printf("%d\n", ret);
    system("pause");

    return 0;
}

我们在验证前几个菲波那切数列都没有问题，但是这样就完了吗？不，其实再往下走，比如给个50他就算不出来了。这是为什么呢，仔细想想就不难发现：原来每次递归调用都会把一个值重复算好多遍，我们用个例子来验证一下：

#include<stdio.h>
#include<stdlib.h>
int count = 0;
int fib(int n)
{

    if (n == 3)
        count++;
    if (n <= 2)
        return  1;
    else 
        return  fib(n - 1) + fib(n - 2);
}
int main()
{
    int n = 0;
    int ret = 0;

    scanf("%d",&n);
    ret = fib(n);
    printf("%d\n", ret);
    printf("%d\n", count);
    system("pause");

    return 0;
}

这个代码输出结果为

这里我们定义一个全局变量count，这里只仅仅计算了fib(3)被重复计算的次数就已经这么大了，可想而知这个代码输入的N值一旦很大计算效率就会变得极其差，那么怎么解决这个问题呢，下面在引进一个方法：

2.非递归——迭代（即循环）

我们怎么做呢，就是这样：前三个菲波那切数我们知道，我们可不可以利用迭代来计算后面的斐波那契数呢，显然是可以的。我们可以这样想：首先让a=1,b=1我们让c=a+b然后利用循环来交换a，b，c的值不就好了。可是如何实现呢，以下分享一下我的想法：

#include<stdio.h>
#include<stdlib.h>
int fib(int n)
{
    int a = 1;
    int b = 1;
    int c = 0;
    while (n > 2)
    {
        c = a + b;
        a = b;
        b = c;
        n--;
    }
    return c;
}
int main()
{
    int n = 0;
    int ret = 0;

    scanf("%d",&n);
    ret = fib(n);
    printf("%d\n", ret);
    system("pause");

    return 0;
}

这个思想可以这样实现，可是又出现一个问题，当n太大时数存不下来，从而导致计算可能有点问题，所以还是需要大佬们来完善一下。可是这个的效率绝对比上面的递归方法要高很多，这个计算比较小的n还是挺快的。
这里我们看到有些问题可以用递归去做，但是不适用递归解决它，否则只会适得其反。希望在小伙伴们的评论区里找到更好的解决办法哦。