c++ - C++ 动态编程中的 UVa 3n + 1

Question

因此，有一些方法可以做到这一点，和/或优化它。我真是愚蠢，我立即想实现一个递归函数，后来导致了段错误，然后我尝试采用动态编程，似乎可行，但不知何故我得到了错误的答案。

问题Here

这是我的代码，我认为它是不言自明的。

#include <iostream>

using namespace std;

int cycleLength(long long int);

int cycleLengthResult[1000000];

int main(int argc, char *argv[])
{
    int i = 0, j = 0, cur = 0, max = 0;
    while ( cin >> i >> j )
    {
        if ( i > j ) //swap to ensure i <= j
        {
            int s = i;
            i = j;
            j = s;
        }
        for ( int k = i ; k <= j ; ++ k )
        {
            cur = cycleLength(k);
            if (cur > max) max = cur;
        }
        cout << i << " " << j << " " << max << endl;
        max = 0;
    }
}

int cycleLength(long long int arg)
{
    if ( arg > 1000000 ) //if out of array bound, then don't memorize, just calculate
    {
        if (arg % 2 == 0)
        {
            return 1 + cycleLength(arg/2);
        }
        else
        {
            return 1 + cycleLength(arg*3+1);
        }
    }
    if (!cycleLengthResult[arg-1]) //if result for arg doesn't exist then....
    {
        int valueForArg = 0;
        if (arg == 1)
        {
            valueForArg = 1;
        }
        else if (arg % 2 == 0)
        {
            valueForArg = 1 + cycleLength(arg/2);
        }
        else
        {
            valueForArg = 1 + cycleLength(arg*3+1);
        }
        cycleLengthResult[arg-1] = valueForArg;
    }
    return cycleLengthResult[arg-1];
}

我通过了所有示例输入，还通过了 (1, 1000000) 速度测试。但看起来这不是问题。

我想修复我的代码，而不是改变使用的方法，当然，我可以不使用递归，而在 main 中使用循环，这样就不会溢出。不过很有趣。

Answer 1

仔细阅读声明:

整数 i 和 j 必须按照它们在输入中出现的顺序出现在输出中

因此，读取后保存它们并打印保存的值。