查找和打印x1 + x2 + x3 = num的解决方案数量 [英] Find and print num of solutions to x1+x2+x3=num

问题描述

我需要编写一个 recusive 函数，该函数获取整数 num 并返回方程式的解数: x1 + x2 + x3 = num ，其中 x1，x2，x3 是1到10之间的数字，该方法应打印所有解决方案.

I need to write a recusive function that recive an integer num and returns the number of solutions to the equation :x1 + x2 + x3 = num, where x1,x2,x3 are numbers between 1-10, the method should print all solutions.

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

For example if num=3 then the method will print 1+1+1 and will return 1.

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

if num=5 the method will return 6 and will print:

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

如果 num< 3 或 num> 30 ，则该方法将返回 0 .

if num<3 or num>30 the method will return 0.

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

The method should be recursive without using loops. Global variables are not allowed. Lists are also not allowed.

在这里，我的代码可以正常工作，但也可以打印出重复的内容，对于 num = 5 可以打印:

Here my code, it works fine but it also prints duplicates, for num=5 it prints:

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?

推荐答案

获取重复项的原因是 solutions(1,2,1)和 solutions(2，1,1)将引导您进入 2 + 2 +1 .

The reason why you're getting duplicates is that both solutions(1,2,1) and solutions(2,1,1) will lead you to 2 + 2 + 1.

不重复获取三位数的简单方法是将其从111计数到10,10,10，就好像它是一个十进制整数一样:

The trivial way of not getting duplicate for three digits is count up from 111 to 10,10,10 as if it was a decimal integer:

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);
}

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

This mimics your approach of searching through the full space with pruning, but a more efficient solution could just search through x1 and x2 and set x3=num-x1-x2.

这篇关于查找和打印x1 + x2 + x3 = num的解决方案数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！