算24点的算法的方法介绍
详细代码下载,参见: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组合的情况就不应该遍历下去了,以节省时间, 程序中没有实现这一点