把小学数学题用java语言解出来
本帖最后由 冥月影 于 2020-10-5 22:11 编辑下午，我看了1个多小时的dfs深度优先搜索，我觉得我又行了，正巧，想起了之前看过的一道小学数学题目:
□ + □ = □
□ - □ = □
□ * □ = □
□ / □ = □
将 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13 填入上面方框，不能重复使用，使等式成立。
然后
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;
static boolean[] fuhao = new boolean; // +-*/
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 != 11) {
flags = true;
for (int j = 1; j <= 13; j++) {
if (!flags && i != 11) {
flags = true;
if (!fuhao && i + j <= 13&& !flags) {
fuhao = true;
flags = 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 = false;
flags = false;
}
if (fuhao && !fuhao && i - j > 0 && !flags) {
fuhao = true;
flags = 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 = false;
flags = false;
}
if (fuhao && fuhao && !fuhao && i * j <= 13&& !flags) {
fuhao = true;
flags = 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 = false;
flags = false;
}
if (fuhao && fuhao && fuhao && !fuhao && i / j > 0 && i % j == 0 && !flags) {
fuhao = true;
flags = 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 = false;
flags = false;
}
flags = false;
}
}
flags = 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，可是瞬间觉得自己又不行了，有没有大佬给个示范。。。
https://static.52pojie.cn/static/image/hrline/line1.png
感谢两位大佬的提示，我改了一下 dfs 方法
static int[] fuhao = new int; // + *
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 != 11) {
flags = true;
for (int j = 1; j <= 13; j++) {
if (!flags && i != 11) {
flags = true;
if (fuhao < 2 && i + j <= 13&& !flags) {
fuhao++;
flags = 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--;
flags = false;
}
if (fuhao == 2 && fuhao < 2 && i * j <= 13&& !flags) {
fuhao++;
flags = 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--;
flags = false;
}
flags = false;
}
}
flags = false;
}
}
return;
}
发现时间节省了一半，可是还是会有重复的情况出现，有没有大佬给个提示，怎么去重。。。 这个可以有 真长，真复杂。 这个题目…有点崩溃 看着头疼。 小学题被你弄得这么复杂，唉！ 看不懂在干些啥。 回溯还可以哦 请继续努力，让复杂的问题简单化。 这样教数学感觉孩子更感兴趣，还能培养孩子编程，希望楼主多多更新！
页:
[1]
2