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 */

답글 남기기

이메일 주소는 공개되지 않습니다.