必威体育Betway必威体育官网
当前位置:首页 > IT技术

24点算法讲解与实现

时间:2019-09-10 22:11:07来源:IT技术作者:seo实验室小编阅读:67次「手机版」
 

24点算法

题目描述:在52张扑克牌中(去掉大小王),随机抽取4张牌,找到所有可能的情况和解。

前言

博主曾在网上看到有很多关于24点的算法,但很多都是没有找全所有表达式,要么就是没有去重,而且搜索的时间过长,有些慢的要半个小时才能得到结果难过。所以经过我的不懈努力奋斗,经过几天的研究,目前我的这个24点的算法能够高效的找出所有解的情况微笑。经过测试,平均在0.1几秒左右就可以找到所有情况。

算法分析

本算法采用穷举的思路,对所有数字和操作符进行组合,从而找到所有的情况。

首先想想,如果是人来计算24点,应该怎么计算?比如1,2,3,4.  首先我们可能会思考一下,然后得出结果(1+2+3)*4=24。

对,没错,那么现在对上面思考的过程进行仔细分析一下,24是怎么来的?6*4=24,对吧,那么6是怎么来的?6=1+2+3。

现在有个问题,虽然我们一眼就能看出1+2+3=6,但是这个过程还是经过了2步计算,首先我们计算1+2=3,然后在计算3+3=6,然后再计算6*4=24,对吧。也就是说我们会从这4个数中选择2个数来进行计算,然后得到一个结果,在将这个结果与剩下的2个数中选择一个数来计算,简单来说就是就是每次我们只会计算2个数,当然这2个数可能有好几种不同的运算。

下面我们再来看看13,13,13,12这几个数,咋一看这个好像没有上面的数字好算了,不能一下得出结果,这里给出3种解(当然不止3种):(13+13)/(13/12) 和 13-((13/13)-12) 和 (13+12)-(13/13),我们再来想想,每次只运算2个数,直到得出结果。

OK,明白了上面,我们再来分析下计算机是怎么运算的。其实也是同样的思路,每次只运算2个数,然后将结果拿去进行下一次运算。那么现在我们有4个数,如1,2,3,4. 在这4个数位置不变的情况下, 第一次选择2个数来计算,有哪些情况?如果位置不变,那只有3种情况:(1-2)-3-4, 1-(2-3)-4, 1-2-(3-4)(先假设操作符都是-号)。那第2次计算呢,有下面几种情况,如果第1次是(1-2)-3-4,则第2次可能是((1-2))-3-4和(1-2)-(3-4),如果第1次是1-(2-3)-4,则第2次可能是(1-(2-3))-4和1-(2-(3-4)),如果第1次是1-2-(3-4),则第2次可能是(1-2)-(3-4)和1-(2-(3-4)),

然后第3次运算就只剩2个数了,在计算这2个数的结果是不是24就行了。

上面我们假设的是操作符都是-号,但实际情况可能有很多种,现在我们还是在这4个数位置不变的情况下,再来改变操作符,即每次2个数进行运算的时候,有4种情况,即1-2,  1+2,  1*2,  1/2,(在这2个数位置不变的情况下)。那么下次进行计算的时候呢?同样有4种情况(+-*/),最后一次计算(第3次)同理。这样我们就找到了在这4个数位置不变的情况下的所有解的情况。

那么接下来再考虑这4个数位置变化的情况,即1,2,3,4  可以变成4,3,2,1   和1,4,2,3等。同理,当位置变化时,我们按照上面的方法重新计算。这样就可以找出每一种情况啦。这里用的是排列组合,如1,2,3,4有24种不同的排列。

以下是具体代码

public class Expression {
	//用来判断是否有解
	private static boolean flag = false;
	//存放操作符
	private static char[] operator = { '+', '-', '*', '/' };
	//存放所有结果
	private static ArrayList<String> results = new ArrayList<String>();
	
