把小学数学题用java语言解出来

冥月影

下午，我看了1个多小时的dfs深度优先搜索，我觉得我又行了，正巧，想起了之前看过的一道小学数学题目:

□ + □ = □
□ - □ = □
□ * □ = □
□ / □ = □
将 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13 填入上面方框，不能重复使用，使等式成立。

然后

[Java] 纯文本查看 复制代码

?

001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 096 097 098 099 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114

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] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

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;     }

发现时间节省了一半，可是还是会有重复的情况出现，有没有大佬给个提示，怎么去重。。。

haidao123

这个可以有

cs7392000

真长，真复杂。

jinxin6670

这个题目…有点崩溃

星辰一枚

看着头疼。

浪与矜持

小学题被你弄得这么复杂，唉！

ioajp

看不懂在干些啥。

QingYi.

回溯还可以哦

nywthy

请继续努力，让复杂的问题简单化。

Mrzhy

这样教数学感觉孩子更感兴趣，还能培养孩子编程，希望楼主多多更新！