十三、Python编程计算24点（之一）

## 十、Python编程计算24点（之一） ----From a high school student's view to learnPython 关键字： python 高中生学编程 Python编程入门 计算24点表达式计算 组合问题 一、问题介绍 对于1-9中任意取出的四个数，找出这四个数组成的所有四则运算表达式，然后从这些表达式中挑出计算结果为24的表达式；对于表达式，不能够重复，如： (1+2+3)*4与(2+1+3)*4只是加法的顺序有些变化，所以只能够算一种。 组合问题、表达式计算的问题在前面的两篇中都进行了详细的介绍，所以，本篇的问题关键就是如何枚举出4个数的表达式组合。 在解决问题之前，提供一个链接，[点此进入](http://www.zhongguosou.com/game_lookup_tools/game_24_point.html)。在网页上输入任意的四个数，就可以列出所有组合，但结果有很多我们在上面所说的重复的情况： [](http://photo.blog.sina.com.cn/showpic.html#blogid=d6cca93e0101eukc&url=http://album.sina.com.cn/pic/d6cca93egx6DdBi4IhU26&690)  如果你输入1 2 34，给出的答案估计有242个，但绝大多数都是顺序变化，再通过加入完全没有必要的()，重复的结果。 所以我们的目的是给出简洁的结果。 二、问题分析 我们将问题分成几种情况来进行讨论，由简到繁： 1、没有括号的表达式 这是最简单的情况，分为两类 加减组合以及全×： -a+-b+-c+-d and a×b×c×d --- 16 这这情况和数的排列顺序没有关系，全减和全除被排除，因为不可能生成24点 2、两个数分组的表达式 这种情况我们处理类似以下的几种类别： (a×b)/(c×/d) (a*/b)+-(c*/d) (a+-b)*/(c+-d) 对于这类分组，我们首先必须清楚一个问题：四个数中两两组合的种类。 四个数中取两个数的组合这很好算，4(2)=4*3/(1*2)=6: ab ac ad bc bd cd 那么两两组合有几种呢，答案是3 (ab) (cd) (ac) (bd) (ad) (bc) 在明确了这个分类之后，对于上面我们列举的几种情况分别处理时就比较简单了，需要注意的是： 1）.分组内【形如(ab)】、组间【形如(ab)与(cd)】的+*是没有顺序但-/是有顺序的，对于有顺序要求的需要处理(ab)(ba)两种情况，注意不要出现重复的情况。 由于我们将数字进行了组合分类，我们只需处理每一类的情况，其余的分类就可以设计循环来处理，每一次的循环我们只是将abcd赋予了不同的数字，这个需要理解清楚。 2）. 分组内(ab) (cd)两个部分中间的符号若是+*，则只有一种情况，但若是-/，则有(ab) (cd) 和(cd) (ab)两种情况，所以要分类讨论。 3、取3个数分组的表达式 这种情况我们处理类似以下的几种类别： (a+-b+-c)*/d    ① a*b*c/d        ② (a+-b*/c)*/d    ③ d/(a+-b*/c)     ④ a*/b*/c+-d 四个数中取三个数的组合是C4(3)=4，但是涉及③④的需要考虑顺序。 同样，我们对于四种组合，只需要处理一种情况，其余的情况由循环来进行处理，每一次的循环abcd的值不同。 尤其针对③④的情况，对于每一组abcd，例如：在处理(a+b/c)/d的情况时，我们只需处理(a+b/c)/d和(a+c/d)/d以及d/(a+b/c)和d/(a+c/d)，其他的情况都将用循环来自动处理 4、情况四a*/b+-c+-d  (a+-b)c*/d  这种情况其实和第二种情况差不多，但是我们为什么又要把它分到另外的一种情况内呢？这又回归上面所说的四个数中两两选择的问题，原先我们认为只有三种，是因为不用考虑重复的情况，但是这种情况下，(ab)(cd) 与 (cd)(ab)是两种不同的情况，我们来举个例子，a*/b+-c+-d与c*/d+-a+-b明显是两种不同结果的组合，所以组合就从三种变为了两种 5、情况五a*b*c/d  这种情况因为十分简单所以就不用利用组合来实现，直接枚举法就可以。 我的更多文章： - [Python程序调试的一些体会](http://blog.sina.com.cn/s/blog_d6cca93e0101ewc9.html)(2013-10-06 22:57:35) - [十四、Python编程计算24点（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101euxx.html)(2013-10-03 22:18:28) - [十二、Python简单数据结构应用（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101euk8.html)(2013-10-02 22:10:41) - [十一、Python简单数据结构应用（之一）](http://blog.sina.com.cn/s/blog_d6cca93e0101ep9z.html)(2013-09-23 23:31:49) - [十、Python编程解决组合问题（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101entc.html) (2013-09-21 23:37:27) - [九、Python编程解决组合问题（之一）](http://blog.sina.com.cn/s/blog_d6cca93e0101ent7.html)(2013-09-21 23:32:54) - [八、Python的函数编程（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101ekwj.html) (2013-09-20 23:09:39) - [七、Python的函数编程（之一）](http://blog.sina.com.cn/s/blog_d6cca93e0101ekwg.html) (2013-09-20 23:09:10) - [六、Python的程序流程](http://blog.sina.com.cn/s/blog_d6cca93e0101ejeg.html)(2013-09-19 16:53:58) - [高中生如何学编程](http://blog.sina.com.cn/s/blog_d6cca93e0101e8fn.html)(2013-09-02 19:26:01)