建议将一个数字写成三个数字的总和，其中每个数字至少是两个

Question

我试图找到所有可能的组合来写一个数字作为三个数字的总和，其中每个数字至少是 2。

所以基本上对于 6 来说是这样的：

2 2 2

对于 7，它将是：

2 2 3 或 2 3 2 或 3 2 2

我想知道是否有比运行 3 个循环更好的方法。

编辑：

public class Problem {
    public static void main(String args[]) {

        int N = 7, n1, n2, n3;

        for (n1 = 2; n1 <= N; n1++) {
            for (n2 = 2; n2 <= N; n2++) {
                for (n3 = 2; n3 <= N; n3++) {
                    if ( (n1+n2+n3)==N ) {
                        System.out.println(n1 + " " + n2 + " " + n3);
                    }
                }
            }
        }
    }
}

这个解决方案可行，但我在想是否还有其他方法。

Answer 1

这是我的建议

创建一个 class 来模拟方程式的每个答案这里我们创建一个静态内部 class 来模拟每个答案：

public static class Answer{
    private int a;
    private int b;
    private int c;
    public Answer(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }

    public int getA() {
        return a;
    }


    public int getB() {
        return b;
    }

    public int getC() {
        return c;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Answer answer = (Answer) o;
        return a == answer.a &&
                b == answer.b &&
                c == answer.c;
    }

    @Override
    public int hashCode() {
        return Objects.hash(a, b, c);
    }

    @Override
    public String toString() {
        return "Answer{" +
                "a=" + a +
                ", b=" + b +
                ", c=" + c +
                '}';
    }
}

然后递归算法产生结果：

// don't call this method directly only combination method must call it
private Set<Answer> combinationHelper(int n){
    Set<Answer> results = new HashSet<>();
    if(n < 0)
        return results;
    if(n  == 0) {
        results.add(new Answer(0, 0, 0));
        return results;
    }

    Set<Answer> remain = combinationHelper(n - 1);
    remain.forEach(element -> {
        int a = element.getA();
        int b = element.getB();
        int c = element.getC();
        results.add(new Answer(a + 1, b, c));
        results.add(new Answer(a, b + 1, c));
        results.add(new Answer(a, b, c + 1));
    });
    return results;
}

public Set<Answer> combination(int n){
    Set<Answer> results = combinationHelper(n - 6);
    return results.stream()
                  .map(a -> new Answer(a.getA() + 2, a.getB() + 2, a.getC() + 2))
                  .collect(Collectors.toSet());
}

然后这样称呼它：

System.out.println(new Comb().combination(6));
System.out.println(new Comb().combination(7));

产生结果：

[Answer{a=2, b=2, c=2}]
[Answer{a=2, b=3, c=2}, Answer{a=3, b=2, c=2}, Answer{a=2, b=2, c=3}]

如果您不喜欢向您的应用程序添加另一个模型 class 的想法，您可以轻松地使用数组来代替

非递归方法：

public List<String> combination(int n){
    List<String> result = new ArrayList<>();
    if(n < 6)
        return result;
    BitSet bits = new BitSet(n - 6);
    bits.set(0, n - 6);
    IntStream
            .range(0, n - 5)
            .forEach(i ->
                    IntStream.range(i, n - 5).forEach(j ->
                            result.add(String.format("%s %d %d %d %s", "{", bits.get(0, i).length() + 2, bits.get(i, j).length() + 2, bits.get(j, n).length() + 2, "}"))));
    return result;

}

非递归方法的结果：

对于输入 7：

[{ 2 2 3 }, { 2 3 2 }, { 3 2 2 }]

对于输入 6：

[{ 2 2 2 }]

Answer 2

您要将 partition 一个整数 n 分成 k 个部分，其中每个部分都有一个最小值 min。这里的经典方法是使用递归。

最初我们创建一个数组来保存零件，将它们初始化为 min 并从 n 中删除 k*min 以获得余数。

static List<int[]> partitions(int n, int k, int min)
{
    int[] parts = new int [k];
    Arrays.fill(parts, min);
    
    int rem = n - k*min;
    
    List<int[]> results = new ArrayList<>();
    partition(results, parts, rem);
    return results;
}

我们现在使用递归的方法来探索依次将每个部分加1。如果余数达到 0，我们就有一个解决方案并将当前解决方案添加到结果中。

static void partition(List<int[]> results, int[] parts, int rem)
{
    if(rem <= 0)
    {
        if(rem == 0) results.add(parts.clone());
        return;
    }
    
    for(int i=0; i<parts.length; i++)
    {
        parts[i] += 1;
        partition(results, parts, rem-1);
        parts[i] -= 1;
    }
}

测试：

public static void main(String[] args)
{
    for(int[] res : partitions(7, 3, 2))
        System.out.println(Arrays.toString(res));       
}

输出：

[3, 2, 2]
[2, 3, 2]
[2, 2, 3]

建议将一个数字写成三个数字的总和，其中每个数字至少是两个

Suggestion to write a number as a sum of three numbers where each number is at least two

algorithm

combinations

sum