用Java构建数学游戏 [英] Building a math game in Java

问题描述

我正在为java构建一个数学游戏，根据我的任务细节，我被困在这个部分。规则很简单：你必须只使用每个数字一次，而只使用从用户那里读取的4个数字来找到一个方程式来获得24。

I am building a math game for java and I'm stuck at this part as per the details of my assignment. The rules are simple: you have to use each number only once and only the 4 numbers that were read from the user to find one equation to obtain 24.

例如，对于数字4,7,8,8，可能的解决方案是：（7-（8/8））* 4 = 24.

For example, for the numbers 4,7,8,8, a possible solution is: (7-(8/8))*4=24.

大多数4位数组可以在导致24的多个方程中使用。例如，输入2,2,4,7可以多种方式使用以获得24：

Most sets of 4 digits can be used in multiple equations that result in 24. For example the input 2,2,4,7 can be used in multiple ways to obtain 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

（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的等式。

There are also combinations of 4 numbers that cannot result into any equation equal with 24. For example 1,1,1,1. In this case, your program should return that there is no possible equation equal with 24.

注意：虽然我们将在1到9之间输入4个整数，但我们将使用双精度计算所有操作。例如，数字3,3,8,8可以组合成公式：8 /（3-8 / 3）= 24.

Note: Although we will enter 4 integers between 1 and 9, we will use doubles to compute all the operations. For example, the numbers 3,3,8,8 can be combined into the formula: 8/(3-8/3) = 24.

工作流程：您的程序应读取用户的4个数字并输出一个导致24的公式。算法应列举4个数字的所有可能顺序，所有可能的组合和所有可能的公式。

Workflow: Your program should read the 4 numbers from the user and output a formula that results in 24. The algorithm should enumerate all the possible orders of 4 numbers, all the possible combinations and all the possible formulas.

这导致我对数字a，b，c，d和运算符的64种排列的24种排列 + - / * 。我如何得出这个结论是4 ^ 3 4个算子只有3个填充点在等式中。除了今天我在编写评估方法时遇到困难，并且还在方程中考虑了父类。

Which leads me to 24 permutations of Numbers a,b,c,d and 64 permutations of operators +-/*. How I came to this conclusion was 4^3 4 operators only 3 fill spots in the equation. Except today I am having trouble writing the evaluation method and also accounting for parentases in the equations.

这是我的代码：

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.
    */
}

推荐答案

这个问题带来了一些挑战。我的解决方案大约有两百行。它可能比赋值所需的时间长一点，因为我将它推广到任意数量的术语。我鼓励你研究算法并编写自己的解决方案。

This problem presents several challenges. My solution below is about two hundred lines long. It's probably a little longer than the assignment requires because I generalized it to any number of terms. I encourage you to study the algorithm and write your own solution.

我们必须克服的主要障碍如下。

The main obstacles we must overcome are the following.

• 我们如何在不重复的情况下生成排列？

• How do we generate permutations without repetition?

我们如何构建和评估算术表达式？

How do we build and evaluate arithmetic expressions?

我们如何将表达式转换为唯一字符串？

How do we convert the expressions into unique strings?

有很多方法可以生成排列。我选择了一种递归方法，因为它很容易理解。主要的复杂因素是术语可以重复，这意味着可能会少于 4！ = 4 * 3 * 2 * 1 排列。例如，如果条款 1 1 1 2 ，则只有四种排列。

There are many ways to generate permutations. I chose a recursive approach because it's easy to understand. The main complication is that terms can be repeated, which means that there may be fewer than 4! = 4*3*2*1 permutations. For example, if the terms are 1 1 1 2, there are only four permutations.

避免重复排列，我们首先对术语进行排序。递归函数从左到右查找所有重复项的位置，而不进行回溯。例如，一旦第一个 1 被放入数组中，所有剩余的 1 条款将被放置在右侧它但是当我们得到 2 术语时，我们可以回到数组的开头。

