3n + 1 솔루션이 잘못된 대답을 내림

-2

이것은 잘못된 대답을하는 3n + 1 문제에 대한 나의 해결책입니다. 나는이 5 일 동안 지난 5 일 동안 여러 번 힘들었습니다. 내 솔루션에서 문제를 찾아 내도록 도와주세요. 꼬리 재귀를 사용하고지도를 저장하여 2의 능력을 추적하여 답변에 빨리 도달하도록했습니다. 문제에 대한 링크는 Programming Challenges - The 3n + 1 problem 3n + 1 솔루션이 잘못된 대답을 내림

#include <stdio.h> 
#include <map> 
using namespace std; 

#define MAX 1000000 
typedef long long int ll; 
map<int, int> globalMap; 

void process(){ 
    ll i = 1, key = 1, value = 1; 
    while(value < MAX){ 
    globalMap[value] = key; 
    key++; value *= 2; 
    } 
    return; 
} 

ll cycleLength(ll n, ll ans){ 
    if(n == 1) return ans; 
    if(globalMap.find(n) != globalMap.end()) return ans+globalMap[n]; 
    else{ 
    if(n%2){ 
     return cycleLength(3*n+1, ++ans); 
    } 
    else return cycleLength(n/2, ++ans); 
    } 
} 
int main(){ 
    ll i, j, temp, max=-1; 
    process(); 
    while(scanf("%lld%lld", &i, &j) != EOF){ 
    max = -1; 
    for(ll a = i; a <= j; ++a){ 
     temp = cycleLength(a, 0); 
     if(max < temp) max = temp; 
    } 
    printf("%lld %lld %lld\n", i, j, max); 
    } 
    return 0; 
}

출처

2014-02-22 tranquil

문제와 관련이 없지만 코드에 몇 가지 다른 문제가 있습니다. 예를 들어 ['scanf'] (http://en.cppreference.com/w/cpp/io/c/fscanf)를 사용하면 입력이 정확하지 않으면 문제가 발생할 수 있습니다. 이상하게 보이는 또 다른 이유는 C++ 프로그램에서'scanf'와'printf'를 사용하는 이유입니다. –

입력 내용, 예상 출력은 무엇인지, 실제 출력은 무엇인지, 이전 출력은 아직 명확하지 않은 경우 무엇이 잘못되었는지를 지정하십시오. –

문제에 관해서는 디버거의 코드를 단계별로 시도해 보셨습니까? 문제를 찾거나 적어도 특정 코드로 범위를 좁히는 데 도움이 될 수 있습니다. 또한 일부 샘플 입력의 경우 * expected * 및 * actual * 출력은 무엇입니까? –

귀하의 process() 기능을 채우는 globalmap 하나의 사이클 길이는 1,하지만 cyclelength 기능 ll = 1 및 ans = 0 전달 경우 0의 사이클 길이를 반환하도록. 다음과 같은 입력에 따라서

: 그것은 당신의 sol'n와 난제로되어 있습니다

1 1 0 
1 2 2

이 보인다 :

1 1 

1 2

여러분의 프로그램은 출력 것이다.

출처

2014-02-22 12:34:57 MarkB

고마워, 그 속임수를했습니다. – tranquil

당신의 솔루션 난 경우> J 작동하지 않습니다이다.

최소 i, j에서 최대 i, j 반복을 시도해보십시오.

i와 j는 원래 순서대로 인쇄해야하므로 i와 j가 잘못된 순서로 바뀌지 않도록주의하십시오.

출처

2014-02-22 11:38:14

그 점을 지적 해 주셔서 감사합니다. 그러나 운은 아직 없다. 나는 여전히 온라인 판사의 대답이 잘못되었다. – tranquil

3n + 1 솔루션이 잘못된 대답을 내림

답변

관련 문제