Programming Challenges – 3n+1 문제

Programming Challenges 책을 구했다.

말그대로 프로그래밍 문제들이 모여 있는 책인데 하나 하나 풀다 보면 모르고 쓰던 알고리즘을 좀 더 심도 있게 공부 할 수 있을듯 하다.
 http://programming-challenges.com 에 가면 책을 사지 않아도 무료로 가입하고 문제도 보고 답도 제출 할 수 있게 되어 있다. 채점 로봇이 몹시 깐깐 한듯 하다. 출력도 정확해야 하고 큰값 , 0, 음수 전범위의 값을 넣어 보면서 제출한 프로그램을 테스트 한다. 답이 나온것 같아도 계속 틀린 답이라 하는데 그것은 생각 하지 않은 부분에서 잘못된 경우가 많기 때문에 대충 대충 해서는 안된다.

알고리즘을 체계적으로 배울 기회가 없었는데 이번 기회에  배우는셈 치고 하나 하나 도전 해볼 생각이다.

여러 좋은 해법들이 많이 나와 있겠지만 일단 알고리즘을 따로 배워본적 없는 나의 입장(왕초보)에서 답을 제시 해보고 조금씩 배우면서 고쳐 나가는것이 더욱 재미 있고 도움이 될 것 같다.

문제출처는 http://programming-challenges.com

문제 <- 클릭

첫 문제라 그런지 쉽다. 하지만 답을 찾는것만이 중요 한게 아니라 최적화를 하면서 여러가지 소소한 기술들을 습득 할 수 있는듯.

#include 

long getCycle(long val) {
	long counter = 1;
	while (val != 1) {
		if (val & 1) {	//%2로 검출하는 것 보다 좋아 보임
			val = val * 3 + 1;
			counter++;
		}
		while (!(val & 1)) {    // 홀수인 경우 *3 +1 을 하면 결국 짝수가 되므로 이렇게..
			val >>= 1;	// 나누기, 곱하기 연산을 쉬프트 연산자로
			counter++;
		}
	}
	return counter;
}

long getMaxCycle(long low, long high) {
	long tmp, current, maxCycle = 0;
	if (low > high) {
		tmp = low;
		low = high;
		high = tmp;
	}
	for (long loop = high; loop >= low; --loop) {
		if (maxCycle < (current = getCycle(loop)))
			maxCycle = current;
	}
	return maxCycle;
}

int main() {
	long i, j;
	while (scanf("%ld %ld", &i, &j) == 2) {
		printf("%ld %ld %ldn", i, j, getMaxCycle(i, j));
	}
	return 0;
}