logo标签列表

寻找整数和任意运算符的组合以得出固定结果的算法

javaalgorithmmath
5

我正在编写一个程序，它接收4个数字作为输入，然后尝试看看这四个数字的加减乘除组合是否可以等于24。我的方法是为每一个可能的四个数字和四种运算符创建一个方法，这有点啰嗦。以下是两种方法的示例：

public static boolean add(int a, int b, int c, int d) {
    boolean adBool;
    adBool = a + b + c + d == 24;
    return adBool;
}

public static boolean sub1(int a, int b, int c, int d) {
    boolean subBool1;
    subBool1 = a - b - c - d == 24;
    return subBool1;
}

接下来在我的Main函数中，我为每个方法创建了一个while循环，如果该方法返回true，则打印该方法停止的位置是解决方案。以下是一个示例。

while (add(num1, num2, num3, num4)) {
    System.out.println("Your solution is "
            + num1 + " + " + num2 + " + " + num3 + " + " + num4
            + " = 24\nCongratulations!");
    break;

}
while (sub1(num1, num2, num3, num4)) {
    System.out.println("Your solution is "
            + num1 + " - " + num2 + " - " + num3 + " - " + num4
            + " = 24\nCongratulations!");
    break;
}

有没有一种方法可以存储像+和-这样的操作符，以便我可以将它们放入一个数组中，并只使用一些嵌套的for循环来编写代码？
1
你应该能够将所有4种方法的逻辑放在一个单一的方法中。 - yogidilip
1
你需要找到所有的组合还是只需要一个就足够了？ - Gaël J
1
你是如何处理操作顺序的？你是否需要担心这4个数字的结合性？ - NotAGenie
如果提供了528、11、7和14，那么528 / 14 * 7 / 11是一个有效的解决方案吗？或者应该像整数一样528 / 14 == 38？ - Andreas
这是同一个问题，但使用了优先级（括号）。我提供了JavaScript的解决方案，但逻辑在这里也应该有用：http://stackoverflow.com/questions/32229242/solution-finder-algorithm-using-basic-operations/32237550#32237550（查看代码的第二个版本，第一个版本过于复杂） - m69 ''snarky and unwelcoming''
显示剩余6条评论
2个回答
2
假设操作数是固定的，您可以创建一个生成器，将可能的运算符输出，并将它们传递给评估器以确定它们是否为真。
while (generator.hasNext()){
    Operators ops = generator.getNext();
    if evaluatesTo(operand1, operand2, operand3, operand4, 24, ops){
       // print it
    }
}

一个简单的生成器可以像这样实现：
List<String> list = new ArrayList<String>();
list.add("+++");
list.add("++-");
...
Iterator generator = list.iterator();

生成器实现了java.util.Iterator接口，它使用所有运算符（+-*/），并输出大小为3的所有排列组合。

evalutesTo方法只是简单地计算它：

public boolean (int operand1, int operand2, int operand3, int operand4, int total, Operators ops ){
    // calculate operand1 "ops.get(0)" operand2 "ops.get(1)" operand3 "ops.get(2)" operand4  == total
}

如果 ops 是 [+-/]，它将进行检查。

if (operand1 + operand2 - operand3 / operand4 == 24) return true;

我应该补充一下，以后你可以添加各种效率，但是你的问题是如何使用更好的策略来完成这个任务。有其他用户在评论中提到了一些细节，但现在不用太担心。首先，你需要建立这种框架，然后再去考虑细节的问题。最关键的是，你不需要创建数百个类似的方法。

evaluatesTo方法在哪里？我在哪里传递操作符？这一切将如何被组织起来？ - Gabe Spound
你需要实现生成器。 - ergonaut
我对Java还很陌生，你能否详细解释每一步操作？我并不是想让别人替我完成（毕竟这不是作业，只是为了学习），但我确实不知道该怎么做。 - Gabe Spound
这里的难点不在于方法及其用途，而在于找出一种高效生成所有256种+、-、/、*组合的方法。 - Ceelos
1
https://dev59.com/fmkv5IYBdhLWcg3w3Eal - ergonaut
显示剩余2条评论
2

我为您做了一些调查。
我找到了这个StackExchange问题，介绍了如何创建给定字符集的所有可能组合。您可以使用此方法生成+、-、/、*的所有可能组合，方法在该问题中有描述。

public static void combinations(int maxLength, char[] alphabet, String curr) {
  // If the current string has reached it's maximum length
  if (curr.length() == maxLength) {
    System.out.println(curr);

    // Else add each letter from the alphabet to new
    // strings and process these new strings again
  } else {
    for (int i = 0; i < alphabet.length; i++) {
      String oldCurr = curr;
      curr += alphabet[i];
      combinations(maxLength, alphabet, curr);
      curr = oldCurr;
    }
  }
}

并且使用类似以下方式进行调用

char[] operators = new char[]{'+', '-', '/', '*'};
// You want to call it with 3 since you only need 3 operators.
combinations(3, operators , "");

