给1-13中的任意四个数 允许重复,求用四则运算(+-*/)是否能够得到24 ,每个数只能用一次。
利用动态规划求解。从集合划分和合并的角度来计算。用二进制表示集合和子集的概念,a0 a1 a2 a3代表输入的4个数,记录int A[4]为输入的四个数的数组
a0 a1 a2 a3 --0001 代表a3 0010 表示{a2} ,0100表示 {a1}, 1000 表示{a0},1111{a0 a1 a2 a3},a1a3对应{0101}。
则A的子集一共有2^4=16个 其中除去空集一共有15个,除去自身一共有14个非空真子集。。。。(感觉在做高中数学集合)
再定义一个大小为15的集合S[],s[i]中存放的是{f(set(i))},其中f(set(i))存放的是对集合set(i)中的所有元素进行四则运算的结果。
则S[15]即为A中所有元素通过四则运算得到的结果。
当然 很明显 此题的关键在于f(set(i))的实现。
实现代码如下:
package meituan; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; //定义一个集合运算 class Elem{ public double res; public String info; public Elem(double r,String in){ res = r; info =in; } } public class Game_24point { //扑克牌中去除大小王,然后剩余的A-K 代表1-13 任意给出四张牌(当然可以重复) 求是否能计算出24点。可以的话输出计算式 public final int N=4; public final int res = 24; public int [] A; public Map<Integer,Set<Elem>> map; public Set<String> answers; //初始化 public Game_24point(int [] a){ A =a; map = new HashMap<Integer,Set<Elem>>(); answers = new HashSet<String>(); } public void help(){ //0-15 for(int i=0;i<(1<<N);i++){ Set<Elem> set = new HashSet<>(); map.put(i, set); } // a0 a1 a2 a3 --0001 代表a3 0010 a2 0100 a1 1000 a0; for(int i=0;i<N;i++){ Elem e = new Elem(A[i], A[i]+""); Set<Elem> set = new HashSet<>(); set.add(e); map.put(1<<i,set); } for(int i=0;i<(1<<N);i++){ fork(i); } Set<Elem> mset = map.get((1<<N)-1); for(Elem e:mset){ if(e.res==res){ answers.add(e.info); } } if(answers.size()==0) System.out.println("No answers"); else{ for(String s:answers) System.out.println(s); System.out.println("共有"+answers.size()+"个解"); } } public Set<Elem> fork(int m){ Set<Elem> mSet = map.get(m); if(mSet.size()>0) return mSet; else{ for(int x = 1; x <= m ; x++) { if((x&m)==x){ Set<Elem> s1 = fork(x); Set<Elem> s2 = fork(m-x); for(Elem e1: s1) { for(Elem e2:s2) { String str = "("+e1.info+"+"+e2.info+")"; mSet.add(new Elem(e1.res+e2.res, str)); str = "("+ e1.info+"-"+e2.info+")"; mSet.add(new Elem(e1.res-e2.res, str)); str = "("+ e2.info+"-"+e1.info+")"; mSet.add(new Elem(e2.res-e1.res, str)); str = "("+ e1.info+"*"+e2.info+")"; mSet.add(new Elem(e1.res*e2.res, str)); if(e1.res!=0) { str = "("+ e2.info+"/"+e1.info+")"; mSet.add(new Elem(e2.res/e1.res, str)); } if(e2.res!=0){ str = "("+ e1.info+"/"+e2.info+")"; mSet.add(new Elem(e1.res/e2.res, str)); } } } } } return mSet; } } }