C++欧拉问题14程序卡住

Question

我正在研究欧拉问题 14: http://projecteuler.net/index.php?section=problems&id=14

我认为最好的方法是创建一个数字 vector 来跟踪该数字的系列有多大...例如从 5 到 1 有 6 个步骤，所以如果在一个系列，我知道我有 6 个步骤，我不需要计算这些步骤。有了这个想法，我编写了以下代码:

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
int main()
{
    vector<int> sizes(1);
    sizes.push_back(1);
    sizes.push_back(2);
    int series, largest = 0, j;
    for (int i = 3; i <= 1000000; i++)
    {
        series = 0;
        j = i;
        while (j > (sizes.size()-1))
        {
            if (j%2)
            {
                j=(3*j+1)/2;
                series+=2;
            }
            else
            {
                j=j/2;
                series++;
            }
        }
        series+=sizes[j];
        sizes.push_back(series);
        if (series>largest)
            largest=series;
        cout << setw(7) << right << i << "::" << setw(5) << right << series << endl;
    }
        cout << largest << endl;
    return 0;
}

对于较小的数字，它似乎工作得相对较好，但这个特定程序在数字 113382 处停滞不前。任何人都可以向我解释我将如何着手弄清楚为什么它卡住在这个数字上吗？

有什么方法可以改进我的算法吗？我意识到我正在使用当前的方式创建重复项:例如，3 的系列是 3,10,5,16,8,4,2,1。所以我已经计算出 10、5、16、8、4、2、1 的大小，但我稍后会复制这些解决方案。

感谢您的帮助!

Answer 1

您是否排除了整数溢出？你能保证 (3*j+1)/2 的结果总是适合 int 吗？

如果切换到更大的数据类型，结果会改变吗？

编辑:最后一个论坛帖子在 http://forums.sun.com/thread.jspa?threadID=5427293似乎证实了这一点。我通过谷歌搜索 113382 3n+1 找到了这个。