1

XP 仮想マシンの MingW コンパイラで CodeBlocks を実行しています。cl1pでアクセス可能ないくつかの単純なコードを書きました。これは、 CodeChefのアルゴリズムの質問に答えます(複数のテスト ケースのループをまだ含めていないため、部分的にしか答えていません。

ただし、私の問題は、デバッグモードで実行しているときに、入力に対して正しい出力 5 が得られることです。

3
1
2 1
1 2 3

しかし、ビルドして実行すると、ばかげた巨大な出力 131078 が表示され、ゴミのように見えます。これがどのように起こっているのかわかりませんが、動的メモリ割り当てに関係していると推測しています。ここで何が問題で、どうすれば修正できますか? BotSkoolのオンライン コンパイラで実行したところ、問題なく動作しました。テスト ケースのループを追加した後、コードは CodeChef でも正しく動作しました。

#include <iostream>

using namespace std;

int main()
{
    // Take In number of rows
    int numofrows;
    cin >> numofrows;

    // Input Only item in first row
    int * prevrow;
    prevrow = new int[1];
    cin >> prevrow[0];

    // For every other row
    for (int currownum = 1; currownum < numofrows; currownum++)
    {
        // Declare an array for that row's max values
        int * currow;
        currow = new int[currownum+1];

        int curnum;
        cin >> curnum;

        // If its the first element, max is prevmax + current input
        currow[0] = prevrow[0] + curnum;

        // for every element
        int i = 1;
        for (; i <= currownum; i++)
        {
            cin >> curnum;

            // if its not the first element, check whether prevmax or prev-1max is greater. Add to current input
            int max = (prevrow[i] > prevrow[i-1]) ? prevrow[i] : prevrow[i-1];

            // save as currmax.
            currow[i] = max + curnum;
        }

        // save entire array in prev
        prevrow = new int[i+1];
        prevrow = currow;
    }

    // get highest element of array
    int ans = 0;
    for (int j=0; j<numofrows; j++)
    {
        if (prevrow[j] > ans)
        {
            ans = prevrow[j];
        }
    }

    cout << ans;
}
4

3 に答える 3

2

Linux マシンで Valgrind を介してコードを実行すると、コードでメモリ リークが発生している場所の数に驚かれることでしょう。メモリを管理するという困難な道を歩んでいる場合は、それをうまく行い、さらに割り当てる前に、新しく割り当てたメモリをすべて「削除」してください。一方、簡単な方法を好む場合は、std::vector を使用し、メモリ管理を忘れてください。

于 2010-01-01T22:17:11.713 に答える
1

一つには、これ：

    //save entire array in prev
    prevrow = new int [i+1];
    prevrow = currow;

配列全体ではなく、ポインターをコピーします。

于 2010-01-01T22:15:22.320 に答える
1

あなたのループには、この行があります

int max = (prevrow[i]>prevrow[i-1])?prevrow[i]:prevrow[i-1];

メイン ループの最初の反復で、が に初期化されたときcurrownum == 1に、この行を含むループに入ります。しかし、最初の反復では、要素は 1 つしかなく、この行は にアクセスしようとします。デバッグ ビルドでは、メモリは単純にゼロに初期化されますが、通常のビルドでは、たまたまメモリ内にあったガベージ値が取得され、結果が表示されます。i1prevrowprevrow[1]

ほとんどの場合、通常のビルドでガベージ値を取得しても、デバッグ ビルドではすべて問題ない場合は、初期化されていないメモリにアクセスしています。

また、あなたのプログラムは狂ったようにメモリをリークしています。newたとえば、ループ内の結果を割り当てる必要はありません。そのprevrow直後にprevrow、割り当てられたメモリの別のブロックを指すように変更するためです。deleteまた、使用しなくなったメモリを呼び出す必要があります。

于 2010-01-01T22:25:43.673 に答える