[M2S] 2009년 01월 23일 금요일 C언어 DailyQuiz 09 ( N 사이클 )

N 사이클

다음 알고리즘을 생각해보자.

1. input n

2. print n

3. if n = 1 then STOP

4. if n is odd then n<-3n + 1

5.else n<-n/2

6.GOTO 2

 

22가 입력되면 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1이 출력된다.

"어떠한 정수 입력에 대해서(1이 출력될때) 위의 알고리즘은 멈춘다"고 추측할 수 있다.
알고리즘은 단순하지만, 이러한추축이 참인지는 알 수 없다.
이것은 0 < n < 1,000,000 범위(실제로 이보다 더 큰 수가 될 수 있는)의 모든 정수 n을사용하여 증명한다.

n이 입력되면 출력되는 모든 숫자의 개수를 알 수 있다. 이것을 "n의 사이클-길이" 라고 부른다.
위의 예에서 22의 사이클 길이는 16이다.

 

두 가지 숫자 i와 j가 주어질 때 i와 j사이의 숫자에서 최대 사이클 길이를 결정한다.

 

입력에서 각 라인은 정수 i, j 한 쌍으로 구서오딘다. 모든 정수는 0보다 크고 10,000보다 작은 값이다. 모든 정수 쌍으로 처리하고, i 와 j사이의 정수에서 최대 싸이클 길이를 구해야 할 것이다.

 

입력 정수 i와 j쌍에 대해서 출력 i,j,  i와 j사이의 정수에서 최대 사이클 길이를 출력해야 한다. 3가지 출력 수는 반드시 입력순서에 따라서 한 개 이상의 공백으로 구분해야 하다. 최대 사이클 길이는 정수 i, j와 같은 선상에 바로 이어서 출력해야 한다.

 

sample input

1 10

100 200

201 210

900 1000

 

sample output

1 10 20

100 200 125

201 210 89

900 1000 174

기한 : 2009년 1월 28일 수요일 PM 02:00 까지. ( 23일 ~ 28일 )

제출 : rockdrumy@nate.com or 네이트온.

제출방법 : 워드문서로 레포트 형식과 동일하게 소스와 실행화면 스샷과 함께 작성하고, 
               Word 파일과 c 파일 1개로 압축하여 제출. 

궁금한 점은 무조건 저한테만 문의 바람. 웹사이트 & 네이버 지식검색 참조 금물.