1

プロジェクト オイラー15 (ネタバレ): ここに画像の説明を入力

私は、この問題が一連の中心二項係数であることに気付き、この問題を解決しました。もう 1 つの良い方法は、動的計画法です。それにもかかわらず、再帰的に行うのは非常に自然に思えたので、とにかくそれを行いました。

これが私の解決策です：

public long getNumberOfPaths()
{
    getPaths(board[0][0]); //2D array of Positions
    return count; //instance member (long)
}

private void getPaths(Position p)
{   
    if (p.hasDown())
    {
        getPaths(p.getDown());
    }

    if (p.hasRight())
    {
        getPaths(p.getRight());
    }

    if ((p.getRow() == board.length - 1) && (p.getColumn() == board.length -1))
    {
        count++;
    }
}

注: ボードのサイズは 1 + inputSize です。この場合、20x20 のグリッドがあるため、21 になります。これは、上記の 2x2 の問題を解くことは 3x3 の問題を解くことと同じであるが、正方形の境界を移動するのではなく、正方形を通過することになるためです。

の論理getPaths(Position p)は次のとおりです。できる限りダウンしてから、できる限り右に進みます。右下Positionにヒットしたら、パスの数 ( ) に 1 を追加countし、最後に降りた場所に戻り、今度は下る代わりに右に行きます (右に行けない場合は、もう一度バックトラックするなど)。プロセスを繰り返します。もちろん、再帰自体がこれらすべてを追跡しています。明確でない場合、または誰かが作業コードを台無しにしたい場合は、ここに 2 つの小さなクラスがあります。いくつかの print ステートメントを追加すると、getPaths(Position p)何が起こっているのかがかなり明確になります。

とにかく、これはすべて正常に機能します。私の質問は、を使用せずにこれを実装する方法countです。繰り返しますが、上で述べたように、この問題を解決するためのより良い方法があることは知っていますが、それは私の問題ではありません。私の問題は、上記と同じ機能を取得しようとしていますが、補助変数を使用していません。これはgetPaths(Position p)、 からvoidを返すように変更することを意味しlongます。簡単な修正かもしれませんが、私は今それを見ていません。前もって感謝します。

基本的に、実際のカウンターではなく、再帰呼び出しでカウントを追跡する必要があります。

4

3 に答える 3

1

私はこれがうまくいくと信じています

private long getPaths(Position p) {
    return (p.hasDown() ? getPaths(p.getDown()) : 0) +
        (p.hasRight() ? getPaths(p.getRight()) : 0) +
        ((p.getRow() == board.length - 1) && (p.getColumn() == board.length -1) ? 1 : 0);
}
于 2013-06-27T16:37:47.933 に答える
0

メソッドのシグネチャを単純に変更して、カウントをパラメーターとして保持することができます。

private long getPaths(Position p, long count) {
    if (p.hasDown()) {
        getPaths(p.getDown(), count);
    }

    if (p.hasRight()) {
        getPaths(p.getRight(), count);
    }

    if ((p.getRow() == board.length - 1) && (p.getColumn() == board.length - 1)) {
        count++;
    }
    return count;
}
于 2013-06-27T16:38:19.700 に答える