您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

常见算法应用实践:24点游戏算法代码实现

时间:2019-07-26 09:30:38  来源:  作者:

24点游戏算法

在现实项目开发应用中,游戏方面的应用程序比较受欢迎,在软件产业中占据了很大的比例。例如24点游戏是一个棋牌类益智游戏,要求结果等于24。在本节中,将详细讲解C语言实现24点游戏的算法。

实例15-2 编程实现24点游戏

问题描述:编写实现24点游戏的C语言程序。

算法分析:其实24点游戏是用4个数字经过数学运行,并得到结果是24的过程。大多数版本应该使用扑克的52张牌(大小王除外),A表示1,K表示13,看任意4张牌是否能够组合得到24。在将4个数进行四则运算时,一般的思维是在4个数中间的3个空放置3个运算符,然后需要在不同的地方加上括号表示优先级的不同。如果仅仅是数字和运算符则很好实现,一旦要添加括号就会变得比较难了。但是后缀表达式可以实现无括号的优先级运算,那么此处使用后缀表达式的这种方法来实现就比较简单了。

在此假设I、J、M、N是4个数,r、s、t是3个运算符。那么使用后缀表达式只有如下4种情况:

(1)I J r M N s t ==> (I r J) t (M s N)

(2)I J r M s N t ==> ((I r J) s M) t N

(3)I J M r s N t ==> (I s (J r M)) t N

(4)I J M N r s t ==> I t (J s (M r N))

上面4种情况分别有1536中可能,4种总计有6144种可能。假如每种情况计算3次,也就20000次计算而已,对计算机来说这个数目是极小的。在实现应用中,没有采用任何取巧的办法,而是每种情况使用了7个for循环进行计算。唯一的取巧是前两种的前边4个for循环是一样,可以将这两种拼接起来。

在处理整数计算时会面对一个问题,计算机无法精确地表示分数,特别是那种无限小数,比如1/3这种。如果不能精确计算,最后就无法判断是否精确等于24,这是计算机的一个弱点。此处的解决方法是,每个数字都用一个int表示,int表示为4字节。由于最大的单个数为13,那么即使是13的连乘也不过28561,不足两个字节能表示的65536。因此使用一个int的低两个字节表示分子或者实际的数值(没有分母,也就等于整个int表示的数),高两个字节表示分母(不存在分母则表示为0)。在做计算时将分子统一为等分母的数,然后计算之后与分母作用得到最后的数。根据上述描述,4/5就表示为0x00050004。

因为找到一种解法就结束,所以根据输入的数据,得到的可能与人工计算得到的结果有出入,比如2 2 6 6,人工计算结果一般为2*6+2*6,但是程序结果可能为(2+6)*(6/2),当然结果也是正确的。另外还需要注意的是,对于任何两个数计算得到负数,并没有继续向下计算,因为这个必须得加一个正数或者乘以一个负数才可能等于24。而既然能够得到负数,两个数的位置调换一下就是一个正数了,没有必要在数值前边加上负号来处理。

具体实现:编写实例文件15-2.c,具体实现代码如下所示。

