“趣味算式”——匪警请拨110……蓝桥杯

算式”——匪警请拨110……蓝桥杯"/>

“趣味算式”——匪警请拨110……蓝桥杯

    匪警请拨110,即使手机欠费也可拨通！


    为了保障社会秩序，保护人民群众生命财产安全，警察叔叔需要与罪犯斗智斗勇，因而需要经常性地进行体力训练和智力训练！


    某批警察叔叔正在进行智力训练：


    1 2 3 4 5 6 7 8 9 = 110;


    请看上边的算式，为了使等式成立，需要在数字间填入加号或者减号（可以不填，但不能填入其它符号）。之间没有填入符号的数字组合成一个数，例如：12+34+56+7-8+9 就是一种合格的填法；123+4+5+67-89 是另一个可能的答案。


    请你利用计算机的优势，帮助警察叔叔快速找到所有答案。


    每个答案占一行。形如：


12+34+56+7-8+9
123+4+5+67-89
......


    已知的两个答案可以输出，但不计分。
    
    各个答案的前后顺序不重要。


   注意：


    请仔细调试！您的程序只有能运行出正确结果的时候才有机会得分！
    
    请把所有类写在同一个文件中，调试好后，存入与【考生文件夹】下对应题号的“解答.txt”中即可。
    
    相关的工程文件不要拷入。
    
    请不要使用package语句。
    

    源程序中只能出现JDK1.5中允许的语法或调用。不能使用1.6或更高版本。

我的代码是：（直接遍历了，没优化，重点和大家交流下思想）

package coding_04;import java.util.ArrayList;
import java.util.List;public class Funny_equation {List<String> list = new ArrayList<String>();public void buildString(String str,int index) {String s = str;if(s.charAt(index)=='9'){if(equation(s)) System.out.println(s);return;}else {String s1 = s.substring(0,index+1)+"+"+s.substring(index+1,s.length());//情况一buildString(s1,index+2);String s2 = s.substring(0,index+1)+"-"+s.substring(index+1,s.length());//情况二buildString(s2,index+2);String s3 = s;//情况三buildString(s3,index+1);}}public boolean equation(String s) {String[] array = s.split("\\+");int result = 0;for(String e:array){if(e.contains("-")) {String[] temp =	e.split("\\-");result+=Integer.parseInt(temp[0]);for(int i=1;i<temp.length;i++)result-=Integer.parseInt(temp[i]);}else{result+=Integer.parseInt(e);}}if(result==110) return true;return false;}public static void main(String[] args) {String  raw = "123456789";Funny_equation test = new Funny_equation();test.buildString(raw, 0);}}