【코딩】 C 언어로 콜라츠의 추측

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 × 2⁵⁸)에서는 종료되지만 모든 입력 값에 대해서는 성립하는지 아직 증명되지 않았다. 혹자는 결국 답을 알아낼 수 없는 문제가 아니냐는 의문을 표한다. 아래 알고리즘은 적당한(~ 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