Java代码实现24点计算

admin管理员组

文章数量:1794759

Java代码实现24点计算

24点是我们小时候经常会玩的游戏。 4个数字，3个操作符，谁先算出24，谁就胜。

本文利用搜索回溯算法计算24点。

核心思路

我有1，2，3，4这四个数字。如何才能让计算机计算出24来呢？ 我们可以这么想，先取出1来，然后让1+2=3，然后再让3+3=6，6+4=10，发现结果不等于24，那我们可以后退一步（回溯）让6-4=2，发现结果也不等，再让6*4=24，结果为24。

图解

abcd代表四个数字

#mermaid-svg-z34CaCnjCo8TDtGw .label{font-family:\'trebuchet ms\', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-z34CaCnjCo8TDtGw .label text{fill:#333}#mermaid-svg-z34CaCnjCo8TDtGw .node rect,#mermaid-svg-z34CaCnjCo8TDtGw .node circle,#mermaid-svg-z34CaCnjCo8TDtGw .node ellipse,#mermaid-svg-z34CaCnjCo8TDtGw .node polygon,#mermaid-svg-z34CaCnjCo8TDtGw .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-z34CaCnjCo8TDtGw .node .label{text-align:center;fill:#333}#mermaid-svg-z34CaCnjCo8TDtGw .node.clickable{cursor:pointer}#mermaid-svg-z34CaCnjCo8TDtGw .arrowheadPath{fill:#333}#mermaid-svg-z34CaCnjCo8TDtGw .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-z34CaCnjCo8TDtGw .flowchart-link{stroke:#333;fill:none}#mermaid-svg-z34CaCnjCo8TDtGw .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-z34CaCnjCo8TDtGw .edgeLabel rect{opacity:0.9}#mermaid-svg-z34CaCnjCo8TDtGw .edgeLabel span{color:#333}#mermaid-svg-z34CaCnjCo8TDtGw .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-z34CaCnjCo8TDtGw .cluster text{fill:#333}#mermaid-svg-z34CaCnjCo8TDtGw div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\'trebuchet ms\', verdana, arial;font-family:var(--mermaid-font-family);font-size:12px;background:#ffffde;border:1px solid #aa3;border-radius:2px;pointer-events:none;z-index:100}#mermaid-svg-z34CaCnjCo8TDtGw .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-z34CaCnjCo8TDtGw text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-z34CaCnjCo8TDtGw .actor-line{stroke:grey}#mermaid-svg-z34CaCnjCo8TDtGw .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-z34CaCnjCo8TDtGw .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-z34CaCnjCo8TDtGw #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-z34CaCnjCo8TDtGw .sequenceNumber{fill:#fff}#mermaid-svg-z34CaCnjCo8TDtGw #sequencenumber{fill:#333}#mermaid-svg-z34CaCnjCo8TDtGw #crosshead path{fill:#333;stroke:#333}#mermaid-svg-z34CaCnjCo8TDtGw .messageText{fill:#333;stroke:#333}#mermaid-svg-z34CaCnjCo8TDtGw .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-z34CaCnjCo8TDtGw .labelText,#mermaid-svg-z34CaCnjCo8TDtGw .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-z34CaCnjCo8TDtGw .loopText,#mermaid-svg-z34CaCnjCo8TDtGw .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-z34CaCnjCo8TDtGw .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-z34CaCnjCo8TDtGw .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-z34CaCnjCo8TDtGw .noteText,#mermaid-svg-z34CaCnjCo8TDtGw .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-z34CaCnjCo8TDtGw .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-z34CaCnjCo8TDtGw .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-z34CaCnjCo8TDtGw .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-z34CaCnjCo8TDtGw .mermaid-main-font{font-family:\"trebuchet ms\", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-z34CaCnjCo8TDtGw .section{stroke:none;opacity:0.2}#mermaid-svg-z34CaCnjCo8TDtGw .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-z34CaCnjCo8TDtGw .section2{fill:#fff400}#mermaid-svg-z34CaCnjCo8TDtGw .section1,#mermaid-svg-z34CaCnjCo8TDtGw .section3{fill:#fff;opacity:0.2}#mermaid-svg-z34CaCnjCo8TDtGw .sectionTitle0{fill:#333}#mermaid-svg-z34CaCnjCo8TDtGw .sectionTitle1{fill:#333}#mermaid-svg-z34CaCnjCo8TDtGw .sectionTitle2{fill:#333}#mermaid-svg-z34CaCnjCo8TDtGw .sectionTitle3{fill:#333}#mermaid-svg-z34CaCnjCo8TDtGw .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:\'trebuchet ms\', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-z34CaCnjCo8TDtGw .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-z34CaCnjCo8TDtGw .grid .tick text{font-family:\'trebuchet ms\', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-z34CaCnjCo8TDtGw .grid path{stroke-width:0}#mermaid-svg-z34CaCnjCo8TDtGw .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-z34CaCnjCo8TDtGw .task{stroke-width:2}#mermaid-svg-z34CaCnjCo8TDtGw .taskText{text-anchor:middle;font-family:\'trebuchet ms\', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-z34CaCnjCo8TDtGw .taskText:not([font-size]){font-size:11px}#mermaid-svg-z34CaCnjCo8TDtGw .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:\'trebuchet ms\', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-z34CaCnjCo8TDtGw .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-z34CaCnjCo8TDtGw .task.clickable{cursor:pointer}#mermaid-svg-z34CaCnjCo8TDtGw .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-z34CaCnjCo8TDtGw .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-z34CaCnjCo8TDtGw .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-z34CaCnjCo8TDtGw .taskText0,#mermaid-svg-z34CaCnjCo8TDtGw .taskText1,#mermaid-svg-z34CaCnjCo8TDtGw .taskText2,#mermaid-svg-z34CaCnjCo8TDtGw .taskText3{fill:#fff}#mermaid-svg-z34CaCnjCo8TDtGw .task0,#mermaid-svg-z34CaCnjCo8TDtGw .task1,#mermaid-svg-z34CaCnjCo8TDtGw .task2,#mermaid-svg-z34CaCnjCo8TDtGw .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-z34CaCnjCo8TDtGw .taskTextOutside0,#mermaid-svg-z34CaCnjCo8TDtGw .taskTextOutside2{fill:#000}#mermaid-svg-z34CaCnjCo8TDtGw .taskTextOutside1,#mermaid-svg-z34CaCnjCo8TDtGw .taskTextOutside3{fill:#000}#mermaid-svg-z34CaCnjCo8TDtGw .active0,#mermaid-svg-z34CaCnjCo8TDtGw .active1,#mermaid-svg-z34CaCnjCo8TDtGw .active2,#mermaid-svg-z34CaCnjCo8TDtGw .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-z34CaCnjCo8TDtGw .activeText0,#mermaid-svg-z34CaCnjCo8TDtGw .activeText1,#mermaid-svg-z34CaCnjCo8TDtGw .activeText2,#mermaid-svg-z34CaCnjCo8TDtGw .activeText3{fill:#000 !important}#mermaid-svg-z34CaCnjCo8TDtGw .done0,#mermaid-svg-z34CaCnjCo8TDtGw .done1,#mermaid-svg-z34CaCnjCo8TDtGw .done2,#mermaid-svg-z34CaCnjCo8TDtGw .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-z34CaCnjCo8TDtGw .doneText0,#mermaid-svg-z34CaCnjCo8TDtGw .doneText1,#mermaid-svg-z34CaCnjCo8TDtGw .doneText2,#mermaid-svg-z34CaCnjCo8TDtGw .doneText3{fill:#000 !important}#mermaid-svg-z34CaCnjCo8TDtGw .crit0,#mermaid-svg-z34CaCnjCo8TDtGw .crit1,#mermaid-svg-z34CaCnjCo8TDtGw .crit2,#mermaid-svg-z34CaCnjCo8TDtGw .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-z34CaCnjCo8TDtGw .activeCrit0,#mermaid-svg-z34CaCnjCo8TDtGw .activeCrit1,#mermaid-svg-z34CaCnjCo8TDtGw .activeCrit2,#mermaid-svg-z34CaCnjCo8TDtGw .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-z34CaCnjCo8TDtGw .doneCrit0,#mermaid-svg-z34CaCnjCo8TDtGw .doneCrit1,#mermaid-svg-z34CaCnjCo8TDtGw .doneCrit2,#mermaid-svg-z34CaCnjCo8TDtGw .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-z34CaCnjCo8TDtGw .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-z34CaCnjCo8TDtGw .milestoneText{font-style:italic}#mermaid-svg-z34CaCnjCo8TDtGw .doneCritText0,#mermaid-svg-z34CaCnjCo8TDtGw .doneCritText1,#mermaid-svg-z34CaCnjCo8TDtGw .doneCritText2,#mermaid-svg-z34CaCnjCo8TDtGw .doneCritText3{fill:#000 !important}#mermaid-svg-z34CaCnjCo8TDtGw .activeCritText0,#mermaid-svg-z34CaCnjCo8TDtGw .activeCritText1,#mermaid-svg-z34CaCnjCo8TDtGw .activeCritText2,#mermaid-svg-z34CaCnjCo8TDtGw .activeCritText3{fill:#000 !important}#mermaid-svg-z34CaCnjCo8TDtGw .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:\'trebuchet ms\', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-z34CaCnjCo8TDtGw g.classGroup text{fill:#9370db;stroke:none;font-family:\'trebuchet ms\', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-z34CaCnjCo8TDtGw g.classGroup text .title{font-weight:bolder}#mermaid-svg-z34CaCnjCo8TDtGw g.clickable{cursor:pointer}#mermaid-svg-z34CaCnjCo8TDtGw g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-z34CaCnjCo8TDtGw g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-z34CaCnjCo8TDtGw .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-z34CaCnjCo8TDtGw .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-z34CaCnjCo8TDtGw .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-z34CaCnjCo8TDtGw .dashed-line{stroke-dasharray:3}#mermaid-svg-z34CaCnjCo8TDtGw #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-z34CaCnjCo8TDtGw #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-z34CaCnjCo8TDtGw #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-z34CaCnjCo8TDtGw #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-z34CaCnjCo8TDtGw #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-z34CaCnjCo8TDtGw #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-z34CaCnjCo8TDtGw #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-z34CaCnjCo8TDtGw #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-z34CaCnjCo8TDtGw mit-id,#mermaid-svg-z34CaCnjCo8TDtGw mit-msg,#mermaid-svg-z34CaCnjCo8TDtGw .branch-label{fill:lightgrey;color:lightgrey;font-family:\'trebuchet ms\', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-z34CaCnjCo8TDtGw .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:\'trebuchet ms\', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-z34CaCnjCo8TDtGw .slice{font-family:\'trebuchet ms\', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-z34CaCnjCo8TDtGw g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:\'trebuchet ms\', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-z34CaCnjCo8TDtGw g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-z34CaCnjCo8TDtGw g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-z34CaCnjCo8TDtGw g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-z34CaCnjCo8TDtGw g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-z34CaCnjCo8TDtGw g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-z34CaCnjCo8TDtGw .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-z34CaCnjCo8TDtGw .stateGroup posit{fill:white;border-bottom:1px}#mermaid-svg-z34CaCnjCo8TDtGw .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-z34CaCnjCo8TDtGw .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-z34CaCnjCo8TDtGw .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-z34CaCnjCo8TDtGw .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-z34CaCnjCo8TDtGw .edgeLabel text{fill:#333}#mermaid-svg-z34CaCnjCo8TDtGw .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:\'trebuchet ms\', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-z34CaCnjCo8TDtGw .node circle.state-start{fill:black;stroke:black}#mermaid-svg-z34CaCnjCo8TDtGw .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-z34CaCnjCo8TDtGw #statediagram-barbEnd{fill:#9370db}#mermaid-svg-z34CaCnjCo8TDtGw .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-z34CaCnjCo8TDtGw .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-z34CaCnjCo8TDtGw .statediagram-state .divider{stroke:#9370db}#mermaid-svg-z34CaCnjCo8TDtGw .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-z34CaCnjCo8TDtGw .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-z34CaCnjCo8TDtGw .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-z34CaCnjCo8TDtGw .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-z34CaCnjCo8TDtGw .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-z34CaCnjCo8TDtGw .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-z34CaCnjCo8TDtGw .note-edge{stroke-dasharray:5}#mermaid-svg-z34CaCnjCo8TDtGw .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: \'\"trebuchet ms\", verdana, arial\';--mermaid-font-family: \"Comic Sans MS\", \"Comic Sans\", cursive}#mermaid-svg-z34CaCnjCo8TDtGw .error-icon{fill:#522}#mermaid-svg-z34CaCnjCo8TDtGw .error-text{fill:#522;stroke:#522}#mermaid-svg-z34CaCnjCo8TDtGw .edge-thickness-normal{stroke-width:2px}#mermaid-svg-z34CaCnjCo8TDtGw .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-z34CaCnjCo8TDtGw .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-z34CaCnjCo8TDtGw .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-z34CaCnjCo8TDtGw .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-z34CaCnjCo8TDtGw .marker{fill:#333}#mermaid-svg-z34CaCnjCo8TDtGw .marker.cross{stroke:#333} :root { --mermaid-font-family: \"trebuchet ms\", verdana, arial;} #mermaid-svg-z34CaCnjCo8TDtGw { color: rgba(0, 0, 0, 0.75); font: ; } a + b + c + d =24? - - - * * * / / /

