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

 

재귀 알고리즘으로 작성한 피보나치 수열

#include <stdio.h>
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);
}

---

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

#include <stdio.h>
#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];
}

---

수행 시간을 비교

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

#include <time.h>
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