寫一個函數，輸入n，其斐波那契數列的第n項。
斐波那契數列的定義如下：
1 #include "stdafx.h"
2 #include<iostream>
3 using namespace std;
4
5
6 //方法1 遞歸 缺點：效率低
7 long long Fibonacci_Solution1(unsigned int n )
8 {
9 if(n <= 0)
10 return 0;
11
12 if( n == 1)
13 return 1;
14
15 return Fibonacci_Solution1(n-1) + Fibonacci_Solution1(n-2);
16 }
17
18 //方法2 循環
19 long long Fibonacci_Solution2(unsigned int n)
20 {
21 int result[2] = {0,1};
22 if(n < 2)
23 return result[n];
24
25 long long fibNMinusOne = 1;
26 long long fibNMinusTwo = 0;
27 long long fibN = 0;
28
29 for(unsigned int i = 2 ; i <= n ; ++i)
30 {
31 fibN = fibNMinusOne + fibNMinusTwo;
32
33 fibNMinusTwo = fibNMinusOne;
34 fibNMinusOne = fibN;
35 }
36
37 return fibN;
38 }
39
40 //方法3 循環 其實和方法2差不多
41 long long Fibonacci_Solution3(unsigned int n)
42 {
43 if(n <= 0)
44 return 0;
45 else if(n == 1)
46 return 1;
47 else
48 {
49 int *array = new int[n+1];
50 array[0] = 0;
51 array[1] = 1;
52 for(int i = 2; i<= n; i++)
53 array[i] = array[i-1] + array[i-2];
54
55 int result = array[n];
56 delete[] array;
57
58 return result;
59 }
60 }
61
62 //方法4 數學歸納法 略
63
64
65 int main()
66 {
67 int num1 = Fibonacci_Solution1(30);
68 int num2 = Fibonacci_Solution2(30);
69 int num3 = Fibonacci_Solution3(30);
70
71 cout << num1 <<endl;
72 cout << num2 <<endl;
73 cout << num3 <<endl;
74
75 return 0;
76 }
運行結果如下:
