>我需要编写一个回避函数,该函数接受整数num
并返回方程的解数:x1 + x2 + x3 = num
,其中x1,x2,x3
是1-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);
}
如何在没有重复的情况下获得所需的输出?
你得到重复的原因是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 + %dn", x1, x2, x3);
me=1;
}
return me + solutions(num, x1, x2, x3+1);
}
这模仿了您通过修剪搜索整个空间的方法,但更有效的解决方案可以搜索x1
和x2
并设置x3=num-x1-x2
。
我们可以使用字符串来解决这个问题。声明一个全局字符串变量
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);
}
嗯...没有集合,没有全局变量,没有重复项。我希望你能使用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
试试这个:
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 = 获得正确总数所需的数字。
如果这两个条件都不成立,就没有更多的解决方案。
结果:
3 + 1+ 1
第一个条件为假,第二个条件为真:我们去掉 1 到 x1,x3 变成 1,x2 在逻辑上变成 2
2 + 2 + 1
第一个条件为真。我们删除 1 到 x2 并将 1 添加到 x3
2 + 1 + 2
第一个条件为假
第二个条件为真
1 + 3 + 1
第一个条件为真
1 + 2+ 2
第一个条件为真
1 + 1 + 3
第一个条件是假的,第二个条件是假的。
我们有 6 种解决方案,所以就这样。
希望有帮助!