UVA 3n+1 (prob 100) 我的 C++ 程序有什么问题

Question

我尝试解决 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;
}

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

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

您将 Num[j] 设置为正确的值，但从未 return 它。

我怀疑你想要的是这样的东西（也摆脱那些完全不必要的 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.
}

不过，我应该提一下，递归可能不是在这里使用的理想工具。其一，序列可能很长的可能性意味着您可能运行在获得解决方案之前 space 出栈。

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

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

UVA 3n+1 (prob 100) 我的 C++ 程序有什么问题

UVA 3n+1 (prob 100) what is Wrong in my C++ program

c++

collatz