come trovare tutte le possibili soluzioni per una formula, come 100 * 7-8 * 3 + 7? (8 su 10 gatti risolve il conto alla rovescia)

Question

così divertente ho deciso di scrivere un semplice programma che può risolvere 8 gatti su 10 Fa Countdown number puzzle, il collegamento è conto alla rovescia, ma le stesse regole. quindi il mio programma passa semplicemente attraverso tutte le possibili combinazioni di AxBxCxDxExF, dove le lettere sono numeri e "x" sono +, -,/e *. ecco il codice per questo:

private void combineRecursive(int step, int[] numbers, int[] operations, int combination[]){ 
    if(step%2==0){//even steps are numbers 
     for(int i=0; i<numbers.length; i++){ 
      combination[ step] = numbers[ i]; 
      if(step==10){//last step, all 6 numbers and 5 operations are placed 
       int index = Solution.isSolutionCorrect(combination, targetSolution); 
       if(index>=0){ 
        solutionQueue.addLast(new Solution(combination, index)); 
       } 
       return; 
      } 
      combineRecursive(step+1, removeIndex(i, numbers), operations, combination); 
     } 
    }else{//odd steps are operations 
     for(int i=0; i<operations.length; i++){ 
      combination[ step] = operations[ i]; 
      combineRecursive(step+1, numbers, operations, combination); 
     } 
    } 
} 

ed ecco quello che uso per testare se la combinazione è ciò che non voglio.

public static int isSolutionCorrect(int[] combination, int targetSolution){ 
    double result = combination[0]; 
    //just a test 
    if(Arrays.equals(combination, new int[]{100,'*',7,'-',8,'*',3,'+',7,'+',50})){ 
     System.out.println("found"); 
    } 
    for(int i=1; i<combination.length; i++){ 
     if(i%2!=0){ 
      switch((char)combination[i]){ 
       case '+': result+= combination[++i];break; 
       case '-': result-= combination[++i];break; 
       case '*': result*= combination[++i];break; 
       case '/': result/= combination[++i];break; 
      } 
     } 
     if(targetSolution==result){ 
      return i; 
     } 
    }  
    return targetSolution==result?0:-1; 
} 

così nell'ultimo episodio ho trovato un problema con il mio codice. questa era la soluzione a uno dei puzzle.

(10*7)-(8*(3+7)) 

ho notato che faccio trovare questa combinazione "10 * 7-8 * 3 + 7" (due volte), ma perché cercare le soluzioni per fare l'operazione da sinistra a destra io in realtà non trovo tutto risposte. controllo solo soluzioni come questa ((((10 * 7) -8) * 3) +7). quindi, anche se ho trovato la combinazione, non ho l'ordine giusto.

quindi ora la domanda è: come posso testare tutti i possibili ordini di matematica, come (10 * 7) - (8 * (3 + 7)), (10 * 7) - ((8 * 3) +7) o 10 * (7-8) * (3 + 7)? Io però posso usare un albero di equilibrio con operazioni come nodi di bilanciamento. ma ancora non ho idea di come passare attraverso tutte le possibili combinazioni senza muoversi attorno alla formula.

(10*7)-(8*(3+7)) 
      - 
    /  \ 
    *   * 
/ \ /\ 
700 7  8 + 
       /\ 
       7 3 

(10*7)-((8*3)+7) 
      - 
    /  \ 
    *   + 
/ \ /\ 
700 7  * 7 
     /\ 
      8 3 

10*(7-8)*(3+7) 

       * 
     /   \ 
      * 
    /  \   10 
    -   + 
/ \ /\ 
7  8  3 7 

come si fa nel codice? non cercando codice risolto più di come dovrei cambiare prospettiva per risolverlo. non so perché sono perplesso.

su di me: 4 ° informatica l'anno, non è nuovo o niubbo in programmazione (mi piace credere almeno;))

Answer 1

