C 언어로 콜라츠의 추측(Collatz conjecture)
추천글 : 【C 언어】 C 언어 목차
콜라츠의 추측은 1937년에 처음으로 이 추측을 제기한 로타르 콜라즈(Lothar Collatz)의 이름을 딴 것으로, 3n+1 문제, 우박수 문제라고도 불린다. 콜라츠의 추측은 임의의 자연수를 입력해도 다음 알고리즘은 항상 끝이 난다는 것이다.
1. n을 입력받는다.
2. 만약 n이 1이면 멈춘다(STOP).
3. 만약 n이 1이 아닌 홀수이면 3n + 1을 한다.
4. 만약 n이 짝수이면 2로 나눈다.
5. 2 ~ 4를 반복한다.
만약 n이 22라면 위 알고리즘은 다음과 같은 값을 출력한다.
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
이 알고리즘은 우리가 다루는 대부분의 수의 범위 내(~ 20 × 258)에서는 종료되지만 모든 입력 값에 대해서는 성립하는지 아직 증명되지 않았다. 혹자는 결국 답을 알아낼 수 없는 문제가 아니냐는 의문을 표한다. 아래 알고리즘은 적당한(~ 10,000,000) 자연수 a와 b 까지의 수 중에서 사이클 길이가 가장 긴 수를 찾는 알고리즘을 담고 있다. 이 알고리즘의 최적화는 각자가 고민해 주기를 바란다. 또한 C2 알고리즘을 응용하면 특정 수에 대한 사이클을 출력할 수 있다.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define count_set 200000000
/*
This code shows you the least length of n's array between a and b defined by Collatz's problem.
Assumption: all counts are below maximum value of 'short' data type.
Procedure goes as;
1 (over)
2 → 1 (over)
3 → 10 → 5 → 16 → 8 → 4 → 2 (over)
4 (over)
5 (over)
6 → 3 (over)
7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 (over)
*/
short set[count_set + 1] = {0, };
int count;
void C2(long long int n){
count ++;
if(n == 1);
else if(n % 2 == 0) C2(n / 2);
else C2(3 * n + 1);
}
int C(long long int n){
if(n > count_set){
// "n > count_set" means too big number just has appeared.
count = 0;
C2(n);
return count;
}
if(set[n] != 0) return set[n];
// if set[n] = 0, set[n] should be filled the proper number.
if(n % 2 == 1) set[n] = C(3 * n + 1) + 1; // n is odd
else set[n] = C(n / 2) + 1; // n is even
return set[n];
}
int main(int argc, char *argv[]) {
long long int i, a, b, max_order = 1, max = 1;
scanf("%lld %lld", &a, &b);
set[1] = 1;
for(i = a; i <= b; i ++){
set[i] = C(i);
if(set[i] > max){
max_order = i;
max = set[i];
}
}
printf("%lld %lld", max_order, max);
return 0;
}
입력 : 2016.03.01 11:34
'▶ 자연과학 > ▷ C, C++' 카테고리의 다른 글
【C++】 1강. C++ 시작하기 (0) | 2020.11.18 |
---|---|
【코딩】 C 언어로 이항계수 (0) | 2016.06.27 |
【코딩】 C 언어로 행렬식 (0) | 2016.06.27 |
【코딩】 C 언어로 큰 수 처리 (0) | 2016.06.27 |
【코딩】 C 언어로 연속수 (0) | 2016.06.27 |
최근댓글