24 点算法 python 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
上一篇: C 语言 - 算牌 24 点游戏
下一篇: C# 24 点游戏求解算法(修订版 1)
推荐阅读
-
24 点博弈及其算法--否则 f(S) = ∪ f( ( ( S-{r1, r2}) ∪ {r} ) 对于每个 r = r1 + r2 , r1 - r2 , r1 × r2 , r1 ÷ r2 (r2 ≠ 0) 和 r1, r2 取二进制中 S 的所有元素的组成。
-
JS 编写计算 24 点的算法
-
24 点算法 python 24 点算法的解释和实现
-
反传销网8月30日发布:视频区块链里的骗子,币里的韭菜,杜子建骂人了!金融大V周召说区块链!——“一小帮骗子玩一大帮小白,被割韭菜,小白还轮流被割,割的就是你!” 什么区块链,统统是骗子 作者:周召(知乎金融领域大V,毕业于上海财经大学,目前任职上海某股权投资基金合伙人) 有人问我,区块链现在这么火,到底是不是骗局? 我的回答是: 是骗局。而且我并不是说数字货币是骗局,而是说所有搞区块链的都是骗局。 -01- 区块链是一种鸡肋技术 人类社会任何技术的发明应用,本质都是为了提高社会的生产效率。而所谓区块链技术本质不过是几种早已成熟的技术的大杂烩,冗余且十分低效,除了提高了洗钱和诈骗的效率以外,对人类社会的进步毫无贡献。 真正意义上的区块链得包含三个要素:分布式系统(包括记账和存储),无法篡改的数据结构,以及共识算法,三者互为基础和因果,就像三体世界一样。看上去挺让人不明觉厉的,而经过几年的瞎折腾,稍微懂点区块链的碰了几次壁后都已经渐渐明白区块链其实并没有什么卵用,区块链技术已经名存实亡,沦为了营销工具和传销组织的画皮。 因为符合上述定义的、以比特币为代表的原教旨区块链技术,是反效率的,从经济学角度来说,不但不是一种帕累托改进,甚至还可以说是一种帕累托倒退。 原教旨区块链技术的效率十分低下,因为要遍历所有节点,只能做非常轻量级的数据应用,一旦涉及到大量的数据传输与更新,区块链就瞎了。 一方面整条链交易速度会极慢,另一方面数据库容量极速膨胀,考虑到人手一份的存储机制,区块链其实是对存储资源和能源的一种极大的浪费。 这里还没有加上为了取得所谓的共识和挖矿消耗的巨大的能源,如果说区块链技术是屎,那么这波区块链投机浪潮可谓人类历史上最大规模的搅屎运动。 区块链也验证不了任何东西。 所谓的智能合约,即不智能,也非合约。我看有人还说,如果有了智能合约,就可以跟老板签一份放区块链上,如果明年销售业绩提升30%,就加薪10%,由于区块链不能篡改,不能抵赖,所以老板必须得执行,说得有板有眼,不懂行的愣一看,好像还真是那么回事。 但仔细一想,问题就来了。首先,在区块链上如何证明你真的达到了30%业绩提升?即便真的达到老板耍赖如何执行? 也就是说,如果区块链真这么厉害,要法院和仲裁干什么。 人类社会真正的符合成本效益原则的是代理制度。之前有人说要用区块链改造注册会计师行业,我不知道他准备怎么设计,我猜想他思路大概是这样的,首先肯定搞去中心化,让所有会计师到链上来,然后一个新人要成为注册会计师就要所有会计师同意并记录在链上。 那我就请问了,我每天上班累死累活,为什么还要花时间去验证一个跟我无关的的人的专业能力?最优做法当然是组织一个委员会,让专门的人来负责,这不就是现在注册会师协会干的事儿吗?区块链的逻辑相当于什么事情都要拿出来公投,这个绝对是扯淡的。 当然这么说都有点抬举区块链了,区块链技术本身根本没有判断是非能力,如果这么高级的人工智能,靠一个无脑分布式记账就能实现的话,我们早就进入共产主义社会了。 虽然EOS等数字货币采用了超级节点,通过再中心化的方式提高效率,有点行业协会的意思,是对区块链原教旨主义的一种修正,但是依然无法突破区块链技术最本质的局限性。有人说,私有链和联盟链是区块链技术的未来,也是扯淡,因为区块链技术没有未来。如果有,说明他是包装成区块链的伪区块链技术。 区块链所涉及的所有底层技术,不管是分布式数据库技术,加密技术,还是点对点传输技术等,基本都是早已存在没什么秘密可言的技术。 比特币系统最重要的特性是封闭性和自洽性,他验证不了任何系统自身以外产生的信息的真实性。 所谓系统自身产生的信息,就是数据库数据的变动信息,有价值的基本上有且只有交易信息。所以说比特币最初不过是中本聪一种炫技的产物,来证明自己对几种技术的掌握,你看我多牛逼,设计出了一个像三体一样的系统。因此,数字货币很有可能是区块链从始至终唯一的杀手应用。 比特币和区块链概念从诞生到今天已经快10年了,很多人说区块链技术在爆发的前夜,但这个前夜好像是不是有点过长了啊朋友,跟三体里的长夜有一拼啊。都说区块链技术像是90年代初的互联网,可是90年代初的互联网在十年发展后,已经出现了一大批伟大的公司,阿里巴巴在99年都成立了,区块链怎么除了币还是币呢? 正规的数字货币未来发展的形式无外乎几种,要么就是论坛币形式,或者类似股票的权益凭证等。问题是论坛币和股票之前,本来也都电子化了,区块链来了到底改变了什么呢? 所有想把TOKEN和应用场景结合起来的人最后都很痛苦,最后他们会发现区块链技术就是脱裤子放屁,自己辛苦搞半天,干嘛不自己作为中心关心门来收钱?最后这些人都产生了价值的虚无感,最终精神崩溃,只能发币疯狂收割韭菜,一边嘴里还说着我是个好人之类的奇怪的话。 因此,之前币圈链圈还泾渭分明,互相瞧不起,但这两年链圈逐渐坐不住了,想着是不是趁着泡沫没彻底破灭之前赶快收割一波,不然可能什么都捞不着了。 前段时间和一个名校毕业的链圈朋友瞎聊天,他说他们“致力于用区块链技术解决数字版权保护问题”,我就问他一个问题,你们如何保证你链的版权所有权声明是真实的,万一盗版者抢先一步把数据放在链上怎么办。他说他们的解决方案是连入国家数字版权保护中心的数据库进行验证…… 所以说区块链技术就是个鸡肋,研究到最后都会落入效率与真实性的黑洞,很多人一头扎进链圈后才发现,真正意义上的区块链技术,其实什么都干不了。 -02- 不是蠢就是坏的区块链媒体 空气币和区块链的造富神话,让区块链自媒体也开始迎风乱扭。一群群根本不知道区块链为何物的妖魔鬼怪纷纷进驻区块链自媒体战场,开始大放厥词胡编乱造。 任何东西,但凡只要和区块,链,分,分布式,记账,加密,验证,可追溯等等这些个关键词沾到哪怕一点点,这些所谓的区块链媒体人就会像狗闻到了屎了一样疯狂地把区块链概念往上套。 这让我想起曾经一度也是热闹非凡的物联网,我曾经去看过江苏一家号称要改变世界的“物联网”企业,过去一看是生产路由器的,我黑人问号脸,对方解释说没有路由器万物怎么互联,我觉得他说得好有道理,竟无言以对。 好,下面让我们进入奇葩共赏析时间,来看看区城链媒体经常有哪些危言耸听的奇谈怪论 区块链(分布式记账)的典型应用是*?? 正如前面所说,真正意义上的区块链分布式记账,不光包括“记”这个动作,还包括分布式存储和共识机制等。而*诞生远远早于区块链这个词的出现,勉强算是“分布式编辑”吧,就被很多区块链媒体拿来强行充当区块链技术应用的典范。 其实事实恰恰相反,*恰恰是去中心化失败的典范,现在如果没有精英和专业人士的编辑和维护,*早就没法看了。 区块链会促进社会分工?? 罗振宇好像就说过类似的话,虽然罗振宇说过很多没有逻辑的话,但这句话绝对是最没逻辑思维的。很多区块链自媒体也常常用这句话来忽悠老百姓,说分工代表效率提高社会进步,而区块链“无疑”会促进分工,他们的理由仅仅是分工和分布式记账都共用一个“分”字,就强行把他们扯到一起。 实际情况恰恰相反,区块链是逆分工的,区块链精神是号召所有人积极地参与到他不擅长也不想掺合的事情里面去。 区块链不能像上帝一样许诺他的子民死后上天国,只能给他们许诺你们是六度人脉中的第一级,我可以赚后面五级人的钱,你处于金字塔的顶端。
-
追赶法/托马斯算法在常微分方程两点边值问题中的差分求解、紧差分求解(用 python 代码实现并作图)
-
快速实现24点游戏的24点Python代码
-
点云学习笔记24:加速的DBSCAN聚类算法,Kdtree在其中的作用
-
玩转经典24点游戏:揭秘算法背后的奥秘
-
Python实现24点游戏的计算器
-
Python函数式编程实现24点游戏:学习并使用itertools和yield*