[Programming Challenges] 3n+1 - 난이도(하)

[ 문제 ] - 3n+1

어떤 수열을 만들어내는 다음과 같은 알고리즘을 생각해보자. 어떤 정수 n에서 시작해 n이 짝수면 2로 나누고, 홀수면 3을 곱한 다음 1을 더한다. 이렇게 해서 새로 만들어진 숫자를 n으로 놓고 n=1이 될 때까지 같은 작업을 계속 반복한다. 예를 들어 n=22이면 다음 과 같은 수열이 만들어 진다. 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 아직 증명되지 않았지만 모든 정수 n에 대해 이 알고리즘을 적용시키면 결국에는 n=1에 이르게 되는 것으로 추측된다. 그리고 이 가설은 적어도 1,000,000까지의 정수에 대해서는 참이다.  n이라는 값이 입력되었을 때 1이 나올 때까지 만들어진 수의 개수 (1 포함)을 n의 사이클 길이라고 한다. 위에 수열을 예로 들면 22의 사이클의 길이는 16이다. i와 j라는 두 개의 수가 주어 졌을 때 두 수(포함) 사이의 모든 수에 대해 최대 사이클 길이를 구하라.

 

[ 입 출력 조건 ]

입력 입력은 일련의 정수 쌍 i와 j로 구성되며 한 줄에 한 쌍의 수가 입력된다. 모든 정수는 1,000,000보다 작고 0보다 크다. i와 j가 -1 이면 종료   출력 각 정수 쌍 i와 j를 입력된 순서대로 출력하고 i와 j 사이의 최대 사이클 길이를 출력한다. 이 세수는 각각 하나씩의 스페이스로 구분되어야 하며 세수가 모두 한 줄에 출력되어야 하고 입력된 각 줄마다 한 줄씩 출력해야 한다.

 

[ 입출력 예 ]

1 10 100 200 100 20 201 210 900 100 900 1000 -1 -1

1 10 20 100 200 125 100 20 119 201 210 89 900 100 179 900 1000 174

 

소스코드

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

#include <stdio.h>   int main() {     int result = 0, a, b, cnt = 1;     while (1)     {         scanf("%d %d", &a, &b);         if (a == -1 && b == -1)             return 0;           if (a < b)         {             for (int i = a; i <= b; i++)             {                 int tmp = i;                 while (1)                 {                     if (tmp == 1)                     {                         if (cnt > result)                         {                             result = cnt;                             break;                         }                         break;                     }                       if (tmp % 2 == 0) // 짝수면                         tmp /= 2;                     else // 홀수면                         tmp = tmp * 3 + 1;                     cnt++;                 }                 cnt = 1;             }         }         else         {             for (int i = a; b <= i; i--)             {                 int tmp = i;                 while (1)                 {                     if (tmp == 1)                     {                         if (cnt > result)                         {                             result = cnt;                             break;                         }                         break;                     }                       if (tmp % 2 == 0) // 짝수면                         tmp /= 2;                     else // 홀수면                         tmp = tmp * 3 + 1;                     cnt++;                 }                 cnt = 1;             }         }         printf("%d %d %d\n", a, b, result);         result = 0;     }     return 0; }

아래는 테스트 케이스입니다. 

Sample Data.zip