题目6、寒假作业
寒假作业
现在小学的数学题目也不是那么好玩的。
看看这个寒假作业：
□ + □ = □
□ - □ = □
□ × □ = □
□ ÷ □ = □
(如果显示不出来，可以参见【图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
就算两种解法。（加法，乘法交换律后算不同的方案）
你一共找到了多少种方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
结果：64
//方法1：DFS搜索
import java.util.ArrayList;
public class Main {
public ArrayList<Integer> list = new ArrayList<Integer>();
public static int count = 0;
public boolean check() {
int len = list.size();
if(len >= 3) {
if(list.get(0) + list.get(1) != list.get(2))
return false;
}
if(len >= 6) {
if(list.get(3) - list.get(4) != list.get(5))
return false;
}
if(len >= 9) {
if(list.get(6) * list.get(7) != list.get(8))
return false;
}
if(len >= 12) {
if(list.get(9) / list.get(10) != list.get(11) || list.get(9) % list.get(10) != 0)
return false;
}
return true;
}
public void dfs(int step) {
if(step == 12) {
System.out.println(list);
count++;
return;
} else {
for(int i = 1;i <= 13;i++) {
if(list.contains(i))
continue;
list.add(i);
if(check() == false) { //类似八皇后问题，此处进行减枝操作
list.remove(list.indexOf(i));
continue;
}
dfs(step + 1);
list.remove(list.size() - 1);
}
}
return;
}
public static void main(String[] args) {
Main test = new Main();
test.dfs(0);
System.out.println(count);
}
}
//方法2：蛮力枚举
import java.util.ArrayList;
import java.util.Collections;
public class Main1 {
public static long count = 0;
public void printResult() {
for(int a1 = 1;a1 <= 13;a1++) {
for(int a2 = 1;a2 <= 13;a2++) {
if(a1 == a2 || a1 + a2 > 13)
continue;
for(int a3 = 1;a3 <= 13;a3++) {
for(int a4 = 1;a4 <= 13;a4++) {
if(a3 == a4 || a3 - a4 < 1)
continue;
for(int a5 = 1;a5 <= 13;a5++) {
for(int a6 = 1;a6 <= 13;a6++) {
if(a5 == a6 || a5 * a6 > 13)
continue;
for(int a7 = 1;a7 <= 13;a7++) {
for(int a8 = 1;a8 <= 13;a8++) {
if(a7 == a8 || a7 % a8 != 0)
continue;
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(a1);
list.add(a2);
list.add((a1 + a2));
list.add(a3);
list.add(a4);
list.add((a3 - a4));
list.add(a5);
list.add(a6);
list.add((a5 * a6));
list.add(a7);
list.add(a8);
list.add((a7 / a8));
ArrayList<Integer> tempList = new ArrayList<Integer>();
for(int i = 0;i < list.size();i++)
tempList.add(list.get(i));
Collections.sort(list);
boolean judge = true;
for(int i = 1;i < list.size();i++) {
if(list.get(i - 1) == list.get(i)) {
judge = false;
break;
}else {
continue;
}
}
if(judge == true) {
System.out.println(tempList);
count++;
}
}
}
}
}
}
}
}
}
}
public static void main(String[] args) {
Main1 test = new Main1();
test.printResult();
System.out.println(count);
}
}