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이 나올 때까지 만들어진 수의 개수를 n의 사이클 길이(cycle-length) 라고 한다. 

문제가 이것이였다. 그래서 Linked-List 자료구조로 한번 만들어 보았다. 여기 문제에서는 1백만번까지의 정수에 대해 참이라고 해서, 한번 2백만번까지 돌려보았다. 2백만번 까지도 참이었다. 그 이상은 안해보아서 모르겠다. 

그리고, 결과 값을 보니 중첩되는 숫자가 없어 혹시나해서 몇번이고 테스트를 해보았다. 신기하게도 중복되는 숫자가 없었다. 

오오~ 아직은 어느 상황에서 쓰면 좋을 지 감이 잘 오지않지만, Houdini에서 중복되는 숫자가 없어야 하는 상황에서 이 알고리즘을 적용해서 쓰면 괜찮겠다는 생각이 든다.

DLinkedList.cpp

DLinkedList.h

ques.cpp

 

실행 결과

과과

---

The_three_algorithm.c