U E D R , A S I H C RSS

3N+1 Problem/문보창

소감

2005/02/18 Accepted 0:03.725 440
문제에 나와 있는 단순한 알고리즘을 제대로 구현만 해도 성공하는 쉬운 문제.
그러나 입력 최악기준 (1, 999999) 에 대해 수시간이 턱없이 길다.

코드

~cpp 
// no100 - The 3n+1 Problem 
#include <iostream> 
using namespace std; 

int findMaxCycle(int a, int b); 

int main() 
{ 
	int a, b;                                      // 입력되는 두 개의 수           
	 while (cin >> a >> b) 
	{          
	      int maxCycle = findMaxCycle(a, b);      // 최대 사이클 
		cout << a << " " << b << " " << maxCycle << endl; 
	} 
	return 0; 
} 

int findMaxCycle(int a, int b) 
{ 
	if (a > b)                                       
	{ 
		int t; 
		t = a; 
		a = b; 
		b = t; 
	} 
	int nCycle;                                     // 사이클 길이 
	 long temp;                                      // 과정 값은 32비트를 넘길 수도 있다. 
	int maxCycle = 0;                               // 최대 사이클 
	
	 if (a == 1 && b == 1)                    
		return 1; 
	else if (a == 1)                                 
		a++; 
	
	int i; 
	for (i=a; i<=b; i++) 
	{ 
		nCycle = 1;                                      
		temp = i; 
		while (true) 
		{ 
			if (temp % 2 == 0) 
			{ 
				temp /= 2; 
				nCycle++; 
				if (temp == 1) 
					break; 
			} 
			else 
			{ 
				temp = (3 * temp + 1) / 2; 
				nCycle += 2; 
			} 
		} 
		if (maxCycle < nCycle) 
			maxCycle = nCycle; 
	} 
	return maxCycle; 
} 
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:16
Processing time 0.0145 sec