JZ-C-09

剑指offer第九题：斐波那契数列
 1 //============================================================================
 2 // Name        : JZ-C-09.cpp
 3 // Author      : Laughing_Lz
 4 // Version     :
 5 // Copyright   : All Right Reserved
 6 // Description : 斐波那契数列
 7 //============================================================================
 8 
 9 #include <iostream>
10 using namespace std;
11 /**
12  *输入n，返回第n个斐波那契数
13  */
14 double Fibonacci(int n) {
15     double fi;
16     if (n <= 0) {
17         return -1; //错误
18     } else if (n == 1 || n == 2) {
19         fi = 1;
20     } else {
21         fi = Fibonacci(n - 1) + Fibonacci(n - 2);//递归的时间复杂度是n的指数递增，还可能导致栈溢出
22     }
23     return fi;
24 }
25 long long Fibonacci1(int n) {
26     long long previous[] = { 1, 1 };//避免重复计算，利用数组存储第n-1和n-2个数。时间复杂度为0(n)
27     if (n <= 0) {
28         return -1; //错误
29     } else {
30         if (n == 1 || n == 2) {
31             return previous[n-1];
32         }
33         for (int m = 2; m < n; m++) {
34             long long pre = previous[1];
35             previous[1] = previous[0] + previous[1];
36             previous[0] = pre;
37         }
38         return previous[1];
39     }
40 }
41 int main() {
42     long long result = Fibonacci1(50);
43     cout << result << endl;
44     return 0;
45     return 0;
46 }