[C언어 소스] 피보나치 수열 – 재귀 알고리즘과 탐욕 알고리즘으로 구현

안녕하세요. 언제나 휴일에 언휴예요.

1. 피보나치 수열과 알고리즘

1, 1, 2, 3, 5, 8, 13, 21, 34, …

어디선가 본 듯한 수열 아닌가요?

수열의 “각 항의 값은 이전 두 항의 값의 합이다.” 명제가 참이라 많이 생각하지요.

하지만 “1항과 2항은 1이다.”라는 예외 조항까지 명확하게 제시해야 참인 피보나치 수열입니다.

피보나치 수열의 정의를 보면 n항을 구하기 위해 피보나치 수열 n-1항과 n-2항을 이용해야 합니다.

이는 재귀적인 방법으로 문제를 해결할 수 있음을 의미하죠.

비교적 간단한 수열이면서 재귀적인 방법으로 계산할 수 있다는 특징을 갖고 있어서 알고리즘 교육에서 자주 등장하는 문제입니다.

특히 이전에 계산한 값을 이용하여 문제를 해결하였을 때 비약적인 속도 개선이 이루어질 수 있어서 탐욕 알고리즘에서도 많이 사용합니다. (탐욕 알고리즘은 경험 정보를 이용하여 문제를 해결하는 알고리즘입니다.)

2. 피보나치 수열 – 재귀 알고리즘으로 구현

#include 
int Fibonacci(int n);

int main()
{
    int i = 0;

    printf("========================\n");
    for (i = 1; i < 20; i++)
    {
        printf("%5d ", Fibonacci(i));
        if (i % 5 == 0)
        {
            printf("\n");
        }
    }
    return 0;
}
int Fibonacci(int n)
{
    if(n<1)
    {
        return 0;
    }
    if ((n == 1) || (n == 2))
    {
        return 1;
    }
    return Fibonacci(n - 2) + Fibonacci(n - 1);
}

3. 피보나치 수열 – 탐욕 알고리즘으로 구현

#include 
#define MAX_FIBO 40
int values[MAX_FIBO] = { 1,1 };

int main()
{
    int i = 0;
    for (i = 1; i < MAX_FIBO; i++)
    {        
        printf("%5d ", Fibonacci2(i));
        if (i % 5 == 0)
        {
            printf("\n");
        }
    }

    return 0;
}
int Fibonacci2(int n)
{
    if (n < 1)
    {
        return 0;
    }
    if (values[n - 1])
    {
        return values[n - 1];
    }
    values[n-1] =  Fibonacci2(n - 2) + Fibonacci2(n - 1);
    return values[n - 1];
}

4. 피보나치 수열 – 수행 시간 비교

/* https://ehpub.co.kr                                                                                          
   언제나 C언어 예제 Center                                                                                                          
   피보나치 수열
   1  1  2  3  5  8  13   21   34 ...
*/
#include 
#define MAX_FIBO 40
int values[MAX_FIBO] = { 1,1 };
int Fibonacci2(int n);
int Fibonacci(int n);
int cnt = 0,cnt2=0;

#include 
int main()
{
    int i = 0;    
    clock_t st, et;
    for (i = MAX_FIBO - 5; i < MAX_FIBO; i++)
    {
        printf("=== test case [%d]th\n", i);
        st = clock();
        Fibonacci(i);
        et = clock();
        printf("%d\n", et - st);
        st = clock();
        Fibonacci2(i);
        et = clock();
        printf("%d\n", et - st);
        printf("cnt:%d cnt2:%d\n", cnt, cnt2);
    }
    return 0;
}


int Fibonacci(int n)
{
    cnt++;
    if(n<1)
    {
        return 0;
    }
    if ((n == 1) || (n == 2))
    {
        return 1;
    }
    return Fibonacci(n - 2) + Fibonacci(n - 1);
}

int Fibonacci2(int n)
{
    cnt2++;
    if (n < 1)
    {
        return 0;
    }
    if (values[n - 1])
    {
        return values[n - 1];
    }
    values[n - 1] = Fibonacci2(n - 2) + Fibonacci2(n - 1);
    return values[n - 1];
}

실행 결과

=== test case [35]th
357
0
cnt:18454929 cnt2:67
=== test case [36]th
551
0
cnt:48315632 cnt2:70
=== test case [37]th
954
0
cnt:96631265 cnt2:73
=== test case [38]th
1489
0
cnt:174807602 cnt2:76
=== test case [39]th
2460
0
cnt:301299573 cnt2:79

C언어 소스