2

行列が与えられたNxN場合、ある場所へのすべての可能なパスをどのように見つけることができますか(i,i)。ナビゲーションはdownwards、に向かってのみrightです。開始点はです(0,0)。

PS宿題ではありません。

4

6 に答える 6

2

？

場所（i、i）、つまり対角線上の1つには、正確にcomb（i、2 * i）パス（2 * i要素のセットからi要素を選択する方法の数）があり、それぞれがiの動きで構成されます。右に移動し、下に移動します。それらを列挙するのは簡単です。

于 2012-07-31T13:54:20.927 に答える
2

（私にとって）最も簡単なのは、再帰的に行うことです。

1）停止条件は（i、i）に到達します

2）各再帰レベルで次の2つの動きを試します。

  • 降りられますか
  • 正しく行けますか

現在の位置が（x、y）であると仮定します。現在の「y」プラス1が（i、i）の「i」よりも大きい場合、正しく進むことはできません。現在の「x」プラス1が（i、i）の「i」よりも大きい場合はダウンできません。

変数のパスを覚えておくか、パスを下に渡して、停止条件が発生したときに出力する必要があります。

したがって、（0,0）から開始すると、これを覚えてから、右または下に移動できるかどうかを確認します。両方とも「はい」の場合は、（0,1）と（1,0）に対して同じメソッドを再帰的に呼び出します。

于 2012-07-31T13:59:12.257 に答える
2

DPを使用してこれを解決することはできますが、これは単純な数学です。

あなたはステップを踏まなければなりません、それから右へのステップ2iでなければなりません。i合計の組み合わせはC(2i,i)です。二項係数の計算を参照してください。

もう1つの同様の問題は、単調パスと呼ばれる対角線を越えることができない場合です。この場合、興味深いカタラン数列が解になります。

于 2012-07-31T14:18:46.053 に答える
1

解決策1-動的計画法を使用する：

必要な（i、j）インデックスまで、ソリューションをボトムアップで追加します。

ans（i、i）= ans（i-1、j）+ ans（i、j-1）

位置（i、i）にも同じものを使用します。

解決策2-単純な順列と組み合わせを使用する

ans =（2i）！/ i！i！

（右に向かってiステップのいずれかを選択する必要があるため、（0,0）から開始してjiステップを下に移動すると、合計は2iステップになります）。

于 2012-07-31T13:56:31.730 に答える
1

45度の角度から問題を見てください。三角配列の頂点へのパスの数を計算しようとしていることがわかります。解はパスカルの三角形で与えられます。

2i choose i

于 2012-07-31T17:34:19.523 に答える
1

これは、（0,0）から開始するか、マトリックス内のランダムな位置から開始するかによって異なります。

（0,0）の場合; 深さ優先を使用して、1つのブランチの終わりまで進み、次に他のブランチの終わりまで進みます。幅優先を使用して、ステップですべての隣接ノードを反復処理します。ダウンノードとライトノードのみを確​​認してください。

マトリックス内のランダムな位置にある場合は、4つの隣接ノードすべてをトレースする必要があります。

于 2016-02-10T13:42:38.183 に答える