이러한 알고리즘이 있다.

n= 10 이면

10 ,5, 16, 8, 4, 2, 1    cnt = 7 (사이클길이)

짝수이면 n/2 로 나누고 , 홀수이면 3n+1 로 한다.

이 알고리즘을 적용을하면 결국에 n 은 1에 이르게 된다.

이 가설은 적어도 1000000까지의 정수에 대해서는 참이라고 한다.


이제부터 문제다.

어떠한  두 정수를 입력받는다.

0~1000000까지만 값을 입력받을수 있도록 하고

예를 들어 1 , 10 을 입력받는다 그러면 1 ~10 사이에 대해 최대 사이클 길이를 구하면 된다.

입력예     출력 예
1 10        1 10 20
100 200   100 200 125


먼저 입력 받는 수를 a와 b 라고 하고 a에 대한 알고리즘을 구했고 그 다음에 a+1 에 대한 결과와 비교하고

또 a+1과 계속 비교해가면서 b까지 비교해서 가장 큰 최대사이클을 구하는 방식으로 하였다.

생각보다 알고리즘 문제 재밌는거 같다 ㅋㅋㅋ

'프로그래밍 기초 > 자료구조 & 알고리즘' 카테고리의 다른 글

여행(The Trip)  (0) 2010.05.11
지뢰찾기  (0) 2010.05.03
3n+1  (0) 2010.05.03
스케줄링 (라운드 로빈)  (0) 2009.12.17
병합정렬 & 퀵 정렬 비교 및 기수정렬  (0) 2009.12.17
연결리스트더미有  (0) 2009.12.16
Posted by 아몰라

댓글을 달아 주세요