The 3n+1 Problem

시간날때마다 Programming Challenges를 보고 있습니다. 그중에 한 문제를 올립니다.

문제는 http://acm.uva.es/p/v1/100.html를 보시면 정확하게 설명되어있습니다.

짧은 설명은 다음과 같습니다.

어떤 수열을 만들어내는 알고리즘이 있는데 n이 짝수이면 2로 나누고, n이 홀수이면 n * 3 + 1을 한다. n=1이 될때까지 같은 작업을 계속 반복한다.

아직 명확하게 증명되지 않았지만 모든 정수 n에 대하여 이 알고리즘을 적용시키면 결국에는 n=1이 된다고 추측된다. 이 가설은 적어도 1,000,000까지의 정수에 대해서는 참이다.

n이라는 값이 입력되었을 때 1이 나올때까지 만들어진 수의 개수(1 포함)를 n의 사이클 길이(cycle-length)라고 한다. i와 j라는 두개의 수가 주어졌을 때 i와 j사이의 모든 수(i, j 포함)에 대하여 최대 사이클 길이를 구하라.

우선 C++로 문제를 풀면 다음과 같다.

// 3nplus1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

unsigned long cycle(unsigned long num);

int main(int argc, char* argv[])
{

    long lbound, ubound, lbOrg, ubOrg, temp;
    long i, length, max_length;

    while(scanf("%ld %ld", &lbound, &ubound) == 2) {
        lbOrg = lbound;
        ubOrg = ubound;

        //printf("%ld %ld", lbound, ubound);
   
        if (lbound > ubound) {
            temp = lbound;
            lbound = ubound;
            ubound = temp;
        }

        max_length = 0;

        for (i = lbound; i <= ubound; i++) {
            //printf("Loof of %ld \n", i);

            length = cycle(i);

            if (length > max_length) {
                max_length = length;
            }

            printf("%ld ~ %ld = %ld\t(Max: %ld)\n", lbOrg, ubOrg, length, max_length);
        }

        printf("Max Cycle is %ld!\n\n", max_length);
    }

    return 0;
}

unsigned long cycle(unsigned long num){
    //printf("New cycle: %ld\n", num);

    unsigned long length, tmp_num;
    tmp_num = num;
    length = 1;

    while(tmp_num != 1) {
        if (tmp_num & 1) {
            tmp_num = tmp_num * 3 + 1;
            length ++;
        }

        while (!(tmp_num & 1)) {
            tmp_num = tmp_num / 2;
            length ++;
        }
    }

    return length;
}

흠.. 적당한지 모르겠다. 뭔가 더 줄일 수 있을것 같기도 하고..
알고리즘 문제는 하나 하나 풀때마다.. 더 어려워지는 것 같다.. 아직도 한발도 나아지지 못한것 같다..

더 좋은 알고리즘을 알고 계신분은 많은 조언부탁드립니다.