3n 1解决方案给出了错误答案

这是我对3n 1问题的解决方案,它给出了错误的答案 . 自从过去5天以来,我已经多次在这个安静的环境中苦苦挣扎 . 请帮我解决我的解决方案中的问题 . 我使用了尾递归,并且还存储了一个 Map 来跟踪2的幂,以更快地达到答案 . 问题的链接是Programming Challenges - The 3n + 1 problem

#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;
}

回答(2)

3 years ago

您的 process() 函数将填充 globalmap ,使循环长度1为1,但如果传入 ll = 1ans = 0 ,则 cyclelength 函数将返回循环长度0 .

所以,在以下输入:

1 1

1 2

你的程序将输出:

1 1 0
1 2 2

这似乎可能是你的sol'n的关键点 .

3 years ago

如果i> j,您的解决方案将无效 .

尝试从i,j的最小值迭代到i,j的最大值 .

请注意,i和j必须按原始顺序打印,因此如果它们的顺序错误,请不要只交换i和j .