3N+1문제 template metaprogramming으로 풀기

어떤 정수 n에서 시작해 n이 짝수면 2로 나누고, 홀수면 3을 곱한 다음 1을 더한다. 이렇게 해서 새로 만들어진 숫자를 n으로 놓고 n=1이 될 때까지 같은 작업을 계속 반복한다.

 

임의의 n이 주어졌을 때, 1이 나올 때까지 만들어진 수의 개수(1 포함)를 구하는 함수를 작성하라.

순차적인 방법

펼쳐두기..

int cycle(int N)

{

    int count = 0;

    while(1)

    {

        ++count;

        if( N == 1 )

            break;

        if( !(N%2) )

        {

            N /= 2;

        }

        else

        {

            N = 3*N+1;

        }

    }

    return count;

}

재귀적인 방법

펼쳐두기..

int selector(int N)

{

    if( !(N%2) )

   {

        return N/2;

    }

    return 3*N+1;

}

 

int cycle(int N)

{

    if( N == 1 )

        return 1;

    return 1 + cycle(selector(N));

}

템플릿 메타프로그래밍

펼쳐두기..

template<bool COND, int N>
struct selector
{
    enum{ next = N / 2 };
};
template<int N>
struct selector<false, N>
{
    enum{ next = 3*N+1 };
};

template<int N>
struct series
{
    enum{ cycle = 1 + series<selector<!(N%2),N>::next>::cycle };
};
template<>
struct series<1>
{
    enum{ cycle = 1 };
};