1

stackoverflow などで3n+1 の問題に関する質問をいくつか見たので、上記のヒントを修正してコードを正しくしようとしました。たとえば、今はどうかを確認しa > bます。または私long longは simple の代わりに使用しますint。それでも間違った答えが得られます。私の答えの何が問題なのですか？

私のコード:

#include <iostream>
using namespace std;

int count_steps(long long int num)
{
    int counter = 1;
    while(num != 1)
    {
        if (num % 2 == 1)
            num = 3*num + 1;
        else
            num /= 2;

        counter++;
    }

    return counter;
}

int max_between(long long int a , long long int b)
{
    int max=0,step;
    for(long long int i = a; i <= b; i++)
    {
        if ((step = count_steps(i)) > max)
            max = step;
    }
    return max;
}

int main()
{
    int max=0,a,b,step;
    cin >> a;
    cin >> b;
    if (a >= b)
        cout << a << ' ' << b << ' ' << max_between(b,a) << endl;
    else
        cout << a << ' ' << b << ' ' << max_between(a,b) << endl;
    return 0;   
}

テストケース:

1 10 (input)
1 10 20 (output)
900 1000 (input)
900 1000 174 (output)
1 1000000 (input)
1 1000000 525 (output)
1000000 1 (input)
1000000 1 525 (output)
4

1 に答える 1

3

あなたのコードへのいくつかのコメント:

メソッドのように使用していますが、aとbを読んでいます。それはナンセンスです。使用されるタイプとしてそれらを読んでください。intlong long int

可能性は低いですが、オーバーフローが発生する可能性があります。これを避けるために、 を使用して整数の範囲を 2 倍にすることができますunsigned long long。

数学的に言えば、あなたはやりすぎです。

奇数の整数n = 2 k + 1の場合、結果3 n + 1は常に偶数になります3 n + 1 = 3(2 k + 1) + 1 = 6k + 4。nしたがって、奇数のケースを次の 2 による除算と組み合わせることができます。その結果は、より3 k + 2もk + 1大きい になりnます。C++ で整数演算を使用すると、これはと評価されてn += (n / 2) + 1で計算できます。n / 2k

コードが受け入れられない別の可能性は、入出力です。プラットフォームの正確な要件に従う必要があります。

問題の説明の次の部分は、コードによって無視されます。

入力は、一連の整数のペアで構成されます

これは簡単に修正できます

int main()
{
    int max=0,a,b,step;
    while ( cin >> a >> b )
    {
       std::cout << a << ' ' << b << ' ';
       if (a >= b)
       {
           std::cout << max_between(b,a);
       }
       else
       {
           std::cout << max_between(a,b);
       }
       std::cout << std::endl;
    }
    return 0;   
}
于 2013-10-24T10:47:32.633 に答える