이 문제는 몇 가지 문제점을 나타냅니다. 내 솔루션은 약 200 줄 정도입니다. 내가 원하는 수만큼 일반화했기 때문에 과제가 요구하는 것보다 조금 더 길다. 알고리즘을 공부하고 나만의 솔루션을 작성하는 것이 좋습니다.
우리가 극복해야하는 주요 장애물은 다음과 같습니다.
순열을 생성하는 데는 여러 가지 방법이 있습니다. 이해하기 쉽기 때문에 재귀 적 접근 방식을 선택했습니다. 주된 복잡성은 용어가 반복 될 수 있다는 것입니다. 즉, 4! = 4*3*2*1 순열보다 적을 수 있습니다. 예를 들어, 용어가 1 1 1 2 인 경우, 단지 4 개의 순열이 있습니다.
순열 복제를 피하기 위해 용어를 정렬하여 시작합니다. 재귀 함수는 역 추적없이 왼쪽에서 오른쪽으로 모든 중복 용어에 대한 위치를 찾습니다. 예를 들어 첫 번째 1이 배열에 배치되면 나머지 모든 1 항이 오른쪽에 배치됩니다. 그러나 2 용어가 생기면 배열의 처음으로 돌아갈 수 있습니다.
산술 표현식을 작성하기 위해 다른 재귀 함수를 사용합니다. 이 함수는 순열의 두 용어 사이의 각 위치를 보면서 배열을 위치의 왼쪽 세그먼트와 오른쪽 세그먼트로 나눕니다. 왼쪽 및 오른쪽 세그먼트에 대한 식을 작성하기 위해 한 쌍의 재귀 호출을 만듭니다. 마지막으로 결과로 나오는 자식 표현식을 네 개의 산술 연산자로 결합합니다. 기본 경우는 배열의 크기가 1이므로 분할 할 수 없습니다. 결과적으로 연산자가없고 자식이없고 값만있는 노드가됩니다.
double 값에 대한 산술 연산을 통해 표현식을 평가하는 것은 부동 소수점 나누기의 부정확성으로 인해 문제가 될 수 있습니다. 예를 들어 1.0/3 = 0.33333...이지만 3 * 0.33333... = 0.99999...입니다. 따라서 double 값을 사용할 때 1/3 * 3 = 1을 확실히 알기가 어렵습니다. 이러한 어려움을 피하기 위해 Fraction 클래스를 정의했습니다. 분수에 대한 산술 연산을 수행하고 항상 가장 큰 제수로 결과를 단순화합니다. 0으로 나누기해도 오류 메시지가 발생하지 않습니다. 대신에 분수 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);
}
}
빠른 질문입니까? 이것이 요구되지 않는다면 이것은 감소 될 수 있고 괄호는 상당히 쉽게 처리 될 수 있습니다. – Obicere
가능한 [수학 24 게임 자바] (http://stackoverflow.com/questions/27118479/math-twenty-four-game-java) –
그것의 숙제? –