Java:将数字分成相等的部分或彼此近似

Question

我有一个数字 = 20。我想将这个数字分成 N 个相等或彼此近似的部分。 N 可能从 1 到 20。

我写这段代码:

ArrayList<Integer> c = new ArrayList<>();
int num = 20;
int count = N; //where N some number (from 1 to 20)
int val = (int) Math.floor(num / count);

for (int i = 0; i < count; i++) {
    c.add(val);
}
c.set(0, c.get(0) + num - sum(c));

它工作正常，例如，当 count = N = 3 时。我得到:8, 6, 6 (8+6+6=20)。但是如果 count = N = 12 我得到下一个结果:9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 (sum = 20)。我希望下一个结果是:1, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1 (sum = 20)。这可能吗？

Answer 1

您计算下一个部分的大小，然后减少值并重复:

private static int[] splitIntoParts(int whole, int parts) {
    int[] arr = new int[parts];
    int remain = whole;
    int partsLeft = parts;
    for (int i = 0; partsLeft > 0; i++) {
        int size = (remain + partsLeft - 1) / partsLeft; // rounded up, aka ceiling
        arr[i] = size;
        remain -= size;
        partsLeft--;
    }
    return arr;
}

如果您愿意，可以压缩该方法，但如上保留它更好，因为它将参数视为不可变的并阐明了逻辑:

private static int[] splitIntoParts(int whole, int parts) {
    int[] arr = new int[parts];
    for (int i = 0; i < arr.length; i++)
        whole -= arr[i] = (whole + parts - i - 1) / (parts - i);
    return arr;
}

测试

for (int parts = 0; parts <= 25; parts++)
    System.out.println(parts + ": " + Arrays.toString(splitIntoParts(20, parts)));

输出

0: []
1: [20]
2: [10, 10]
3: [7, 7, 6]
4: [5, 5, 5, 5]
5: [4, 4, 4, 4, 4]
6: [4, 4, 3, 3, 3, 3]
7: [3, 3, 3, 3, 3, 3, 2]
8: [3, 3, 3, 3, 2, 2, 2, 2]
9: [3, 3, 2, 2, 2, 2, 2, 2, 2]
10: [2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
11: [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1]
12: [2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1]
13: [2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1]
14: [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1]
15: [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
16: [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
17: [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
18: [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
19: [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
20: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
21: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
22: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0]
23: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]
24: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0]
25: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0]

请注意 0 返回空数组。如果失败，请添加 if 语句。负值将因 NegativeArraySizeException 而失败。如您所见，太多的部分将简单地返回 0 大小的部分。同样，如果失败则添加 if 语句