成功：12+3+45+67-8-9 = 110
成功：12-3+4-5+6+7+89 = 110
成功：1+2+34+5+67-8+9 = 110
成功：1-2+3+45-6+78-9 = 110
成功：123+4-5-6-7-8+9 = 110
成功：123-4+5-6-7+8-9 = 110
成功：123-4-5+6+7-8-9 = 110
成功：123+4+5+67-89 = 110
成功：1+234-56-78+9 = 110
两种方法：
/**
* Copyright (C) 2012 Lear C
*/
/**
* 1 2 3 4 5 6 7 8 9 = 110
* <p/>
* 在数字间填入加号或者减号（可以不填，但不能填入其它符号）使等式成立。 <br/>
* 一种更好的方法是：<br/>
* 每一个空隙之间都有三种可能，"+", "-", ""，所以一共有3^8种可能。
*
* @author Lear
*/
public class Tester2 {
private static final char[] NUMBERS = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};
private static final String[] OPERATORS = {"+", "-", ""};
private static final int RESULT = 110; // 计算结果
public static void main(String[] args) {
sortAndCompute(0, "");
}
private static void sortAndCompute(int numIndex, String buffer) {
// 说明到最后一个字符了
if(numIndex == NUMBERS.length - 1) {
buffer += NUMBERS[numIndex];
String formula = buffer.toString();
if(sum(formula) == RESULT) {
System.out.println(formula + " = " + RESULT);
}
return;
}
for(int operIndex = 0; operIndex < OPERATORS.length; ++operIndex) {
buffer += NUMBERS[numIndex];
buffer += OPERATORS[operIndex];
sortAndCompute(numIndex + 1, buffer);
// 消除前面两个已经添加的字符恢复原状，以便下一次循环的叠加
// 但是当中间连接符变为''的时候，则只删除buffer中的前面一个字符
buffer = operIndex != 2 ? buffer.substring(0, buffer.length() - 2)
: buffer.substring(0, buffer.length() - 1);
}
}
private static int sum(String formula) {
if(formula == null || formula.trim().length() == 0)
throw new IllegalArgumentException("formula is invalid!");
Stack<String> numStack = new Stack<String>();
Stack<String> operStack = new Stack<String>();
StringBuffer numBuffer = new StringBuffer();
formula += "#";// 添加一个结束符到公式末尾便于计算
char[] chs = formula.toCharArray();
for(int index = 0; index < formula.length(); ++index) {
if(chs[index] != '+' && chs[index] != '-' && chs[index] != '#') {
numBuffer.append(chs[index]);
} else {
numStack.push(numBuffer.toString());
numBuffer.delete(0, numBuffer.length());
if(operStack.isEmpty()) operStack.push(chs[index] + "");
else {
int numAft = Integer.parseInt(numStack.pop());
int numBef = Integer.parseInt(numStack.pop());
String oper = operStack.pop();
int sum = oper.equals("+") ? numBef + numAft : numBef - numAft;
numStack.push(sum + "");
operStack.push(chs[index] + "");
}
}
}
return Integer.parseInt(numStack.pop());
}
}
package test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* 1 2 3 4 5 6 7 8 9 = 110
* <p/>
* 在数字间填入加号或者减号（可以不填，但不能填入其它符号）使等式成立。
* @author Lear
*
*/
public class Tester {
private static final char[] NUMBERS = {'1', '2', '3', '4', '5', '6', '7', '8', '9'/**/};
private static final int RESULT = 110;// 计算结果
public static void main(String[] args) {
List<List<String>> all = sort(NUMBERS);
testPrint(all);
for(List<String> aRank : all) {
printEstablishEquation(aRank);
}
}
private static void testPrint(List<List<String>> all) {
for(List<String> aRank : all) {
System.out.println(aRank);
}
}
/**
* 按nums的顺序进行排列组合，最后返回一个List数组，它将包含所有的可能的一个由一列数据的List数组。
* <p/>
* 此为一个递归函数，第一个的组合数字后面的字符都将继续调用此函数以计算出List<List<String>>.<br/>
* 缺点：数据量增大时，将导致内存溢出，而且算法的效率低下
*
* @param nums
* @return 格式：[[1,2,3,4..],[12,3,4,..],[12,34,...],....]
*/
private static List<List<String>> sort(char[] nums) {
if(nums.length == 0) return Collections.emptyList();
List<List<String>> all = new ArrayList<List<String>>();
// 字符数组直接加入此List中
List<String> firstRank = new ArrayList<String>();
for(int i = 0; i < nums.length; ++i) {
firstRank.add(nums[i] + "");
}
all.add(firstRank);
// 组合数字的个数，如：1,2,3,4.... ; 12,3,4,5.. ; 123,4,5.. ; 1234.5 ...
for(int combinationNum = 2; combinationNum <= nums.length; ++combinationNum) {
// 此组合的偏移量，如：12,3.... ; 1,23,4....; 1,2,34,...
for(int offset = 0; offset < nums.length - (combinationNum - 1); ++offset) {
List<String> preRank = new ArrayList<String>();
StringBuilder buffer = new StringBuilder();
for(int i = 0; i < offset; ++i) {// 前
preRank.add(nums[i] + "");
}
for(int i = offset; i < offset + combinationNum; ++i) {// 中
buffer.append(nums[i]);
}
preRank.add(buffer.toString());
// 获取后面的字符数组，然后递归组合
char[] suffix = new char[nums.length - (offset + combinationNum)];
for(int i = offset + combinationNum, index = 0; i < nums.length; ++i, ++index) {// 后
suffix[index] = nums[i];
}
// 例如：12组合的后面 [[3,4,5,6,7...],[34,5,6...],[345...]]
List<List<String>> sufArray = sort(suffix);
// 为里面的所有List<String>添加前面的数字组合,
// 例如：添加12到上面的例子中，使之成为[[12,3,4,...],[12,34...]....]
if(sufArray.size() != 0)
for(List<String> sufRank : sufArray) {
// 组合前后的List
List<String> allRank = new ArrayList<String>();
for(int i = 0; i < preRank.size(); ++i) allRank.add(preRank.get(i));
for(int i = 0; i < sufRank.size(); ++i) allRank.add(sufRank.get(i));
// 添加到all中去
all.add(allRank);
}
else
all.add(preRank);// 说明到末尾了
}
}
return all;
}
private static void printEstablishEquation(List<String> ls) {
char[] operators = {'+', '-'};
StringBuilder buff = new StringBuilder();
// 转换为数字
int[] nums = new int[ls.size()];
for(int i = 0; i < ls.size(); ++i) {
nums[i] = Integer.parseInt(ls.get(i));
}
// 对应的操作符是否变化的数组
boolean[] isOperChanges = new boolean[nums.length - 1];
// 计算每一个isOperChange的变化周期
int[] perOperChangeCounts = new int[isOperChanges.length];
for(int index = 0; index < isOperChanges.length; ++index) {
perOperChangeCounts[index] = (int) Math.pow(2, index);
}
// 可能性的计算次数 2^(nums.length - 1)
int computeCount = (int) Math.pow(2, nums.length -1);
for(int i = 1; i <= computeCount; ++i) {
// 迭代计算
int sum = nums[0];
buff.append(nums[0]);
for(int index = 0; index < nums.length - 1; ++index) {
sum = isOperChanges[index] ? sum - nums[index + 1] : sum + nums[index + 1];
buff.append(isOperChanges[index] ? operators[1] : operators[0]);
buff.append(nums[index + 1]);
}
// 打印
if(sum == RESULT)// 输出等式成立的表达式
System.out.println("成功：" + buff.toString() + " = " + sum);
//else
//System.out.println("失败：" + buff.toString() + " = " + sum);
buff.delete(0, buff.length());
// 操作符交替变化数组的迭代计算。
// 第1操作符，每次交替变化；第2操作符，i每 2^2次变化一次；第3操作符，i每2^3次变化一次
for(int index = 0; index < isOperChanges.length; ++index) {
if(i % perOperChangeCounts[index] == 0)
isOperChanges[index] = !isOperChanges[index];// 交替
}
}
}
}