Построение математической игры в Java

Ответ 1

Эта проблема представляет несколько проблем. Мое решение ниже - около двухсот строк. Это, вероятно, немного дольше, чем требуется назначение, потому что я обобщил его на любое количество терминов. Я рекомендую вам изучить алгоритм и написать собственное решение.

Основными препятствиями, которые мы должны преодолеть, являются следующие.

• Как мы создаем перестановки без повторения?

• Как мы можем строить и оценивать арифметические выражения?

• Как мы преобразуем выражения в уникальные строки?

Существует много способов генерации перестановок. Я выбрал рекурсивный подход, потому что это легко понять. Основное усложнение заключается в том, что термины могут быть повторены, что означает, что может быть меньше перестановок 4! = 4*3*2*1. Например, если термины 1 1 1 2, существует только четыре перестановки.

Чтобы избежать дублирования подстановок, начнем с сортировки терминов. Рекурсивная функция находит места для всех повторяющихся терминов слева направо без обратного слежения. Например, как только первый 1 был помещен в массив, все остальные 1 термины помещаются справа от него. Но когда мы перейдем к термину 2, мы можем вернуться к началу массива.

Чтобы построить арифметические выражения, мы используем другую рекурсивную функцию. Эта функция просматривает каждую позицию между двумя терминами перестановки, разбивая массив на сегмент слева от позиции и сегмент справа. Он создает пару рекурсивных вызовов для построения выражений для левого и правого сегментов. Наконец, он объединяет результирующие дочерние выражения с каждым из четырех арифметических операторов. Основной случай - когда массив имеет размер один, поэтому его нельзя разделить. Это приводит к node без оператора и без детей, только значение.

Оценка выражений путем выполнения арифметики по значениям double была бы проблематичной из-за неточности деления с плавающей запятой. Например, 1.0 / 3 = 0.33333..., но 3 * 0.33333... = 0.99999.... Это затрудняет уверенность в том, что 1 / 3 * 3 = 1, когда вы используете значения double. Чтобы избежать этих трудностей, я определил класс Fraction. Он выполняет арифметические операции над дроби и всегда упрощает результат с помощью наибольшего общего делителя. Деление на ноль не приводит к сообщению об ошибке. Вместо этого мы сохраняем долю 0/0.

Последний фрагмент головоломки - преобразование выражений в строки. Мы хотим сделать канонические или нормированные строки, чтобы мы не повторяли себя бесполезно. Например, мы не хотим отображать 1 + (1 + (1 + 2)) и ((1 + 1) + 1) + 2, так как это по существу то же самое выражение. Вместо того, чтобы показывать все возможные скобки, мы просто хотим отобразить 1 + 1 + 1 + 2.

Мы можем добиться этого, добавив круглые скобки только при необходимости. Для этого нужны круглые скобки, если node с оператором с более высоким приоритетом (умножение или деление) является родительским элементом node с оператором с более низким приоритетом (сложение или вычитание). По приоритету я имею в виду приоритет оператора, также известный как порядок операций. Операторы с более высоким приоритетом связывают более плотно, чем нижние. Поэтому, если родительский node имеет более высокий приоритет, чем оператор дочернего элемента node, необходимо скопировать его в скобки. Чтобы убедиться, что мы закончили с уникальными строками, мы проверяем их против хэш-набора, прежде чем добавлять их в список результатов.

Следующая программа, Equation.java, принимает ввод пользователя в командной строке. Параметры игры находятся в первой строке класса Equation. Вы можете изменить их, чтобы создавать выражения с большим количеством терминов, более крупных терминов и разных целевых значений.

import java.lang.*;
import java.util.*;
import java.io.*;

