2

実線上の点 0 に立っているとします。各ステップで、左に l か所、または右に r か所移動できます。あなたは数pに到達するつもりです。また、踏んではいけない数字もあります。これができる回数を数えてください。言及されているすべての数値は整数です (もちろん、l と r は正です)。これを数えるための良い方法は何でしょうか？

ノート。旅の途中で p 自体を踏むこともできるので、場合によっては答えは無限大です。

4

2 に答える 2

0

これはアルゴリズムの問​​題ではなく、数学の問題です。それにもかかわらず、ここに解決策があります。l数値とが正の整数であると仮定しましょうr(いずれもゼロではありません)。

r * x - l * y = p解が存在するのは、方程式に非負の整数解がある場合だけです(x, y)。この式は、任意の順序で、x右に2 回、左に 2 回歩いたことを表しています。yこの方程式はベズー恒等式として知られており、その解がどのように見えるかは正確にわかっています。

gcd(r,l)が割り切れる場合p、整数解 が存在し、(x0, y0)他のすべての解は の形式x = x0 + k * r / gcd(l,r)になります。ここで、整数y = y0 + k * l / gcd(l,r)がk実行されます。明らかに、 ifはとthenとkの両方よりも大きいので、無限に多くの解があります。-x0 * gcd(l,r) / r-y0 * gcd(l,r) / lxy

gcd(r,l)が割り切れない場合p、左辺は常に割り切れますgcd(l,r)が、右辺は割り切れないため、解はありません。

要約すると、ソリューションをカウントするためのアルゴリズムは次のようになります。

if p % gcd(l,r):
    return Infinity
else:
    return 0

この時点で、すべてのパスを列挙しようとするのは無意味に思えます。非負の解ごとに、右への移動と左への移動を(x,y)配置するすべての可能な方法を列挙するだけです。そのよう なパスがあります（右への移動になるステップピックの中で）。xy(x+y)!/(x! * y!)x+yx

于 2012-09-10T19:16:20.497 に答える
0

「L*x+R*y=P の整数(x,y) 解はいくつあるか」のようなものです。

この問題に関する記事はたくさんあると思います。

于 2012-09-10T17:33:53.063 に答える