javascript - アルゴリズム: 数値が与えられた場合、合計がこの数値と等しくなる方法は何通りありますか?

Question

たとえば、8、4 プラス 4、2 プラス 5 プラス 1 などがあります。方法は何通りあり、すべての方法をまとめてリストします。

Answer 1

1. 実数には解がない

2. 負の数には解決策がありません

3. 数値の数が非常に単純である必要がある場合、2 つある場合は半分を列挙できます。以下のアルゴリズムを参照して固定長に変更できます

。

4. 数字の数が不明な場合は、0は存在しませんので、参照してください。

式の長さに応じて再帰をトラバースします。枝刈りが可能であり、効率がかなり高いためです

リーリー

私が最初に考えた方法は、1~n 個の式の結果を毎回再帰的にキャッシュすることでした。これはスペースを無駄にし、繰り返し実行すると非常に遅くなります。 リーリー

Answer 2

実数なら...この質問は意味がありません

2×2の足し算を書く

ここに再帰を書いてください...私は再帰について少ししか知りません。 。

R

リーリー

S

Answer 3

十分な条件を与えなかったからといって解決策はありません。正の整数を使用して解決できます。最も単純な再帰では、時間の複雑さは許容できません。 n=100 のプログラムはすぐにクラッシュします
私が使用する動的プログラミングでは、行列を使用して s[i,j] を保存し、対応する結果を保存します。そのため、毎回前の結果を再計算する必要はありません。
このうち、si,j,i=n、jから始まる組み合わせの数、0の場合がないのでs[i,0]としているのがs[i,1]です。 +s[i,2]+..+s[i,j] の結果
たとえば、s[5,1] は n=5、1+1+1+1+1、1+1+ を意味します。 1+2、1+1+1+ 3、1+1+1+4、1+2+2、5 つの場合、
実際、この方法によれば、s[i,1] であることが簡単にわかります。 =s[i-1,0]、つまり
s [i,0]=s[i,1]+s[i,2]+...+s[i,j]
s[i,0] =s[i-1,0]+s[i ,2]+...+s[i,j]
このうち、繰り返し条件を除くと、s[i,i]の計算だけで済みますので、
s[i,0]=s[i-1,0] +...+s[i,i]
s[i,i]=1 なので、
s[i,2] を計算するだけで済みます。 +s[i,3]+...+s[i 最後に、i-1] 結果
後続の数値の組み合わせは前の組み合わせで結合できるため、
s[i, 1] = s[i-1,0],
s[i,j] = s[i-j,k]、j > 1、j <= k <= i
以下は疑似コードです

リーリー

以下はPHPで実装されています

リーリー

si,j>1を計算する際に、事前に過去の組み合わせの数を保存しておき、空間を介して時間を交換できるようにするとさらに最適化できる気がします。
お役に立てば幸いです

Answer 4

これには分割関数 P と呼ばれる関数があります
私は以前、これに関連する小さなアルゴリズムの質問をしたことがあります:神の 90 億の名前
ただし、私の質問では整数の分割の数のみが必要であり、特定の組み合わせは含まれていません。おそらく上記の記事に関係しています 拆分函数P

Answer 5

この種のアルゴリズムロジックには、要素番号とターゲット番号が指定された数あることが最善であると暫定的に考えています。

Java バージョン:

リーリー

C# バージョン:

リーリー

Rubyのバージョン:

リーリー

Python バージョン:

リーリー

与えられた条件が正の数の場合、配列を1~Nに変更します。同じロジックが負の数にも当てはまります。

Answer 6

このアルゴリズムは比較的単純です
分解する数値が18などの偶数の場合、結果はほぼ(18/2+1)の組み合わせになります。すると、最初の数値は0から増加し、2番目の数値はから始まります。最大値を減らすだけです
それが奇数の17の場合、それに1を加えて2で割ると、再び(18/2)になります。その後、最初の数は0から増加し始めます。 2番目の数値は最大値から減少します