Ответ 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);
}
}