17

S=5およびN=3とすると、解は次のようになります-<0,0,5> <0,1,4> <0,2,3> <0,3,2> <5,0,0> < 2,3,0><3,2,0><1,2,2>など。

一般的なケースでは、N個のネストされたループを使用して問題を解決できます。N個のネストされたループを実行し、その中でループ変数がSになるかどうかを確認します。

事前にNがわからない場合は、再帰的なソリューションを使用できます。各レベルで、0からNまでのループを実行してから、関数自体を再度呼び出します。深さNに達したら、得られた数の合計がSになるかどうかを確認します。

他の動的計画法ソリューションはありますか？

4

6 に答える 6

9

この再帰関数を試してください：

f(s, n) = 1                                    if s = 0
        = 0                                    if s != 0 and n = 0
        = sum f(s - i, n - 1) over i in [0, s] otherwise

動的計画法を使用するには、評価後にfの値をキャッシュし、評価する前に値がキャッシュにすでに存在するかどうかを確認します。

于 2011-01-03T21:19:07.770 に答える
6

閉じた形の式があります：binomial（s + n -1、s）またはbinomial（s + n-1、n-1）

それらの数はシンプレックス数です。

それらを計算する場合は、対数ガンマ関数または任意精度の演算を使用します。

https://math.stackexchange.com/questions/2455/geometric-proof-of-the-formula-for-simplex-numbersを参照してください

于 2011-01-03T21:25:05.213 に答える
5

私はこれのために私自身の公式を持っています。私たちは友人のジオと一緒に、これに関する調査報告を行いました。得られた式はです[2 raised to (n-1) - 1]。ここで、nは、加数の数を探している数です。

やってみよう。

  • nが1の場合、その加数はoです。合計を1（0を除く）にするために追加できる数値は2つ以上ありません。もっと大きな数字を試してみましょう。
  • 4を試してみましょう4 has addends: 1+1+1+1, 1+2+1, 1+1+2, 2+1+1, 1+3, 2+2, 3+1。その合計は7 です。式で確認しましょう。2を（4-1）に上げ-1 = 2を（3）に上げ-1 = 8-1=7。
  • 15. 2を（15-1）に上げて-1 = 2を（14）に上げて-1 = 16384-1 = 16383を試してみましょう。したがって、15に等しい数を追加する方法は16383あります。

（注：加数は正の数のみです。）

（他の数値を試して、数式が正しいかどうかを確認できます。）

于 2012-08-16T13:13:30.843 に答える
3

これは、次の方法でO(s+n) （または近似値O(1)を気にしない場合は）計算できます。

n-1Xとsoが含まれる文字列があるとします。したがって、s = 5、n = 3の例では、1つの例の文字列は次のようになります。

oXooXoo

Xがoを3つの異なるグループに分割していることに注意してください。1つは長さ1、長さ2、長さ2です。これは<1,2,2>の解に対応します。可能なすべての文字列は、行のoの数を数えることによって異なる解決策を提供します（0は可能です：たとえば、XoooooX<0,5,0>に対応します）。したがって、このフォームの可能な文字列の数を数えることで、あなたの質問に対する答えが得られます。

os+(n-1)を選択するポジションがあるので、答えはです。sChoose(s+n-1, s)

于 2012-04-06T16:02:21.720 に答える
1

答えを見つけるための決まった公式があります。R要素の合計としてNを取得する方法の数を見つけたい場合。答えは常に：（N + R-1）！/（（R-1）！*（N）！）または言い換えると：（N + R-1）C（R-1）

于 2013-02-25T13:25:33.077 に答える
0

これは実際には、ハノイの塔の問題によく似ていますが、ディスクをより大きなディスクにのみスタックするという制約はありません。N個のタワーで任意の組み合わせが可能なS個のディスクがあります。それが私にそれについて考えさせた理由です。

私が思うのは、再帰的なプログラミングを必要としない、推測できる式があるということです。でももう少し時間が必要です。

于 2011-01-03T21:43:11.957 に答える