好友
阅读权限10
听众
最后登录1970-1-1
|
冥月影
发表于 2020-10-5 00:32
本帖最后由 冥月影 于 2020-10-5 22:11 编辑
下午，我看了1个多小时的dfs深度优先搜索，我觉得我又行了，正巧，想起了之前看过的一道小学数学题目:
□ + □ = □
□ - □ = □
□ * □ = □
□ / □ = □
将 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13 填入上面方框，不能重复使用，使等式成立。
然后
[Java] 纯文本查看 复制代码 import java.util.List;
import java.util.ArrayList;
/**
* □ + □ = □
* □ - □ = □
* □ * □ = □
* □ / □ = □
*
* 将 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13 填入上面方框，不能重复使用，使等式成立。
*
*
* @author 1234
*
*/
public class _dfs深搜01 {
static boolean[] flags = new boolean[14];
static boolean[] fuhao = new boolean[4]; // +-*/
static List<ArrayList<Integer>> result = new ArrayList<>();
public static void dfs(ArrayList<Integer> arr) {
if (arr.size() == 12) {
System.out.println("in " + arr);
List<Integer> arr1 = new ArrayList<>();
arr1.addAll(arr);
result.add((ArrayList<Integer>) arr1);
return;
}
for (int i = 1; i <= 13; i++) {
if (!flags[i] && i != 11) {
flags[i] = true;
for (int j = 1; j <= 13; j++) {
if (!flags[j] && i != 11) {
flags[j] = true;
if (!fuhao[0] && i + j <= 13&& !flags[i+j]) {
fuhao[0] = true;
flags[i+j] = true;
arr.add(i);
arr.add(j);
arr.add(i+j);
dfs(arr);
arr.remove(new Integer(i));
arr.remove(new Integer(j));
arr.remove(new Integer(i + j));
fuhao[0] = false;
flags[i+j] = false;
}
if (fuhao[0] && !fuhao[1] && i - j > 0 && !flags[i-j]) {
fuhao[1] = true;
flags[i-j] = true;
arr.add(i);
arr.add(j);
arr.add(i-j);
dfs(arr);
arr.remove(new Integer(i));
arr.remove(new Integer(j));
arr.remove(new Integer(i-j));
fuhao[1] = false;
flags[i-j] = false;
}
if (fuhao[0] && fuhao[1] && !fuhao[2] && i * j <= 13&& !flags[i*j]) {
fuhao[2] = true;
flags[i*j] = true;
arr.add(i);
arr.add(j);
arr.add(i*j);
dfs(arr);
arr.remove(new Integer(i));
arr.remove(new Integer(j));
arr.remove(new Integer(i*j));
fuhao[2] = false;
flags[i*j] = false;
}
if (fuhao[0] && fuhao[1] && fuhao[2] && !fuhao[3] && i / j > 0 && i % j == 0 && !flags[i/j]) {
fuhao[3] = true;
flags[i/j] = true;
arr.add(i);
arr.add(j);
arr.add(i/j);
dfs(arr);
arr.remove(new Integer(i));
arr.remove(new Integer(j));
arr.remove(new Integer(i/j));
fuhao[3] = false;
flags[i/j] = false;
}
flags[j] = false;
}
}
flags[i] = false;
}
}
return;
}
public static void main(String[] args) {
// TODO 自动生成的方法存根
long startTime = System.currentTimeMillis();
dfs(new ArrayList<Integer>());
System.out.println(result.size());
System.out.println(result);
System.out.println("共花时: " + (System.currentTimeMillis() - startTime) + " 毫秒");
}
}
输出按顺序对应题目的 □
感觉写的好乱，好长，而且出来的结果有好长重复的，例如 12 / 3 = 4, 12 / 4 = 3，可是瞬间觉得自己又不行了，有没有大佬给个示范。。。
感谢两位大佬的提示，我改了一下 dfs 方法
[Java] 纯文本查看 复制代码 static int[] fuhao = new int[3]; // + *
public static void dfs(ArrayList<Integer> arr) {
if (arr.size() == 12) {
System.out.println("in " + arr);
List<Integer> arr1 = new ArrayList<>();
arr1.addAll(arr);
result.add((ArrayList<Integer>) arr1);
return;
}
for (int i = 1; i <= 13; i++) {
if (!flags[i] && i != 11) {
flags[i] = true;
for (int j = 1; j <= 13; j++) {
if (!flags[j] && i != 11) {
flags[j] = true;
if (fuhao[0] < 2 && i + j <= 13&& !flags[i+j]) {
fuhao[0]++;
flags[i+j] = true;
arr.add(i);
arr.add(j);
arr.add(i+j);
dfs(arr);
arr.remove(new Integer(i));
arr.remove(new Integer(j));
arr.remove(new Integer(i + j));
fuhao[0]--;
flags[i+j] = false;
}
if (fuhao[0] == 2 && fuhao[1] < 2 && i * j <= 13&& !flags[i*j]) {
fuhao[1]++;
flags[i*j] = true;
arr.add(i);
arr.add(j);
arr.add(i*j);
dfs(arr);
arr.remove(new Integer(i));
arr.remove(new Integer(j));
arr.remove(new Integer(i*j));
fuhao[1]--;
flags[i*j] = false;
}
flags[j] = false;
}
}
flags[i] = false;
}
}
return;
}
发现时间节省了一半，可是还是会有重复的情况出现，有没有大佬给个提示，怎么去重。。。 |
免费评分
-
查看全部评分
|
发帖前要善用【论坛搜索】功能，那里可能会有你要找的答案或者已经有人发布过相同内容了，请勿重复发帖。 |
|
|
|
|
|
|