To avoid duplicating permutations, we start by sorting the terms. The recursive function finds places for all duplicate terms from left to right without backtracking. For example, once the first 1 has been placed in the array, all the remaining 1 terms are placed to the right of it. But when we get to a 2 term, we can go back to the beginning of the array.

要构建算术表达式，我们使用另一个递归函数。此函数查看排列的两个项之间的每个位置，将数组拆分为位置左侧的段和右侧的段。它进行一对递归调用以构建左右段的表达式。最后，它将结果子表达式与四个算术运算符中的每一个连接起来。基本情况是当数组大小为1时，因此无法拆分。这导致节点没有运算符且没有子节点，只有一个值。

To build arithmetic expressions, we use another recursive function. This function looks at each position between two terms of the permutation, splitting the array into a segment to the left of the position and a segment to the right. It makes a pair of recursive calls to build expressions for the left and right segments. Finally, it joins the resulting child expressions with each of the four arithmetic operators. The base case is when the array is of size one, so it can't be split. This results in a node with no operator and no children, only a value.

通过对 double 由于浮点除法不精确，值会有问题。例如， 1.0 / 3 = 0.33333 ... ，但 3 * 0.33333 ... = 0.99999 ... 。这使得当您使用 double 值时，很难确定 1/3 * 3 = 1 。为了避免这些困难，我定义了一个 Fraction 类。它对分数执行算术运算，并始终通过最大公约数来简化结果。除以零不会导致错误消息。相反，我们存储分数0/0。

Evaluating the expressions by performing arithmetic on double values would be problematic due to the imprecision of floating-point division. For example, 1.0 / 3 = 0.33333..., but 3 * 0.33333... = 0.99999.... This makes it difficult to know for sure that 1 / 3 * 3 = 1 when you're using double values. To avoid these difficulties, I defined a Fraction class. It performs arithmetic operations on fractions and always simplifies the result by means of the greatest common divisor. Division by zero does not result in an error message. Instead, we store the fraction 0/0.

最后一个难题是将表达式转换为字符串。我们想要制作规范或规范化的字符串，这样我们就不会不必要地重复自己。例如，我们不想显示 1 +（1 +（1 + 2））和（（1 + 1）+ 1） + 2 ，因为这些表达式基本相同。我们只想显示 1 + 1 + 1 + 2 ，而不是显示所有可能的括号。

The final piece of the puzzle is converting expressions into strings. We want to make canonical or normalized strings so that we don't repeat ourselves needlessly. For example, we don't want to display 1 + (1 + (1 + 2)) and ((1 + 1) + 1) + 2, since these are essentially the same expression. Instead of showing all possible parenthesizations, we just want to display 1 + 1 + 1 + 2.

我们可以通过仅在必要时添加括号来实现此目的。也就是说，如果具有较高优先级运算符（乘法或除法）的节点是具有较低优先级运算符（加法或减法）的节点的父节点，则必须使用括号。优先级是指运算符优先级，也称为运算顺序。优先级较高的运算符比较低优先级的运算符绑定更紧密。因此，如果父节点的优先级高于子节点的运算符，则必须为子节点括号。为了确保我们最终得到唯一的字符串，我们会在将它们添加到结果列表之前对它们进行检查。

We can achieve this by adding parentheses only when necessary. To wit, parentheses are necessary if a node with a higher-priority operator (multiplication or division) is the parent of a node with a lower-priority operator (addition or subtraction). By priority I mean operator precedence, also known as the order of operations. The higher-priority operators bind more tightly than the lower ones. So if a parent node has higher priority than the operator of a child node, it is necessary to parenthesize the child. To ensure that we end up with unique strings, we check them against a hash set before adding them to the result list.

以下程序， Equation.java ，接受命令行上的用户输入。游戏的参数位于 Equation 类的第一行。您可以修改这些来构建包含更多术语，更大术语和不同目标值的表达式。

The following program, Equation.java, accepts user input on the command line. The parameters of the game are on the first line of the Equation class. You can modify these to build expressions with more terms, bigger terms, and different target values.

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

这篇关于用Java构建数学游戏的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！