4

C++ でProject Euler Problem 14を完成させようとしていますが、正直に行き詰まっています。現在、問題を実行すると、これまでのところ、最大カウントの数: 155 のカウントを持つ 113370 でスタックします。これまでのところ、最大カウントの数ですが、i 値を 113371 以上に変更しようとすると、機能します。何が起こっている？？

質問は：

次の反復シーケンスは、正の整数のセットに対して定義されます: n → n/2 (n は偶数) n → 3n + 1 (n は奇数)

上記のルールを使用して 13 から開始すると、次のシーケンスが生成されます。

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 このシーケンス (13 で始まり 1 で終わる) には 10 個の項が含まれていることがわかります。まだ証明されていませんが (コラッツ問題)、開始数はすべて 1 で終わると考えられています。

#include<stdio.h>
int main() {
    int limit = 1000000;
    int highNum, number, i;
    int highCount = 0;
    int count = 0;
    for( number = 13; number <= 1000000; number++ )
    {
        i = number;
        while( i != 1 ) {
            if (( i % 2 ) != 0 ) {
                i = ( i * 3 ) + 1;
                count++;
            }
            else {
                count++;
                i /= 2;
            }
        }
        count++;
        printf( "So Far: the number with the highest count: %d with the count of %d\n",
                     number, count );
        if( highCount < count ) {
            highCount = count;
            highNum = number;
        }
        count = 0;
        //break;
    }
    printf( "The number with the highest count: %d with the count of %d\n",
            highNum, highCount );
}
4

4 に答える 4

3

整数オーバーフローが発生しています。次のようにコードを更新して、自分で確認してください。

if (( i % 2 ) != 0 ) {
    int prevI = i;
    i = ( i * 3 ) + 1;
    if (i < prevI) {
        printf("oops, i < prevI: %d\n", i);
        return 0;
    }
    count++;
}

オーバーフローを防ぐために、の型をitolong longまたはに変更する必要があります。unsigned long long

(そして、はい、中間結果をキャッシュします)

于 2014-10-24T22:17:00.747 に答える
0

アルゴリズムを使用して、複数の時系列を計算します。以前の数値の結果をキャッシュして再利用することができます。

何かのようなもの：

void compute(std::map<std::uint64_t, int>& counts, std::uint64_t i)
{
    std::vector<std::uint64_t> series;
    while (counts[i] == 0) {
        series.push_back(i);
        if ((i % 2) != 0) {
            i = (i * 3) + 1;
        } else {
            i /= 2;
        }
    }
    int count = counts[i];
    for (auto it = series.rbegin(); it != series.rend(); ++it)
    {
        counts[*it] = ++count;
    }
}

int main()
{
    const std::uint64_t limit = 1000000;

    std::map<std::uint64_t, int> counts;
    counts[1] = 1;
    for (std::size_t i = 2; i != limit; ++i) {
        compute(counts, i);
    }
    auto it = std::max_element(counts.begin(), counts.end(),
        [](const std::pair<std::uint64_t, int>& lhs, const std::pair<std::uint64_t, int>& rhs)
        {
            return lhs.second < rhs.second;
        });
    std::cout << it->first << ":" << it->second << std::endl;
    std::cout << limit-1 << ":" << counts[limit-1] << std::endl;
}

デモ(10 秒)

于 2014-10-24T21:46:40.223 に答える