프로그래밍 | 2010. 1. 19. 20:56
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 사이의 모든수( i, j 포함 )에 대해 최대 사이클 길이를 구하라.
입력
입력은 일련의 정수쌍 i, j로 구성되며 한 줄에 한 쌍의 수가 입력된다.
모든 정수는 1,000,000보다 작고 0보다 크다.
출력
각 정수쌍 i와 j에 대해 i와 j를 입력된 순서대로 출력하고 i와 j사이( i, j포함 )의 최대 사이클 길이를 출력한다.
이 세수는 각각 하나씩 스페이스로 구분되어야 하며 세수가 모두 한 줄에 출력되어야 하고, 입력된 각 줄마다 한 줄씩 출력해야 한다.
Sample Input
1 10
100 200
201 210
900 1000
Sample Output
1 10 20
100 200 125
201 210 89
900 1000 174
코딩도장 - Four Boxes (0) | 2010.01.19 |
---|---|
코딩도장 - Primary Arithmetic (0) | 2010.01.19 |
WinDbg 출력 결과를 파일로 보내자 (0) | 2010.01.07 |
IME를 강제로 활성, 비활성 시키기 (0) | 2009.12.24 |
Collective Intelligence - Making Recommendations (0) | 2009.12.24 |
Recent Comments