图的意思是让a+b+c+d=24是否等于24，不是的话就a+b+c-d=24？ 再*d，不等于24话除于d，如果还不等就退回到a+b,让a+b-c+d，不是的话就让a+b-c-d …复返这类操作，直到等于24或无解。

上图中的排列时abcd，但不至于abcd的排列，所以我们要实现全排列的代码

public static void permutations(int[] nums, int start, int end) { if (start == end) { all[countOfall++] = Arrays.copyOf(nums, nums.length); } else { for (int i = start; i < end; i++) { swap(nums, start, i); permutations(nums, start + 1, end); swap(nums, start, i); } } } public static void swap(int[] nums, int a, int b) { int t = nums[a]; nums[a] = nums[b]; nums[b] = t; }

全排列用递归非常轻易实现，思路就是固定第一个数字，让后面的n-1个数就行全排列，再次固定第二个数字，让n-2个数进行全排列，直到到最后一位。

大体思路已经讲清下面贴出全部代码

import Java.util.*; import static java.lang.System.out; /** * 使用搜索回溯法，返回和为24的公式 */ public class Main { static Set<Stack<String>> hashSet = new HashSet<Stack<String>>(); // 去除重复项 static char[] syms = new char[]{'+', '-', '*', '/'}; static boolean[] visited = new boolean[3]; // 数字是否被访问过， true为访问过，false没有 static Stack<String> fu = new Stack<String>(); // 装载公式的栈 static int[][] all = new int[24][]; // 装载4个数字的全排列的数组 static int countOfall = 0; // all数组的索引 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] nums = new int[4]; out.println("输入四个数字(空格分割):"); for (int i = 0; i < nums.length; i++) { nums[i] = sc.nextInt(); } permutations(nums, 0, nums.length); nums = new int[3]; for (int i = 0; i < all.length; i++) { int numOne = all[i][0]; nums = Arrays.copyOfRange(all[i], 1, all[i].length); fu.push(Integer.toString(numOne)); resolve(numOne, nums); fu.pop(); } /** * 输出所有符合的项 */ if (!hashSet.isEmpty()) { for (Stack<String> st : hashSet) { if (!st.isEmpty()) out.println(st); } } else out.println("无解"); } /* 全排列 */ public static void permutations(int[] nums, int start, int end) { if (start == end) { all[countOfall++] = Arrays.copyOf(nums, nums.length); } else { for (int i = start; i < end; i++) { swap(nums, start, i); permutations(nums, start + 1, end); swap(nums, start, i); } } } public static void swap(int[] nums, int a, int b) { int t = nums[a]; nums[a] = nums[b]; nums[b] = t; } /* 计算24点的代码 num为四个数字的第一个数，nums装载其他3个数 需要注意的是除法，因为除法要必须是整除，所以得额外判断，如果不能整除 直接放弃这个运算，break出来 */ public static void resolve(int num, int[] nums) { if (num == 24 && fu.size() == 7) { hashSet.add((Stack<String>) fu.clone()); return; } else if (fu.size() == 7) { // 栈中有个四个数和三个运算符 //但并不符合规则 return; } for (int i = 0; i < nums.length; i++) { if (!visited[i]) { for (int j = 0; j < syms.length; j++) { if (syms[j] == '+') { visited[i] = true; fu.push("+"); fu.push(Integer.toString(nums[i])); resolve(nums[i] + num, nums); visited[i] = false; fu.pop(); fu.pop(); } else if (syms[j] == '-') { visited[i] = true; fu.push("-"); fu.push(Integer.toString(nums[i])); resolve(num - nums[i], nums); visited[i] = false; fu.pop(); fu.pop(); } else if (syms[j] == '*') { visited[i] = true; fu.push("*"); fu.push(Integer.toString(nums[i])); resolve(nums[i] * num, nums); visited[i] = false; fu.pop(); fu.pop(); } else { if (num % nums[i] == 0) { visited[i] = true; fu.push("/"); fu.push(Integer.toString(nums[i])); resolve(num / nums[i], nums); visited[i] = false; fu.pop(); fu.pop(); } else break; } } } } } }

本文标签： 代码java