层楼高一个数学游戏在Java中 [英] Buiding a math game in Java
问题描述
我建立一个数学游戏，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
。工作流程：你的程序读取用户，并输出一个公式，导致24.算法应该列举的4个数字，所有可能的组合和所有可能的公式所有可能的订单4个数字
。这使我对数字A，B，C，D的24排列64排列运营商 + - / * 。我如何得出这一结论是4 ^ 3 4运营商只有3补点的公式所示。除了今天我有麻烦写的评价方法，也占方程parentases。
下面是我的code：
公共静态无效的评估（CBAR [] []操作，双击[] []操作数）
{
/ *
这是一个让我我怎么核算的部分
为parentases，并把所有这些EX pressions togather到
实际上形成和公式。
* /
}
这个问题presents一些挑战。下面我的解决办法是约两几百行代码。这可能是一个小长于分配要求，因为我把它推广到任意数量的条款。我鼓励你学习的算法，并编写自己的解决方案。
我们必须克服的主要障碍有以下几种。
-
我们如何产生排列不重复？
-
我们如何构建和评估算术前pressions？
-
我们如何转换前pressions成唯一的字符串？
有许多方法来产生置换。我选择了一个递归的方法，因为它很容易理解。主要并发症是术语可以被重复，这意味着有可能比 4少！ = 4 * 3 * 2 * 1 排列。例如，如果该条款是 1 1 1 2 ，只有四种排列。
要避免重复排列，我们首先排序项。递归函数查找所有重复项地方从左至右没有回溯。例如，一旦第一个 1 已被放置在阵列中，所有剩余的 1 术语被放置到正确的它。但是，当我们得到一个 2 来看，我们可以回到数组的开始。
要建立算术EX pressions，我们用另一种递归函数。此功能着眼于两个术语的排列的间的各个位置，数组分成一个段的位置的左侧和段到右侧。它使一对递归调用建立前pressions用于左和右段。最后，加入产生前儿童pressions与四个算术运算符。基础案例是当阵列的大小为1，因此它不能被分割。这将导致没有运营商和没有子女，只有一个值的节点。
通过执行算术评估前pressions双值是有问题的，由于浮点除法的IM precision。例如， 1.0 / 3 = 0.33333 ... ，而 3 * 0.33333 ... = 0.99999 ... 。这使得肯定知道这很难说 1/3 * 3 = 1 当你使用双值。为了避免这些困难，我定义了一个分数类。它执行对馏分算术运算和总是由最大公约数的装置简化了结果。除以零不会导致错误消息。相反，我们保存分数0/0。
最后一块拼图是转换前pressions成字符串。我们要规范和标准化的字符串，让我们不要重复自己不必要的。例如，我们不希望显示 1 +（1 +（1 + 2））和（（1 + 1）+ 1） +2 ，因为这些在本质上是相同的前pression。相反，显示出所有可能的parenthesizations的，我们只是想显示 1 + 1 + 1 + 2 。
我们可以通过只在必要时加入括号实现这一目标。要机智，括号是必要的，如果具有较高优先级的运算符（乘除）一个节点是一个低优先级的运算符（加或减）一个节点的父节点。按优先级我的意思是运营商precedence，也被称为操作的顺序。较高优先级的运营商绑定比低的人越紧。因此，如果父节点的优先级高于子节点的操作者，它必须圆括号子。为了确保我们最终唯一的字符串，我们要检查他们对一个哈希集合将它们添加到结果列表中。
下面的程序， Equation.java ，接受命令行上的用户输入。游戏的参数都在公式类的第一道防线。您可以修改这些建前pressions更多的方面，更大的方面，不同的目标值。
进口的java.lang。*;
导入的java.util。*;
进口java.io. *;
类分数{//避免了浮点麻烦。
INT NUM，DENOM;
静态INT GCD（INT A，INT B）{//最大公约数。
状态，（b！= 0）{
INT T = B：
B = A％B;
A =吨;
}
返回;
}
分数（INT NUM，诠释DENOM）{//使一个简化的部分。
如果（DENOM == 0）{//除零的结果
this.num = this.denom = 0; //分数0/0。我们不
}其他{//抛出一个错误。
INT X = Fraction.gcd（NUM，DENOM）;
this.num = NUM / X;
this.denom = DENOM / X;
}
}
分数加（部分除外）{
返回新的分数（this.num * other.denom + other.num * this.denom，
this.denom * other.denom）;
}
减去分数（分数等）{
返回this.plus（新分数（-other.num，other.denom））;
}
分数次（部分除外）{
返回新的分数（this.num * other.num，this.denom * other.denom）;
}
分数除法（分数等）{
返回新的分数（this.num * other.denom，this.denom * other.num）;
}
公共字符串的toString（）{//省略了分母如果可能的话。
如果（DENOM == 1）{
回归+ NUM;
}
返回NUM +/+ DENOM;
}
}
其中的值类防爆pression {//树节点，
分数值; //任选地操纵其
字符串操作人员; //操作数。
防爆pression左，右;
静态INT级（字符串运算符）{
如果（operator.compareTo（+）== 0 || operator.compareTo（ - ）== 0）{
返回0; //返回评价的优先权，
} //也被称为运营商precedence
返回1; //或操作的顺序。
}
防爆pression（INT X）{//简单的情况：一个整数。
值=新分数（X，1）;
}
防爆pression（出pression离开，字符串操作人员，防爆pression右）{
如果（==操作符+）{
值= left.value.plus（right.value）;
}否则，如果（==操作符 - ）{
值= left.value.minus（right.value）;
}否则，如果（==操作符*）{
值= left.value.times（right.value）;
}否则，如果（==操作符/）{
值= left.value.divide（right.value）;
}
this.operator =运算符;
this.left =左;
this.right =权利;
}
公共字符串的toString（）{//返回一个标准化的前pression，
如果（运营商== NULL）{//插入括号，只有在
返回value.toString（）; //必须避免含糊不清。
}
INT级=前pression.level（运营商）;
字符串= left.toString（），AOP = left.operator，
B = right.toString（），BOP = right.operator;
如果（AOP = NULL和放大器;！＆安培;防爆pression.level（AOP）＆LT;Ⅲ级）{
一个=（+ A +）;只有当//圆括号孩子了
} //优先级比家长的下部。
如果（BOP = NULL和放大器;！＆安培;防爆pression.level（BOP）＆LT;Ⅲ级）{
B =（+ B +）;
}
返回一个++运营商++ B;
}
}
公共类方程{
//这些是游戏的参数。
静态INT需求= 4，分= 1，最大值= 9，目标= 24;
INT []方面，置换;
布尔[]使用;
ArrayList的＆LT;字符串＆GT;胜=新的ArrayList＆LT;字符串＆GT;（）;
设置＆LT;字符串＆GT;万迪诺=新的HashSet＆LT;字符串＆GT;（）;
串[]运营= {+， - ，*，/};
//递归向上突破的条件分为左右
//部分，与四大运营商之一，加入他们。
ArrayList的＆LT;防爆pression＆GT;使（INT左，右诠释）{
ArrayList的＆LT;防爆pression＆GT;结果=新的ArrayList＆LT;防爆pression＆GT;（）;
如果（左+ 1 ==右）{
result.add（新前pression（排列[左]））;
} 其他 {
的for（int i =左+ 1; I＆LT;权利; ++ I）{
ArrayList的＆LT;防爆pression＆GT; leftSide =彩妆（左一）;
ArrayList的＆LT;防爆pression＆GT; rightSide =做（我，对不对）;
对于（INT J = 0; J＆LT; leftSide.size（）; ++ j）条{
对于（INT K = 0; K＆LT; rightSide.size（）; ++ K）{
为（中间体p值= 0; P＆所述; operators.length ++ p）的{
result.add（新前pression（leftSide.get（J）
算[P]，
rightSide.get（k））的）;
}
}
}
}
}
返回结果;
}
//给定条件的一个排列，构成所有可能的算术
// EX pressions。检查结果并保存那些
//具有目标值。
制定无效（）{
ArrayList的＆LT;防爆pression＆GT; EX pressions =令（0，terms.length）;
的for（int i = 0; I＆LT;除权pressions.size（）; ++ I）{
防爆pression EX pression = EX pressions.get（我）;
分数值= EX pression.value;
如果（value.num ==靶安培;＆安培; value.denom == 1）{
字符串s = EX pressions.get（I）的ToString（）;
如果（！winSet.contains（S））{//检查一个前pression看
wins.add（多个）; //具有相同的归一化的串
winSet.add（多个）; //重新presentation先前保存。
}
}
}
}
// Permutes条款不重复。要求条款
//进行排序。注意，我们查了下学期，如果看到
// 一样的。如果是，我们不返回到开始
//数组中。
无效置换（INT termIx，INT POS）{
如果（POS == terms.length）{
返回;
}
如果（！使用[POS]）{
排列[POS] =术语[termIx]
如果（termIx + 1 == terms.length）{
制定（）;
} 其他 {
二手[POS] =真;
如果（术语[termIx + 1] ==术语[termIx]）{
置换（termIx + 1，POS + 1）;
} 其他 {
置换（termIx + 1，0）;
}
二手[POS] = FALSE;
}
}
置换（termIx，POS + 1）;
}
//开始置换过程，计算最终结果，显示它们。
解决无效（INT []术语）{
this.terms =条件; //我们必须条件，以便整理
Arrays.sort（条款）; //的置换（）功能工作。
置换=新INT [terms.length]
二手=新的布尔[terms.length]
置换（0，0）;
如果（wins.size（）== 0）{
的System.out.println（有没有可行的EX pressions。）;
}否则如果（wins.size（）== 1）{
的System.out.println（有一个可行的EX pression：）;
} 其他 {
的System.out.println（有+ wins.size（）+可行EX pressions：）;
}
的for（int i = 0; I＆LT; wins.size（）; ++ I）{
的System.out.println（wins.get（ⅰ）+=+靶）;
}
}
//获取命令行用户的输入，并检查它的有效性。
公共静态无效的主要（字串[] args）{
如果（args.length！=需求）{
的System.out.println（必须指定+需要+数字）;
返回;
}
INT位[] =新的INT [需要]
的for（int i = 0; I＆LT;需要; ++ I）{
尝试 {
数字[I] =的Integer.parseInt（参数[I]）;
}赶上（NumberFormatException异常E）{
的System.out.println（\+的args [I] +\不是一个整数）;
返回;
}
如果（数字[1] - ;分钟||位数[Ⅰ]≥最大）{
的System.out.println（位[我] +的范围[外+
分+，+ MAX +]）;
返回;
}
}
（新公式（））解决（数字）。
}
}
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.
For example, for the numbers 4,7,8,8, a possible solution is: (7-(8/8))*4=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*(7+4) = 24
(2+2)*7-4 = 24
(2*2)*7-4 = 24
2*(2*7)-4 = 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.
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.
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.
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.
Here is my code:
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?
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.
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.
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.
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.
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.
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屋！
