找回密码
 注册[Register]

QQ登录

只需一步,快速开始

搜索
开启左侧

讨论区 怎么样提高Python编程能力?试试这个经典的24点问题

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?注册[Register]

x
u=3021476997,478649574&fm=26&gp=0.jpg
1. 问题

暑假期间,办公室里经常会出现因无人看护而不得不跟随爸爸妈妈来上班的小朋友。如果不忙的话,我会陪他们一起玩,他们也都很喜欢和我玩。我们都喜欢玩数字游戏。这不,有位小朋友给我出了一道难题:三个5和一个1,只用加减乘除四则运算,每个数字只能且必须使用一次,如何让结果等于24?
这不就是经典的24点问题吗?这个咱拿手啊,从小就玩,小儿科的游戏岂能难倒老许!可是,对于这道题,我尝试了很久,却仍然找不到答案。
“这个题,是不是无解啊?”我试探着问小朋友。
“不是啦,这个题有答案,而且很简单。”小朋友一脸认真。
“好,再给我5分钟。”我赶紧溜进自己办公室,关上门,打开电脑。不用Python,估计是镇不住场子了。

2. 分析

走投无路的时候,穷举也许是最佳选择。4个数字,4种运算符号,外加括号,如何穷尽全部的算式呢?我们把问题分解一下。

2.1 数字

4个数字,每个数字只能且必须使用一次,这是一个排列问题,共有<span class="MathJax" id="MathJax-Element-1-Frame" tabindex="0" style="position: relative;" data-mathml="4×3×2=24      4\times3\times2=24" role="presentation">4×3×2=24
4×3×2=24种排列方案。
Python内置模块itertools提供了排列函数permutations(),可以给出全部的排列方案。如果用ABCD表示4个数字,那么全部的排列如下。
  1. >>> from itertools import permutations
  2. >>> for item in permutations('ABCD'):
  3.                 print(item)
  4.         
  5. ('A', 'B', 'C', 'D')
  6. ('A', 'B', 'D', 'C')
  7. ('A', 'C', 'B', 'D')
  8. ('A', 'C', 'D', 'B')
  9. ('A', 'D', 'B', 'C')
  10. ('A', 'D', 'C', 'B')
  11. ('B', 'A', 'C', 'D')
  12. ('B', 'A', 'D', 'C')
  13. ('B', 'C', 'A', 'D')
  14. ('B', 'C', 'D', 'A')
  15. ('B', 'D', 'A', 'C')
  16. ('B', 'D', 'C', 'A')
  17. ('C', 'A', 'B', 'D')
  18. ('C', 'A', 'D', 'B')
  19. ('C', 'B', 'A', 'D')
  20. ('C', 'B', 'D', 'A')
  21. ('C', 'D', 'A', 'B')
  22. ('C', 'D', 'B', 'A')
  23. ('D', 'A', 'B', 'C')
  24. ('D', 'A', 'C', 'B')
  25. ('D', 'B', 'A', 'C')
  26. ('D', 'B', 'C', 'A')
  27. ('D', 'C', 'A', 'B')
  28. ('D', 'C', 'B', 'A')
复制代码

2.2 运算符号
针对每一种数字排列,我们需要从4种运算符号中允许重复地取出3个,组成一个算式。这个问题幻化成如下描述:有3个篮子,每个篮子里都有4种运算符,从每个篮子里各取1个符号,共有多少种可能?这是一个笛卡尔积的问题,答案是<span class="MathJax" id="MathJax-Element-2-Frame" tabindex="0" style="position: relative;" data-mathml="4×4×4=64      4\times4\times4=64" role="presentation">4×4×4=64
4×4×4=64种可能。
Python内置模块itertools提供了笛卡尔积函数product(),可以给出全部的方案。
  1. >>> from itertools import product
  2. >>> for item in product('+-*/', '+-*/', '+-*/'):
  3.                 print(item)
  4.         
  5. ('+', '+', '+')
  6. ('+', '+', '-')
  7. ('+', '+', '*')
  8. ('+', '+', '/')
  9. ('+', '-', '+')
  10. ('+', '-', '-')
  11. ('+', '-', '*')
  12. ('+', '-', '/')
  13. ('+', '*', '+')
  14. ('+', '*', '-')
  15. ('+', '*', '*')
  16. ('+', '*', '/')
  17. ('+', '/', '+')
  18. ('+', '/', '-')
  19. ('+', '/', '*')
  20. ('+', '/', '/')
  21. ('-', '+', '+')
  22. ('-', '+', '-')
  23. ('-', '+', '*')
  24. ('-', '+', '/')
  25. ('-', '-', '+')
  26. ('-', '-', '-')
  27. ('-', '-', '*')
  28. ('-', '-', '/')
  29. ('-', '*', '+')
  30. ('-', '*', '-')
  31. ('-', '*', '*')
  32. ('-', '*', '/')
  33. ('-', '/', '+')
  34. ('-', '/', '-')
  35. ('-', '/', '*')
  36. ('-', '/', '/')
  37. ('*', '+', '+')
  38. ('*', '+', '-')
  39. ('*', '+', '*')
  40. ('*', '+', '/')
  41. ('*', '-', '+')
  42. ('*', '-', '-')
  43. ('*', '-', '*')
  44. ('*', '-', '/')
  45. ('*', '*', '+')
  46. ('*', '*', '-')
  47. ('*', '*', '*')
  48. ('*', '*', '/')
  49. ('*', '/', '+')
  50. ('*', '/', '-')
  51. ('*', '/', '*')
  52. ('*', '/', '/')
  53. ('/', '+', '+')
  54. ('/', '+', '-')
  55. ('/', '+', '*')
  56. ('/', '+', '/')
  57. ('/', '-', '+')
  58. ('/', '-', '-')
  59. ('/', '-', '*')
  60. ('/', '-', '/')
  61. ('/', '*', '+')
  62. ('/', '*', '-')
  63. ('/', '*', '*')
  64. ('/', '*', '/')
  65. ('/', '/', '+')
  66. ('/', '/', '-')
  67. ('/', '/', '*')
  68. ('/', '/', '/')
