오랜만에 서북부에서 jachin님을 만났다,
그리고 받아온 책이,,'Programming Challenges' 이다,,

첫장을 넘기며 첫번째 퀴즈를 보았는데, 재밌어 보였다.
잠깐 생각해보고, 다음날이 되서야 곰곰히 생각해 볼수 있었다.

어떤 수열을 만들어내는 다음과 같은 알고리즘을 생각해보자. 어떤 정수 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포함)에 대해 최대 사이클 길이를 구하라.

이와 같은 문제였다. 문제를 풀기는 했다, 소스는 다음과 같다,,

오랜만에 내 집중력을 높여준 문제인것 같다. 사실 문제의 위에 문제의 ID와 인기도, 성공률, 레벨 등이 나와있었는데, 성공률이 낮다는 말에 이 문제에 더 집착하게 된건지도 모르겠다.

저 위에 소스는 우선 책에 나와있는 요구조건메 맞춰 풀어보았다.
입력 예와 맞게 나오는 걸로 만족 했지만, 이 것의 본 문제를 찾게 되었다.

책의 문제에 대한 힌트 부분에 http://www.math.grinnell.edu/~chamberl/conf.html 이와 같은 URL이 있었다. 사실,, 독어를 읽을줄 몰라 다른 한국어 웹페이지를 찾았는데,,
http://goodking.new21.net/bbs/rgboard/view.php?&bbs_id=00005&page=3&doc_num=1705&PHPSESSID=2d320016a96a89b89bad77a8b139ab69 이와 같은 URL에 문제가 나와 있었다. 이 페이지에 의한 본 문제는,
문제. 아래 두 명령을 가지고 자연수 9를 1로 만들 수 있을까?

       명령 1. 홀수인 경우, X를 곱한 후 Y를 더하라!
       명령 2. 짝수인 경우, Z로 나누기를 하라!

9가 1로 변환되려면, X, Y, Z는 1,2,3 중에서 각각 어떤 것이 되어야 할까?

Collatz Conjecture: 명령 1과 명령 2에 의해 모든 자연수는 항상 1로 변환될까?

문제를 만족하는 (X,Y,Z)에 대해 명령 1과 2에 의한 컴퓨터 계산 결과, 반례가 나온 적은 아직 없다고 합니다. 그러나 왜 그런지는 증명이 안 되었기 때문에, Collatz Conjecture는 아직 안 풀린 문제로 남아 있다고 합니다.
라고 한다. 여러 댓글이 달렸는데,, 으음,,, 이 문제는 좀더 복잡한것 같다.
이 문제에 대해서도 내가 코딩을 할 수 있을까?

+ Recent posts