24点算法
介绍
网上的24点算法基本上都专注于4张牌凑24点，有的算法甚至枚举了所有括号的组合，让人看得头晕眼花。这些算法若是推广到n个数凑n点，基本都歇菜了。
丧心病狂如这位：https://blog.csdn.net/xyisv/article/details/54709207
这位大哥写的不错，可惜思路太复杂：https://blog.csdn.net/luoweifu/article/details/11578457?ticket=ST-393344-z99pqTL6Z26a3Hr5WxhS-passport.csdn.net
本算法采用暴力枚举法，能处理任意个数凑任意值。以24点为例，本算法会枚举出4个数+3个运算符能组成的所有组合，每种组合当作后缀表达式构造成为表达式树，得出结果。
枚举所有可能的后缀表达式
枚举所有排列的算法就是套用递归模板。
以24点为例，4个数，必然需要3个运算符。我们的目的就是找到这4数3符的所有排列方式。
第一步：枚举出“从加减乘除四种运算符中拿出三个运算符”的所有情况。
这可不是A43=4这样简单，因为每种运算符可以重复。（比如“+++”、“---”这样）。最简单的办法是无脑枚举出所有情况（4*4*4=64种）然后删除重复的。或者如下面genOpPermute(int n)方法所做的，枚举的过程中剪掉重复的。最终会留下20种组合。
第二步：将枚举出的20种运算符组合与4个数字整合成一个String数组。分别找出20个string数组的全排列。
比如四个数是8，7，4，7，那么我就有了 {8，7，4，7，+，+，+} {8，7，4，7，-，-，-}...等20种组合。对每种组合，我们都要找到其全排列。全排列的算法下面有，注意要避免重复的情况，如8 7 4 7 和 8 7 4 7应算是同一种情况。
package helpers;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class PermuteGen {
private static char[] ops=new char[] {'+','-','*','/'};
/**
* 加减乘除选n个 可重复选 所有选法
* @param n
* @return
*/
public static List<List<Character>> genOpPermute(int n){
ArrayList<Character> tempList=new ArrayList<Character>();
List<List<Character>> ans=new ArrayList<List<Character>>();
opbacktrack(n,tempList,ans,new HashSet<integer>());//用HashSet保存运算符的乘积，已达到去除重复的目的（+*/和*/+算是一种情况，这两种情况三个char的乘积是相同的） return ans;
}
private static void opBacktrack(int n,ArrayList<Character> tempList,List<List<Character>> ans,HashSet<Integer> set) {
if(tempList.size()==n) {
int i=1;
for(char c:tempList) {
i*=c;
}
if(!set.contains(i)) {
ans.add(new ArrayList<Character>(tempList));
set.add(i);
}
}else {
for(int i=0;i<4;i++) {
tempList.add(ops[i]);
opBacktrack(n,tempList,ans,set);
tempList.remove(tempList.size()-1);
}
}
}
/**
* 输出n个String的全排列
* @param n
* @return
*/
public static List<List<String>> genStrPermute(String[] strs){
ArrayList<String> tempList=new ArrayList<String>();
List<List<String>> ans=new ArrayList<List<String>>();
arrays.sort(strs);//先排序，让相同元素相邻
strBacktrack(strs,tempList,ans,new boolean[strs.length]);//由于可能含有重复元素（一次抽出两张2等） 必须有一个数组保存各个元素的访问状态
return ans;
}
private static void strBacktrack(String[] strs,ArrayList<String> tempList,List<List<String>> ans,boolean[] used) {
if(tempList.size()==strs.length) {
ans.add(new ArrayList<String>(tempList));
}else {
for(int i=0;i<strs.length;i++) {
if(!(used[i] || i>0 && strs[i].equals(strs[i-1]) && !used[i-1])) {
//这里的逻辑是：当这个元素已被访问过，则这次不访问
//或者
//两个连续的相同元素 若前一个还没被访问过 后面的坚决不访问！
//这就相当于给这些重复元素规定了内在的顺序，避免了重复！
tempList.add(strs[i]);
used[i]=true;
strBacktrack(strs,tempList,ans,used);
tempList.remove(tempList.size()-1);
used[i]=false;;
}
}
}
}
}
构建表达式树
表达式树没什么特别的，直接用以前作业改。唯一需要注意的点就是，用枚举出的所有组合构建表达式树的过程中一定会出现无法成功建树的情况。比如+++1234一定无法构建表达式树，我们需要对这种情况进行甄别。简单的方法就是看最终构建表达式树的栈是不是只剩下1个结点。如果能在生成全排列的过程中剪枝掉不合格的后缀表达式，本算法甚至不需要用表达式树，不过本算法突出一个简单，最大化利用已有资源，就不考虑那些事情了。
public boolean build (List<String> expr ) // Build tree from prefix expression
{
Stack<ExprTreeNode> nodeStack=new Stack<ExprTreeNode>();
for(int i=0;i<expr.size();i++) {
String c=expr.get(i);
if(isdigit(c)) {
nodeStack.push(new ExprTreeNode(c,null,null));
}
else {
ExprTreeNode left=null;
ExprTreeNode right=null;
try {
left=nodeStack.pop();
right=nodeStack.pop();
}catch(Exception e) {
}
ExprTreeNode opNode=new ExprTreeNode(c,left,right);
nodeStack.push(opNode);
}
}
if(nodeStack.size()==1) {//仅当栈内只有1个节点的时候，表达式树才算构造成功
this.root=nodeStack.pop();
return true;
}
return false;
}
当然，表达式树里还封装了计算出后缀表达式结果的方法。算一下看看是否等于24就可以了！
图形界面
笔者亦制作了配套的图形界面。
不足之处
由于本算法是枚举出所有情况，复杂度相对较高，并且对交换律未作优化，会产生冗余答案，忘读者批评指正！
GitHub: https://github.com/iCeors/24poiots
相关阅读
对前阵子即将上线的细雨算法2.0，百度官方近日给出了针对细雨算法2.0的具体问题的错误示例和整改建议，帮助站长们具体地理解细雨
现代启发式算法 启发式算法（heuristic algorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。启
MD5算法最近看了一个MD5的视频，突然发现MD5挺意思的，所以记录一下代码（写好封装），没准以后要用。也为一些寻找MD5算法的人提供便利。MD
吐槽 国庆假期第二天，去实验室开门，给猫猫铲丑丑，然后给她换猫粮，换水，喂这货吃的emmmmmm，然后今天就把之前在极客时间上买的数据结构与
Metropolis准则——以概率接受新状态 固体退火问题介绍 退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温