Questo problema presenta diverse sfide. La mia soluzione di seguito è lunga circa duecento righe. Probabilmente è un po 'più lungo di quanto richiede l'assegnazione perché l'ho generalizzato a un numero qualsiasi di termini. Ti incoraggio a studiare l'algoritmo e scrivere la tua soluzione.
I principali ostacoli che dobbiamo superare sono i seguenti.
Come si generano permutazioni senza ripetizione?
Come si costruiscono e si valutano le espressioni aritmetiche?
Come convertiamo le espressioni in stringhe univoche?
Ci sono molti modi per generare permutazioni. Ho scelto un approccio ricorsivo perché è facile da capire. La principale complicazione è che i termini possono essere ripetuti, il che significa che potrebbero esserci meno di 4! = 4*3*2*1 permutazioni. Ad esempio, se i termini sono 1 1 1 2, ci sono solo quattro permutazioni.
Per evitare la duplicazione delle permutazioni, iniziamo ordinando i termini. La funzione ricorsiva trova i posti per tutti i termini duplicati da sinistra a destra senza retrocedere. Ad esempio, una volta che il primo 1 è stato inserito nell'array, tutti i restanti termini 1 vengono posizionati a destra di esso. Ma quando arriviamo a un termine 2, possiamo tornare all'inizio dell'array.
Per creare espressioni aritmetiche, viene utilizzata un'altra funzione ricorsiva. Questa funzione esamina ogni posizione tra due termini della permutazione, suddividendo l'array in un segmento a sinistra della posizione e un segmento a destra. Effettua una coppia di chiamate ricorsive per creare espressioni per i segmenti sinistro e destro. Infine, unisce le espressioni figlio risultanti con ciascuno dei quattro operatori aritmetici. Il caso base è quando l'array è di taglia 1, quindi non può essere diviso. Ciò si traduce in un nodo senza operatore e senza figli, solo un valore.
La valutazione delle espressioni eseguendo l'aritmetica sui valori double sarebbe problematica a causa dell'imprecisione della divisione in virgola mobile. Ad esempio, 1.0/3 = 0.33333..., ma 3 * 0.33333... = 0.99999.... Ciò rende difficile sapere con certezza che 1/3 * 3 = 1 quando si utilizzano valori double. Per evitare queste difficoltà, ho definito una classe Fraction. Esegue operazioni aritmetiche su frazioni e semplifica sempre il risultato per mezzo del massimo comun divisore. La divisione per zero non genera un messaggio di errore. Invece, memorizziamo la frazione 0/0.
Il pezzo finale del puzzle è la conversione di espressioni in stringhe. Vogliamo creare stringhe canoniche o normalizzate in modo da non ripeterci inutilmente. Ad esempio, non vogliamo visualizzare 1 + (1 + (1 + 2)) e ((1 + 1) + 1) + 2, poiché si tratta essenzialmente della stessa espressione. Invece di mostrare tutte le possibili parentesi, vogliamo solo mostrare 1 + 1 + 1 + 2.
Possiamo ottenere questo aggiungendo parentesi solo quando necessario. Ad esempio, le parentesi sono necessarie se un nodo con un operatore con priorità più alta (moltiplicazione o divisione) è il genitore di un nodo con un operatore con priorità più bassa (addizione o sottrazione). Per priorità intendo la precedenza degli operatori, anche nota come ordine delle operazioni. Gli operatori con priorità più alta si legano più strettamente di quelli inferiori. Quindi, se un nodo genitore ha una priorità più alta rispetto all'operatore di un nodo figlio, è necessario scegliere tra parentesi il bambino. Per assicurarci di finire con stringhe univoche, le confrontiamo con un set di hash prima di aggiungerle all'elenco dei risultati.
Il seguente programma, Equation.java, accetta l'input dell'utente sulla riga di comando. I parametri del gioco sono sulla prima riga della classe Equation. Puoi modificarli per creare espressioni con più termini, termini più grandi e valori target diversi.
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);
}
}
Domanda rapida, è assolutamente necessario includere un caso 'a + b' se hai già il caso' b + a'? Se non è richiesto, questo potrebbe essere ridotto e la parentesi gestita abbastanza facilmente. – Obicere
possibile duplicato di [Math venti four game Java] (http://stackoverflow.com/questions/27118479/math-twenty-four-game-java) –
E 'un compito? –