为什么我的 3n+1 谜题解法被拒绝了？

Question

我正在尝试解决 UVa 在线判断上的算法问题，但我卡在 3n+1 problem 上。我每次都看到正确的输出，但法官说这是一个错误的答案。为什么？

此外，我该如何优化这段代码，使 1000000 不会花费很长时间？

#include <iostream>
#include <string>
#include <stdio.h>

using namespace std;

int main(){
    int a;


 int b;
    int cyclelength(int i);
     while (scanf("%d %d\n",&a,&b)==2){

    int max = 0;

   if (b < a){
        for (int i = b; i < a; i++){
        if (cyclelength(i) > max)
            max = cyclelength(i);
             }
   }

   else    
   {
        for (int i = a; i < b; i++){
             if (cyclelength(i) > max)
                  max = cyclelength(i);
         }
   }


    cout << a << " " << b << " " << max << endl;

    }
}

int cyclelength(int i){
    if(i==1)
        return 1;


    if(!(i%2))
         return cyclelength(i/2)+1;
     else
        return cyclelength(3*i+1)+1;
     }

Answer 1

您提交的内容不正确，因为您没有遍历从 a 到 b（含）的范围。

问题陈述如下：

For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j.

您的代码循环结束

for (int i = b; i < a; i++)

和

for (int i = a; i < b; i++)

因此省略了前者的 a 和后者的 b。

您应该将循环更改为

for (int i = b; i <= a; i++)

和

for (int i = a; i <= b; i++)

您可以通过 memoizing cyclelength 的结果稍微加快您的代码速度。这使您可以查找以前计算的值，而不是花时间再次计算它们。

这是 cyclelength 的记忆版本：

#include <map>
using namespace std;

map<long long, int> memo;

int cyclelength(long long i) {
  if (i == 1) {
    return 1;
  } 

  if (memo.count(i) == 1) {
    return memo[i];
  }

  if (i%2 == 0) { 
    return memo[i] = 1 + cyclelength(i/2);
  } else { 
    return memo[i] = 1 + cyclelength(3*i + 1);
  } 
}

unordered_map 会更快，但 UVA 判断返回 #include <unordered_map> 的编译错误。

请注意，我的 cyclelength 版本采用 long long 参数。这让我可以计算 cyclelength(999999)，如果您将自己限制为 32 位整数值，它最终会由于重复 3n+1 次操作而导致整数溢出。问题陈述承诺 "no operation overflows a 32-bit integer" 如果你只使用 int 值，你可以让你的提交被接受，但是如果你想计算 cyclelength 中的值，你必须使用更大的整数类型范围 [1, 1000000].

为什么我的 3n+1 谜题解法被拒绝了？

Why is my solution to the 3n+1 puzzle being rejected?

c++

algorithm

recursion

memoization