可能な組み合わせの数
https://stackoverflow.com/questions/59743
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
次のことがわかっている場合、変数 a、b、c、d、e の可能な組み合わせは何通りありますか。
a+b+c+d+e = 500
そして、それらはすべて整数で >= 0 であるため、それらが有限であることがわかります。
解決
@トーラック、@ジェイソン・コーエン:ここでは、再発は悪い考えです。なぜなら、「サブ問題が重複する」からです。つまり、選択した場合 a として 1 そして b として 2, の場合、変数が 3 つ残っており、合計すると 497 になります。を選択すると、同じ副問題にたどり着きます。 a として 2 そして b として 1. 。(そのような偶然の一致の数は、数が増えるにつれて爆発的に増加します。)
このような問題に対処する従来の方法は次のとおりです。 動的プログラミング:副次的な問題に対する解決策の表をボトムアップで作成し (「1 つの変数の合計が 0 になるまでの組み合わせは何個か?」から始まります)、それから反復を通じて構築していきます (「変数の組み合わせは何個あるのか」という解決策)。 n 変数の合計は k?」は「何通りの組み合わせがあるか」の解の合計です。 n-1 変数の合計は j?" 0 <= j <= k).
public static long getCombos( int n, int sum ) {
// tab[i][j] is how many combinations of (i+1) vars add up to j
long[][] tab = new long[n][sum+1];
// # of combos of 1 var for any sum is 1
for( int j=0; j < tab[0].length; ++j ) {
tab[0][j] = 1;
}
for( int i=1; i < tab.length; ++i ) {
for( int j=0; j < tab[i].length; ++j ) {
// # combos of (i+1) vars adding up to j is the sum of the #
// of combos of i vars adding up to k, for all 0 <= k <= j
// (choosing i vars forces the choice of the (i+1)st).
tab[i][j] = 0;
for( int k=0; k <= j; ++k ) {
tab[i][j] += tab[i-1][k];
}
}
}
return tab[n-1][sum];
}
$ time java Combos 2656615626 real 0m0.151s user 0m0.120s sys 0m0.012s
他のヒント
あなたの質問に対する答えは 2656615626 です.
答えを生成するコードは次のとおりです。
public static long getNumCombinations( int summands, int sum )
{
if ( summands <= 1 )
return 1;
long combos = 0;
for ( int a = 0 ; a <= sum ; a++ )
combos += getNumCombinations( summands-1, sum-a );
return combos;
}
あなたの場合、 summands は5であり、 sum は500です。
このコードは遅いことに注意してください. 。速度が必要な場合は、結果をキャッシュします。 summand,sum ペア。
数字が欲しいのだと思います >=0. 。あなたが望むなら >0, 、ループの初期化を次のように置き換えます。 a = 1 そしてループ条件は a < sum. 。また、順列が必要であると仮定します（例： 1+2+3+4+5 プラス 2+1+3+4+5 等）。必要に応じて for ループを変更できます a >= b >= c >= d >= e.
私は数か月前に父のためにこの問題を解決しました...延長してご利用ください。これらは 1 回限りの問題になることが多いため、最も再利用可能なものは選びませんでした...
a+b+c+d = 合計
i = 組み合わせの数
for (a=0;a<=sum;a++)
{
for (b = 0; b <= (sum - a); b++)
{
for (c = 0; c <= (sum - a - b); c++)
{
//d = sum - a - b - c;
i++
}
}
}
これは、ホワイトボードに書き込むことができるほど単純ですが、十分に慎重に考えないとつまずいてしまう可能性があるほど複雑であるため、実際には面接で尋ねるのに良い質問です。また、実装がまったく異なる原因となる 2 つの異なる答えについても可能です。
順序の問題
順序が重要な場合、どの解法でも変数のいずれかにゼロが現れることを許可する必要があります。したがって、最も単純な解決策は次のようになります。
public class Combos {
public static void main() {
long counter = 0;
for (int a = 0; a <= 500; a++) {
for (int b = 0; b <= (500 - a); b++) {
for (int c = 0; c <= (500 - a - b); c++) {
for (int d = 0; d <= (500 - a - b - c); d++) {
counter++;
}
}
}
}
System.out.println(counter);
}
}
これは 2656615626 を返します。
順序は関係ありません
順序が重要でない場合、和がすでに見つかっていない限りゼロが不可能であることを確認するだけなので、解決策はそれほど難しくありません。
public class Combos {
public static void main() {
long counter = 0;
for (int a = 1; a <= 500; a++) {
for (int b = (a != 500) ? 1 : 0; b <= (500 - a); b++) {
for (int c = (a + b != 500) ? 1 : 0; c <= (500 - a - b); c++) {
for (int d = (a + b + c != 500) ? 1 : 0; d <= (500 - a - b - c); d++) {
counter++;
}
}
}
}
System.out.println(counter);
}
}
2573155876 が返されます。
この問題を調べる 1 つの方法は次のとおりです。
まず、a には 0 ～ 500 の任意の値を指定できます。次に、b+c+d+e = 500-a となります。これにより、問題が 1 変数減ります。完了するまで繰り返します。
たとえば、a が 500 の場合、b+c+d+e=0 になります。これは、a = 500 の場合、b、c、d、および e の値の組み合わせは 1 つだけであることを意味します。
a が 300 の場合、b+c+d+e=200 になります。これは、実際には元の問題と同じ問題を 1 変数だけ削減したものになります。
注記：Chris が指摘しているように、これは実際に問題を解決しようとするひどい方法です。
それらが実数であれば無限です...それ以外の場合は少し複雑になります。
(OK、実数のコンピューター表現には有限の数が存在します...でもそれは大きいでしょう！）
一般的な公式がある場合、
a + b + c + d = N
この場合、非負の積分解の数は次のようになります。 C(N + number_of_variable - 1, N)
@Chris Conwayの答えは正しいです。少額の場合に適した単純なコードでテストしました。
long counter = 0;
int sum=25;
for (int a = 0; a <= sum; a++) {
for (int b = 0; b <= sum ; b++) {
for (int c = 0; c <= sum; c++) {
for (int d = 0; d <= sum; d++) {
for (int e = 0; e <= sum; e++) {
if ((a+b+c+d+e)==sum) counter=counter+1L;
}
}
}
}
}
System.out.println("counter e "+counter);
数学の答えは 504!/(500!*4!)。
正式には、x1+x2+...xk=n の場合、非負数 x1,...xk の組み合わせの数が二項係数になります。(n+k-1) 個の要素を含むセットからの (k-1) 個の組み合わせ。
直感的には、(n+k-1) 個の点から (k-1) 個の点を選択し、選択した 2 つの点の間の点の数を使用して x1,..xk の数値を表します。
スタック オーバーフローに初めて回答したため、数学編が貧弱で申し訳ありません。
Just a test for code block
Just a test for code block
Just a test for code block
マイナスも含めて？無限。
ポジティブな部分だけを含めますか？この場合、それらは「整数」ではなく「自然数」と呼ばれます。この場合...これを本当に解くことはできません、できればいいのですが、私の数学はあまりにも錆びついています。おそらくこれを解決するためのクレイジーな積分方法があるでしょう。数学に熟練した人たちにいくつかのヒントを与えることができます。
最終結果であるaの範囲は0からx、bの範囲は0から（x -a）、cの範囲は0から（x -a -b）、および（x -a -b）になります。 eまで。
答えはそれらすべての可能性の合計です。
Google でもっと直接的な公式を見つけようとしていますが、今日は Google-Fu が本当に不足しています...
