标题: 马虎的算式
小明是个急性子，上小学的时候经常把老师写在黑板上的题目抄错了。
有一次，老师出的题目是：36 x 495 = ?，他却给抄成了：396 x 45 = ?
但结果却很戏剧性，他的答案竟然是对的！！因为 36 * 495 = 396 * 45 = 17820
类似这样的巧合情况可能还有很多，比如：27 * 594 = 297 * 54
假设 a b c d e 代表1~9不同的5个数字（注意是各不相同的数字，且不含0）
能满足形如： ab * cde = adb * ce 这样的算式一共有多少种呢？
请你利用计算机的优势寻找所有的可能，并回答不同算式的种类数。
满足乘法交换律的算式计为不同的种类，所以答案肯定是个偶数。
答案直接通过浏览器提交。
注意：只提交一个表示最终统计种类数的数字，不要提交解答过程或其它多余的内容。
解析：
方案一：（循环嵌套法）
int count = 0;
for (int a = 1; a <= 9; a++) {
for (int b = 1; b <= 9; b++) {
if(b == a) continue;
for (int c = 1; c <= 9; c++) {
if(c == a || c == b) continue;
for (int d = 1; d <=9; d++) {
if(d == a || d == b || d == c) continue;
for (int e = 1; e <= 9; e++) {
if(e == a || e == b || e == c || e == d) continue;
if((a*10+b)*(c*100+d*10+e) == (a*100+d*10+b)*(c*10+e))
count++;
}
}
}
}
}
System.out.println(count);
结果：142
方案二：（递归全排列）
先写出M个数取N个数全排列的框架:（如果M个数字中有重复数字，则在List集合中不存储具体数据，而存储下标，则可算出全排列的下标，然后根据下标得到全排列的数字）。
static int count = 0;
/**
* 从m个元素中任取n个并对结果进行全排列
* @param list 用于承载可能的排列情况的List
* @param ints 总的整形数组，长度为m
* @param n 从中取得字符个数
*/
public static void listAll(List<Integer> list, int[] ints, int n)
{
if (n == 0) {
System.out.println(list); // 输出一种可能的排列
count++;
return;
}
for (int i = 0; i < ints.length; i++) {
if(!list.contains(ints[i]))
{
list.set(list.size()-n, ints[i]);
}
else{ continue; }
listAll(list, ints, n - 1); // 下一位
list.set(list.size() - n, -1); // 还原
}
}
public static void main(String[] args) {
// 以字符数组承载总的字符集合
int[] ints = {1,2,3,4,5};
int n = 3; //n=3则是取3个数
List<Integer> intList = new ArrayList<Integer>();
//通过这一步初始化序列的长度(i<3则是取三个数)
for (int i = 0; i < n; i++) {
intList.add(-1);
}
listAll(intList, ints, n);
System.out.println(count);
}
然后在以上框架基础上，在n==0的判断中去加工：
static int count = 0;
public static void listAll(List<Integer> list, int[] ints, int n)
{
if (n == 0) {
//System.out.println(list); // 输出一种可能的排列
int a = list.get(0); int b=list.get(1); int c=list.get(2); int d=list.get(3); int e=list.get(4);
if((a*10+b)*(c*100+d*10+e) == (a*100+d*10+b)*(c*10+e))
count++;
return;
}
for (int i = 0; i < ints.length; i++) {
if(!list.contains(ints[i]))
{
list.set(list.size()-n, ints[i]);
}
else{ continue; }
listAll(list, ints, n - 1); // 下一位
list.set(list.size() - n, -1); // 还原
}
}
public static void main(String[] args) {
// 以字符数组承载总的字符集合
int[] ints = {1,2,3,4,5,6,7,8,9};
int n = 5; //n=3则是取3个数
List<Integer> intList = new ArrayList<Integer>();
//通过这一步初始化序列的长度(i<3则是取三个数)
for (int i = 0; i < n; i++) {
intList.add(-1);
}
listAll(intList, ints, n);
System.out.println(count);
}
扩展：M个数字取N个数字全排列（如果M个数字中有数字重复）的模板
如果M个数字中有重复数字，则在List集合中不存储具体数据，而存储下标，则可算出全排列的下标，然后根据下标得到全排列的数字。
static Set<String> set = new HashSet<String>();
public static void main(String[] args) {
int[] ints = {1,2,2,4,5};
int n = 3; //取三个数字
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < n; i++)
list.add(-1);
listAll(list,ints,n);
System.out.println(set);
System.out.println(set.size());
}
public static void listAll(List<Integer> list,int[] ints,int n)
{
if(n == 0) //其中一种排列方式完成
{
String r = ints[list.get(0)]+""+ints[list.get(1)]+""+ints[list.get(2)];
set.add(r);
return;
}
for (int i = 0; i < ints.length; i++) {
if(!list.contains(i))
list.set(list.size()-n, i);
else
continue;
listAll(list,ints,n-1);
list.set(list.size()-n, -1);
}
}
