양의 정수 n에 대하여, 다음과 같은 계산 과정을 반복하기로 합니다.
n → n / 2 (n이 짝수일 때)
n → 3 n + 1 (n이 홀수일 때)
n → 3 n + 1 (n이 홀수일 때)
13에 대하여 위의 규칙을 적용해보면 아래처럼 10번의 과정을 통해 1이 됩니다.
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
아직 증명은 되지 않았지만, 이런 과정을 거치면 어떤 수로 시작해도 마지막에는 1로 끝나리라 생각됩니다.
(역주: 이것은 콜라츠 추측 Collatz Conjecture이라고 하며, 이런 수들을 우박수 hailstone sequence라 부르기도 합니다)
(역주: 이것은 콜라츠 추측 Collatz Conjecture이라고 하며, 이런 수들을 우박수 hailstone sequence라 부르기도 합니다)
그러면, 백만(1,000,000) 이하의 수로 시작했을 때 1까지 도달하는데 가장 긴 과정을 거치는 숫자는 얼마입니까?
참고: 계산 과정 도중에는 숫자가 백만을 넘어가도 괜찮습니다.
규칙을 찾아보려고 했는데, hailstone sequence 로 검색을 해보니 아직까지도 연구가 되고 있는 수열인듯 했습니다. 처음엔 바이너리 트리로 구현을 해보려 했으나, 수행속도에 비해 트리 구현하는 시간이 훨씬 오래 걸릴 것 같아서 브루트 포스를 적용하였습니다. ( 실은 답이 너무 궁금했습니다. ) 후에 궁금해지면 트리를 구현 해봐야겠습니다.
포스팅 맨 아래에는 답이 있으므로, 원하지 않으시면 스크롤에 주의해주세요 :)
오류 1 : int 의 인식범위맨 처음에는 모든 숫자변수를 int 로 구현했습니다. C++의 int 범위는 -2,147,483,648 ~ 2,147,483,647 (약 21억) 정도인데, hailstone 그래프를 보면 20억보다 더 높이 치솟는 것을 볼 수 있습니다. 문제의 조건값 범위가 100만보다 훨씬 아래였다면 int 로도 무사히(?) 넘어갔을텐데, 이로 인해 변수타입의 범위에 대해 한번 더 경각심을 일깨우게 되네요.
int로 구현하면, 범위 초과에 의해 답이 910107(475~6회 수행)이 나옵니다. 아무리 사이트에 답을 때려넣어도 "틀렸으니 재시도 바람" 이라는데, 코드는 아무리 봐도 정상인것 같을 뿐이고. 분명 어딘가 틀렸는데 어디가 틀린건지 알 수가 없었습니다. 결국엔 구글 검색을 해보았는데, 저와 같은 짓을 하신 분들이 꽤 계셨습니다 ㅋㅋㅋ 잠깐 동질감 느끼고, 얼른 변수형태를 바꿨습니다.
#include <iostream>
using namespace std;
int main(void)
{
unsigned long int now = 1; // 현재 연산 숫자
int cnt = 0; // 연산수행 카운터
unsigned long int nowMax = 0; // 최다 연산수 숫자
int cntMax = 0; // 최다 연산수
unsigned long int tmpMax = 0;
while ( now++ < 1000000 ) {
cnt = 1;
unsigned long int tmp = 0; // 연산용 임시변수
tmp = now;
while(tmp > 1) {
if ( tmp % 2 == 0 ) {
tmp = tmp >> 1; // 짝수이면 2로 나눔
} else {
tmp = tmp * 3 + 1; // 홀수이면 n*3+1
}
if ( tmp > tmpMax ) tmpMax = tmp;
cnt++;
}
if ( cnt > cntMax ) { // 최다 연산수 확인
cntMax = cnt;
nowMax = now;
cout << now << " " << cnt << " " << tmpMax << endl;
}
}
cout << nowMax << " " << cntMax << endl; // 출력
return 0;
}
연산 도중 최대 값이 궁금하여 tmpMax를 삽입하였습니다.
위에 대한 출력은 다음과 같습니다.
2 2 1
3 8 16
6 9 16
7 17 52
9 20 52
18 21 160
25 24 160
27 112 9232
54 113 9232
73 116 9232
97 119 9232
129 122 9232
171 125 9232
231 128 9232
313 131 13120
327 144 13120
649 145 41524
703 171 250504
871 179 250504
1161 182 250504
2223 183 1276936
2463 209 1276936
2919 217 1276936
3711 238 1276936
6171 262 8153620
10971 268 27114424
13255 276 27114424
17647 279 27114424
23529 282 50143264
26623 308 106358020
34239 311 121012864
35655 324 121012864
52527 340 121012864
77031 351 593279152
106239 354 1570824736
142587 375 2798323360
156159 383 2798323360
216367 386 17202377752
230631 443 17202377752
410011 449 24648077896
511935 470 24648077896
626331 509 24648077896
837799 525 56991483520
837799 525
참조
자바스크립트 연산범위 참고 : http://lambdaexp.tistory.com/59
동일한 오류 (int범위 초과) : http://www.dreamincode.net/forums/topic/165403-project-euler-collatz-sequence/