class Fraction {                  // Avoids floating-point trouble.
  int num, denom;
  static int gcd(int a, int b) {  // Greatest common divisor.
    while (b != 0) {
      int t = b;
      b = a % b;
      a = t;
    }
    return a;
  }
  Fraction(int num, int denom) {  // Makes a simplified fraction.
    if (denom == 0) {             // Division by zero results in
      this.num = this.denom = 0;  //  the fraction 0/0. We do not
    } else {                      //  throw an error.
      int x = Fraction.gcd(num, denom);
      this.num = num / x;
      this.denom = denom / x;     
    }
  }
  Fraction plus(Fraction other) {
    return new Fraction(this.num * other.denom + other.num * this.denom,
        this.denom * other.denom);
  }
  Fraction minus(Fraction other) {
    return this.plus(new Fraction(-other.num, other.denom));
  }
  Fraction times(Fraction other) {
    return new Fraction(this.num * other.num, this.denom * other.denom);
  }
  Fraction divide(Fraction other) {
    return new Fraction(this.num * other.denom, this.denom * other.num);
  }
  public String toString() {      // Omits the denominator if possible.
    if (denom == 1) {
      return ""+num;
    }
    return num+"/"+denom;
  }
}

class Expression {                // A tree node containing a value and
  Fraction value;                 //  optionally an operator and its
  String operator;                //  operands.
  Expression left, right;
  static int level(String operator) {
    if (operator.compareTo("+") == 0 || operator.compareTo("-") == 0) {
      return 0;                   // Returns the priority of evaluation,
    }                             //  also known as operator precedence
    return 1;                     //  or the order of operations.
  }
  Expression(int x) {             // Simplest case: a whole number.
    value = new Fraction(x, 1);
  }
  Expression(Expression left, String operator, Expression right) {
    if (operator == "+") {
      value = left.value.plus(right.value);
    } else if (operator == "-") {
      value = left.value.minus(right.value);
    } else if (operator == "*") {
      value = left.value.times(right.value);
    } else if (operator == "/") {
      value = left.value.divide(right.value);
    }
    this.operator = operator;
    this.left = left;
    this.right = right;
  }
  public String toString() {      // Returns a normalized expression,
    if (operator == null) {       //  inserting parentheses only where
      return value.toString();    //  necessary to avoid ambiguity.
    }
    int level = Expression.level(operator);
    String a = left.toString(), aOp = left.operator,
           b = right.toString(), bOp = right.operator;
    if (aOp != null && Expression.level(aOp) < level) {
      a = "("+a+")";              // Parenthesize the child only if its
    }                             //  priority is lower than the parent's.
    if (bOp != null && Expression.level(bOp) < level) {
      b = "("+b+")";
    }
    return a + " " + operator + " " + b;
  }
}

public class Equation {

  // These are the parameters of the game.
  static int need = 4, min = 1, max = 9, target = 24;

  int[] terms, permutation;
  boolean[] used;
  ArrayList<String> wins = new ArrayList<String>();
  Set<String> winSet = new HashSet<String>();
  String[] operators = {"+", "-", "*", "/"};

  // Recursively break up the terms into left and right
  //  portions, joining them with one of the four operators.
  ArrayList<Expression> make(int left, int right) {
    ArrayList<Expression> result = new ArrayList<Expression>();
    if (left+1 == right) {
      result.add(new Expression(permutation[left]));
    } else {
      for (int i = left+1; i < right; ++i) {
        ArrayList<Expression> leftSide = make(left, i);
        ArrayList<Expression> rightSide = make(i, right);
        for (int j = 0; j < leftSide.size(); ++j) {
          for (int k = 0; k < rightSide.size(); ++k) {
            for (int p = 0; p < operators.length; ++p) {
              result.add(new Expression(leftSide.get(j),
                    operators[p],
                    rightSide.get(k)));
            }
          }
        }
      }
    }
    return result;
  }

  // Given a permutation of terms, form all possible arithmetic
  //  expressions. Inspect the results and save those that
  //  have the target value.
  void formulate() {
    ArrayList<Expression> expressions = make(0, terms.length);
    for (int i = 0; i < expressions.size(); ++i) {
      Expression expression = expressions.get(i);
      Fraction value = expression.value;
      if (value.num == target && value.denom == 1) {
        String s = expressions.get(i).toString();
        if (!winSet.contains(s)) {// Check to see if an expression
          wins.add(s);            //  with the same normalized string
          winSet.add(s);          //  representation was saved earlier.
        }
      }
    }
  }

