검색결과 리스트
사이클 길이에 해당되는 글 1건
- 2011.02.18 문제1 3n+1문제
글
문제1 3n+1문제
알고리즘.데이터구조
2011. 2. 18. 11:39
정수 n에서 n이 짝수면 2로 나누고, 홀수면 3을 곱하고 1을 더한다. 이렇게 만들어지는 수를
다시 n으로 놓고, n=1이 될 때까지 반복해서 나오는 수들의 개수를 정수 n의 사이클 길이(cycle length)라고 한다.
(1을 포함)
i, j 두개의 수가 주어졌을 때, 두 수 사이의 모든 수(i, j 포함)들 중 최대 사이클 길이를 구하라
입력 : i j ( 0 <= i, j <= 1000000)
출력 : i j cycle_length
ex) 입력 : 1 10
출력 : 1 10 20
3n_1.c/*
입력 : 정수 i, j
출력 : 정수 i, j, 최대 사이클 길이
*/
#include <stdio.h>
int cycle_length(int num);
int main (int argc, char const* argv[])
{
int left_bound, right_bound, max = 0;
int i, cycle_len;
scanf("%d %d", &left_bound, &right_bound);
for (i = left_bound; i <= right_bound; i++) {
cycle_len = cycle_length(i);
if (cycle_len > max) {
max = cycle_len;
}
}
printf("%d %d %d \n", left_bound, right_bound, max);
return 0;
}
int cycle_length(int num) {
int n = num, cn = 1;
while (n != 1) {
if (n % 2) {
n = 3*n + 1;
} else {
n = n >> 1;
}
cn++;
}
return cn;
}
'알고리즘.데이터구조' 카테고리의 다른 글
| HMAC-SHA1 (0) | 2011.03.11 |
|---|---|
| 문제5 그래픽편집기 (0) | 2011.02.18 |
| 문제4 LCD디스플레이 (0) | 2011.02.18 |
| 문제3 여행 (0) | 2011.02.18 |
| 문제2 지뢰찾기 (0) | 2011.02.18 |
| 문제1 3n+1문제 (0) | 2011.02.18 |
