第三届(2012)蓝桥杯第十题——趣味算式

浅浅的花香味﹌ 2022-11-17 05:50 157阅读 0赞

### @第三届蓝桥杯第十题——趣味算式 ###

*   *  1、点我快速查看题目
     *  2、来和笔笔一起认真分析~~
     *   *  2.1、要求分析：
         *  2.2、功能实现分析：
     *  3、代码实现~~

## 1、点我快速查看题目 ##

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

## 2、来和笔笔一起认真分析~~ ##

### 2.1、要求分析： ###

这题考的主要是笔者对全排列的一个理解与应用(不了解的朋友可以先了解一下——>[**这一篇带你了解全排列**][Link 1]);。它要求我们将1~9这9个数字用+、-进行连接，组合出满足值为110的式子并将其打印出来。

### 2.2、功能实现分析： ###

首先，分析一下大致的实现思路，利用循环或递归得到其全排列，然后对每一个排列进行判断，是否满足式子的值==110；下面，我主要介绍一下递归方式：对于递归解这道题:我们需要先构造递归的相似性，也就是递归所需要的控制变量(方法的形式参数)，使该方法可以通过递归来达到我们期望的效果。根据分析，首先需要一个String参数，用来接收需要全排列的字符串，接着，还需要一个指向当前字符的int指针，便于我们对字符的操作。  
          具体的实现方式：构造的递归方法接收一个字符串，从第一个字符开始尝试将后面的字符用+号拼接起来并判断，例如:

递归拼接+号
    第一次：123456789 
    第二次：1+23456789
    第三次：1+2+3456789
    ...
    第k次：1+2+3+4+5+6+7+8+9 （判断是否符合条件，不符合就回溯，改换成拼接-号继续尝试，仍不符合，则不作拼接加减处理）；
    
    if:false:回溯到上一层
    	1+2+3+4+5+6+7+8-9 尝试使用-号拼接
    if:false:回溯到上一层
    	1+2+3+4+5+6+7+89 不作拼接处理

当k指向了字符串的最后一个字符时，就应该进行判断了，因为到了这里的字符串已经用+、-处理完毕了。我们可以按‘+’或‘-’分割字符串，这样就可以得到一个不包含‘-’获‘+’的字符串数组，例如:12+34-56+7-8+9，我们按‘-’进行分割，得到【12+34，56+7，8+9】，然后，再对分割后的字符串数组的每一个元素按‘+’分割，例如：12+34分割后就是【12，34】 将分割得到的值进行相加，就得到了‘-’号分割后的每一个字符串的值，最后再进行累减即可得到传入的字符串的值，如果该值==110，就将这个字符串打印出来，再配合递归即可得到所有的可能。

## 3、代码实现~~ ##

public static void main(String[] args) { 
    		select110("123456789", 0);	
    	}
    	
    	/** * * @param s 待判断的表达式 * @param k 当前的字符的指向 */
    	private static void select110(String s, int k) { 
    		if (k == 9) { 
    			check(s);// 检查是否符合条件
    		} else { 
    			//从1的后面开始添加+号，逐渐再每一个数字的后面添加+号，如果不符合条件，开始回溯
    			select110(s.replace(k + "", k + "+"), k + 1);
    			//回溯到1，逐渐往数字后面添加-号，如果不符合条件，开始回溯
    			select110(s.replace(k + "", k + "-"), k + 1);
    			//回溯到1，n往前移动一位，1、2合成12，继续判断操作，添加+号或减号
    			select110(s, k + 1);
    		}
    	}
    
    	// 检查是否符合条件
    	private static void check(String s) { 
    		int sum = 0;
    		//截取所有+号两端的表达式，\\+表示转义，在截取特殊字符时一定要使用转义字符
    		String[] strArr = s.split("\\+");
    
    		for (String t : strArr) { 
    			//截取包含-号的表达式
    			String[] ss = t.split("\\-");
    			//获取截取-号表达式的第一个元素：
    			//一个元素直接进行累加，如果是减号表达式则还需进行累减操作
    			int num = Integer.parseInt(ss[0]);
    			for (int i = 1; i < ss.length; i++) { 
    				num = num - Integer.parseInt(ss[i]);
    			}
    			//累加和
    			sum += num;
    		}
    		if (sum == 110) { 
    			System.out.println(s + "=" + 110);
    		}
    	}

**运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70]

[Link 1]: https://blog.csdn.net/qq_47953855/article/details/113703118
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70]: /images/20221022/33fb79ae73f844118065ba7af42e6338.png