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,1,1,1(总和= 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如果失败则添加语句