0

クラスのJava割り当てに取り組んでいますが、この問題を解決する方法がわかりません。私はそれを完成させたくありませんが、正しい方向に向けて始めてください。プログラムの再帰部分についてはほとんどわかりません。私はプログラミングがあまり得意ではありません。

問題：

北東の経路は、2 次元グリッドを上下に移動することによって取得されます。たとえば、下の図では、1,0 から 0,1 への 2 つのパスがあります。1 つ目は (1,0)、(0,0)、(0,1)、2 つ目は (1,0)、(1,1)、(0,1) です。(0,1) から他のポイントへの北東パスがないことに注意してください。また、(1,1) から (0,1) への北東パスが 1 つあることに注意してください。数値 (グリッドのサイズ - 10 以下) と開始位置と終了位置を取り、すべての「北東」パスを再帰的に計算するプログラムを作成します。

0,0 0,1

1,0 1,1

ファイルprog2.datを読んでいます

最初にグリッド サイズを読み込み、次に開始座標、終了座標を読み込みます。例えば：

5

3 0

1 3

1つのファイルである必要があるため、メソッドを使用します。誰かが私を始めさせたり、すでに投稿されている同様の質問に私を誘導したりできれば、私はそれを感謝します.

4

3 に答える 3

0

パスカルの三角形について読むことから始めます。

開始位置 (x0, y0) と終了位置 (x1, y1) を指定し、グリッド上を北または東に移動するように制限すると、最小長のパスは正確に (x1-x0) ステップで構成されます。ある順序で東と (y1-y0) の手順で北に移動します。

于 2010-02-09T19:34:17.310 に答える
0

これは役立つかもしれません：

http://en.wikipedia.org/wiki/Binomial_theorem

于 2010-02-09T19:22:48.063 に答える
0

再帰を伴う解決策の 1 つは、目的地に最も近いパス上の次のポイントを見つけることです。そのポイントを取得したら、同じ方法を使用して次に近いポイントを見つけます。このプロセス (または再帰) は、目的地に到着したときに終了します。

次のようなことを試すことができます。

void getNextPoint(Point start, Point end, Path currentPath) {
    //if start == end, then you're done with the recursion
    //and you have a valid path

    //if you can move east from start to get closer to end
    //Point next = east of start
    //append next to the currentPath
    //then call getNextPoint(next, end, currentPath)

    //if you can move north from start to get closer to end
    //Point next = north of start
    //append next to currentPath
    //then call getNextPoint(next, end, currentPath)
}

詳しくはご自身で理解していただけるように、多くの詳細は省略していますが、これは再帰を使用するための 1 つのアプローチです。基本的に、パスを構築しています。パスを管理する方法を理解する必要がありますが、パスからポイントをプッシュおよびポップできる必要がある可能性があります。

于 2010-02-09T19:49:32.373 に答える