dingpong의 블로그

Categories: Algorithm

3n+1 문제 (The 3n+1 Problem / 알고리즘 트레이닝 북 1번 문제)

알고리즘 트레이닝 책을 보고 3n+1 문제를 풀어보았습니다.

최적화 된 코드는 아닙니다. 인터넷에서 여러 가지 코드를 찾아 보실 수 있을 것입니다.

[이곳]을 방문하시면 문제와 좀 더 최적화 된 답을 보실 수 있을 것입니다.

여러 가지 방법을 적용해 볼 까 하다가 많은 답이나 코딩 방법이 나오기 때문에

처음 답을 맞췄던 코드로 올립니다. 간단하니 참고하시길 바랍니다.

1146637707.zip

/* @JUDGE_ID: 110101 100 C++ */

/* @BEGIN_OF_SOURCE_CODE */

#include <iostream>

using namespace std;

int main()
{
   int oriStart = 0;
   int oriEnd = 0;

   while(cin >> oriEnd >> oriStart != 0) ///< 두개의 값을 입력받는다.
   {
   int start = oriStart;
   int end = oriEnd;

   int maxCount = 0; ///< 최대 사이클 횟수를 저장

   if(end > start) ///< 만약 서로 입력 순서가 바뀌었다면 서로 바꿔준다.
   swap(end, start);

   for(int i = end; i <= start; ++i)
   {
   if(i < 1 || i >= 1000000) ///< 예외처리 코드
   continue;

   int count = 1;
   int result = i;

   while(result != 1)
   {
   if(!(result & 1)) ///< 짝수일때 == if(result % 2 == 0)
   {
   result >>= 1;; ///< == result /= 2
   }
   else ///< 홀수일때
   {
   result = result * 3 + 1;
   }
   ++count;
   }
   if(count > maxCount) ///< 현재 수가 최대 사이클을 기록했다면 기록을 갈아치우자
   maxCount = count;
   }
   cout << oriEnd << ” “ << oriStart << ” “ << maxCount << endl;
   }

   return 0;
}

/* END_OF_SOURCE_CODE */