一个大学竞赛题！ 看看？

Question

 1__2__3__4__5__6__7__8__9=110？
只可以填+或-，  或者不填   不填也代表多位数；  如：1__2不填代表是12；
求:所有可能的填法...

Answer 1

public class Demo{
    public static void main(String args[]){
        String str="123456789";
        char[] chars = str.toCharArray();
        int[] array = new int[8];
        StringBuffer sb = new StringBuffer();
        while(array[0]<3){
            sb.append(chars[0]);
            for(int k=0;k<chars.length-1;k++){
                if(array[k]==1){
                    sb.append("+");
                }
                else if(array[k]==2){
                    sb.append("-");
                }
                
                sb.append(chars[k+1]);
            }
            if(parse(sb.toString())){
                System.out.println(sb.toString());
            }
            sb.setLength(0);
            
            array[7]++;
            for(int i=7;i>0;i--){
                if(array[i]==3){
                    array[i]=0;
                    array[i-1]++;
                }
            }
            
        }
    }
    private static boolean parse(String str) {
        String[] str1 = str.split("[\\+]|[-]");
        String str2 = str.replaceAll("\\d*","");
        int sum = 0;
        sum = Integer.parseInt(str1[0]);
        for(int i=0;i<str1.length-1;i++){
            switch(str2.charAt(i)){
            case '+':
                sum+=Integer.parseInt(str1[i+1]);
                break;
            case '-':
                sum -=Integer.parseInt(str1[i+1]);
                break;
            }
        }
        if(sum==110){
            return true;
        }
        return false;
    }
}

Answer 2

刚写完了  感觉有点麻烦但还是算出来了
import java.util.ArrayList;public class test {
// 取出最后一次出现运算符的位置
static int getlastindex(String str) {
int index = 0;
int temp = str.lastIndexOf("+");
int temp1 = str.lastIndexOf("-");
index = Math.max(temp, temp1); return index;
} // 取出从指定位置开始搜索第一次出现运算符的位置
static int getfirstindex(String str, int beginindex) {
int index = 0;
int temp = str.indexOf("+", beginindex);
int temp1 = str.indexOf("-", beginindex);
index = Math.min(temp, temp1);
if (temp1 == -1 && temp == -1)
index = 0;
else if (temp == -1)
index = temp1;
else if (temp1 == -1)
index = temp; return index;
} public static void main(String[] args) {
String[] a = { "2", "+2", "-2" };
String[] b = { "3", "+3", "-3" };
String[] c = { "4", "+4", "-4" };
String[] d = { "5", "+5", "-5" };
String[] e = { "6", "+6", "-6" };
String[] f = { "7", "+7", "-7" };
String[] g = { "8", "+8", "-8" };
String[] h = { "9", "+9", "-9" };
int count = 0;
for (int ai = 0; ai < a.length; ai++) {
for (int bi = 0; bi < b.length; bi++) {
for (int ci = 0; ci < c.length; ci++) {
for (int di = 0; di < d.length; di++) {
for (int ei = 0; ei < e.length; ei++) {
for (int fi = 0; fi < f.length; fi++) {
for (int gi = 0; gi < g.length; gi++) {
for (int hi = 0; hi < g.length; hi++) {
String str = "1" + a[ai] + b[bi]
+ c[ci] + d[di] + e[ei] + f[fi]
+ g[gi] + h[hi];
// 取出最后一次出现运算符的位置
int overindex = getlastindex(str); int beginindex = 0;
int endindex = 0;
String sub = null;
ArrayList<String> number = new ArrayList<String>();
while (beginindex != overindex) {
if (overindex == -1)
break;
// 取出从指定位置开始第一次出现运算符的位置
endindex = getfirstindex(str,
beginindex + 1); sub = str.substring(beginindex,
endindex);
number.add(sub);
beginindex = endindex; }
if (overindex != -1) {
sub = str.substring(overindex, str
.length());
number.add(sub);
int sum = 0;
for (int i = 0; i < number.size(); i++) {
String temp = number.get(i);
if (temp.charAt(0) == '+')
temp = temp.substring(1);
sum = sum + new Integer(temp); }
if (sum == 110) {
System.out
.println(str + "=110");
count = count + 1;
} }
}
}
}
}
}
}
} }
System.out.println("一共" + count + "种类算法");
}
}

Answer 3

package com.cc;
public class T{ public static void main(String[] args) {
//1x2x3x4x5x6x7x8x9=110
int num=0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
for(int k=0;k<3;k++){
for(int l=0;l<3;l++){
for(int m=0;m<3;m++){
for(int n=0;n<3;n++){
for(int o=0;o<3;o++){
for(int p=0;p<3;p++){
String sb="";
char operate='+';
long ip=0,ib=0;
String str="1",st=i+""+j+""+k+""+l+""+m+""+n+""+o+""+p;
//得到算式的字符串形式
for(int t=0;t<st.length();t++){
if(st.charAt(t)=='0'){str=str+""+(t+2);}
else if(st.charAt(t)=='1'){str=str+"+"+(t+2);}
else if(st.charAt(t)=='2'){str=str+"-"+(t+2);}
}
//计算
str=str+"=";
for(int t=0;t<str.length();t++){
if(str.charAt(t)>='0'&&str.charAt(t)<='9'){
sb=sb+str.charAt(t);
}else {
ib=Integer.parseInt(sb);
if(operate=='+') ip=ip+ib;
else ip=ip-ib;
operate=str.charAt(t);sb="";
}
}
if(ip==110) System.out.println((++num)+"\t"+str+ip);
}}}}}}}

}
}
}
结果：
1 123+4+5+67-89=110
2 123+4-5-6-7-8+9=110
3 123-4+5-6-7+8-9=110
4 123-4-5+6+7-8-9=110
5 12+34+56+7-8+9=110
6 12+3+45+67-8-9=110
7 12-3+4-5+6+7+89=110
8 1+234-56-78+9=110
9 1+2+34+5+67-8+9=110
10 1-2+3+45-6+78-9=110