文档章节

24点游戏算法

自由的角马
 自由的角马
发布于 2015/01/10 13:58
字数 885
阅读 102
收藏 0

24点游戏算法

现在我们在做一个24点的小游戏,我主要负责算法部分,前面有章博客已经讲解了加括号的四则表达式的计算算法,现在要解决就是24点的算法。

24点游戏的说明:

54张牌去掉大小王2张牌,剩余52张。任意发1K之间的4张牌(也就是有1-13的四个数字),用+-*/()连结成算式,使得式子的计算结果为24.

算法描述

24点的算法还处比较复杂的,网上有各种别人写的现成代码,大部分都写的不太好。

 

主要的思想是穷举法,列举出所有4个数字+3个运算符+括号的组合;在计算的过程利用剪枝把一些不可能的情况去除掉。

 

网上有很多算法,主要来讲一下,像以下有几个比较一下。

如:http://843788041.iteye.com/blog/1117558

这种方式没有考虑加括号的情况,不能很好地解决问题

再有:http://www.iteye.com/topic/312476

还是没有完整地解决问题,这里只对前两个数及后两个数进行了加括号,即先计算两个数,再计算后两个数,最后把两个结果进行计算。没有计算的顺序和加括号。

后然还是找到一种比较好的解决方案,基本上可以解决的问题。这算法逻辑比较复杂,但是基本都看懂了,既然已经别人都已经写好了,我就不再花时间了,直接贴代码吗。

 

/**
		 * 他的主要想法是
		 * 先对四个数中的任意两个数进行四则运算,得到的结果加剩余的两个数还有三个数
		 * 再对三个数中的任意两个数进行四则运算,得到的结果加剩余的一个数还有二个数
		 * 再对剩余的两个数进行四则运算,得到的结果如果是24,就说明该表达式能得到24,表达式正确;
		 * 如果结果不是24,则说明表达式不正确
		 * @param n
		 * @return
		 */
		public boolean is24(int n) {
			if (n == 1)
				return (Math.abs(number[0] - 24) < EPISON);
			for (int i = 0; i < n; i++) {
				for (int j = i + 1; j < n; j++) { // 进行组合
					double a, b;
					String expa, expb;
					a = number[i]; // 保存起来,在方法最后再恢复,以便继续计算
					b = number[j]; // 保存起来,在方法最后再恢复,以便继续计算
					number[j] = number[n - 1]; // 将最后一个数挪过来
					expa = exp[i]; // 保存起来,在方法最后再恢复,以便继续计算
					expb = exp[j]; // 保存起来,在方法最后再恢复,以便继续计算
					exp[j] = exp[n - 1]; // 将最后一个式子挪过来j'
					exp[i] = "(" + expa + "+" + expb + ")"; // 看看加法能否算出,如果能算出,返回true
					number[i] = a + b;
					if (is24(n - 1))
						return true;
					exp[i] = "(" + expa + "-" + expb + ")"; // 看看减法能否算
					number[i] = a - b;
					if (is24(n - 1))
						return true;
					exp[i] = "(" + expb + "-" + expa + ")";
					number[i] = b - a;
					if (is24(n - 1))
						return true;
					exp[i] = "(" + expa + "*" + expb + ")"; // 看看乘法能否算
					number[i] = a * b;
					if (is24(n - 1))
						return true;
					if (b != 0) {
						exp[i] = "(" + expa + "/" + expb + ")"; // 看看除法能否算
						number[i] = a / b;
						if (is24(n - 1))
							return true;
					}
					if (a != 0) {
						exp[i] = "(" + expb + "/" + expa + ")";
						number[i] = b / a;
						if (is24(n - 1))
							return true;
					}
					//如果以上的加、减、乘、除都不能得到有效的结果,则恢复数据进行下一轮的计算。 
					number[i] = a; // 恢复
					number[j] = b;
					exp[i] = expa;
					exp[j] = expb;
				}
			}
			return false;
		}

 循环的过程如下


本文转载自:http://blog.csdn.net/luoweifu/article/details/11578457

自由的角马
粉丝 1
博文 269
码字总数 0
作品 0
文山
私信 提问
24点算法

24点是把4个整数(一般是正整数)通过加减乘除运算,使最后的计算结果是24的一个数学游戏 写一个函数,输入4个整形参数,返回运算过程

Soga
2012/09/07
546
2
编写程序实现快速计算《24点》这个游戏的答案

《24点》这个游戏的规则就是 很多人一起玩都可以,桌面上随意翻出4张牌,大家就利用这4张牌分别进行加减乘除运算,不能重复使用每张牌,谁最快算出结果等于24 就赢。 在程序的角度来讲,就是...

曾阿牛弟
2014/06/12
2.9K
1
休闲益智小游戏--calc24

calc24 是使用 JS 实现的计算24点的小游戏 利用四则运算,使得运算结果为24

漂白
2015/02/26
448
0
开源24点数字游戏,联机对战版

经典游戏24点,小时候用扑克牌玩的,做了个联机对战版,目前是抢答模式 规则:4个数,使用四则运算(加减乘除,以及括号),使结果等于24 代码:https://git.oschina.net/664712890/Twenty-...

老陌
2017/02/23
424
0
[深搜回溯]24点

题目描述: 24点是一个有趣的扑克牌游戏。发4张牌,然后计算是否能够算出24点来。(不考虑有括号的算式,输出计算式将从左到有进行计算) 如果可以,输出算数表达式; 如果不可以,输出NONE ...

肥宅_Sean
2017/11/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Boot 2 实战:使用 Spring Boot Admin 监控你的应用

1. 前言 生产上对 Web 应用 的监控是十分必要的。我们可以近乎实时来对应用的健康、性能等其他指标进行监控来及时应对一些突发情况。避免一些故障的发生。对于 Spring Boot 应用来说我们可以...

码农小胖哥
今天
6
0
ZetCode 教程翻译计划正式启动 | ApacheCN

原文:ZetCode 协议:CC BY-NC-SA 4.0 欢迎任何人参与和完善:一个人可以走的很快,但是一群人却可以走的更远。 ApacheCN 学习资源 贡献指南 本项目需要校对,欢迎大家提交 Pull Request。 ...

ApacheCN_飞龙
今天
4
0
CSS定位

CSS定位 relative相对定位 absolute绝对定位 fixed和sticky及zIndex relative相对定位 position特性:css position属性用于指定一个元素在文档中的定位方式。top、right、bottom、left属性则...

studywin
今天
7
0
从零基础到拿到网易Java实习offer,我做对了哪些事

作为一个非科班小白,我在读研期间基本是自学Java,从一开始几乎零基础,只有一点点数据结构和Java方面的基础,到最终获得网易游戏的Java实习offer,我大概用了半年左右的时间。本文将会讲到...

Java技术江湖
昨天
7
0
程序性能checklist

程序性能checklist

Moks角木
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部