我正在为java构建一个数学游戏,根据我的任务细节,我被困在这个部分.规则很简单:你必须只使用每个数字一次,只使用从用户读取的4个数字来找到一个方程式来获得24.
例如,对于数字4,7,8,8,可能的解决方案是:(7-(8/8))*4 = 24.
大多数4位数组可用于导致24的多个方程中.例如,输入2,2,4,7可以多种方式使用以获得24:
2 + 2*(4 + 7)= 24
2 + 2*(7 + 4)= 24
(2 + 2)*7-4 = 24
(2*2)*7-4 = 24
2*(2*7)-4 = 24
还有4个数字的组合不能导致任何等于24的等式.例如1,1,1,1.在这种情况下,您的程序应该返回没有可能等于24的等式.
注意:虽然我们将在1到9之间输入4个整数,但我们将使用双精度来计算所有操作.例如,数字3,3,8,8可以组合成公式:8 /(3-8/3)= 24.
工作流程:您的程序应该读取用户的4个数字并输出一个导致24的公式.算法应该枚举4个数字的所有可能顺序,所有可能的组合和所有可能的公式.
这导致了数字a,b,c,d和运算符的64种排列的24种排列+-/*.我如何得出这个结论是4 ^ 3 4个算子只有3个填充点在等式中.除了今天,我在编写评估方法时遇到问题,并且还要考虑方程中的父类.
这是我的代码:
public static void evaluate(cbar [][] operations , double [][] operands)
{
/*
This is the part that gets me how am I supposed to account
for parentases and bring all these expressions togather to
actually form and equation.
*/
}
这个问题带来了一些挑战.我的解决方案大约有两百行.这可能比任务需要的时间长一点,因为我将它推广到任意数量的术语.我鼓励您研究算法并编写自己的解决方案.
我们必须克服的主要障碍如下.
我们如何在不重复的情况下生成排列？
我们如何构建和评估算术表达式？
我们如何将表达式转换为唯一的字符串？
有许多方法可以生成排列.我选择了一种递归方法,因为它很容易理解.主要的复杂因素是术语可以重复,这意味着可能少于4! = 4*3*2*1排列.例如,如果条款是1 1 1 2,则只有四种排列.
为避免重复排列,我们首先对术语进行排序.递归函数从左到右查找所有重复项的位置,而不进行回溯.例如,一旦将第一个1放置在数组中,所有剩余的1术语都放在它的右侧.但是当我们达到一个2术语时,我们可以回到数组的开头.
为了构建算术表达式,我们使用另一个递归函数.此函数查看排列的两个项之间的每个位置,将数组拆分为位置左侧的段和右侧的段.它进行一对递归调用以构建左右段的表达式.最后,它将结果子表达式与四个算术运算符中的每一个连接起来.基本情况是当数组大小为1时,因此无法拆分.这导致节点没有运算符且没有子节点,只有一个值.
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.
我们可以通过仅在必要时添加括号来实现此目的.也就是说,如果具有较高优先级运算符(乘法或除法)的节点是具有较低优先级运算符(加法或减法)的节点的父节点,则必须使用括号.优先级是指运算符优先级,也称为运算顺序.优先级较高的运算符比较低优先级的运算符绑定更紧密.因此,如果父节点的优先级高于子节点的运算符,则必须为子节点括号.为了确保我们最终得到唯一的字符串,我们会在将它们添加到结果列表之前根据哈希集检查它们.
以下程序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's 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);
}
}
我建议您使用树结构来存储方程，即语法树，其中根表示并且运算符有两个子级表示操作数，依此类推。您可能会得到一个更干净的代码，因为这样您就不需要“手动”生成操作数的组合，但您可以编写一个从一维 char[] operands = 中选取每个操作数的代码新的 char[] {'+','-','*','/'} 数组。
如果您不想使用语法树或认为它对于您的用例来说没有必要，您可以随时尝试找到一种不同的方法来使代码从一维数组中选取操作数并将它们存储到不同的数据结构中。但我会特别避免像您一样编写所有组合。看起来不太容易维护。