문제 1 : 3n + 1 문제 ( The 3n+1 Problem )

PC/UVa ID : 110101/100, 인기도 : A, 성공률 : 낮음, 레벨 : 1

반복 사이클의 길이를 구하는 문제이다. 반복 사이클의 길이는 어떤 정수 n 이 있을 때, n으로 시작해 n이 짝수면 2로 나누고, 홀수면 3을 곱한 다음 1을 더한다. 이렇게 해서 새로 만들어진 숫자 n 이 1 이 될 때까지 같은 작업을 계속 반복한다. 이 반복이 1번당 길이 1 이라고 친다.

예를 들어 n == 22 라면, 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 가 만들어 지고, 16 사이클로 길이가 나온다.

입력

정수 두개( i, j )를 받는다. 이 두 정수는 1 ~ 1,000,000 사이의 숫자여야 한다. 1 ~ 1,000,000 까지의 수자는 모두 n == 1 로 만들어 진다고 하는데, 그 원리는 아직 증명되지 못했다고 한다.

출력

i, j 를 우선 출력하고, 이 사이의 숫자 중 가장 긴 사이클의 길이를 출력 한다.

예)

입력 : 1 10
출력 : 1 10 20

총평

문제를 푸는 중에 생각 하게 만든 것은 n == 1 이 될때까지 루프를 돌려야 한다는 점, 짝수일 경우와 홀수일 경우 를 체크해야 한다는 점, 그리고, 사이 값들의 싸이클 길이를 기록해 두어야 한다는 점, 이 중 최고 큰 사이클을 출력해야 하는 점 을 우선 생각했고, 부수적으로 값이 입력 값의 대소관계에 따른 문제점을 추가적으로 생각했다.

음, 입 코딩은 여기서 그만, 루아 코드 첨부

function input_number_extent_check( a ) if 0 < a and 1000000 >= a then return true end return false end function swap( a, b ) local t = a a = b b = t return a, b end function get_cycle_lenght( n ) --print( "get_cycle_lenght() start", n ) local tm_n = n local count = 1 while 1 ~= n do if 0 == n % 2 then n = n / 2 else n = ( n * 3 ) + 1 end count = count + 1 end --print( "return of get_cycle_lenght() is "..count ) return count end function main() local i, j = io.read("*number", "*number") local a = input_number_extent_check( i ) local b = input_number_extent_check( j ) if false == ( a and b ) then local error_msg = "입력 정수는 1 ~ 1,000,000 사이여야만 합니다" return error_msg end tm_i, tm_j = i, j if tm_i > tm_j then tm_i, tm_j = swap( tm_i, tm_j ) end local tb_cycle_lenght = { } while tm_i <= tm_j do tb_cycle_lenght[#tb_cycle_lenght + 1] = get_cycle_lenght( tm_i ) tm_i = tm_i + 1 end table.sort( tb_cycle_lenght ) return i, j, tb_cycle_lenght[#tb_cycle_lenght] end print( main() )