12

各グループの要素の合計が A になるように、N 個の整数の異なる順序付きグループの数を計算したい

例: N = 3 で A = 3 の場合、結果は 10 になります。
1 = [3, 0, 0]
2 = [2, 1, 0]
3 = [1, 2, 0]
4 = [0, 3 , 0]
5 = [2, 0, 1]
6 = [1, 1, 1]
7 = [0, 2, 1]
8 = [1, 0, 2]
9 = [0, 1, 2]
10 = [0, 0, 3]

私がやった方法は力ずくでした：

public static int calc(int a, int n){
    if (n <= 1 || a == 0) return 1;

    int sum = 0;
    for (int i=0; i<=n; i++)
        sum += calc(a - i, n - 1);

    return sum;
}

もっと良い方法があると思います（私が見逃しているいくつかの数学的計算..）はありますか？

編集 元の質問では、順序を考慮するのを忘れていました

4

5 に答える 5

5

これは、AをN個の部分（ゼロ部分を含む）に組み合わせた構成です。ペア（A、N）の構成の数は、C（A + N -1、A）に等しくなります。ここで、C（）は、組み合わせ数、つまり二項係数です。こことここで同じ式を参照してください

于 2012-10-12T16:56:02.210 に答える
3

長さの大きなセグメントを想像してくださいA。N-1そして、セグメントをパーツに分割する順序付きセパレーターを想像してみてください。したがって、各部分は被加数ですが、セグメント全体は合計です。

エルゴ、必要なのは、セパレーターの場所を列挙するアルゴリズムを提供することだけです。

N+1P_0={0,1,...N}のいずれかの位置に配置できる最初のセパレーター

2 番目の区切り文字は、P_1={P_0,...N} のいずれかに入ることができます

等々。

これを実装するには、再帰を使用できます。

于 2012-10-12T12:02:18.067 に答える
2

これに答える数学的な計算があると確信していますが、これはプログラミングの Q&A であるため、プログラムでより速く答えを出す方法を説明します: memoizationを使用できます。

calc(a, n)現在、プログラムは毎回答えを再計算します。ただし、その後の呼び出しでは変化しないため、答えは 1 回計算できます。の結果に 2D 配列を追加し、calc(a,n)で初期化し-1、それを使用して計算する前に結果を検索し、同じ数値を何度も再計算する時間を大幅に節約します。

private static int[][] memo = new int[30][30];
static {
    for(int i = 0 ; i != 30 ; i++)
        for(int j = 0 ; j != 30 ; j++)
            memo[i][j] = -1;
}
public static int calc(int a, int n){
    if (n <= 1 || a == 0) return 1;
    if (memo[a][n] > 0) return memo[a][n];
    int sum = 0;
    for (int i=0; i<=n; i++)
        sum += calc(a - i, n - 1);
    return (memo[a][n] = sum);
}
于 2012-10-12T10:55:28.537 に答える
1

列挙の場合：上記の他のソリューションで指定された式を使用してください。より効率的です。必要でない限り、n 整数合成の完全なセットを実際に生成する必要はありません。特に、それらを生成するのではなく合計するだけの場合は、扱いにくいプロパティがあります。それらを生成することは別の問題です...

生成の場合: ループレス アルゴリズムを使用してください... O(1) ごとのグレイ コード シーケンスの結果が多数あります。ループレスアルゴリズムを持たない、または持つことができる、制限された整数構成のバリエーションはほとんどありません。整数合成に関するこのクラスの問題には多くのアルゴリズムがあり、そのほとんどは非常に特殊ですが、この特定の問題のために存在する最新のループレス アルゴリズムがたくさんあります。超効率的。大量の並列コンピューティングを自由に使用できる場合を除き、力ずくでこの問題を解決することはできません。Google または Google Scholar を自由に使用できます。:D

お役に立てれば！

于 2012-12-20T23:55:50.783 に答える
0

再帰のみで区切り記号を使用しない別の解決策を見つけました。

public class App201210121604 {

public static Vector<int[]> split(int sum, int count) {

    if( sum < 0 ) {
        throw new IllegalArgumentException("Negative sum is not allowed");
    }

    Vector<int[]> ans = new Vector<int[]>();

    // "reserved" end of recursion
    if( count <= 0 ) {
        // nothing to do
    }

    // end of recursion
    else if( count == 1 ) {
        ans.add(new int[] {sum});
    }

    // body of recursion
    else {
        // for each first summand from 0 to summ
        for(int i=0; i<=sum; ++i) {

            // do a recursion to get the "tail"
            for(int[] tail : split(sum-i, count-1)) {

                int[] group = new int[count];
                group[0] = i;
                System.arraycopy(tail, 0, group, 1, count-1);

                ans.add(group);
            }
        }
    }

    return ans;
}

public static void main(String[] args) {

    Vector<int[]> ans = split(8, 4);

    for(int[] group : ans) {
        for(int i=0; i<group.length; ++i) {
            if( i>0 ) System.out.print("+");
            System.out.print(group[i]);
        }
        System.out.println("");
    }
}

}
于 2012-10-12T14:18:08.817 に答える