C++ 斐波那契数列（Fibonacci Sequence）_c++斐波那契数列

C++ 斐波那契数列（Fibonacci Sequence）

一、斐波那契数列

指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……
在数学上，斐波纳契数列以如下被以递归的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）。

也可用矩阵来表示：

斐波那契数列在自然生活中无处不在，花瓣数目、黄金分割、杨辉三角、近似的股票波动周期等。

二、源代码：

#include <iostream>
#include <iomanip>
#include <memory>
#include <queue>
#include <vector>
#include <cmath>

using namespace std;

//Iteration
unsigned long long Fib_Iteration(unsigned long long fib) {
	if (fib > 2) {
		auto a1 = 1, a2 = 2, a3 = 0;
		for (auto i = 0; i < fib - 2; ++i) {
			a3 = a1 + a2;
			a1 = a2;
			a2 = a3;
		}
		return a3;
	}
	else if (fib == 2) {
		return 2;
	}
	else if (fib == 1) {
		return 1;
	}
	return 1;
}

//Recursive
unsigned long long Fib_Recursive(unsigned long long fib) {
	if (fib > 2) {
		return (Fib_Recursive(fib - 1) + Fib_Recursive(fib - 2));
	}
	else if (2 == fib) {
		return 2;
	}
	else if (1 == fib) {
		return 1;
	}
	return 1;
}

//Formula
unsigned long long Fib_Formula(unsigned long long fib) {
	if (fib > 0) {
		double square_root_5 = sqrt((double)5);
		return (pow((1 + square_root_5), (double)(fib + 1)) - pow((1 - square_root_5), (double)(fib + 1))) / (pow((double)2, (double)(fib + 1))*square_root_5);
	}
	return 1;
}

//Queue
unsigned long long Fib_Queue(unsigned long long fib) {
	if (fib > 2) {
		queue<unsigned long long> resultQueue;
		resultQueue.push(1);
		resultQueue.push(2);
		for (auto i = 2; i < fib; ++i) {
			resultQueue.push(resultQueue.front() + resultQueue.back());
			resultQueue.pop();
		}
		return resultQueue.back();
	}
	else if (2 == fib) {
		return 2;
	}
	else if (1 == fib) {
		return 1;
	}
	return 1;
}

//Array
unsigned long long Fib_Array(unsigned long long fib) {
	unsigned long long result = 1;
	if (fib > 2) {
		unique_ptr<unsigned long long[]> pArray(new unsigned long long[fib]);
		pArray[0] = 1;
		pArray[1] = 2;
		unsigned long long i;

		for (i = 2; i < fib; ++i) {
			pArray[i] = pArray[i - 1] + pArray[i - 2];
		}
		result = pArray[i - 1];
	}
	else if (2 == fib) {
		return 2;
	}
	else if (1 == fib) {
		return 1;
	}
	return result;
}

//Vector
unsigned long long Fib_Vector(unsigned long long fib) {
	if (fib > 2) {
		vector<unsigned long long> resultVec;
		resultVec.reserve(fib);
		resultVec.push_back(1);
		resultVec.push_back(2);
		unsigned long long i;

		for (i = 2; i < fib; ++i) {
			resultVec.push_back(resultVec.at(i - 1) + resultVec.at(i - 2));
		}
		return resultVec.at(i - 1);
	}
	else if (2 == fib) {
		return 2;
	}
	else if (1 == fib) {
		return 1;
	}
	return 1;
}

int main() {
	unsigned long long ii;
	while (cin >> ii) {
		for (auto i = 0; i <= ii; ++i) {
			//cout << Fib_Iteration(i) << endl;
			//cout << Fib_Recursive(i) << endl;
			//cout << Fib_Formula(i) << endl;
			//cout << Fib_Queue(i) << endl;
			//cout << Fib_Array(i) << endl;
			cout << Fib_Vector(i) << endl;
		}
	}

	/*while (cin >> ii) {
		for (auto i = 0; i <= ii; ++i) {
			cout << Fib_Vector(i) << setw(20);
			cout << Fib_Array(i) << setw(20);
			cout << Fib_Formula(i) << setw(20);
			cout << Fib_Queue(i) << setw(20);
			cout << Fib_Recursive(i) << setw(20);
			cout << Fib_Iteration(i) << endl;
		}
	}*/
	
	return 0;
}
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145