查找并打印 x1+x2+x3=num 的解数

Question

我需要编写一个 recusive 函数来接收整数 num 和 returns 方程的解数：x1 + x2 + x3 = num，其中 x1,x2,x3 是 1-10 之间的数字，该方法应打印所有解决方案。

例如，如果 num=3 则该方法将打印 1+1+1 并将 return 1.

如果 num=5 该方法将 return 6 并打印：

1 + 1 + 3
1 + 2 + 2
1 + 3 + 1
2 + 1 + 2
2 + 2 + 1
3 + 1 + 1

如果 num<3 或 num>30 该方法将 return 0.

该方法应该是递归的，不使用循环。不允许使用全局变量。列表也是不允许的。

这是我的代码，它工作正常但它也打印重复项，因为 num=5 它打印：

3 + 1 + 1
2 + 2 + 1
2 + 1 + 2
2 + 2 + 1
1 + 3 + 1
1 + 2 + 2
2 + 1 + 2
1 + 2 + 2
1 + 1 + 3

这是我的代码：

public static void main(String[] args) {
    System.out.println("num of solutions: "+solutions(5));

}

public static int solutions(int num) 
{

    if (num < 3 || num > 30)
        return 0;

    return solutions(num, 1, 1, 1);
}
private static int solutions(int num, int x1, int x2, int x3)
{
    if (x1 < 1 || x1 > 10 || x2 < 1 || x2 > 10||x3 < 1 || x3 > 10)
        return 0;
    if (x1 + x2 + x3 > num)
        return 0;       
    if (x1 + x2 + x3 == num)
    {
        System.out.println(x1 + " + " + x2 + " + " + x3);
        return 1;
    }           
    return solutions(num, x1 + 1, x2, x3) + solutions(num, x1, x2 + 1, x3) + solutions(num, x1, x2, x3 + 1);

}

How do I get the desired output without duplicates?

Answer 1

我们可以使用字符串来解决这个问题。声明一个全局字符串变量

static String str=""; // taken null intially

现在，我们可以使用这个字符串str来存储序列，并检查它是否已经出现在前面。这样我们就可以跟踪重复的问题，您将得到答案。我已附上我的代码如下。

private static int solutions(int num, int x1, int x2, int x3)
{
    if (x1 < 1 || x1 > 10 || x2 < 1 || x2 > 10||x3 < 1 || x3 > 10)
        return 0;
    if (x1 + x2 + x3 > num)
        return 0;       
    if (x1 + x2 + x3 == num)
    {
        String s= String.valueOf(x1)+"+"+String.valueOf(x2)+"+"+String.valueOf(x2);
        if(!str.contains(s))
        {
            str=str+s+"\n";
            System.out.println(x1 + " + " + x2 + " + " + x3);
            return 1;
        }
    }           
    return solutions(num, x1 + 1, x2, x3) + solutions(num, x1, x2 + 1, x3) + solutions(num, x1, x2, x3 + 1);

}

Answer 2

您得到重复项的原因是 solutions(1,2,1) 和 solutions(2,1,1) 都会将您带到 2 + 2 + 1。

不重复三位数的简单方法是从 111 递增到 10、10、10，就好像它是十进制整数一样：

private static int solutions(int num, int x1, int x2, int x3)
{
  if (x1 > 10 || x1 > num)
    return 0;
  if (x2 > 10 || x1+x2 > num)
    return solutions(num, x1+1, 1, 1);
  if (x3 > 10 || x1+x2+x3 > num)
    return solutions(num, x1, x2+1, 1);

  int me = 0;
  if (x1+x2+x3 == num) {
    System.out.printf("%d + %d + %d\n", x1, x2, x3);
    me=1;
  }
  return me + solutions(num, x1, x2, x3+1);
}

这模仿了您通过修剪搜索整个 space 的方法，但更有效的解决方案可以只搜索 x1 和 x2 并设置 x3=num-x1-x2。

Answer 3

嗯...没有集合，没有全局变量，没有重复项。希望您可以使用 StringBuilder？

public static void main(String[] args) {
    StringBuilder sb = new StringBuilder();

    System.out.println("num of solutions: " + solutions(5, sb));

    System.out.println(sb.toString());
}

public static int solutions(int num, StringBuilder sb) {
    if (num < 3 || num > 30)
        return 0;

    return solutions(num, 1, 1, 1, sb);
}

private static int solutions(int num, int x1, int x2, int x3, StringBuilder sb) {
    if (x1 > 10 || x2 > 10 || x3 > 10) {
        return 0;
    }

    if (x1 + x2 + x3 > num) {
        return 0;
    }

    if (x1 + x2 + x3 == num) {
        String str = x1 + " + " + x2 + " + " + x3;
        if (!sb.toString().contains(str)) {
            sb.append(str).append(System.lineSeparator());
            return 1;
        }
    }

    return solutions(num, x1 + 1, x2, x3, sb) 
           + solutions(num, x1, x2 + 1, x3, sb) 
           + solutions(num, x1, x2, x3 + 1, sb);
}

结果：

    num of solutions: 6
    3 + 1 + 1
    2 + 2 + 1
    2 + 1 + 2
    1 + 3 + 1
    1 + 2 + 2
    1 + 1 + 3

Answer 4

试试这个：

public static void main(String... args) {
    System.out.println(solutions(5));
}
public static int solutions(int n) {

    if (n < 3 || n > 30) return 0;
    return solutions(n, n-2, 1, 1, 0);

}

public static int solutions(int n, int x1, int x2, int x3, int solutions) {

    ++solutions;
    System.out.println("Solution found : "+x1 +"+" + x2 + "+" + x3);

    if(x3 == n-2) return solutions;

    if(x2 > 1) {
        return solutions(n, x1, x2-1, x3+1, solutions);
    }

    if(x1 > 1) {
        return solutions(n, x1-1, n-x1, 1, solutions);
    }
    return solutions;
}

输出：6

思路如下：

你从尽可能大的 x1 开始。

那么你要遵循这两条规则:

如果 x2 > 1 那么 x2 = x2 - 1 并且 x3 = x3 + 1

如果不是，并且如果 x1 > 1，则 x1 = x1 - 1，x3 = 1 且 x2 = 获得正确总数所需的数量。

如果这两个条件中有none个成立，则无解。

结果：

3 + 1 + 1

第一个条件为假，第二个为真：我们把1去掉x1，x3变成1，x2逻辑上变成2

2 + 2 + 1

第一个条件为真。我们从 x2 中删除 1，然后将 1 添加到 x3

2 + 1 + 2

第一个条件为假

第二个条件为真

1 + 3 + 1

第一个条件为真

1 + 2 + 2

第一个条件为真

1 + 1 + 3

第一个条件为假，第二个条件为假。

我们有 6 个解决方案，就是这样。

希望对您有所帮助！

查找并打印 x1+x2+x3=num 的解数

Find and print num of solutions to x1+x2+x3=num

java

recursion

backtracking