10

ごめんなさい！私の間違いです！ご指摘ありがとうございます。f(0,k) == f(k,0) == 1 であることがわかりました。この質問は、グリッド (0,0) から (m,n) への最短経路の数を数える方法に関するものです。 ）。

次の方程式を解いて、f(m,n) が何に等しいかを正確に調べなければなりません。

1) f(m,n) = 0 : when (m,n) = (0,0)
**2) f(m,n) = 1 : when f(0,k) or f(k,0)**
3) f(m,n) = f(m-1,n) + f(m,n-1) : when else

例えば：

1) f(0,0) = 0; 
2) f(0,1) = 1; f(2,0) = 1; 
3) f(2,1) = f(1,1) + f(2,0) = f(0, 1) + f(1, 0) + f(2, 0) = 1 + 1 + 1 = 3

数年前にアルゴリズムのクラスで学んだように、そのような種類のバイナリ再帰方程式を解く標準的な方法があることを覚えていますが、今のところ思い出せません。

誰でもヒントを与えることができますか？または、答えを見つける方法のキーワードは？

4

3 に答える 3

10

うーん、関数の生成に関する古い教科書を読んで楽しんでいたところ、また質問が変わってしまいましたね!

この質問は、グリッド (0,0) から (m,n) までの最短経路の数を数える方法に関するものです。

これは組み合わせ論の基本的な質問です。関数の生成や再帰関係についての知識は必要ありません。

解決するには、パスが一連の U (「上」) と R (「右」) として書き出されていると想像してください。(0,0) から (5, 8) に移動する場合、5 つの R と 8 つの U が必要です。ほんの一例：

RRUURURUUURUU

この例では、8 つの U と 5 つの R が常に存在します。パスが異なると、それらが異なる順序になります。したがって、U の位置を 8 つ選択するだけで、残りは R にする必要があります。したがって、答えは

(8+5) choose (8)

または、一般的に、

(m+n) choose (m)
于 2012-01-26T23:27:23.457 に答える
3

これは単に二項係数です

f(m,n) = (m+n choose m) = (m+n choose n)

これは、同じ再帰関係を満たしていることに注目することで証明できます。

数式を導き出すには (推測して確認することができない場合)、Chris Nash が正しく示唆しているように生成関数を使用します。

于 2012-01-26T23:25:50.923 に答える
2

文献で「生成関数」を調べてみてください。1 つのアプローチは、x^my^n の係数が f(m,n) である関数 P(x,y) を想像することです。再帰行 (3 行目) は、 P(x,y) - xP(x,y) - yP(x,y) = (1-xy) P(x,y) は、厄介な点を除いて非常に単純であることを示しています。エッジ値。次に、P(x,y) を解きます。

よろしいf(k,0) = f(0,k) = kですか 1 ではありませんか? もしそうなら、いくつかの値を書き出して、それが何であるかを推測し、それを証明するのが最善の策だと思います。

于 2012-01-26T23:14:27.937 に答える