'3n+1'에 해당되는 글 2건

  1. 2008.10.29 3n+1 Problem - Programming Challenges 110101 (4)
  2. 2007.07.21 '3n+1 Problem' 드디어 Solved를 받아내다;; (3)
몇달째 Python만 손대다보니 C, C++ 문법조차 다 잊어버린 상황.
다시금 C, C++ 감을 찾기위해 Programming Challenges 책을 꺼내들었다.
심심할때마다 처음부터 차근차근 하나씩 풀어가기 위해.
처음으로 풀어본 문제는 예전에도 이미 한번 풀어본 적 있는 '3n+1 Problem'.
아직 이 문제를 효율적으로 풀 수 있는 알고리즘을 제대로 이해하지 못해서 직관적인 방법으로 풀었던니 실행시간이 너무 길다.(최단시간 0.008초, 내껀 0.828초...-_-)
효율적인 알고리즘을 공부 한 뒤에 다시 풀어봐야지...~_~

* 문제
- http://www.programming-challenges.com/downloadproblem.php?probid=110101&format=ps (PS)
- http://www.programming-challenges.com/downloadproblem.php?probid=110101&format=pdf (PDF)

* C 버전 소스코드

* C++ 버전 소스코드
Posted by RyuiSaka

 

문제풀이 시간 : 10분(코딩 포함)
Solved 받아낼때까지 걸린 시간 : 1시간

그동안 Wrong Answer로 일관하던 Programming Challenges 로봇이 드디어 'Solved'를
뱉어냈다;;
문제는 경계값도 아니고 입력문제도 아니고 기본자료형의 최대크기문제???
Visual C++에서는 int형을 4바이트로 처리하기때문에 1,000,000이라는 숫자를 다룰 때 문제가
없지만 Programming Challenges의 로봇이 사용하는 컴파일러는 아마도 int형을 2바이트로
처리하는듯 하다.
그래서 65535를 넘어가면 문제를 일으켜서 'Wrong Answer'를 뱉어낸것 같다.
하지만 Runtime이 3초가 넘는걸 보면 알고리즘을 엄청나게 비효율적으로 설계한듯;;
Best Time이 0.008초로 나와있는데....대체 어떻게 알고리즘을 설계했길래 저런 시간이
나올 수 있는겐지;;
암튼 오랫동안 답을 얻지 못했던 문제를 풀어서 뿌듯하다.(물론 오래전에 문제를 풀긴 했으나
로봇덕분에 삽질을 계속 했었다;)

Posted by RyuiSaka