#include <stdint.h>
#include <unistd.h>
#include <stdio.h>
#define MASK 0xFFFF
#define SHIFT 16
enum {FAILURE = 0, SUCCESS};
const char ops[] = "+*-/";
int test (const int nums[], char *result);
int calculate (int num1, int num2, char op);
int main(int argc, char * argv[])
{
int len = 0;
int nums[4] = {0};
int i;
char *result;
if (argc != 5)
 {
printf("Usage: 24.exe num1 num2 num3 num4n");
exit(1);
 }
for (i = 0 ;i < 4 ;i++ )
 {
len += strlen (argv[i+1]);
nums[i] = atoi (argv[i+1]);
if (nums[i] < 1 || nums[i] > 13)
 {
 printf ("所有的数字都应该是1到13正整数n");
 exit(2);
 }
 }
 /*2 pairs of paren, 3 operators, 1 for NULL. */
len += 4 + 3 + 1;
result = (char *)malloc (len);
if (test(nums, result))
 printf ("%sn", result);
else
 printf ("No Matched.n");
if (result != NULL)
 free (result);
getch();
return 0;
}
/* 测试所有可能的情况,找到一种解法*/
int test (const int nums[], char * result)
{
 int I, J, M, N;
int r, s, t;
int ret, ret1, ret2;
 /*first loop: I J r M N s t ==> (I r J) t (M s N) */
for (I = 0; I < 4; I++)
 {
for (J = 0; J < 4; J++)
 {
if (J == I)
continue;
for (r = 0; r < 4; r++)
 {
 ret1 = calculate (nums[I], nums[J], ops[r]);
if (ret1 <= 0)
 continue;
for (M = 0; M < 4; M++)
 {
if (M == I || M == J)
 continue;
for (N = 0; N < 4; N++)
 {
if (N == I || N == J || N == M)
 continue;
for (s = 0; s < 4; s++)
 {
 ret2 = calculate (nums[M], nums[N], ops[s]);
if (ret2 <= 0)
 continue;
for (t = 0; t < 4; t++)
 {
ret = calculate (ret1, ret2, ops[t]);
if (((ret&MASK)==24) && ((ret>>SHIFT)==0))
 {
 sprintf (result, "(%d%c%d)%c(%d%c%d)", 
 nums[I], ops[r], nums[J], ops[t],
 nums[M], ops[s], nums[N]);
 return SUCCESS;
 }
 }
 }
 }
 /* second loop: I J r M s N t ==> ((I r J) s M) t N */
for (s = 0; s < 4; s++)
 {
 ret2 = calculate (ret1, nums[M], ops[s]);
if (ret2 <= 0)
 continue;
for (N = 0; N < 4; N++)
 {
if (N == I || N == J || N == M)
 continue;
for (t = 0; t < 4; t++)
 {
ret = calculate (ret2, nums[N], ops[t]);
if (((ret&MASK)==24) && ((ret>>SHIFT)==0))
 {
sprintf (result, "((%d%c%d)%c%d)%c%d", 
nums[I], ops[r], nums[J], ops[s],
nums[M], ops[t], nums[N]);
return SUCCESS;
 }
 }
 }
 }
 }
 }
 }
 }
 /* third loop: I J M r s N t ==> (I s (J r M)) t N */
for (I = 0; I < 4; I++)
 {
for (J = 0; J < 4; J++)
 {
if (J == I)
 continue;
for (M = 0; M < 4; M++)
 {
if (M == I || M == J)
 continue;
for (r = 0; r < 4; r++)
 {
 ret1 = calculate (nums[J], nums[M], ops[r]);
if (ret1 <= 0)
 continue;
for (s = 0; s < 4; s++)
 {
 ret2 = calculate (nums[I], ret1, ops[s]);
if (ret2 <= 0)
 continue;
for (N = 0; N < 4; N++)
 {
if (N == I || N == J || N == M)
 continue;
for (t = 0; t < 4; t++)
 {
 ret = calculate (ret2, nums[N], ops[t]);
if (((ret&MASK)==24) && ((ret>>SHIFT)==0))
 {
 sprintf (result, "(%d%c(%d%c%d))%c%d", 
 nums[I], ops[s], nums[J], ops[r],
 nums[M], ops[t], nums[N]);
 return SUCCESS;
 }
 }
 }
 }
 }
 }
 }
 }
 /* forth loop: I J M N r s t ==> I t (J s (M r N)) */
for (I = 0; I < 4; I++)
 {
for (J = 0; J < 4; J++)
 {
if (J == I)
 continue;
for (M = 0; M < 4; M++)
 {
if (M == I || M == J)
 continue;
for (N = 0; N < 4; N++)
 {
if (N == I || N == J || N == M)
 continue;
for (r = 0; r < 4; r++)
 {
 ret1 = calculate (nums[M], nums[N], ops[r]);
if (ret1 <= 0)
 continue;
for (s = 0; s < 4; s++)
 {
 ret2 = calculate (nums[J], ret1, ops[s]);
if (ret2 <= 0)
 continue;
for (t = 0; t < 4; t++)
 {
ret = calculate (nums[I], ret2, ops[t]);
if (((ret&MASK)==24) && ((ret>>SHIFT)==0))
 {
 sprintf (result, "%d%c(%d%c(%d%c%d))", 
 nums[I], ops[t], nums[J], ops[s],
 nums[M], ops[r], nums[N]);
 return SUCCESS;
 }
 }
 }
 }
 }
 }
 }
 }
return FAILURE;
}
/* 计算两个特定的数和操作符的结果*/
int calculate (int num1, int num2, char op)
{
 int numerator_num1, numerator_num2;
 int denominator_num1, denominator_num2;
 int ret = 0;
 int denominator, numerator;
 denominator_num1 = num1 >> SHIFT; //分母
 denominator_num2 = num2 >> SHIFT;
 numerator_num1 = num1 & MASK; //分子
 numerator_num2 = num2 & MASK;
 /* 确定分母,将分子同一化*/
if (denominator_num1 > 0 && denominator_num2 > 0)
 {
 denominator = denominator_num1 * denominator_num2;
 numerator_num1 = denominator_num2 * numerator_num1;
 numerator_num2 = denominator_num1 * numerator_num2;
 }
else if (denominator_num1 > 0 && denominator_num2 == 0)
 {
 denominator = denominator_num1;
 numerator_num2 = denominator_num1 * numerator_num2;
 }
else if (denominator_num1 == 0 && denominator_num2 > 0)
 {
 denominator = denominator_num2;
 numerator_num1 = denominator_num2 * numerator_num1;
 }
else
 {
 denominator = 0;
 }
 /* 计算*/
if (op == '+')
 {
 numerator = numerator_num1 + numerator_num2;
 }
else if (op == '-')
 {
 numerator = numerator_num1 - numerator_num2;
 }
else if (op == '*')
 {
 numerator = numerator_num1 * numerator_num2;
 denominator *= denominator;
 }
else if (op == '/')
 {
if (numerator_num2 > 0 && numerator_num1%numerator_num2 == 0)
 {
 /* 分子可以整除,分母就没有必要了。*/
 numerator = numerator_num1 / numerator_num2;
 denominator = 0;
 }
else
 {
 numerator = numerator_num1;
 denominator = numerator_num2;
 }
 }
if (denominator>0 && numerator%denominator == 0)
 {
 numerator = numerator / denominator;
 denominator = 0;
 }
 ret = (numerator<=0)?numerator:((numerator&MASK) | (denominator<<SHIFT));
 return ret;
}

