2

所以，有办法做到这一点，和/或优化这一点。我很傻，我立即想实现一个递归函数，后来导致分段错误，然后我尝试采用动态编程，它似乎有效，但不知何故我得到了错误的答案。

问题在这里

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

#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 中使用循环，这不会溢出。但这很有趣。

4

1 回答 1

3

仔细阅读声明：

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

所以在阅读后保存它们并打印保存的值。

于 2012-12-24T19:21:37.943 回答