-2

这是我对给出错误答案的 3n+1 问题的解决方案。自从过去 5 天以来，我已经在这个安静的环境中挣扎了很多次。请帮助我找出解决方案中的问题。我使用了尾递归，并且还存储了一张地图来跟踪 2 的幂，以便更快地找到答案。问题的链接是编程挑战 - 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;
}
4

2 回答 2

2

您的process()函数将填充globalmap1 的循环长度为 1，但cyclelength如果传入ll = 1and ，您的函数将返回 0 的循环长度ans = 0。

因此，在以下输入中：

1 1

1 2

您的程序将输出：

1 1 0
1 2 2

这似乎是你解决方案的症结所在。

于 2014-02-22T12:34:57.203 回答
1

如果 i>j，您的解决方案将不起作用。

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

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

于 2014-02-22T11:38:14.120 回答