5

次のことがわかっている場合、変数 a、b、c、d、e の可能な組み合わせはいくつありますか。

a+b+c+d+e = 500

そして、それらはすべて整数で >= 0 であるため、それらが有限であることはわかっています。

4

10 に答える 10

11

@Torlack、@Jason Cohen：「重複する副問題」があるため、再帰はここでは悪い考えです。aつまり、 as1とbasを選択した場合2、合計 497 になる 3 つの変数が残ります。aas2とbasを選択すると、同じ副問題に到達します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 コンボ
2656615626

実質 0m0.151s
ユーザー 0分0.120秒
システム 0m0.012s
于 2008-09-12T20:04:30.877 に答える
5

あなたの質問に対する答えは 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でsum500です。

このコードは遅いことに注意してください。速度が必要な場合は、summand,sumペアからの結果をキャッシュします。

私はあなたが数字が欲しいと仮定しています>=0。必要に応じ>0て、ループの初期化を に置き換え、a = 1ループ条件をに置き換えますa < sum。また、順列（1+2+3+4+5プラス2+1+3+4+5など）が必要だと仮定しています。必要に応じて for ループを変更できますa >= b >= c >= d >= e。

于 2008-09-12T19:57:33.187 に答える
2

数か月前に父のためにこの問題を解決しました...あなたの使用のために拡張してください。これらは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++
                }
            }
        }
于 2008-09-12T20:03:43.453 に答える
2

これは、ホワイトボードに書き込めるほど単純な質問ですが、よく考えないとつまずく可能性があるほど複雑な質問なので、実際には面接で尋ねるのに適した質問です。また、実装がまったく異なる原因となる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 を返します。

于 2008-09-12T22:43:34.270 に答える
1

この問題を調べる 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 が指摘しているように、これは実際に問題を解決しようとする恐ろしい方法です。

リンクテキスト

于 2008-09-12T19:14:19.017 に答える
0

@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);
于 2013-11-05T08:13:18.003 に答える
0

それらが実数の場合、無限になります...そうでない場合は、少しトリッキーです。

（OK、実数のコンピュータ表現には有限のカウントがあります...しかし、それは大きいでしょう！）

于 2008-09-12T18:54:01.547 に答える
0


a + b + c + d = N の場合、一般式があります。
非負の積分解の数は次のようになります。C(N + number_of_variable - 1, N)

于 2012-11-11T17:14:37.240 に答える
0

数学の答えは 504!/(500! * 4!) です。

形式的には、x1+x2+...xk=n の場合、非負の数 x1,...xk の組み合わせの数は二項係数です: (k-1)-(n+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
于 2017-06-22T15:35:08.413 に答える
-1

マイナスも含めて？無限。

ポジティブなものだけを含む？この場合、それらは「整数」ではなく「自然」と呼ばれます。この場合...私はこれを本当に解決することはできません.できればいいのですが、私の数学は錆びすぎています. おそらく、これを解決するためのクレイジーで不可欠な方法があります。数学に精通した人にいくつかの指針を与えることができます。

x が最終結果であるとすると、a の範囲は 0 から x になり、b の範囲は 0 から (x - a) になり、c の範囲は 0 から (x - a - b) になります。 eまで同様です。

答えは、これらすべての可能性の合計です。

Google でもっと直接的な数式を見つけようとしていますが、今日は Google-Fu が本当に不足しています...

于 2008-09-12T19:19:45.743 に答える