Algorithmus zum Finden von Kombinationen von Ganzzahlen und beliebigen Operanden, um ein festes Ergebnis zu erhalten

Question

Ich schreibe ein Programm, das 4 Zahlen als Eingabe nimmt und dann versucht zu sehen, ob eine Kombination von Additions-Subtraktions-Division und Multiplikation der vier Zahlen sie gleich machen kann bis 24. Mein Weg war, eine Methode für jede einzelne mögliche Kombination der vier Zahlen und der vier Operanden zu erstellen, die ein wenig ausführlich ist. Hier ist ein Beispiel für 2 Methoden.

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

Da ist in meinem Haupt ich für jede Methode eine while-Schleife erstellen, wenn die Methode true zurückgibt, gedruckt wird, dass das Verfahren auf gestoppt, die Lösung war. Hier ist ein Beispiel.

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

Gibt es eine Möglichkeit Operanden wie + zu speichern und - so, dass ich sie in einem Array setzen und verwenden nur einige verschachtelte for-Schleifen zu schreiben?

Answer 1

Angenommen, die Operanden sind fest, können Sie einen Generator erstellen, der die möglichen Operatoren ausgibt und an einen Evaluator weiterleitet, um festzustellen, ob sie wahr sind.

List<String> list = new ArrayList<String>(); 
list.add("+++"); 
list.add("++-"); 
... 
Iterator generator = list.iterator(); 

wo Generator den java.util.Iterator-Schnittstelle implementiert, die mit allen Operatoren initialisiert (+ - * /) und Deponien aus all:

while (generator.hasNext()){ 
    Operators ops = generator.getNext(); 
    if evaluatesTo(operand1, operand2, operand3, operand4, 24, ops){ 
     // print it 
    } 
} 

Ein einfachen Generator wie dies getan werden könnte Permutationen der Größe 3.

Die evalutesTo Methode berechnet es einfach:

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 
} 

Also, wenn ops ist [+ - /] wäre es

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

prüfe ich hinzufügen, sollten alle Arten von Effizienzen es später hinzufügen können, aber du bist Frage ist, wie Sie dies mit einer besseren Strategie zu tun. Es gibt ein paar Kommentare zu Details von anderen Benutzern, aber ich würde mich jetzt nicht darum kümmern. Zuerst müssen Sie diese Art von Framework einrichten, dann können Sie sich um die Details kümmern. Der Hauptgrund dafür ist, dass Sie nicht 100er mit ähnlich aussehenden Methoden erstellen müssen.

Answer 2

Ich habe etwas für Sie gegraben.
Ich habe gefunden this stackexchange question geht darüber, wie alle möglichen Kombinationen für eine bestimmte Reihe von Zeichen zu erstellen. Damit können Sie alle möglichen Kombinationen von + zu erzeugen, -, /, * durch die Methode in der

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

Frage beschrieben ist und es mit so etwas wie

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

Nach (oder stattdessen Aufruf of) Drucken der neuen Kombination (System.out.println(curr);) Sie können eine Methode zur Interpretation der Ausgabe aufrufen.
Sie können von etwas ähnlich diesem stackoverflow simple calculator example ausgehen.
Zum Beispiel können Sie so etwas wie haben:

if(curr.charAt(0) == '+'){ 
//add the first and second number 
} 

ich denke, das sollte ausreichen, um Sie zu gehen.

EDIT
Hatte Zeit auf meinen Händen und wollte dieses beenden, da ich es interessant fand. Hier gehst du. Das funktioniert genau so, wie Sie es brauchen.

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

Um es interessant zu machen, habe ich Zufallszahlen verwendet. Nicht sicher, wie du deine Zahleneingabe erhältst. Eine Sache zu beachten ist, dass Dezimalstellen in Division fallen, wenn Sie mit der Ganzzahl umgehen. Also etwas wie 12/64 = 0 oder 11/5 = 2.
Hier ist ein Beispiel für die Ausgabe:

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) 

34 Minuten dauerte, den Lauf durch die wirklich schwierig diejenigen wie /// und *** 100 aufgrund der zufälligen ganzen Zahl Kappe abzuschließen. Außerdem habe ich mich nicht darum gekümmert, das so sauber/effizient wie möglich zu machen und habe nicht auf Objektlecks/unnötige Objekterzeugung geachtet. Das liegt an dir :)
Prost!