4

私は動的計画法を学んでおり、動的計画法を使用してプロジェクトオイラーの問題15を解決しようとしました。二項係数を使用して問題を解決できることは知っていますが、動的計画法をどれだけ学び、試したかを知りたいと思いました。コードは次のとおりです。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>

using namespace std;

int main()
{
    int gridsize;
    cin>>gridsize;


    int** grid = new int*[gridsize+1];
    for ( int i = 0; i < gridsize+1; i++) {
        grid[i] = new int[gridsize+1];
    }

    //Initialize the grid distances

    for ( int i = 1; i <= gridsize ; i++) {
        grid[i][0] = 1;
        grid[0][i] = 1;
    }
    grid[0][0] = 0;

    for ( int i = 1; i <= gridsize ; i++) {
        for ( int j = 1; j <= gridsize ; j++) {
            grid[i][j] = grid[i-1][j] + grid[i][j-1];
        }
    }
    cout<<grid[gridsize][gridsize]<<endl;
    delete(grid);   
    return 0;
}

期待される答えは137846528820ですが、私が得ている答えは407575348です。

4

3 に答える 3

4

あなたの論理はかなり正しいです、問題はあなたが整数オーバーフローのケースを得ているということです。これは、完全に機能するコードの修正バージョンです。タイプに変更するだけintです。long long unsigned

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>

using namespace std;
typedef unsigned long long ull;
int main()
{
    ull gridsize;
    cin>>gridsize;


    ull** grid = (ull**) malloc((gridsize+1)*sizeof(ull*));
    for ( int i = 0; i < gridsize+1; i++) {
        grid[i] = (ull*) malloc((gridsize +1)*sizeof(ull));
    }

    //Initialize the grid distances

    for ( int i = 1; i <= gridsize ; i++) {
        grid[i][0] = 1;
        grid[0][i] = 1;
    }
    grid[0][0] = 0;

    for ( int i = 1; i <= gridsize ; i++) {
        for ( int j = 1; j <= gridsize ; j++) {
            grid[i][j] = grid[i-1][j] + grid[i][j-1];
        }
    }
    cout<<grid[gridsize][gridsize];
    free(grid);
    return 0;
}
于 2012-06-07T06:59:18.600 に答える
2

intデータ型がオーバーフローしたようです。計算によると：

137 846 528 820モジュロ（2 ^ 32）= 407 575 348

于 2012-06-07T07:01:20.513 に答える
-2

ここにある便利なデバッグ（または元の開発）ツールはスプレッドシートのようです。アルゴリズムに従って問題を解決するためにスプレッドシートをすばやく作成できます。これにより、各ステップで結果が表示されます。これにより、グリッドの右下側のオーバーフローを簡単に識別できるようになります（grid [16] [18]から開始）。

于 2012-06-23T17:53:34.823 に答える