现在的位置: 首页 > 综合 > 正文

算24点的算法,个人觉得比网上那些要完善

2018年01月23日 ⁄ 综合 ⁄ 共 1282字 ⁄ 字号 评论关闭

详细代码下载,参见:http://download.csdn.net/source/1632402

先说说我的思路,以四个整数计算24为例,这4个数存放在arr中,分别为arr[0]~arr[3]:
首先是4个数的顺序组合,应该是有以下24种:
arr[0],arr[1],arr[2],arr[3]
arr[0],arr[1],arr[3],arr[2]
arr[0],arr[3],arr[2],arr[1]
arr[0],arr[3],arr[1],arr[2]
arr[0],arr[2],arr[3],arr[1]
arr[0],arr[2],arr[1],arr[3]

arr[1],arr[0],arr[2],arr[3]
arr[1],arr[0],arr[3],arr[2]
arr[1],arr[3],arr[2],arr[0]
arr[1],arr[3],arr[0],arr[2]
arr[1],arr[2],arr[3],arr[0]
arr[1],arr[2],arr[0],arr[3]

arr[2],arr[1],arr[0],arr[3]
arr[2],arr[1],arr[3],arr[0]
arr[2],arr[3],arr[0],arr[1]
arr[2],arr[3],arr[1],arr[0]
arr[2],arr[0],arr[3],arr[1]
arr[2],arr[0],arr[1],arr[3]

arr[3],arr[1],arr[2],arr[0]
arr[3],arr[1],arr[0],arr[2]
arr[3],arr[0],arr[2],arr[1]
arr[3],arr[0],arr[1],arr[2]
arr[3],arr[2],arr[0],arr[1]
arr[3],arr[2],arr[1],arr[0]

然后针对上面的每一种组合,比如:arr[0],arr[1],arr[2],arr[3]
1)计算arr[0]和arr[1]的6种运算结果k1:a+b,a-b,a*b,a/b,    b-a, b/a
2)计算k1和arr[2]的6种运算结果k2
3)计算k2和arr[3]的6种运算结果k3
如果(k3*10)取整=240 (乘10是为了防止24.01和23.99的情况)
就是正确结果,并输出

 不过本程序也还有一些缺点:
1、每一步都加上的括号,可能结果看起来不太好看,呵呵

2、重复结果太多,比如 8,3,1,1的部分结果:
(((1*3)*8)*1) = 24
(((1*3)*1)*8) = 24
(((1*3)*8)/1) = 24
(((1*8)*3)*1) = 24
(((1*8)*3)/1) = 24
(((1*3)/1)*8) = 24
大家可以看到,尤其是第一行和第二行,实际是一样的,程序中该如何处理,我还在思考中,大家有什么意见提提?

3、程序还可以优化,比如1,2,2,3
1和2组合的最大值是1+2=3
此时后两个数的最大组合是2*3=6
那么3和6的最大组合是:3*6=18,不可能=24,所以1和2组合的情况就不应该遍历下去了,以节省时间,
程序中没有实现这一点

抱歉!评论已关闭.