通过上述算法代码,计算了4个1~13之间的数(包含)是否能够通过加减乘除达到结果为24。执行效果如图15-1所示。

 

常见算法应用实践:24点游戏算法代码实现

24点游戏执行效果



Tags:算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Tags: 算法  点击:(1)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  Tags: 算法  点击:(7)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15  Tags: 算法  点击:(16)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  Tags: 算法  点击:(24)  评论:(0)  加入收藏
基于算法的业务或者说AI的应用在这几年发展得很快。但是,在实际应用的场景中,我们经常会遇到一些非常奇怪的偏差现象。例如,Facebook将黑人标记为灵长类动物、城市图像识别系统...【详细内容】
2021-11-08  Tags: 算法  点击:(32)  评论:(0)  加入收藏
随着注册制的加速推进,新股越来越多,截止到今天A股上市公司的总数高达4500余家,A股一直就是重融资,轻投资的市场,而上市公司发行可转债这种再融资的(圈钱方式)是最能让普通投资者接...【详细内容】
2021-11-05  Tags: 算法  点击:(98)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  Tags: 算法  点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  Tags: 算法  点击:(36)  评论:(0)  加入收藏
每个人都有过这样的经历:打开手机准备回消息或打电话,一看到微信图标右上方的小红点,于是忍不住先打开微信;看完微信,不知不觉又被另一个App牵引,直到关闭手机屏幕才发现自己早已...【详细内容】
2021-11-03  Tags: 算法  点击:(30)  评论:(0)  加入收藏
文丨互联网怪盗团在互联网行业,尤其是在投资人心目中,往往存在一种“算法迷信”或曰“技术迷信”:某公司的广告变现做得好,一定是因为有算法;某公司的云计算业务开展的好,也是因为...【详细内容】
2021-11-03  Tags: 算法  点击:(25)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条