# 一个简单的求解算法

```package wis.lacrosse;

/*
* This program tries to find an arithmetic pattern with a set
* of integers and three operators '+', '-' and '='. For
* example,
*      5 + 3 - 2 = 6
* Given a set of integers, the program tries to find at least one solution
* that satisfies the numbers. For the above example, the input is the sequence
* of numbers '5', '3', '2' and '6' in that order. The program comes up with the
* pattern that uses the numbers '5', '3' and '2' so that the result is '6'.
* Notice that there could be more than one solution for a given set of
* numbers, but the program finds at least one, if one exists.
*
* Written by: Kasi Periyasamy
* Date created: September 26, 2010.
*/

import javax.swing.*;
import java.util.*;

public class ArithmeticPattern {

public static void main(String[] args) {
java.awt.EventQueue.invokeLater(new Runnable() {
public void run() {
new ArithmeticPattern().solve();
}
});
}

/**
* This method receives a sequence of integers from input and calls another
* method to find the solution for this pattern. This method validates every
* input to make sure that it is a positive integer.
*/

public void solve() {
Vector<Integer> numbers;
Vector<Character> operators;
boolean received, found, done, terminate;
String inString;
String components[];
int i;
String regularExpressionInt = "[1-9]+";

terminate = false;
while (!terminate) {
//
// initialize variables
//

inString = "";
components = null;
numbers = new Vector<Integer>();
operators = new Vector<Character>();

//
// Get the string representing all numbers
//

inString = JOptionPane.showInputDialog(null,
" Input the sequence of positive integers that represent the pattern, separated by spaces.\\n"
+ " For example, if 5 + 3 - 2 = 6 is the ultimate expression you expect, then input\\n"
+ "       5 3 2 6\\n"
+ " in that order. Remember that the integers must be all positive.\\n"
+ " Any number that is a zero or associated with a non-numeric character will be discarded.\\n\\n"
+ " Press 'Cancel' to terminate the program.");

if (inString == null) {
terminate = true;
}

else {

components = inString.split(" ");

if (components.length < 3)
display(" There must be at least three inputs\\n", true);
else {

//
// extract individual integers from the input
//

done = false;
i = 0;
while (!done && i < components.length) {
if (!components[i].matches(regularExpressionInt)) {
display(" Input " + (i + 1) + " is not a positive integer\\n", true);
done = true;
} else {
i++;
}
}
if (!done)
}

}
}

//
// Call the 'findSolution()' method and see whether there is at
// least one solution for the
// given pattern.
//

if (numbers.size() > 0) {

found = findSolution(numbers, operators);
if (found)
printSolution(numbers, operators);
else
display(" No solution is found for the given pattern", true);

}

} // end of while (!terminate)
}

/**
* This method tries to find a solution for a given pattern. It receives an
* integer vector that contains the numbers to be manipulated and a
* character vector to fill up the operators.
*
* @param numbers
*            the integer vector containing the numbers.
* @param operators
*            the character vector for the operators; passed as empty; to be
*            filled in by this method.
*/

public boolean findSolution(Vector<Integer> numbers, Vector<Character> operators) {

int j, howmany, iter, result;
boolean success = false;

/*
* The following array will be used to store a binary pattern of a
* number.
*/

int[] binary = new int[numbers.size()];

/* Initialize the binary array to -1 */

for (j = 0; j < binary.length; j++)
binary[j] = -1;

howmany = numbers.size();

/*
* There are "howmany" integers and "howmany-1" operators. The integer
* at numbers[homany-1] is the final answer of the the pattern and the
* operator in front of that integer is '='. Therefore, we need to find
* "howmany-2" operators. There are 2 raised to the power (howmany - 2)
* possible ways of arranging the operators. Get the binary pattern for
* each of these combinations and assign '+' for 'true' and '-' for
* 'false'. Use each such combination to verify the result. When one
* matches, stop checking and report the pattern.
*/

iter = 1;
while (!success && iter <= (int) (Math.pow(2, howmany - 2))) {
result = (Integer) numbers.elementAt(0);
binary = computeBinary(iter, howmany - 2);
for (j = 0; j < howmany - 2; j++) {
if (binary[j] == 1)
result = result + (Integer) numbers.elementAt(j + 1);
if (binary[j] == 0)
result = result - (Integer) numbers.elementAt(j + 1);
}
success = result == (Integer) numbers.elementAt(howmany - 1);
iter++;
}
if (success) { // set the operators
for (j = 0; j < howmany - 2; j++) {
if (binary[j] == 1)
if (binary[j] == 0)
}
// Set the '=' operator at the end
}
return success;
}

/**
* This method computes and returns the binary pattern of a number.
*
* @param num
*            the number whose binary pattern is required.
* @param len
*            the number of binary digits required.
* @return the binary pattern.
*/

public static int[] computeBinary(int num, int len) {

int[] bin = new int[10]; // must be edited again.
int i;
for (i = 0; i < len; i++)
bin[i] = 0;
for (i = len; i < bin.length; i++)
bin[i] = -1;
i = 0;
while (num > 0) {
bin[i++] = num % 2;
num = num / 2;
}
return bin;
}

/**
* This method prints the solution.
*
* @param the
*            vector containing the numbers
* @param the
*            vector that contains the operators
*/

public void printSolution(Vector<Integer> numbers, Vector<Character> operators) {
String out = " Here is one possible solution\\n";
for (int i = 0; i < numbers.size() - 1; i++) {
out = out + " " + numbers.elementAt(i) + " " + operators.elementAt(i);
}
out = out + " " + numbers.elementAt(numbers.size() - 1) + "\\n";
display(out, false);
}

/**
* This method displays the error or informative messages.
*
* @param msg
*            the message to be displayed.
* @param what
*            the type of message - `true' indicates error message and
*            `false' indicates informative message.
*/

public void display(String msg, boolean what) {
if (what)
JOptionPane.showMessageDialog(null, " Error : " + msg + "\\n");
else
JOptionPane.showMessageDialog(null, msg + "\\n");
}
}
//该片段来自于http://outofmemory.cn
```

0人收藏

0

0