15

2 つの整数を と とし、正の数を合計して を得る方法がいくつあるかを返すメソッドを作成する必要nがありmます。たとえば、このようなメソッド呼び出しは、可能な方法が 3 つあるため、3 を返す必要があります。それらは、、およびです。ちなみに、は と同じなので、このメソッドはそれらを 2 つの異なるバリエーションとして数えるべきではありません。誰も問題の解決策を知っていますか?mnpartition(6, 2)5 + 14 + 23 + 34 + 22 + 4

更新:nおよびmは 150 以下です。

4

6 に答える 6

2 
public static long p(final long n, final long m) {
    System.out.println("n=" + n + ", m=" + m);
    return p(n, 1, m);
}

private static long p(final long n, final long digitFrom, final long m) {
    final long digitTo = n - m + 1;
    if (digitFrom > digitTo) return 0;
    if (m == 1) return 1;
    long sum = 0;
    for (long firstDigit = digitFrom; firstDigit <= digitTo; firstDigit++)
        sum += p(n - firstDigit, firstDigit, m - 1);
    return sum;
}

デバッグ例:

n=6, m=3
1+1+4
1+2+3
2+2+2

デバッグ バージョンから:

public static long p(final long n, final long m) {
    System.out.println("n=" + n + ", m=" + m);
    return p(n, 1, m, new Stack<String>());
}

private static long p(final long n, final long digitFrom, final long m, Stack<String> digitStack) {
    final long digitTo = n - m + 1;
    if (digitFrom > digitTo) return 0;
    if (m == 1) {
        digitStack.push(n + "");
        printStack(digitStack);
        digitStack.pop();
        System.out.println();
        return 1;
    }
    long sum = 0;
    for (long firstDigit = digitFrom; firstDigit <= digitTo; firstDigit++) {
        digitStack.push(firstDigit + "+");
        sum += p(n - firstDigit, firstDigit, m - 1, digitStack);
        digitStack.pop();
    }
    return sum;
}
于 2015-10-02T12:57:53.820 に答える
0

使用する桁数がわかっているので、これができると思います。

まず、partition(n, 2) を繰り返し実行することでこれを行うことができます。n = 3、m = 3 が必要な場合は、partition(n, 2) を実行してから、各回答に対して partition(k, 2) を実行できます。

例：

パーティション (6、3):

パーティション (6、2):

5 + 1、4 + 2、3 + 3、2 + 4、5 + 1

パーティション (5、2):

4 + 1、3 + 2 ...

次に、それらをすべて一緒に追加します。

(4+1) + 1、(3+2)+1、(2+3)+1、(1+4)+1、(3+1)+2...

それらを並べ替えます（最大数が最初）。

4+1+1、4+1+1...

次に、すべての重複を削除できます

Partition(n, 2) は O(n) で実行されます (n までループして x + (nx) を実行するだけでよいため)。これを行う必要がある回数は、ある種の O(m) です。また、並べ替えは n 単位で実行できます (すべて整数であることがわかっているため)。したがって、これは O(n*m) で実行されると思いますが、これは良くありませんが、使用できる可能性があります (n または m がかなり小さい場合)。

于 2015-10-02T12:50:26.750 に答える
-2

この問題はサブセット合計問題のようです

これは、NP problemすべてのソリューションが存在することを意味しますnon-deterministic(つまり、既知の効率的なアルゴリズムはありません)。

ただし、ヒューリスティックなアプローチを試して、より効率的な方法で満足のいく結果を見つけることができます。

于 2015-10-02T12:44:32.087 に答える