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

Question

我需要编写一个recusive函数，它接收一个整数num并返回方程的解数：x1 + x2 + x3 = num，其中x1,x2,x31-10 之间的数字，该方法应打印所有解。

例如，如果num=3那么该方法将打印1+1+1并返回1。

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

1 + 1 + 3

1 + 2 + 2

1 + 3 + 1

2 + 1 + 2

2 + 2 + 1

3 + 1 + 1

如果num<3或num>30方法将返回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);

}

如何在没有重复的情况下获得所需的输出？

Answer 1

你得到重复的原因是两者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){&nbsp; if (x1 > 10 || x1 > num)&nbsp; &nbsp; return 0;&nbsp; if (x2 > 10 || x1+x2 > num)&nbsp; &nbsp; return solutions(num, x1+1, 1, 1);&nbsp; if (x3 > 10 || x1+x2+x3 > num)&nbsp; &nbsp; return solutions(num, x1, x2+1, 1);&nbsp; int me = 0;&nbsp; if (x1+x2+x3 == num) {&nbsp; &nbsp; System.out.printf("%d + %d + %d\n", x1, x2, x3);&nbsp; &nbsp; me=1;&nbsp; }&nbsp; return me + solutions(num, x1, x2, x3+1);}这模仿了您通过修剪搜索整个空间的方法，但更有效的解决方案可以只搜索x1和x2并设置x3=num-x1-x2。

Answer 2

我们可以使用字符串来解决这个问题。声明一个全局字符串变量static String str=""; // taken null intially现在，我们可以使用这个字符串 str 来存储序列并检查它是否已经出现在前面。这样我们就可以跟踪重复的问题，您将得到答案。我已附上我的代码如下。private static int solutions(int num, int x1, int x2, int x3){&nbsp; &nbsp; if (x1 < 1 || x1 > 10 || x2 < 1 || x2 > 10||x3 < 1 || x3 > 10)&nbsp; &nbsp; &nbsp; &nbsp; return 0;&nbsp; &nbsp; if (x1 + x2 + x3 > num)&nbsp; &nbsp; &nbsp; &nbsp; return 0;&nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; if (x1 + x2 + x3 == num)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; String s= String.valueOf(x1)+"+"+String.valueOf(x2)+"+"+String.valueOf(x2);&nbsp; &nbsp; &nbsp; &nbsp; if(!str.contains(s))&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; str=str+s+"\n";&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println(x1 + " + " + x2 + " + " + x3);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; return solutions(num, x1 + 1, x2, x3) + solutions(num, x1, x2 + 1, x3) + solutions(num, x1, x2, x3 + 1);}

Answer 3

好吧......没有集合，没有全局变量，没有重复项。我希望你被允许使用 StringBuilder？public static void main(String[] args) {&nbsp; &nbsp; StringBuilder sb = new StringBuilder();&nbsp; &nbsp; System.out.println("num of solutions: " + solutions(5, sb));&nbsp; &nbsp; System.out.println(sb.toString());}public static int solutions(int num, StringBuilder sb) {&nbsp; &nbsp; if (num < 3 || num > 30)&nbsp; &nbsp; &nbsp; &nbsp; return 0;&nbsp; &nbsp; return solutions(num, 1, 1, 1, sb);}private static int solutions(int num, int x1, int x2, int x3, StringBuilder sb) {&nbsp; &nbsp; if (x1 > 10 || x2 > 10 || x3 > 10) {&nbsp; &nbsp; &nbsp; &nbsp; return 0;&nbsp; &nbsp; }&nbsp; &nbsp; if (x1 + x2 + x3 > num) {&nbsp; &nbsp; &nbsp; &nbsp; return 0;&nbsp; &nbsp; }&nbsp; &nbsp; if (x1 + x2 + x3 == num) {&nbsp; &nbsp; &nbsp; &nbsp; String str = x1 + " + " + x2 + " + " + x3;&nbsp; &nbsp; &nbsp; &nbsp; if (!sb.toString().contains(str)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sb.append(str).append(System.lineSeparator());&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return solutions(num, x1 + 1, x2, x3, sb)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;+ solutions(num, x1, x2 + 1, x3, sb)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;+ solutions(num, x1, x2, x3 + 1, sb);}结果：&nbsp; &nbsp; num of solutions: 6&nbsp; &nbsp; 3 + 1 + 1&nbsp; &nbsp; 2 + 2 + 1&nbsp; &nbsp; 2 + 1 + 2&nbsp; &nbsp; 1 + 3 + 1&nbsp; &nbsp; 1 + 2 + 2&nbsp; &nbsp; 1 + 1 + 3

Answer 4

试试这个 ：public static void main(String... args) {&nbsp; &nbsp; System.out.println(solutions(5));}public static int solutions(int n) {&nbsp; &nbsp; if (n < 3 || n > 30) return 0;&nbsp; &nbsp; return solutions(n, n-2, 1, 1, 0);}public static int solutions(int n, int x1, int x2, int x3, int solutions) {&nbsp; &nbsp; ++solutions;&nbsp; &nbsp; System.out.println("Solution found : "+x1 +"+" + x2 + "+" + x3);&nbsp; &nbsp; if(x3 == n-2) return solutions;&nbsp; &nbsp; if(x2 > 1) {&nbsp; &nbsp; &nbsp; &nbsp; return solutions(n, x1, x2-1, x3+1, solutions);&nbsp; &nbsp; }&nbsp; &nbsp; if(x1 > 1) {&nbsp; &nbsp; &nbsp; &nbsp; return solutions(n, x1-1, n-x1, 1, solutions);&nbsp; &nbsp; }&nbsp; &nbsp; return solutions;}输出：6这个想法如下：您从尽可能大的 x1 开始。然后你遵循这两个规则：如果 x2 > 1 则 x2 = x2 - 1 且 x3 = x3 + 1如果不是，并且如果 x1 > 1 THEN x1 = x1 - 1，x3 = 1 和 x2 = 获得正确总数所需的数量。如果这两个条件都不成立，则没有更多的解决方案。结果 ：3 + 1 + 1第一个条件为假，第二个条件为真：我们将 1 移至 x1，x3 变为 1，x2 变为逻辑上的 22 + 2 + 1第一个条件为真。我们从 x2 中删除 1，然后将 1 添加到 x32 + 1 + 2第一个条件为假第二个条件为真1 + 3 + 1第一个条件为真1 + 2 + 2第一个条件为真1 + 1 + 3第一个条件为假，第二个为假。我们有 6 个解决方案，就是这样。希望有所帮助！