2

したがって、これを行う方法、および/またはこれを最適化する方法があります。私は愚かですが、すぐに再帰関数を実装したいのですが、後でセグメンテーション違反が発生し、動的計画法を採用しようとしましたが、うまくいったようですが、どういうわけか間違った答えが返ってきました。

ここでの問題

これが私のコードです、そしてそれはかなり自明だと思います。

#include <iostream>

using namespace std;

int cycleLength(long long int);

int cycleLengthResult[1000000];

int main(int argc, char *argv[])
{
    int i = 0, j = 0, cur = 0, max = 0;
    while ( cin >> i >> j )
    {
        if ( i > j ) //swap to ensure i <= j
        {
            int s = i;
            i = j;
            j = s;
        }
        for ( int k = i ; k <= j ; ++ k )
        {
            cur = cycleLength(k);
            if (cur > max) max = cur;
        }
        cout << i << " " << j << " " << max << endl;
        max = 0;
    }
}

int cycleLength(long long int arg)
{
    if ( arg > 1000000 ) //if out of array bound, then don't memorize, just calculate
    {
        if (arg % 2 == 0)
        {
            return 1 + cycleLength(arg/2);
        }
        else
        {
            return 1 + cycleLength(arg*3+1);
        }
    }
    if (!cycleLengthResult[arg-1]) //if result for arg doesn't exist then....
    {
        int valueForArg = 0;
        if (arg == 1)
        {
            valueForArg = 1;
        }
        else if (arg % 2 == 0)
        {
            valueForArg = 1 + cycleLength(arg/2);
        }
        else
        {
            valueForArg = 1 + cycleLength(arg*3+1);
        }
        cycleLengthResult[arg-1] = valueForArg;
    }
    return cycleLengthResult[arg-1];
}

すべてのサンプル入力に合格し、速度テスト用に（1、1000000）も合格しました。しかし、それは問題ではないようでした。

コードを修正し、使用する方法を変更したくないのですが、もちろん、再帰を使用することはできず、代わりにメインでループを使用します。これはオーバーフローしません。しかし、それは楽しいです。

4

1 に答える 1

3

ステートメントを注意深く読んでください：

整数iとjは、入力に表示されたのと同じ順序で出力に表示される必要があります

したがって、保存した値を読み取って印刷した後、それらを保存してください。

于 2012-12-24T19:21:37.943 に答える