	public static void main(String[] args) {
		//所有正确的解的个数
		int rightCount = 0;
		//所有情况的个数
		int allCount = 0;
		//存放4个数字
		double[] number = new double[4];
		
		long startTime = system.currenttimemillis();
		
	/*	第1次去重,过滤掉可能产生的重复的情况,比如1,2,3,4  和4,3,2,1
		因为后面是通过排列组合来找出所有情况,1,2,3,4可以组合成4,3,2,1
		这样就重复了,这里为了过滤掉这些重复的*/
		for (int i = 1; i <= 13; i++) {
			for (int j = i; j <= 13; j++) {
				for (int k = j; k <= 13; k++) {
					for (int m = k; m <= 13; m++) {
						number[0] = i;
						number[1] = j;
						number[2] = k;
						number[3] = m;
						//由于过滤掉重复的,这里重新计算重复的次数(在计算所有情况的个数时需要)
						//如果你不需要计算所有情况的个数,可以不需要
						int count = times(i, j , k ,m);
						allCount += count;
						duplicateRemoval(number);
						//判断是否有解
						if(flag == true){
							rightCount += count;
							flag = false;
						}
					}
				}
			}
		}
		long endTime = System.currentTimeMillis();
		
		for (int i = 0; i < results.size(); i++) {
			System.out.println(results.get(i));
		}
		System.out.println("共耗费时间:" + (endTime - startTime) + "ms");
		System.out.println("所有可能的个数:" + allCount);
		System.out.println("有解的个数:" + rightCount);
		System.out.println("有解的几率" + (double)rightCount/allCount);
	}
	
	/**
	 * 由于最开始过滤掉一部分重复的情况,但这些重复情况是存在的
	 * 这里是为了计算每种重复情况有多少次数,如当3张牌相同,另一张牌不同时,
	 * 如3,3,3,5  抽牌时有16种不同的情况(根据花色的不同)
	 * 而在计算时为了去重把这些过滤掉了,这里是为了重新计算这些情况
	 * 如果你不需要计算所有情况的个数,可以不需要次方法
	 */
    private static int times(int i,int j,int k,int m){
        //判断有多少种重复
        Set<integer> set = new HashSet<Integer>();
        set.add(i);
        set.add(j);
        set.add(k);
        set.add(m);
        if(set.size() == 1){
        	//当4个数的数字全部一样时(不同花色),只可能有一种组合
            return 1;
        } else if(set.size() == 3){
        	//当4个数中,有两个数相同,其余的数都不相同时
            return 96;
        } else if(set.size() == 4){
        	//当4个数全部不同时
            return 256;
        } else{
            if((i == j && k == m)||(i == k && j == m)||(i == m && k == j)){
            	//当4个数中,两两相同时
                return 36;
            } else {
            	//当4个数中有三个数相同,另外一个数不同时
                return 16;
            }
        }
    }
    
