근육 트레이닝을 못하니 뇌라도 트레이닝 해야지 라는 생각에 샀지만.. 사실.. 아마 한달이 못가서 어디 구석에 박혀 있을듯함..-.-;
어차피 책 자체가 웹상에 있는 알고리즘 문제를 옮겨다 `번역해서` 적어놓은 것이기 때문에.. 내가 여기다 불펌을 해도 그다지 큰 문제가 될...지는 모르겠음. (만약 역자-혹은 관계자분-께서 지우라시면 즉시 지우겠슴.)
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의 사이클 길이(cycle-length)라고 한다. 위에 있는 수열을 예로 들면 22의 사이클 길이는 16이다. i와 j라는 두 개의 수가 주어졌을 때 i와 j사이의 모든 수(i,j 포함)에 대해 최대 사이클 길이를 구하라.
입력 예 (입력은 일련의 정수쌍 i와 j로 구성되며, 한줄에 한 쌍의 수가 입력된다.)
1 10
출력 예(각 정수쌍 i와 j에 대해 i와 j를 입력된 순서대로 출력하고 i와 j사이(i ,j포함)의 최대 사이클 길이를 출력한다.)
1 10 20
덧글