-2

我尝试解决 3n+1 问题（UVa 100），这是我的代码，但根据 UVa 在线判断我的程序给出了错误的答案，我的代码通过了我能想到的所有测试用例，但无法检测到问题所在帮我找出错误。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> Num;// for Memoization till 1000000

int counter(long int j)  {
    if(j > 1000000) {
        if(j%2 == 1)  return(counter((3*j+1)>>1)+2);
        else return(counter(j>>1)+1);
    }
    else {
        if(Num[j] != 0) return Num[j];
        if(j%2 == 1)  Num[j] = counter(3*j+1)+1;
        else Num[j] = counter(j>>1)+1;
    }
}

int main() {
    Num.resize(1000001);//auto initilizes the vector with 0
    Num[1] = 1; // set the counter for n = 1 as 1;
    int X,Y;
    while ( cin >> X >> Y )  {
        int x = X , y = Y, mxl = 0;
        if(X > Y) swap(X,Y);
        for ( long int j = Y; j >= X; --j)  {
            if(Num[j] == 0)  counter(j);
            if(mxl < Num[j])  mxl = Num[j];
        }
        cout << x << " " << y << " " << mxl << endl;
    }
return 0;
}
4

1 回答 1

1 
int counter(long int j)  {
    if(j > 1000000) {
        if(j%2 == 1)  return(counter((3*j+1)>>1)+2);
        else return(counter(j>>1)+1);
    }
    else {
        if(Num[j] != 0) return Num[j];
        if(j%2 == 1)  Num[j] = counter(3*j+1)+1;
        else Num[j] = counter(j>>1)+1;
    }
}

Num[j] == 0在最后一个代码段（外部）中的情况下，您的返回值在哪里else？

您设置 Num[j]了正确的值，但从不返回它。

我怀疑你所追求的是（也摆脱那些完全不必要的if..return..else结构）：

int counter(long int j)  {
    if(j > 1000000) {
        if(j%2 == 1)
            return(counter((3*j+1)>>1)+2);
        return(counter(j>>1)+1);
    }
    if(Num[j] != 0)
        return Num[j];
    if(j%2 == 1)
        Num[j] = counter(3*j+1)+1;
    else
        Num[j] = counter(j>>1)+1;

    return Num[j];  // This is important.
}

然而，我应该提到，递归可能不是在这里使用的理想工具。一方面，序列可能很长的可能性意味着您可能会在获得解决方案之前用完堆栈空间。

其次，递归调用并非没有成本。在搜索解决方案时，可能会花费大量时间来设置和拆除堆栈框架。

我倾向于使用迭代解决方案来避免这些潜在问题。

于 2015-03-19T06:17:04.817 回答