         /**
	 * 第2次去重,由于排列组合可能导致数字组合的重复
	 * 这里进行第2次过滤,只计算给定4个数的所有不同的排列
	 */
	private static void duplicateRemoval(double[] number){
		Map<Double, Integer> map = new HashMap<Double, Integer>();
		//存放数字,用来判断输入的4个数字中有几个重复的,和重复的情况
		for (int i = 0; i < number.length; i++) {
			if(map.get(number[i]) == null){
				map.put(number[i], 1);
			} else {
				map.put(number[i], map.get(number[i]) + 1);
			}
		}
		if(map.size() == 1){
			//如果只有一种数字(4个不同花色的),此时只有一种排列组合,如6,6,6,6
			calculation(number[0], number[1],number[2],number[3]);
		} else if(map.size() == 2){
			//如果只有2种数字,有2种情况,如1,1,2,2和1,1,1,2
			int index = 0;//用于数据处理
			int state = 0;//判断是那种情况
			for (Double key : map.keySet()) {
				if(map.get(key) == 1){
					//如果是有1个数字和其他3个都不同,将number变为 number[0]=number[1]=number[2],
					//将不同的那个放到number[3],方便计算
					number[3] = key;
					state = 1;
				} else if(map.get(key) == 2){
					//两两相同的情况,将number变为number[0]=number[1],number[2]=number[3]的情况,方便计算
					number[index++] = key;
					number[index++] = key;
				} else {
					number[index++] = key;
				}
			}
			//列出2种情况的所有排列组合,并分别计算
			if(state == 1){
				calculation(number[3], number[1], number[1], number[1]);
				calculation(number[1], number[3], number[1], number[1]);
				calculation(number[1], number[1], number[3], number[1]);
				calculation(number[1], number[1], number[1], number[3]);
			}
			if(state == 0){
				calculation(number[1], number[1], number[3], number[3]);
				calculation(number[1], number[3], number[1], number[3]);
				calculation(number[1], number[3], number[3], number[1]);
				calculation(number[3], number[1], number[1], number[3]);
				calculation(number[3], number[3], number[1], number[1]);
				calculation(number[3], number[1], number[3], number[1]);
			}
		} else if(map.size() == 3){
			//有3种数字的情况
			int index = 0;
			for (Double key : map.keySet()) {
				if(map.get(key) == 2){
					//将相同的2个数字放到number[2]=number[3],方便计算
					number[2] = key;
					number[3] = key;
				} else {
					number[index++] = key;
				}
			}
			//排列组合,所有情况
			calculation(number[0], number[1], number[3], number[3]);
			calculation(number[0], number[3], number[1], number[3]);
			calculation(number[0], number[3], number[3], number[1]);
			calculation(number[1], number[0], number[3], number[3]);
			calculation(number[1], number[3], number[0], number[3]);
			calculation(number[1], number[3], number[3], number[0]);
			calculation(number[3], number[0], number[1], number[3]);
			calculation(number[3], number[0], number[3], number[1]);
			calculation(number[3], number[1], number[0], number[3]);
			calculation(number[3], number[1], number[3], number[0]);
			calculation(number[3], number[3], number[0], number[1]);
			calculation(number[3], number[3], number[1], number[0]);
		} else if(map.size() == 4){
			//4个数都不同的情况
			getNumber(number);
		}
	}
	
