3n+1문제 질문인데요
3n+1문제를 풀어보는데 몇 개 테스트해보면 다 맞게 나오는 것 같은데 채점 사이트에는 틀리다고 뜨네요.
혹시 뭐가 문제인지 아시는 분 도움 줄 수 있나요?
아래는 제 코드이고 이건 3n+1문제가 무엇인지 나와있는 사이트입니다.
문제: http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110101&format=html
코드:
#include
int cyclelen(int n);
int main()
{
int i, j, k, max_length, length, tmp;
while(scanf("%d %d", &i, &j) == 2) {
max_length = 1;
if(j < i) {
tmp = j;
j = i;
i = tmp;
}
for(k = i; k <= j; k++) {
length = cyclelen(k);
if(length > max_length)
max_length = length;
}
printf("%d %d %d\n", i, j, max_length);
}
return 0;
}
int cyclelen(int n)
{
int length = 1;
while(n != 1)
{
if(n % 2 == 0)
n = n / 2;
else
n = 3 * n + 1;
length++;
}
return length;
}
입력된 순서대로 출력하라는 조건이 있습니다.. 그런데
입력된 순서대로 출력하라는 조건이 있습니다..
그런데 i>j 인경우에는 값을 바꿔버리시네요..
--
그런데 n=1 인경우에는 어떻게 되나요?
1 4 2 1 로 볼 수도 있을 것 같은데요..
이건 문제가 좀 애매하게 써 있는듯..
n=1인 경우 1로 끝납니다. 아니면 1-4-2-1로
n=1인 경우 1로 끝납니다. 아니면 1-4-2-1로 무한반복이죠.
피할 수 있을때 즐겨라! http://melotopia.net/b
문제의 원글은 아래와 같죠..Start with
문제의 원글은 아래와 같죠..
여기서 "when n=1"의 n이 입력의 n인지, 출력의 n인지가 불분명하다는 뜻입니다.
즉 termination condition을 operation 전에 체크하느냐, 후에 체크하느냐가 좀 명확치 않은 것 같아서요..
while() 과 do{}while()의 차이...
음. 제 생각에는
우선 입력된 n 이 1 이면 바로 끝나는게 맞는것 같고요.
풀이하신 알고리즘 같은 경우에는 아마 Time Limit Exceed 에러가 나올 것 같은데요.
모든 경우에 Cycle을 전부 계산하시면 시간 초과가 될 수 있다고 생각이 됩니다.
음. N 을 구하기 위해서 1 .. N - 1 까지의 결과를 알고 있고 이걸 이용하면 좀 더 빨리 계산 할 수 있을 것 같아요.
댓글 달기