C 斐波那契数列题目两则

师匠考我，说要写斐波那契数列，刚开始给了一道题，后来变成两道，作为算法入门题，虽然简单，但似乎确实很有教育意义，想折腾算法的不妨试试。

1、输入两个数，输出两个数间的斐波那契数列的数：如输入1 6，输出 1 1 2 3 5，输入4 4， 输出NONE
2、写一个斐波那契函数，列出第N个斐波那契数列的数，如输入0 输出0 输入3 输出2。

递归总是可以用的，但递归的效率很低，这种时候我们想到的就是“最优”，我写的不一定就是最优的，只是：有办法解决，仅此而已。

第一道：

#include <stdio.h>

int main(void)
{
    int start, former, later, end, temp, i;

    printf("print the start num: ");
    scanf("%d", &start);
    printf("print the end num: ");
    scanf("%d", &end);

    former = 0;
    later = 1;
    i = 0;

    while (former <= end) {
        if (former >= start) {
            printf("%d ", former);
            i++;
        }
        temp = later;
        later = former + later;
        former = temp;
    }

    if (i == 0)
    {
        printf("NONE");
    }

    return 0;

}

第二道：

#include <stdio.h>

int fibonacci(int num);

int main(void)
{
    int num;

    printf("Print the num: ");
    scanf("%d", &num);

    if (num > 50)
        printf("Sorry the number is too big");
    else
        printf("%d", fibonacci(num));
    return 0;
}

int fibonacci(int num)
{
    int list[50], former, later, temp, n;
    former = 0;
    later = 1;

    for (n = 0;n <= num; n++) {
        list[n] = former;

        temp = later;
        later = former + later;
        former = temp;
    }

    return list[num];

}

这个写法效率比递归高，递归是这样：

    if (n <= 2)
        return 1;
    return fib(n-2) + fib(n-1);

一般递归的效率都不高，能不用递归就尽量不使用。

其中题目2中，如果函数并不是一次性使用，而是要被频繁调用，那么我们可以直接先生成完整的表，然后在查询（这就是查表或者说缓存了），针对不同的使用方式，也会有不同效率的写法。