	/**
	 * 排列组合,用来处理4个数都不同的情况
	 * 如1,2,3,4  可以转化为1,3,2,4   2,3,1,4    1,4,2,3等
	 * 并计算每种的结果
	 */
	public static void getNumber(double[] number){
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if(i == j){
					continue;
				}
				for (int k = 0; k < 4; k++) {
					if(k == j || k == i){
						continue;
					}
					for (int m = 0; m < 4; m++) {
						if(m == k || m == j || m == i){
							continue;
						}
						calculation(number[i], number[j], number[k], number[m]);
					}
				}
			}
		}
	}
	
	/**
	 * 给定4个数,当这4个数位置不变时,只改变操作符号,计算所有的可能性
	 * 如1+2+3+4  ,1*2*3*4 , 1-2+3*4 等
	 * 如果能得到24点,就将表达式添加到结果集
	 */
	public static boolean calculation(double num1, double num2, double num3, double num4){
		for (int i = 0; i < 4; i++) {
		/*	第一次计算,保存此时的操作符和计算结果
			此时有3中情况,相当于从4个数中选择2个相邻的数来计算
			如(1-2)-3-4, 1-(2-3)-4, 1-2-(3-4)
			则保存此时第一次计算的结果和操作符*/
			char operator1 = operator[i];
			//根据操作符,先计算第1,2两个数,如输入数字是1,2,3,4  则计算1+2(1-2,1*2,1/2等),
			//这里通过循环来改变操作符,下同
			double firstResult = calcute(num1, num2, operator1);
			//根据操作符,先计算第2,3两个数,如输入数字是1,2,3,4  则计算2+3
			double midResult = calcute(num2, num3, operator1);
			//根据操作符,先计算第3,4两个数,如输入数字是1,2,3,4  则计算3+4
			double tailResult = calcute(num3, num4, operator1);
			for (int j = 0; j < 4; j++) {
				/*	第2次计算,保存此时的操作符和计算结果
				此时有5中情况,相当于从4个数中选择2个相邻的数来计算
				如((1-2)-3)-4, (1-(2-3))-4, (1-2)-(3-4),1-((2-3)-4),1-(2-(3-4))
				则保存此时第2次计算的结果和操作符*/
				char operator2 = operator[j];
				//根据操作符和第1次计算的结果,计算第2次的情况,如第一次计算是(1-2)-3-4,
				//就计算((1-2)-3)-4 ,则第一次计算结果为1-2=-1  -->   即计算-1-3,即firstResult-3
				//下面的原理类似
				double firstMidResult = calcute(firstResult, num3, operator2);
				double firstTailResult = calcute(num3, num4, operator2);
				double midFirstResult = calcute(num1, midResult, operator2);
				double midTailResult = calcute(midResult, num4, operator2);
				double tailMidResult = calcute(num2, tailResult, operator2);
				for (int k = 0; k < 4; k++) {
					//最后1次计算,得出结果,如果是24则保存表达式,原理同上
					char operator3 = operator[k];
					if(calcute(firstMidResult, num4, operator3) == 24){
						String expression = "((" + (int)num1 + operator1 + (int)num2 + ")" + operator2 + (int)num3 + ")" + operator3 + (int)num4;
						results.add(expression);
						flag = true;
					}
					if(calcute(firstResult, firstTailResult, operator3) == 24){
						String expression = "(" + (int)num1 + operator1 + (int)num2 + ")" + operator3 + "(" + (int)num3 + operator2 + (int)num4 + ")";
						results.add(expression);
						flag = true;
					}
					if(calcute(midFirstResult, num4, operator3) == 24){
						String expression = "(" + (int)num1 + operator2 + "(" + (int)num2 + operator1 + (int)num3 + "))" + operator3 + (int)num4;
						results.add(expression);
						flag = true;
					}
					if(calcute(num1, midTailResult, operator3) == 24){
						String expression = "" + (int)num1 + operator3 + "((" + (int)num2 + operator1 + (int)num3 + ")" + operator2 + (int)num4 + ")";
						results.add(expression);
						flag = true;
					}
					if(calcute(num1, tailMidResult, operator3) == 24){
						String expression = "" + (int)num1 + operator3 + "(" + (int)num2 + operator2 + "(" + (int)num3 + operator1 + (int)num4 + "))";
						results.add(expression);
						flag = true;
					}
				}
			}
		}
		return flag;
	}
	
	/**
	 * 给定2个数和指定操作符的计算
	 * @date 2017年12月22日 下午2:47:49 
	 */
	 private static double calcute(double number1, double number2, char operator) {
	        if (operator == '+') {
	            return number1 + number2;
	        } else if (operator == '-') {
	            return number1 - number2;
	        } else if (operator == '*') {
	            return number1 * number2;
	        } else if (operator == '/' && number2 != 0) {
	            return number1 / number2;
	        } else {
	            return -1;
	        }
	    }

}
这是GitHub:https://github.com/1404510094/24-java-.git

相关阅读

需求管理的两个维度:需求来源管理和需求实现管理

产品经理在平时的工作中有一大部分工作都是在“为客人点菜”——需求管理。一个流传较广的段子,形象地描述了产品经理的角色:你去饭

选择排序(Java代码实现)

每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 选择排序是

U-Mail邮件营销:怎样实现工资条邮件一对一群发

邮件群发不仅仅是可以用来大规模推广商品/服务,实际上,越来越多的企业应用事务性邮件非常频繁,它不仅可用来完善购物流程、提升售后

华渔旗下“普罗米休斯星球”与ClassFlow整合 实现全方

(北京 9月29日)全球领先的互联网教育品牌网龙华渔教育旗下子公司普罗米休斯于9月28日宣布,将&ldquo;普罗米休斯星球&rdquo;这一世

总结 - Ajax工作原理和实现步骤

目录 一 Ajax技术与原理 1.1 Ajax简介 1.2 Ajax所包含的技术 1.3 Ajax的工作原理 1.4 XMLHttpRequest 对象的三个常用的属性 1. o

分享到:

栏目导航

推荐阅读

热门阅读