  // Permutes terms without duplication. Requires the terms to
  //  be sorted. Notice how we check the next term to see if
  //  it the same. If it is, we don't return to the beginning
  //  of the array.
  void permute(int termIx, int pos) {
    if (pos == terms.length) {
      return;
    }
    if (!used[pos]) {
      permutation[pos] = terms[termIx];
      if (termIx+1 == terms.length) {
        formulate();
      } else {
        used[pos] = true;
        if (terms[termIx+1] == terms[termIx]) {
          permute(termIx+1, pos+1);
        } else {
          permute(termIx+1, 0);
        }
        used[pos] = false;
      }
    }
    permute(termIx, pos+1);
  }

  // Start the permutation process, count the end results, display them.
  void solve(int[] terms) {
    this.terms = terms;           // We must sort the terms in order for
    Arrays.sort(terms);           //  the permute() function to work.
    permutation = new int[terms.length];
    used = new boolean[terms.length];
    permute(0, 0);
    if (wins.size() == 0) {
      System.out.println("There are no feasible expressions.");
    } else if (wins.size() == 1) {
      System.out.println("There is one feasible expression:");
    } else {
      System.out.println("There are "+wins.size()+" feasible expressions:");
    }
    for (int i = 0; i < wins.size(); ++i) {
      System.out.println(wins.get(i) + " = " + target);
    }
  }

  // Get user input from the command line and check its validity.
  public static void main(String[] args) {
    if (args.length != need) {
      System.out.println("must specify "+need+" digits");
      return;
    }
    int digits[] = new int[need];
    for (int i = 0; i < need; ++i) {
      try {
        digits[i] = Integer.parseInt(args[i]);
      } catch (NumberFormatException e) {
        System.out.println("\""+args[i]+"\" is not an integer");
        return;
      }
      if (digits[i] < min || digits[i] > max) {
        System.out.println(digits[i]+" is outside the range ["+
            min+", "+max+"]");
        return;
      }
    }
    (new Equation()).solve(digits);
  }
}

Ответ 2

Я бы рекомендовал вам использовать древовидную структуру для хранения уравнения, то есть синтаксического дерева, в котором корень представляет и оператор имеет два дочерних элемента, представляющих операнды и т.д. рекурсивно. Вероятно, вы получили бы более чистый код, делающий это так, потому что тогда вам не нужно будет создавать комбинации операндов "вручную", но вы можете сделать код, который выбирает каждый операнд из одномерного char [] operands = new char [] {'+', '-', '*', '/'}.

Если вы не хотите использовать синтаксическое дерево или считаете, что это не обязательно для вашего случая использования, вы всегда можете попытаться найти другой способ заставить код выбирать операнды из одномерного массива и хранить их в различная структура данных. Но я бы особенно избегал писать все комбинации, как вы делаете. Это не очень просто поддерживать.

Ответ 3

Я установил аналогичную головоломку с помощью кода ниже.

public static boolean game24Points(int[] operands) {
    ScriptEngineManager sem = new ScriptEngineManager();
    ScriptEngine engine = sem.getEngineByName("javascript");

    char[] operations = new char[] { '+', '-', '*', '/' };
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
                try {
                    String exp = "" + operands[0] + operations[i] + operands[1] + operations[j]
                            + operands[2] + operations[k] + operands[3];
                    String res = engine.eval(exp).toString();
                    if (Double.valueOf(res).intValue() == 24) {
                        System.out.println(exp);
                        return true;
                    }
                } catch (ScriptException e) {
                    return false;
                }
            }
        }
    }
    return false;
}

Вот тестовые файлы

public void testCase01() {
    int[] operands = { 7, 2, 1, 10 };
    assertEquals(true, Demo.game24Points(operands));
}

public void testCase02() {
    int[] operands = { 1, 2, 3, 4 };
    assertEquals(true, Demo.game24Points(operands));
}

public void testCase03() {
    int[] operands1 = { 5, 7, 12, 12 };
    assertEquals(true, Demo.game24Points(operands1));
    int[] operands = { 10, 3, 3, 23 };
    assertEquals(true, Demo.game24Points(operands));
}