CodeSky 代码之空

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

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

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

第一道：

1#include <stdio.h>
2
3int main(void)
4{
5    int start, former, later, end, temp, i;
6
7    printf("print the start num: ");
8    scanf("%d", &start);
9    printf("print the end num: ");
10    scanf("%d", &end);
11
12    former = 0;
13    later = 1;
14    i = 0;
15
16    while (former <= end) {
17        if (former >= start) {
18            printf("%d ", former);
19            i++;
20        }
21        temp = later;
22        later = former + later;
23        former = temp;
24    }
25
26    if (i == 0)
27    {
28        printf("NONE");
29    }
30
31    return 0;
32
33}
34

第二道：

1#include <stdio.h>
2
3int fibonacci(int num);
4
5int main(void)
6{
7    int num;
8
9    printf("Print the num: ");
10    scanf("%d", &num);
11
12    if (num > 50)
13        printf("Sorry the number is too big");
14    else
15        printf("%d", fibonacci(num));
16    return 0;
17}
18
19int fibonacci(int num)
20{
21    int list[50], former, later, temp, n;
22    former = 0;
23    later = 1;
24
25    for (n = 0;n <= num; n++) {
26        list[n] = former;
27
28        temp = later;
29        later = former + later;
30        former = temp;
31    }
32
33    return list[num];
34
35}
36

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

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

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

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