0

1 から 1000000 までのコラッツ数列の最大値を見つけようとしています。以下のコードを書きました。それは正しいと思いますが、非常に遅いです。速くするためのヒントを教えてください。ありがとう。

#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

実際、私はテストしたところ、あなたのコードは「非常に遅い」だけでなく、無限にループしています。いいえ、コラッツ予想を反証しただけではありませんが、私が見る限り、整数オーバーフローに苦しんでいます。

より具体的には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引数を aに変更するlong longと、プログラムはすぐに終了します。

もちろん、問題は、無限ループを引き起こさず、見過ごされるオーバーフローが発生しないかどうかです。その場合でも、間違った答えになってしまうからです。ただし入れた後は

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

ループの最後でwhile(1)何も余分に出力されていないことを確認すると、 a が 1 から 1000000 までの数値の Collat​​z シーケンスに十分な大きさであると確信できると思いますlong long(私のコンピューターでは 8 バイトで、 an の 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 つの注意点: 実際には 1 から 999999 までしかループしていないため、1000000 のコラッツ シーケンスが最長のものである場合、それを見逃す可能性があります...

于 2014-01-23T20:58:05.933 に答える
2

いくつかのヒントを次に示します。

ベクトルを容量に初期化します。
要素をプッシュしている間、ベクトルが拡大している可能性があります。最悪の場合、push_back ごとに 1 つの再割り当て。

ベクトルを配列として扱う ベクトル
をその容量まで初期化したら、 を呼び出す代わりに演算子 [] を使用してベクトル スロットにアクセスできますpush_back。

collat​​z
の最適化 これがおそらくボトルネックです。別のファイルに配置して、コンパイラの最適化を上げてみてください。

もっと最適なアルゴリズムがあるかもしれません。

于 2014-01-23T19:51:42.937 に答える