马虎的算式
小明是个急性子，上小学的时候经常把老师写在黑板上的题目抄错了。
有一次，老师出的题目是：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 这样的算式一共有多少种呢？
请你利用计算机的优势寻找所有的可能，并回答不同算式的种类数。
满足乘法交换律的算式计为不同的种类，所以答案肯定是个偶数。
答案一：
public class Baolipojie {
/**
* @param args
*/
public static void main(String[] args) {
int count = 0;
for (int a = 1; a < 10; a++) {
for (int b = 1; b < 10; b++) {
for (int c = 1; c < 10; c++) {
for (int d = 1; d < 10; d++) {
for (int e = 1; e < 10; e++) {
if (a != b && a != c && a != d && a != e && b != c
&& b != d && b != e && c != d && c != e
&& d != e) {
int m = a * 10 + b;
int n = c * 100 + d * 10 + e;
int x = a * 100 + d * 10 + b;
int y = c * 10 + e;
if (m * n == x * y) {
count++;
}
}
}
}
}
}
}
System.out.println(count);
}
}答案一：运行结果142
网上说这是暴力破解的方法，这个我看懂了。
答案二：
public class Right {
static int kinds = 0;
static int a[] = new int[6];
static boolean vis[] = new boolean[10];
static void check(int a[]) {
int num1 = a[1] * 10 + a[2];
int num2 = a[3] * 100 + a[4] * 10 + a[5];
int num3 = a[1] * 100 + a[4] * 10 + a[2];
int num4 = a[3] * 10 + a[5];
if (num1 * num2 == num3 * num4) {
kinds++;
System.out.println(num1 + "*" + num2 + "==" + num3 + "*" + num4);
}
}
static void dfs(int start, int n) {
if (start == 6) {
check(a);
} else {
for (int i = 1; i < n; i++) {
if (vis[i])
continue;
a[start] = i;
vis[i] = true;
dfs(start + 1, n);
vis[i] = false;
}
}
}
public static void main(String[] args) {
dfs(1, 10);
System.out.println(kinds);
}
}这是CSDN大神的给的答案，主要是这一个段没懂。
static void dfs(int start, int n) {
if (start == 6) {
check(a);
} else {
for (int i = 1; i < n; i++) {
if (vis[i])
continue;
a[start] = i;
vis[i] = true;
dfs(start + 1, n);
vis[i] = false;
}
}
}上网查这是递归算法，想不通，哪位大神能给解释下。不知道这段代码的执行顺序是什么，什么时候vis[i]=false;
递归没学好。。。
------解决思路----------------------
static void dfs(int start, int n) {
if (start == 6) {取够5个数后，判断是否符合要求，6是由于start+1
check(a);
} else {
for (int i = 1; i < n; i++) {
if (vis[i]) // 如果已经取过dii个数，直接跳过，进行下一次循环
continue;
a[start] = i; // 第i个数没有取过，现在取出它
vis[i] = true; // 标记
dfs(start + 1, n); //从下一个位置开始继续取数
vis[i] = false; // 回溯的过程清除标记
}
}
}
比如1,2,3,4,5,6,7,8,9；第一次选五个数1,2,3,4,5；这些位置都被标记为true，此时start=6；进行check（）;然后最后一次递归退出，vis[5] = false;进行下一次for循环，i = 6，vis[6] = true;a[5] = 6,这是选择的就是1,2,3,4,6这5个数，，，，，然后1,2,3,4,7；12348；12349；12354；12356；。。。。。遍历所有的情况
------解决思路----------------------
因为for循环到9就结束了，这时本次递归（start=5）就退出了，上一次递归(start=4)还阻塞在dfs(start + 1, n);位置，那么它现在可以继续执行了，就是执行vis[4]=false;这样下一次4又可以重新被使用了，继续进行for循环，此时i=5，start=4 ，所以a[4] = i =5; (现在就是1235)继续下一次递归，下一次递归到达for后首先还是从前到后寻找没有用过数，刚才提到vis[4] = false;所以现在可以选择4，即a[5] = 4;此时选够5个了（此时选择的数是12354），判断是否符合要求，继续。。。。。
------解决思路----------------------
画了一个流程图，不知道能更清楚不。
dfs(start + 1, n);
是不是修改为 start++；
dfs(start , n); 会好一些。
a[1]~a[5]表示a b c d e5个数字。
start 初始值为1 表示a[1]，每次设置1个数字（从1到9），设置好后，标记为ture（表示不能再设置），
start+1，设置下一位。
直到设置到a[5]。
此时start=6，进行check判断。当前a[5的值取消标记]，数值+1，a[5]赋值，数值标记，进行check判断，
直到数值设置到9，跳出当前递归（start=6），设置a[4]，a[5]，...........
------解决思路----------------------
LZ，我把递归改成循环了，这样好理解些，而且效率比起循环也要好点
int work()
{
int count = 0;
for (int a = 1; a < 10; a++)
{
for (int b = 1; b < 10; b++)
{
if (b == a)
continue;
for (int c = 1; c < 10; c++)
{
if (c == a
------解决思路----------------------
c == b)
continue;
for (int d = 1; d < 10; d++)
{
if (d == c
------解决思路----------------------
d == b
------解决思路----------------------
d == a)
continue;
for (int e = 1; e < 10; e++)
{
if (e == d
------解决思路----------------------
e == c
------解决思路----------------------
e == b
------解决思路----------------------
e == a)
continue;
int m = a * 10 + b;
int n = c * 100 + d * 10 + e;
int x = a * 100 + d * 10 + b;
int y = c * 10 + e;
if (m * n == x * y)
count++;
}
}
}
}
}
return count;
}