0

我试图找到 1 到 1000000 之间的最大Collat​​z 序列。我在下面编写了以下代码。我想这是正确的，但它非常慢。你能给我一些提示让它更快吗？谢谢。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool myfn(int i, int j) { return i<j; }

int collatz(int x);

int main()
{
    vector <int> myvector;
    for(int i = 1; i < 1000000; i++)
    {
        myvector.push_back(collatz(i));
    }

    cout<<*max_element(myvector.begin(),myvector.end(),myfn);


    return 0;

}

int collatz(int x)
{
    int counter = 1;


    while(1)
    {
        if(x == 1)
            break;

        if(x % 2 == 0)
        {
            x = x / 2;
            counter++;
        }
        else
        {
            x = 3 * x + 1;
            counter++;
        }
    }

    return counter;
}
4

2 回答 2

4

实际上，我刚刚测试过，您的代码不仅“非常慢”，而且无限循环。不，您不仅反驳了 Collat​​z 猜想，而且据我所知，您正遭受整数溢出的困扰。

更具体地说，由于溢出collatz(113383)，变量变为负数：int x

551580299 1654740898 827370449 -1812855948 -906427974 -453213987

此后不久，它开始按以下顺序循环，因此永远不会退出循环

-37 -110 -55 -164 -82 -41 -122 -61 -182 -91 -272 -136 -68 -34 -17 -50 -25 -74 -37 ...

在我将int x参数更改为 along long后，程序很快就完成了。

那么问题当然仍然是是否没有发生不会导致无限循环并且被忽视的溢出，因为您最终仍然会得到错误的答案。然而，放上去之后

if (x < 0) {
    cout << "ERROR" << endl;
}

在while(1)循环结束时并没有看到任何额外的输出，我认为您可以确信 along long对于数字 1 到 1000000 的 Collat​​z 序列而言足够大（在我的计算机上为 8 个字节，而对于 a 则为 4 个字节int，如果你会感兴趣的）。

编辑：附带说明：如果您只需要最大值，我看不出有任何理由保留所有结果的向量。以下代码会消耗更少的内存：

int maxCollatz = 0;
for(int i = 1; i < 1000000; i++) {
    if (i % 10000 == 0)
        cout << i << endl;
    maxCollatz = max(maxCollatz, collatz(i));
}

另一个注意事项：你实际上只是从 1 循环到 999999，所以如果 1000000 的 Collat​​z 序列是最长的，你可能会错过那个......

于 2014-01-23T20:58:05.933 回答
2

以下是一些提示：

将向量初始化为您的容量。
当您推动元素时，矢量可能正在扩展。最坏的情况，每个 push_back 重新分配一次。

将向量视为数组
在将向量初始化为其容量后，您可以使用运算符 [] 来访问向量槽，而不是调用push_back.

优化 collat​​z
这可能是你的瓶颈。尝试放入一个单独的文件并在其上启动编译器优化。

可能有更优化的算法。

于 2014-01-23T19:51:42.937 回答