fibonacchi 수열

fibonacchi 수열의 n번째 항을 구하는 코드를 작성해보자.

f(1) = 1,

f(2) = 2,

f(n) = f(n-1) + f(n-2) ( if n > 2 )

 

순차적인 방법

펼쳐두기..

int fibonacchi(int n)

{

    int f1 = 1, f2 = 2;

    int result;

 

    n -= 2;

    while( n > 0 )

    {

        result = f2 + f1;

        f1 = f2;

        f2 = result;

        --n;

    }

    return result;

}

재귀적인 방법

펼쳐두기..

int fibonacchi(int n)
{
    if( n == 1 )
        return 1;
    else if( n == 2 )
        return 2;
    else
        return fibonacchi( n - 1 ) + fibonacchi( n - 2 );
}

 

템플릿 메타프로그래밍

펼쳐두기..

template<int N>
struct fibonacchi
{
    enum{ result = fibonacchi<N-1> + fibonacchi<N-2> };
};

template<>
struct fibonacchi<1>
{
    enum{ result = 1 };
};

template<>
struct fibonacchi<2>
{
    enum{ result = 2 };
};