UVa Online Judge 3n+1 문제.. -_- 왜 제 코드는 거부할까요.
글쓴이: sayhappy / 작성시간: 일, 2008/04/27 - 6:55오후
제가 작성한 C코드(제출하면 wrong answer이라고 합니다 )
수정하였습니다.__;
#include <stdio.h>
int main(void) {
unsigned int i,re,max,t,start,end,small,large;
while( scanf("%d %d", &start, &end) == 2) {
if(start >= 1 && start <= 1000000 && end >= 1 && end <= 1000000) {
max = 0;
if(start > end) { small=end;large=start; }
else {small=start;large=end;}
for(i=small;i < large; i++) {
t = i;
re = 0;
while(t != 1) {
if( t % 2 == 0 )
t = t >> 1;
else
t = 3 * t + 1;
re++;
}
re++;
if( max < re )
max = re;
}
printf("%d %d %d\n",start,end,max);
}
}
return 0;
}인터넷에 어떤분이 올리신 C++코드(제출하면 accept 됩니다)
#include <iostream>
using namespace std;
int main(void)
{
unsigned int maxCycle, start, end, cycle, i, inputNumber;
cout << sizeof(int) << endl;
while(cin >> start >> end)
{
if(start >= 1 && start <= 1000000 && end >= 1 && end <= 1000000)
{
cout << start << " " << end << " ";
if(start > end)
{
int temp;
temp = start;
start = end;
end = temp;
}
maxCycle = 1;
for(i = start; i <= end; i++)
{
inputNumber = i;
cycle = 1;
while(inputNumber != 1)
{
if(inputNumber % 2 == 0)
{
inputNumber /= 2;
}
else if(inputNumber % 2 == 1)
{
inputNumber = (inputNumber * 3) + 1;
}
cycle++;
}
if(cycle > maxCycle)
{
maxCycle = cycle;
}
}
cout << maxCycle << endl;
}
}
return 0;
}두 코드에 사용한 알고리즘은 단순한 것으로 서로 같습니다.
몇 가지 입력값을 넣고 테스트를 해봐도 결과도 같았습니다.
혹시 제가 못보고 있는 것이 있나요ㅠ_ㅠ 아니면 검사할 때 제 코드에 문제가 있다고 보는 걸까요..
너무도 답답해서 -_-; 올려봅니다.
'3n+1' 문제는 다음과 같은 내용입니다.
Quote:
3n+1문제라고 해서...어떤 정수 n에서 시작해 n이 짝수면 /2, 홀수면 X 3 + 1 을 하여서 n=1 이 될때까지 반복하는 것인데요, 예를 들어 n = 22 이면 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 이라는 수열이 만들어지는데,
이 때 사이클 길이는 16입니다(수열의 개수)
자, 이제 정수쌍 i, j가 입력되었을 때 i, j 사이의 모든 수(i, j 포함)에 대한 최대 사이클 길이를 구하라가 문제입니다.
[출처] 3n+1 문제 (The 3n+1 Problem / 알고리즘 트레이닝 북 1번 문제)|작성자 우담바라
Forums:
저넘의 온라인판사.
problemset No 1.
콜라츠의 문제!! NP문제
요즘은 이메일에서 클라이언트로 바꿨던데...ㅋㅋㅋ
져지시스템이 많이 공개가 안되서 자세한 이유는 모르겠지만, splint 같은 걸로 돌려보시고, warning 을 잘 보시는 것이 좋습니다.
for(i=small;i 1; else t = 3 * t + 1; re++; } re++;이 부분이 오타가 아니라면 infinite-loop 이네요.
Hello World.
-_-; 아..
splint로 돌려보니 어디가 잘못되었는지 어디가 문제인지 짐작이 갑니다.;
감사합니다.^^;
갑자기 학생 때 ACM
갑자기 학생 때 ACM ICPC대회에 나갔던 추억이 떠오르네요.
그 대회에 나갔던 사람들은 저 사이트에 들어가서 문제들을 풀어보는데...
정말 아주 사소한 이유로 틀렸다고 통보를 받지요.
코드가 보이지 않으니 정확한 코드를 다시 올려야 할 것 같습니다.
댓글 달기