第三届蓝桥杯-省赛_9

这次介绍的是第三届蓝桥杯省赛题目的第九题….

    匪警请拨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或更高版本。

题目求解: 首先将1~9作为一个字符串，然后要在其中添加+/-号还有拼接。首先插入就可以使用递归来插入，分三种情况，添加+号、添加-号、不添加直接拼接。递归出口就是达到最后一个字符9，检测总和是否为110，是就打印，否就跳过。判断这里，要将整个字符串用+/-来分隔，在分开+号的字符串中再分隔-号的字符，相加相减，判断110，跳出。

java代码实现如下:

package Problem_2;

public class Question_9_1 {
    // 1 2 3 4 5 6 7 8 9 = 110 填入加减号使等式成立。
    public static void main(String[] args) {
        String str = "123456789";
        func(str, 1);
    }

    private static void func(String str, int i) {
        if (i == 9) {
            check(str);
        } else {
            func(str.replace(i + "", i + "+"), i + 1);
            func(str.replace(i + "", i + "-"), i + 1);
            func(str, i + 1);
        }
    }

    private static void check(String str) {
        String[] s = str.split("[\\+]");
        int sum = 0;
        for (String s1 : s) {
            String[] sub = s1.split("[\\-]");
            int num = Integer.parseInt(sub[0]);
            for (int i = 1; i < sub.length; i++) {
                num -= Integer.parseInt(sub[i]);
            }
            sum += num;
        }
        if (sum == 110) {
            System.out.println(str);
        }
    }
}