// Fibonacci sequence
What is Fibonacci sequence?
<Fibonacci sequence>란, 임의의 항의 값이 이전의 두 항의 값을 더한 값을 가지는 수열을 의미한다. 이를 점화식으로 표현하면 아래와 같다.
An = 1 , ( n <= 2 ) An = A(n-1) + A(n-2) , otherwise |
위 식을 토대로 간략하게 10번째 항까지 구해보면 아래와 같다.
A1 | A2 | A3 | A4 | A5 | A6 | A7 | A8 | A9 | A10 |
1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 |
위의 표를 살펴보면,
- A1 + A2 = A3
- A2 + A3 = A4
- A3 + A4 = A5
- A4 + A5 = A6
- A5 + A6 = A7
- A7 + A8 = A9
- A8 + A9 = A10
의 식들이 성립함을 알 수 있다.
위의 표에 나타나지 않은 11번째 항부터 값이 어떻게 될까 예상해보려 한다면 <Fibonacci sequence>는 큰 어려움 없이 쉽게 이해할 수 있는 개념일 것이다.
Code
"<Dynamic programming (동적계획)>을 이용하여 구현한 <Fibonacci sequence>"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <iostream>
#include <vector>
#define N 93
using namespace std;
int n;
vector<unsigned long long> Fibonacci_dynamic(N + 1);
int main() {
cin >> n;
// *********** Dynamic programming ***********
Fibonacci_dynamic[0] = 0;
Fibonacci_dynamic[1] = 1;
for (int i = 2; i <= n; i++) {
Fibonacci_dynamic[i] = Fibonacci_dynamic[i - 1] + Fibonacci_dynamic[i - 2];
}
// ********************************************
cout << Fibonacci_dynamic[n];
}
|
cs |
위 코드에서 fibonacci_dynamic vector의 자료형을 0을 포함한 양의 정수의 범위에서 표현할 수 있는 가장 큰 자료형인unsigned long long으로 지정했음에도 위 코드에서는 피보나치수열의 93번째항 까지만 구할 수 있다.
Fibonacci_dynamic[92] == 7,540,113,804,746,346,429 Fibonacci_dynamic[93] == 12,200,160,415,121,876,738 max number of unsigned long long == 18,446,744,073,709,551,615 |
위의 박스 안의 수치들만 봐도, 94번째 항을 unsigned long long 자료형으로 표현했다간 overflow가 발생할 것 이라는 걸 알 수 있다. 만약 93번째 항보다 더 이후의 항의 값을 알기를 원한다면, 정수형 자료형이 아닌 실수형 자료형을 이용할 수도 있을거라는 생각을 할 수 있다.
만약 <Fibonacci sequence>를 구현해야 한다면 이 <Dynamic programming>을 사용하는 것을 추천한다.
"<Recursion (재귀)>을 이용하여 구현한 <Fibonacci sequence>"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <iostream>
using namespace std;
int Fibonacci_re(int num) {
if (num == 0) return 0;
else if (num == 1) return 1;
else {
return Fibonacci_re(num - 1) + Fibonacci_re(num - 2);
}
}
int main() {
int num;
cin >> num;
cout << Fibonacci_re(num);
}
|
cs |
위 코드는 <Recursion>를 이용하여 <fibonacci sequence>를 구현한 것인데, 이 방법은 입력되는 num 의 값이 작은 경우에만 사용 가능하다. 그 이유는 아래 입력되는 num값에 따른 Fibonacci_re함수의 호출 횟수를 보며 파악하자. num이 0과 1일때는 당연히 호출횟수가 1회임을 알 수 있으므로 아래 표에선 제외했다.
num | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Fibonacci 호출횟수 |
3 | 5 | 9 | 15 | 25 | 41 | 67 | 109 | 177 |
num값에 대한 Fibonacci_re함수의 호출 횟수는 (num - 1)값과 (num - 2)값의 호출 횟수를 더한 값에 처음에 Fibonacci_re[num]을 한번 호출했던 횟수인 1을 더한 값임을 알 수 있다. 결국 num이 커질수록 Fibonacci_re함수의 호출횟수 또한 기하급수적으로 커지는 것이다. 따라서 우리는 <Recursion>을 이용하여 <Fibonacci sequence>를 구현하려면 구현하고자 하는 항의 크기가 작을때만 사용 가능하다는 것을 알 수 있다.
"수열(Sequence)" 이란?
* 어떠한 규칙에 따라 차례로 나열된 수의 열을 말한다.
'Algorithm (C++ based) > Math' 카테고리의 다른 글
CCW (Counter Clock Wise) (0) | 2021.06.27 |
---|---|
Monge array (Monge matrix) (0) | 2021.02.03 |
power 함수 구현 (분할 정복 이용) (0) | 2021.01.29 |
Pascal's triangle (파스칼의 삼각형) (0) | 2021.01.28 |
Lucas's theorem (뤼카의 정리) (0) | 2021.01.27 |
댓글