1441434079
摘要：本题是2014年第五届蓝桥杯全国软件大赛预赛A组第3题。
题目描述
标题：神奇算式
由4个不同的数字，组成的一个乘法算式，它们的乘积仍然由这4个数字组成。
比如：
210 x 6 = 1260
8 x 473 = 3784
27 x 81 = 2187
都符合要求。
如果满足乘法交换律的算式算作同一种情况，那么，包含上边已列出的3种情况，一共有多少种满足要求的算式。
请填写该数字，通过浏览器提交答案，不要填写多余内容（例如：列出所有算式）。
解题思路
对于这道题目我使用的遍历，加控制条件减少遍历次数
两个明显的限制条件：
1.每个数字的每一位数字不允许重复；
2.算式左边个数字跟右边的相等。
我的解题思路是从结果开始遍历，先判断限制条件一，
然后再通过结果这个数的数字构造出1位数的2位数的，
接着再用结果除以这个数来判断是否符合。
巧用Java集合类排序
运行时间0.165s左右，还算乐观。
之后百度发现用枚举法是不错的选择，对每个数出现的数字进行标记
代码实现
package lanqiaobei;
import java.util.HashSet;
import java.util.TreeSet;
/**
- @author Ape
- @date 2015-9-5
- /
public class SuanShi {
private static TreeSet< Integer> set = new TreeSet<>();
/**
* 递归排序结果，并拿到1位数和2位数的排序放到set集合，三位数的没必要拿到，因为一除就可以得到那个三位数或者两位数
* @param s1
* @param s2
*/
public static void put(StringBuilder s1, StringBuilder s2) {
if (s2.length() == 1 || s2.length() == 2)
set.add(Integer.parseInt(s2.toString()));
for (int i = 0; i < s1.length(); i++) put(new StringBuilder(s1).deleteCharAt(i), new StringBuilder(s2).append(s1.charAt(i))); } /** * 判断是否符合不重复数字的4位数 * @param i * @return */ public static boolean isNum(int i) { HashSet< Integer> set = new HashSet<>();
while (i > 0) {
set.add(i % 10);
i = i / 10;
}
if (set.size() == 4)
return true;
else
return false;
}
/**
* 判断两个数的数字跟结果是否相同
* @param i
* @param k
* @param j
* @return
*/
public static boolean isNum(int i, int k, int j) {
TreeSet< Integer> set1 = new TreeSet();
TreeSet< Integer> set2 = new TreeSet();
int n = 0;
while (i > 0) {
set1.add(i % 10);
i = i / 10;
}
while (j > 0) {
set2.add(j % 10);
j = j / 10;
n++;
}
while (k > 0) {
set2.add(k % 10);
k = k / 10;
n++;
}
if (n == 4 && set1.equals(set2))
return true;
return false;
}
public static void main(String agrs[]) {
for (int i = 1023; i k)
break;
if (i % vInteger == 0 && isNum(i, k, vInteger))
System.out.println(vInteger + " * " + k + " = " + i);
else
continue;
}
//每次循环清空集合
set.clear();
} else {
set.clear();
continue;
}
}
}}
运行结果
6 * 201 = 1206
6 * 210 = 1260
21 * 60 = 1260
15 * 93 = 1395
35 * 41 = 1435
3 * 501 = 1503
3 * 510 = 1530
30 * 51 = 1530
21 * 87 = 1827
27 * 81 = 2187
9 * 351 = 3159
8 * 473 = 3784
答案
12种