(C언어)프로젝트 오일러(Project Euler)14.백만 이하로 시작하는 우박수 중 가장 긴 과정을 거치는 것은?

양의 정수 n에 대하여, 다음과 같은 계산 과정을 반복하기로 합니다.

n → n / 2 (n이 짝수일 때)
n → 3 n + 1 (n이 홀수일 때)

13에 대하여 위의 규칙을 적용해보면 아래처럼 10번의 과정을 통해 1이 됩니다.
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

아직 증명은 되지 않았지만, 이런 과정을 거치면 어떤 수로 시작해도 마지막에는 1로 끝나리라 생각됩니다.
(역주: 이것은 콜라츠 추측 Collatz Conjecture이라고 하며, 이런 수들을 우박수 hailstone sequence라 부르기도 합니다)

그러면, 백만(1,000,000) 이하의 수로 시작했을 때 1까지 도달하는데 가장 긴 과정을 거치는 숫자는 얼마입니까?참고: 계산 과정 도중에는 숫자가 백만을 넘어가도 괜찮습니다.

---

#include <stdio.h>

int hailstone(long long n, int count);

int main(void)
{
    long long n; 
    int max_value, count, max_count = 0;
    for (n = 1; n <= 1000000; n++)            //n을 1부터 백만까지 늘린다.
    {
        count = 1;                            
        count = hailstone(n, count);        //hailstone을 호출해 횟수를 구한 후 반환한다.
        if (max_count < count) {            //가장 많은 횟수를 거친 우박수를 저장한다.
            max_value = n;
            max_count = count;
        }
    }
    printf("%d, %d\n", max_value, max_count);    //우박수와 횟수를 출력한다

    return 0;
}

int hailstone(long long n, int count)        //n과 count를 인수로 받는다.
{
    if (n == 1)                                //n이 1이라면
        return count;                        //count를 반환해 과정을 마친다
    if (n % 2 == 0)                            //n이 짝수일 때
        n = n / 2;
    else                                    //n이 홀수일 때
        n = 3 * n + 1;
    count++;                                //과정을 1회 실시한 후 count를 1 증가시킨다
    return hailstone(n, count);                //재귀호출로 n이 1이 될때까지 실시한다
    
}​

 

 

c언어 교재에서 팩토리얼을 계산할 때 재귀호출 함수를 쓰던 게 기억났다. 콜라츠 추측도 비슷하게 할 수 있지 않을까 싶어 시도해봤다.

 

int hailstone(long long n, int count)        //n과 count를 인수로 받는다.
{
    if (n == 1)                                //n이 1이라면
        return count;                        //count를 반환해 과정을 마친다
    if (n % 2 == 0)                            //n이 짝수일 때
        n = n / 2;
    else                                    //n이 홀수일 때
        n = 3 * n + 1;
    count++;                                //과정을 1회 실시한 후 count를 1 증가시킨다
    return hailstone(n, count);                //재귀호출로 n이 1이 될때까지 실시한다
    
}​

 

pythontutor를 통해 hailstone 함수가 어떻게 실행되는지 살펴보자.

 

 

문제에서 13을 예시로 들었으므로, 여기서도 13을 사용한다.

n과 i를 long long형으로 선언하고, n을 i에 대입하는 과정은 여기서는 의미 없다. 

 

9번째 줄: 문제에서 13부터 첫 회차라고 인정했으므로, count에 1을 대입하고 시작한다.

10번째 줄: hailstone에서 마지막에 반환되는 값은 실행 횟수이므로 이를 count에 다시 대입한다.

 

 

 

i, count를 인수로 주었으니 hailstone 함수 안에서 n과 count의 초기값은 13, 1이 된다.

13은 1이 아니고, 짝수도 아니므로 20번째 else 구문을 실행한다. n = 13 * 3 + 1 = 40 이 된다.

이후 count를 증가시키고, n과 count를 인수로 해 hailstone을 재귀호출한다.

 

n은 짝수이므로 이 호출단계에서 n = 40 / 2 = 20이다. 

 

 

 

이 과정을 n이 1이 될 때까지 반복한다. 

 

 

마지막 과정엔 hailstone의 count 값이 main함수의 count값에 반환된다. count값은 10으로 문제에서 예로 든 해답과 동일하다. 

이 과정을 반복문에 넣어 백만번 돌리면 된다.

 

if (max_count < count) {            //가장 많은 횟수를 거친 우박수를 저장한다.
            max_value = n;
            max_count = count;
        }
    }
    printf("%d, %d\n", max_value, max_count);    //우박수와 횟수를 출력한다

 

max_count는 최대 실행 횟수를 저장하는 변수이다. 이 값이 count보다 작으면(현재 count값이 가장 크면) max_value에는 현재 n값이 저장되고, max_count에는 현재 count값이 저장된다. 그리고 값을 출력한다.

 

 

---

n을 long long으로 선언하고, i라는 변수를 만든 이유

1. 처음에 hailstone 함수의 매개변수 n을 int형으로 선언했었다. n이 100일 때, 1000일 때, 10000일 떄도 잘 실행되어서 기뻤는데, 1000000을 집어넣으니 스택오버플로우가 발생했다. n이 int형으로 선언된 게 문제였다. 계산 중에 int 범위를 넘어버렸나보다. long long으로 변경하면 잘 실행된다.

 

2. long long으로 변경하기 이전에, 재귀호출을 너무 많이해서 에러가 났나 싶어 한 번 반복문으로 바꾸었다. 

 

int main(void)
{
    int n, count, max_value, max_count = 0;
    for (n = 1; n <= 1000000; n++)
    {
        int i = n;
        count = 1;
        while (i != 1) {
            if (i % 2 == 0)
                i = i / 2;
            else
                i = 3 * i + 1;
            count++;

            if (max_count < count) {
                max_value = n;
                max_count = count;
            }
        }
    }
    printf("%d, %d\n", max_value, max_count);

    return 0;
}​

 

이 코드에서는 i가 아니라 n을 그대로 사용하면 안된다. i가 모두 n이었다 생각해보면, while문 안에서 n은 최종적으로 1이 된다. 그리고 while문을 빠져나오면 n은 1인 상태에서 for문에 의해 2가 된다. 다시 1이 되고, 2가 되고 1이 되는 무한루프에 빠진다. 그래서 i에다 n을 대입해 사용했던건데, 캡처할 때 안바꾼지 몰랐다.

---

 

실행하니 5초 정도 지난 후 결과가 출력됐다.

정답: 837799 , 525회 실행