Fibonacci sequence (피보나치 수열)

// 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>"

#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];
}

  위 코드에서 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>"

#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);
}

  위 코드는 <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)" 이란?

* 어떠한 규칙에 따라 차례로 나열된 수의 열을 말한다.