Questo è più facile risolto con una classe dedicata che rappresenta un'espressione, e non con una matrice . Quindi puoi semplicemente enumerare tutti gli alberi possibili. Un mix di another answer that I wrote for a similar task, ed un answer that shows how to generate all binary trees dato questo:

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 

public class NumberPuzzleWithCats 
{ 
    public static void main(String[] args) 
    { 
     List<Integer> numbers = Arrays.asList(10,7,8,3,7); 
     solve(numbers); 
    } 

    private static void solve(List<Integer> numbers) 
    { 
     List<Node> nodes = new ArrayList<Node>(); 
     for (int i=0; i<numbers.size(); i++) 
     { 
      Integer number = numbers.get(i); 
      nodes.add(new Node(number)); 
     } 
     System.out.println(nodes); 
     List<Node> all = create(nodes); 
     System.out.println("Found "+all.size()+" combinations"); 


     for (Node node : all) 
     { 
      String s = node.toString(); 
      System.out.print(s); 
      if (s.equals("((10*7)-(8*(3+7)))")) 
      { 
       System.out.println(" <--- There is is :)"); 
      } 
      else 
      { 
       System.out.println(); 
      } 
     } 
    } 

    private static List<Node> create(Node n0, Node n1) 
    { 
     List<Node> nodes = new ArrayList<Node>(); 
     nodes.add(new Node(n0, '+', n1)); 
     nodes.add(new Node(n0, '*', n1)); 
     nodes.add(new Node(n0, '-', n1)); 
     nodes.add(new Node(n0, '/', n1)); 
     nodes.add(new Node(n1, '+', n0)); 
     nodes.add(new Node(n1, '*', n0)); 
     nodes.add(new Node(n1, '-', n0)); 
     nodes.add(new Node(n1, '/', n0)); 
     return nodes; 
    } 

    private static List<Node> create(List<Node> nodes) 
    { 
     if (nodes.size() == 1) 
     { 
      return nodes; 
     } 
     if (nodes.size() == 2) 
     { 
      Node n0 = nodes.get(0); 
      Node n1 = nodes.get(1); 
      return create(n0, n1); 
     } 
     List<Node> nextNodes = new ArrayList<Node>(); 
     for (int i=1; i<nodes.size()-1; i++) 
     { 
      List<Node> s0 = create(nodes.subList(0, i)); 
      List<Node> s1 = create(nodes.subList(i, nodes.size())); 
      for (Node n0 : s0) 
      { 
       for (Node n1 : s1) 
       { 
        nextNodes.addAll(create(n0, n1)); 
       } 
      } 
     } 
     return nextNodes; 
    } 

    static class Node 
    { 
     int value; 
     Node left; 
     Character op; 
     Node right; 

     Node(Node left, Character op, Node right) 
     { 
      this.left = left; 
      this.op = op; 
      this.right = right; 
     } 
     Node(Integer value) 
     { 
      this.value = value; 
     } 

     @Override 
     public String toString() 
     { 
      if (op == null) 
      { 
       return String.valueOf(value); 
      } 
      return "("+left.toString()+op+right.toString()+")"; 
     } 
    } 
} 

Si stamperà tutte le combinazioni che vengono creati, compreso quello che state cercando:

[10, 7, 8, 3, 7] 
Found 16384 combinations 
(10+(7+(8+(3+7)))) 
(10*(7+(8+(3+7)))) 
... 
((10*7)+(8*(3+7))) 
((10*7)*(8*(3+7))) 
((10*7)-(8*(3+7))) <--- There is is :) 
((10*7)/(8*(3+7))) 
((8*(3+7))+(10*7)) 
... 
((7/3)-((8/7)/10)) 
((7/3)/((8/7)/10)) 

Naturalmente, verificare se il la giusta soluzione è trovata confrontando le rappresentazioni String è ... "molto pragmatico", per dirla in questo modo, ma penso che l'approccio effettivo della generazione sia l'importante qui.

(spero che questo è davvero quello che state cercando - non ho potuto vedere il sito che si è collegato al ...)