문제 1. The 3n + 1 problem

정수 n이 짝수면 2로나누고, 홀수면 3을 곱한 다음 1을 더한다.

이렇게 해서 n=1이 될 때까지 작업을 반복한다.

예) n=22

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

 

이 가설은 1,000,000까지의 정수에 대해서는 참이다.

 

n이라는 값이 입력되고, 1이 나올 떄까지 만들어 진 수의 갯수를 사이클 길이라고 할때 22의 사이클 길이는 16이다.

이떄 i,j라는 두개의 수가 주어 졌을 때 i,j 두 수를 포함한 사이의 모든 수의 최대 사이클 길이를 구하라.

 

입력은 i, j 한쌍이며 모든 정수는 1,000,000보다 작고 0보다 크다.

 

입력 예)

1 10

100 200

201 210

900 1000

 

출력 예

1 10 20

100 200 125

201 210 89

900 1000 174

 

하.. 아직 문제 1번이라 쉽게 풀었는데 문제는 사이트에 검사 받는 과정이...

뭐가 잘못 된건지 처음엔 계속 컴파일 에러...

보니깐 c++인데 #include<stdio.h>나 printf, scanf등을 써서 그랬던 것 이었습니다.

그리고 이제 다 고쳤다 싶었는데 이번엔 잘못된 답이라고..

이것도 찾다보니

0보다 작거나 같을때, 1,000,000보다 크거나 같을 때 등 예외상황에 대한 처리, 그리고 인풋에서 들어오는 인수의 순서에 상관없이

결과값이 나오게 해야 됐던게 문제가 됐습니다.

그런 문제들을 다 해결하니 제대로 나오는...

아무튼 문제를 푸는 것 보다 힘이 많이 들었습니다.

 

 

 

#include 
using namespace std;

int Algorithm1( int n,int *c )
{
	(*c)++;
	if( 1==n )
		return 1;
	if( 0==n%2 )
		Algoritm1( n/2,c );
	else
		Algoritm1(n*3+1,c);
	return *c;
}

int main()
{
	int a=0,b=0;

	while( cin>>a >> b )
	{
		if( a<=0 || b <=0 || a>=1000000 || b >=1000000 )
			break;

		int iMax = 0;
		int cc = 0;
		int c,d;
		c = a;
		d = b;
		if( a>b)
		{
			c = b;
			d= a;
		}

		for( int i=c; i<=d; i++ )
		{
			cc=0;
			int a = Algorithm1(i, &cc );
			iMax =  iMax > a ? iMax  : a;
		}

		cout << a <<" " << b << " " << iMax << endl;
	}

	return 0;
}