寒假作业
现在小学的数学题目也不是那么好玩的。
看看这个寒假作业：
□ + □ = □
□ - □ = □
□ × □ = □
□ ÷ □ = □
(如果显示不出来，可以参见【图1.jpg】)
每个方块代表1~13中的某一个数字，但不能重复。
比如：
6 + 7 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5
以及：
7 + 6 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5
就算两种解法。（加法，乘法交换律后算不同的方案）
你一共找到了多少种方案？
public class Main {
static int num = 0;
static int[] a = new int[13]; //存下标对应1-12数字
static boolean[] b = new boolean[14]; //标记是否已经被用了
public static void dfs(int k)
{
if(k == 4) if(a[1] + a[2] != a[3]) return; //每次进行每个要求的判定，能减少很多时间
if(k == 7) if(a[4] - a[5] != a[6]) return;
if(k == 10) if(a[7] * a[8] != a[9]) return;
if(k == 13) if(a[10] != a[11] * a[12]) return;
if(k == 13) {
num++;
return;
}
for(int i = 1; i <14; i++) { //每次赋值，dfs
if(b[i] == false) {
b[i] =true;
a[k] = i;
dfs(k+1);
a[k] = 0;
b[i] = false;
}
}
}
public static void main(String[] args)
{
dfs(1);
System.out.print(num);
}
}
代码改了又改，简单的dfs暴力运行的话，会运行比较久，可能还运行不出来
加上每次的判定，返回，时间会减少很多。
64