首页 > 代码库 > 24点游戏的算法实现
24点游戏的算法实现
根据要求实现一个24点的游戏算法,要求如下:
输入:n1,n2,m1,m2
如果这个四个数的运算结果是24,则输出运算表达式
如11,8,3,5
输出:(11-8)*(3*5)=24
解法一:蛮力法,遍历所有的表达式组合,首先遍历所有的数字的排列组合,然后遍历运算符的组合,然后计算出
这个表达式的值,看其是否等于24
测试输入:
5,5,5,1 3,3,7,73,3,8,81,4,5,6
3,8,8,10 4,,410,10 9,9,6,2 11,8,3,5
#---*--- encoding=utf8 ---*--- ''' Created on 2015-1-4 @author: demaxiya ''' from __future__ import division #实现除法的真除,比如3/8=是一个小数,而不是0 import itertools #实现排列组合的工具函数 def game24_force(arr,n,result_dic={}): ''' 24点游戏的蛮力法 输入一个数字字符数组,输出与n值相等的表达式 ''' result_dic=result_dic # 数组的长度大于等于2,则进一步分解,如果小于2则输出组合的表达式 if len(arr)<2: if len(arr)>0 and round(eval(arr[0]),1)==n: if arr[0] not in result_dic: result_dic[arr[0]]=(arr[0])[1:-1]+" = "+str(n) # 下面的注释是用于调试用的,可以用来打印出所有的组合的表达式 # elif len(arr)>0 and arr[0]=='(8/(3-(8/3)))': # print round(eval(arr[0]),2),float(eval(arr[0])),round((eval(arr[0])))==n else: return result_dic elif len(arr)>=2: nums=itertools.permutations(arr,2) exp=('+','-','*','/') for num in nums: for item in exp: tmp='('+num[0]+item+num[1]+')' if item=='/' and float(eval(num[1]))==0.0: continue arr.remove(num[0]) arr.remove(num[1]) arr.append(tmp) game24_force([item for item in arr],24) arr.remove(tmp) arr.append(num[0]) arr.append(num[1]) # 在计算完子问题后,把之前移除的数给添加到原来的数组中 return result_dic if __name__ == '__main__': arr1=['5','5','5','1'] arr2=['3','3','7','7'] arr3=['9','9','2','6'] arr4=['4','4','10','10'] arr5=['3','8','8','10'] arr6=['1','4','5','6'] arr7=['3','3','8','8'] arr8=['11','3','8','5'] result_dic=game24_force(arr5,24) for item in result_dic.keys(): print result_dic[item]
</pre><p></p><pre>就是这个小程序,纠结了我一天的时间,首先是递归比较难理解和写程序,而且是python的写的递归,没能很快从C和C++中跳出来,
发现python传参数的时候,还是用
[item for item in arr]这个好些,特别是递归程序。
还有就是发现一个神奇的问题,
from __future__ import division xx=eval('8/(3-8/3)') print int(xx)
这个的运行结果竟然是23,估计是int函数的取整导致的,直接舍去小数部分
而且float(xx)==float(24)的结果竟然是false,估计是float的小数的保留位数的原因
还有就是在递归程序中添加全局变量的话,通过默认参数来给,比如result_dic
用round函数来进行四舍五入,python比较时,24==24.00是为True的
话说这个小程序没有做异常处理的,我就懒得加的,如果有报错的话,自己根据报错信息改吧...
24点游戏的算法实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。