在打印出新组合(System.out.println(curr);)之后（或在其替代），你可以调用一个方法来解释输出。可以参考类似于这个stackoverflow简单计算器示例的东西。
例如，可以使用如下内容:
```java interpretOutput(curr); ```
其中，`interpretOutput`是一个自定义的方法，在方法中对`curr`进行解释。
if (curr.charAt(0) == '+') {
  //add the first and second number
}

我认为这已经足够让你开始了。

手头有时间，而且觉得这很有趣，所以想要完成它。给你。这完全符合你的需求。

import java.util.Random;
import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;

public class Blah {
  public static void main(String[] args) throws ScriptException {
    char[] operators = new char[]{'+', '-', '/', '*'};
    combinations(3, operators, "");
  }

  public static void combinations(
        int maxLength, char[] alphabet, String curr)
        throws ScriptException {
    // If the current string has reached it's maximum length
    if (curr.length() == maxLength) {
      System.out.println(curr);
      calculate(curr);

      // Else add each letter from the alphabet to new
      // strings and process these new strings again
    } else {
      for (int i = 0; i < alphabet.length; i++) {
        String oldCurr = curr;
        curr += alphabet[i];
        combinations(maxLength, alphabet, curr);
        curr = oldCurr;
      }
    }
  }

  private static void calculate(String operators) throws ScriptException {
    int operand1, operand2, operand3, operand4;
    Random randGen = new Random();
    ScriptEngineManager mgr = new ScriptEngineManager();
    ScriptEngine engine = mgr.getEngineByName("JavaScript");

    int result = 0;
    String operation = ""; // this will hold all the operands and operators
    while (result != 20) {
      operand1 = randGen.nextInt(101);
      operand2 = randGen.nextInt(101);
      operand3 = randGen.nextInt(101);
      operand4 = randGen.nextInt(101);
      // So here is where it got a bit tricky
      // and you can go different ways about this.
      // I went the easy way and used the built-in Javascript engine.
      operation = String.valueOf(operand1) + operators.charAt(0)
              + String.valueOf(operand2) + operators.charAt(1)
              + String.valueOf(operand3) + operators.charAt(2)
              + String.valueOf(operand4);
      // System.out.println(operation);
      result = (int) Double.parseDouble(engine.eval(operation).toString());
    }
    System.out.println(operation + "= 20");
  }
}

为了增加趣味性，我使用了随机数。不确定您如何获取数字输入。需要记住的一件事是，在处理整数时，除法中的小数部分会被舍去。因此，像12/64 = 0或11/5 = 2这样的运算结果都是整数。
以下是一个示例输出：
run:
+++
0+0+10+10= 20
++-
59+3+38-80= 20
++/
19+0+66/53= 20
++*
15+5+0*54= 20
+-+
23+26-97+68= 20
+--
87+66-73-60= 20
+-/
15+5-0/33= 20
+-*
63+57-50*2= 20
+/+
8+61/37+11= 20
+/-
72+38/55-52= 20
+//
20+61/71/8= 20
+/*
18+5/28*14= 20
+*+
2+0*14+18= 20
+*-
35+1*75-90= 20
+*/
20+8*5/54= 20
+**
20+91*0*2= 20
-++
37-100+17+66= 20
-+-
65-89+46-2= 20
-+/
52-32+33/84= 20
-+*
52-32+44*0= 20
--+
39-74-22+77= 20
---
92-0-54-18= 20
--/
62-41-45/73= 20
--*
54-34-0*82= 20
-/+
22-98/9+9= 20
-/-
66-27/71-45= 20
-//
20-0/17/41= 20
-/*
42-20/71*76= 20
-*+
9-2*0+11= 20
-*-
90-6*10-10= 20
-*/
40-75*24/90= 20
-**
20-0*26*90= 20
/++
65/47+6+13= 20
/+-
91/5+56-54= 20
/+/
64/4+69/16= 20
/+*
54/81+2*10= 20
/-+
80/89-68+88= 20
/--
65/2-11-1= 20
/-/
86/4-96/98= 20
/-*
80/4-0*100= 20
//+
12/64/57+20= 20
//-
64/1/1-44= 20
///
82/1/4/1= 20
//*
45/7/18*57= 20
/*+
45/12*4+5= 20
/*-
44/21*45-74= 20
/*/
87/6*55/38= 20
/**
29/76*5*11= 20
*++
0*36+3+17= 20
*+-
4*13+55-87= 20
*+/
2*10+14/72= 20
*+*
0*100+2*10= 20
*-+
49*1-29+0= 20
*--
48*2-54-22= 20
*-/
1*21-11/73= 20
*-*
44*52-27*84= 20
*/+
7*8/56+19= 20
*/-
38*77/55-33= 20
*//
95*99/6/77= 20
*/*
2*9/72*83= 20
**+
0*11*40+20= 20
**-
8*6*1-28= 20
**/
29*59*1/82= 20
***
4*1*5*1= 20
BUILD SUCCESSFUL (total time: 34 minutes 35 seconds)

由于100个随机整数的限制，像///和***这样的非常棘手的问题使得运行需要34分钟。此外，我没有尽可能地使其更加清洁/高效，并且也没有注意对象泄漏/不必要的对象创建。这将由您来完成。

它非常慢，因为您每次修改字符串后都需要解析字符串并进行评估。仅存储运算符更有效率。 - phuclv
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接