1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
* 快速fibnacci数列
*
* author : ismdeep
*/
#include <iostream>
using namespace std;

// MAXN 给1000肯定是会溢出的,这里只是给一个例子,快速fibnacci
#define MAXN 1000

int fib[MAXN];

// 初始化
void init()
{
for (int i = 0; i < MAXN; i++)
{
fib[i] = -1; // 因为fibnacci数列里面不可能出现-1,所以这里给每个数值都赋值为-1作为是否计算出结果的标记
}
fib[0] = 0;
fib[1] = 1;
}

// 递归去搜索
// 这里不需要递归的临界判断,因为下标0和下标1都一定不为-1,一定可以return结果的。
int search_fib(int index)
{
if (-1 != fib[index])
{
return fib[index];
}
else
{
fib[index] = search_fib(index-1)+search_fib(index-2);
return fib[index];
}
}

int main()
{
init();
int n;
while (scanf("%d", &n) != EOF)
{
int ans = search_fib(n);
printf("%d\n", ans);
}
}