复制代码

2.3 括号
针对一个算式,枚举所有添加括号的可能,似乎没有规律。稍加分析,也很容易找到解决方案。我们用N表示数字,用#表示运算符,可能的情况大概有以下11种类型(其中有些是等价的,为了简单起见,我们不再继续优化了)。
  • N # N # N # N
  • (N # N ) # N # N
  • N # N # (N # N)
  • N # (N # N) # N
  • (N # N) # (N # N)
  • (N # N # N) # N
  • ((N # N) # N) # N
  • (N # (N # N)) # N
  • N # (N # N # N)
  • N # ((N # N) # N)
  • N # (N # (N # N))

2.4 计算

数字有24种排列方式,运算符号有64种方案,添加括号有11种可能,则全部可能的算式有<span class="MathJax" id="MathJax-Element-3-Frame" tabindex="0" style="position: relative;" data-mathml="24×64×11=16896      24\times64\times11=16896" role="presentation">24×64×11=16896
24×64×11=16896个。我们只要将每一个字符串形式的算式(表达式)用eval()函数计算结果,就可以找到结果等于24的算式。当然,有些算式可能无意义,比如除数为0的情况。针对无意义的算式,eval()会抛出异常,我们只需捕捉并忽略异常就可以。

3. 答案

有了上面的分析,写代码就成了水到渠成、轻松愉快的事情了。
  1. >>> from itertools import permutations, product
  2. >>> def game24(n1,n2,n3,n4):
  3.                 for a,b,c,d in permutations((n1,n2,n3,n4),4):
  4.                         for o1,o2,o3 in product(['+','-','*','/'], repeat=3): # 笛卡尔积的另一种写法
  5.                                 cases = list()
  6.                                 cases.append('%d%s%d%s%d%s%d'%(a,o1,b,o2,c,o3,d))
  7.                                 cases.append('(%d%s%d)%s%d%s%d'%(a,o1,b,o2,c,o3,d))
  8.                                 cases.append('%d%s%d%s(%d%s%d)'%(a,o1,b,o2,c,o3,d))
  9.                                 cases.append('%d%s(%d%s%d)%s%d'%(a,o1,b,o2,c,o3,d))
  10.                                 cases.append('(%d%s%d)%s(%d%s%d)'%(a,o1,b,o2,c,o3,d))
  11.                                 cases.append('(%d%s%d%s%d)%s%d'%(a,o1,b,o2,c,o3,d))
  12.                                 cases.append('((%d%s%d)%s%d)%s%d'%(a,o1,b,o2,c,o3,d))
  13.                                 cases.append('(%d%s(%d%s%d))%s%d'%(a,o1,b,o2,c,o3,d))
  14.                                 cases.append('%d%s(%d%s%d%s%d)'%(a,o1,b,o2,c,o3,d))
  15.                                 cases.append('%d%s((%d%s%d)%s%d)'%(a,o1,b,o2,c,o3,d))
  16.                                 cases.append('%d%s(%d%s(%d%s%d))'%(a,o1,b,o2,c,o3,d))
  17.                                 for expression in cases:
  18.                                         try: # 捕获表达式中分母为0的异常
  19.                                                 if eval(expression) == 24:
  20.                                                         print('答案:%s = 24'%expression)
  21.                                                         return
  22.                                         except:
  23.                                                 pass
  24.                 print('无解!')
  25.         
  26. >>> game24(5,5,5,1)
  27. 答案:5*(5-1/5) = 24
  28. >>> game24(1,3,4,6)
  29. 答案:6/(1-3/4) = 24
  30. >>> game24(10,10,4,4)
  31. 答案:(10*10-4)/4 = 24
  32. >>> game24(7,7,3,3)
  33. 答案:7*(3/7+3) = 24
  34. >>> game24(1,5,7,10)
  35. 答案:(1+7/5)*10 = 24
  36. >>> game24(15,25,37,80)
  37. 无解!
复制代码

穷举所有变化,速度怎么样?加上时间度量,用上面同样的题目测试,最快5毫秒,最慢(全部穷尽算式)146毫秒。
  1. >>> game24(5,5,5,1)
  2. 答案:5*(5-1/5) = 24,耗时0.011
  3. >>> game24(1,3,4,6)
  4. 答案:6/(1-3/4) = 24,耗时0.117
  5. >>> game24(10,10,4,4)
  6. 答案:(10*10-4)/4 = 24,耗时0.005
  7. >>> game24(7,7,3,3)
  8. 答案:7*(3/7+3) = 24,耗时0.017
  9. >>> game24(1,5,7,10)
  10. 答案:(1+7/5)*10 = 24,耗时0.014
  11. >>> game24(15,25,37,80)
  12. 无解!耗时0.146
复制代码
经过验证,一切都OK了。接下来,就是我在小朋友们面前吹牛的时刻了,你一定能想象得到。
时间太少,能力太小!
您需要登录后才可以回帖 登录 | 注册[Register]

免责声明

    本站资源来自互联网用户收集发布,仅供用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。本站信息来自网络,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容。如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。如有侵权之处,请联系邮箱(jubao@facehoo.cn)并出示版权证明以便删除,敬请谅解!