2842人阅读
原著中给出了两种解法：穷举和分治。后来加上去除冗余括号等操作，自己写了四个实现代码，但完全还是用的原著中的算法思想。暂且把自己的实现过程记录下来。
自己的第一种代码实现，完全穷举，没有任何的优化。代码写得极其笨拙。程序穷举了四个数字能组成的所有可能的算式，分别计算它们的值，找到结果是24的那个算式，输出它。一个不带括号的算式总是有形式a op1 b op2 c op3 d，其中a,b,c,d是运算数，op1,op2,op3是运算符。代码中一个三重循环穷举三个运算符的43种组合，然后在每种组合下再穷举四个运算数的所有4!种排列，这样便得到了一个没有括号的算式。然后穷举五种加括号的形式，逐个判断值是否为24。这个过程中唯一值得回忆和感兴趣的是四个运算数五种不同加括号方式的由来。这是一个经典的Catalan数问题。
这个经典Catalan数问题在组合数学教材上都能找到。原题目是：n 个数相乘, 不改变它们的位置, 只用括号表示不同的相乘顺序，令g(n)表示这种条件下构成不同乘积的方法数，令C(n)表示第n个Catalan数。则有g(n)=C(n-1)。前几个Catalan数为：C(0)=1,C(1)=1,C(2)=2,C(3)=5,C(4)=14,C(5)=42。所以g(4)=C(3)=5。根据Catalan数的计算公式，有g(4)=g(1)g(3)+g(2)g(2)+g(3)g(1)。Catalan数的计算公式也同时提供了构造答案的方法。对于4个数，中间有3个位置，可以在任何一个位置一分为二，被分开的两半各自的加括号方案再拼凑起来就得到一种4个数的加括号方案：
只有一个数时：(A)，一种
两个数：g(2)=g(1)g(1)，所以是(A)(B)=(AB)，一种
三个数：g(3)=g(1)g(2)+g(2)g(1)=(A)(BC)+(AB)(C)，两种
四个数：g(4)=g(1)g(3)+g(2)g(2)+g(3)g(1)
&&&&&&&&&&&&& && =(A)[(B)(CD)+(BC)(D)]+(AB)(CD)+[(A)(BC)+(AB)(C)](D)
&&&&&&&&&&&&& && =A(B(CD)) + A((BC)D) + (AB)(CD) + (A(BC))D + ((AB)C)D
共有五种。于是写代码枚举这五种加括号的方式即可。这种方法只是一种能得到正确答案的方法，扩展性和效率都极差。而且生成的表达式中也有冗余括号。
同样是这种思想，《编程之美》上给出了一种优化的实现方法。一个算术表达式，无论如何复杂，总是按照优先级取出两个运算数进行运算得到一个中间结果，把这个中间结果加入到原表达式中，不断重复这一过程，直到剩下一个数。根据这个思想，可以很快写出实现代码。《编程之美》上即给出了一个完整的代码。
第二种实现的效率和扩展性显然不是第一种能比的。把两个数之间的一次加、减、乘、除看作一次基本运算。那么第一种实现要穷举四种运算符可重复的3组合，有43种，然后4个运算数的全排列，有4!种，之后5种不同的加括号方案，第种括号下要进行3次运算。总共需要做：43*4!*5*3=23040次基本运算。在第二种实现中，假设T(n)表示n个数要进行的基本运算次数，则T(1)=0, T(2) = 6, T(n)=C(n,2)*[6 + 6*T(n-1)]。其中C(n,2)表示n个数中取2个数的组合数。在第二种实现中，对于每一个2-组合，都要做6次基本运算，然后得到6个n-1个数的子问题。所以有上述公式。根据T(n)的公式，T(3)=126, T(4)=4572，所以在第二种实现方法中，穷举4个数的24点问题最多需要做4572次基本运算，这远低于第一种实现的23040次。
第二种实现所需要穷举的基本运算次数公式T(n)写成下面的形式更好看：
例如T(4)=C(4,2)*6+C(4,2)*6*C(3,2)*6+C(4,2)*6*C(3,2)*6*C(2,2)*6，这个形式让人感觉更有规律。那么有个问题：T(n)的最小值是多少？第二种实现有没有冗余计算？对于冗余计算，我觉得应该说，第二种实现可能会产生重复的计算，在4个运算数有重复的时候便会如此，但应该不会重复计算本质上相同的表达式。比如在第一种实现中，当三个运算符都是加的时候，四个数的全排列以及每种全排列下的五种加括号方案所形成的120个表达式都是本质上相同的。
效率的问题由于能力的限制只能止于此了。下面是另一个问题：去除冗余括号。对于去除冗余括号，自己写了两个不同的实现代码。还是像上面一样，不管这个实现的效率有多低，代码有多笨拙，自己只是想验证一下这种想法可以得到正确答案。
自己的第一个去除冗余括号的方法是：先把得到的中缀表达式转化为后缀表达式，这样可以把所有括号都去掉，然后把后缀表达式转化为中缀表达式，判断出必须加括号的情况，加上必要的括号。那么必须加括号的情况是什么呢？对于一个表达式树来说，当子表达式树的优先级严格低于根的优先级时，应该用括号把子表达式保护起来。另外，当根的运算是减号时，右子树为加号或减号的话则应该用括号保护，当根的运算是除法时，右子树如果是乘法或者优先级低于除法的应该保护。初始时运算数的优先级高于所有的优先级，这样可以避免给运算数加上冗余的括号。其实现代码附在最后。
第二个去除冗余括号的方法是：并不是在最后得到结果后才开始统一去除冗余括号，而是在每一步计算中都判断是否应该把子表达式加括号保护。这种方法更简单，效率更高。把《编程之美》原书中解法一的实现代码略做修改即可。完整的实现代码附在最后。
《编程之美》上给出的最后一个解法是用分治的思想。在原著中这个方法讲得非常详细。用一个公式来说就是f(A)=UFork(f(A1), f(A-A1))，其中A1取遍A的所有非空真子集，U表示求集合的并集，f(A)表示集合A中元素进行所有可能的四则混合运算所得到的值(不存在重复)。Fork(A,B)定义为：Fork(A,B)={a+b,a-b,b-a,a*b,a/b(b!=0),b/a(a!=0) | a 属于集合A，b属于集合B}。这个解法另一个值得学习的地方就是代码实现的技巧，从低位起第i个二进制位为1表示第i个数在这个集合中。下面是自己参照《编程之美》最后这种分治法的伪代码写的实现代码：
struct Node {
value = 0;
Node(const string& str, double v) {
bool operator&(const Node& n) const {
return value & n.
} cards[CardsNumber];
set&Node& S[1 && CardsNumber];
// f(i)的作用是求出i代表的那个集合中的所有元素进行四则运算的
// 结果，并将结果存放在S[i]中
void f(int i) {
if(!S[i].empty())
for(int x = 1; x &= (i-x); x++) {
if((x & i) == x) { // 找到一个真子集
f(x); //计算集合x，并将结果存放到S[x]中
f(i-x); //计算集合i-x，并将结果存放到S[i-x]中
set&Node&::iterator it1, it2;
for(it1 = S[x].begin(); it1 != S[x].end(); it1++) {
for(it2 = S[i-x].begin(); it2 != S[i-x].end(); it2++) {
const Node& a = *it1, b = *it2;
S[i].insert(
Node("("+a.exp+"+"+b.exp+")", a.value+b.value));
S[i].insert(
Node("("+a.exp+"-"+b.exp+")", a.value-b.value));
S[i].insert(
Node("("+b.exp+"-"+a.exp+")", b.value-a.value));
S[i].insert(
Node("("+a.exp+"*"+b.exp+")", a.value*b.value));
if(b.value != 0) {
S[i].insert(
Node("("+a.exp+"/"+b.exp+")", a.value/b.value));
if(a.value != 0) {
S[i].insert(
Node("("+b.exp+"/"+a.exp+")", b.value/a.value));
int pre(const char& ch) {
switch(ch) {
return 10;
int f(int n) {
// n表示当前有几个数字
if(n == 1) {
if(cards[0] == Dest) {
cout && exp[0] &&
for(i = 0; i & i++) {
for(j = i+1; j & j++) {
R a = cards[i], b = cards[j];
cards[j] = cards[n-1];
string expa = exp[i], expb = exp[j];
exp[j] = exp[n-1];
int pa = prev[i], pb = prev[j],
prev[j] = prev[n-1];
exp[i] = expa + "+" +
cards[i] = a +
prev[i] = pre('+');
if(f(n-1))
exp[i] = expa + "-";
if(pb &= pre('-'))
exp[i] += "(" + expb + ")";
cards[i] = a -
prev[i] = pre('-');
if(f(n-1))
exp[i] = expb + "-";
if(pa &= pre('-'))
exp[i] += "(" + expa + ")";
cards[i] = b -
prev[i] = pre('-');
if(f(n-1))
p = pre('*');
exp[i] = "(" + expa + ")" + "*";
exp[i] = expa + "*";
if(pb & p)
exp[i] += "(" + expb + ")";
cards[i] = a*b;
if(f(n-1))
if(b.numerator != 0) {
p = pre('/');
if(pa & p)
exp[i] = "(" + expa + ")" + "/";
exp[i] = expa + "/";
if(pb &= p)
exp[i] += "(" + expb + ")";
cards[i] = a/b;
if(f(n-1))
if(a.numerator != 0) {
p = pre('/');
if(pb & p)
exp[i] = "(" + expb + ")" + "/";
exp[i] = expb + "/";
if(pa &= p)
exp[i] += "(" + expa + ")";
cards[i] = b /
if(f(n-1))
cards[i] =
cards[j] =
其中R是自己定义的一个分数类。
上面的代码都只是为了得到结果。其中COUNT()宏是用来统计得到结果所用的基本运算次数。在分治法的实现中，因为集合中不允许有重复元素，所以insert操作不一定总成功，但即使不成功，也进行过一次基本运算，所以计入了总数。自己写程序把以上几种实现代码的输出结果组织成了一个HTML表格，用来对比，如下：
Expression 1
Expression 2
Expression 3
(5-(1/5))*5
(5*(5-(1/5)))
(3+(3/7))*7
(7*(3+(3/7)))
8/(3-(8/3))
(8/(3-(8/3)))
((10*10)-4)/4
(10*10-4)/4
(((10*10)-4)/4)
4/(1-(5/6))
(6/((5/4)-1))
((8*10)-8)/3
(8*10-8)/3
(((8*10)-8)/3)
(9+(9-6))*2
(9*((6/9)+2))
12 5 10 11
Unsolvable
Unsolvable
Unsolvable
(7+(6-5))*3
(7+5)/(3/6)
(3*(7-(5-6)))
12+((9-5)*3)
(12-9+5)*3
(12-(3*(5-9)))
10+(9+(9-4))
(10-((4-9)-9))
12+((8-7)*12)
12-(7-8)*12
(12-((7-8)*12))
9+((7-4)*5)
(9-((4-7)*5))
8+(12+(8-4))
12-(4-8-8)
((8+(12+8))-4)
10+(2*(1*7))
(10+(2/(1/7)))
12*(10/(9-4))
12*10/(9-4)
(12/((9-4)/10))
7+(12+(9-4))
(4+7-9)*12
(4/((9-7)/12))
Unsolvable
Unsolvable
Unsolvable
10 11 10 6
Unsolvable
Unsolvable
Unsolvable
(5+(7-6))*4
(6-4)*(7+5)
(4*((5+7)-6))
Unsolvable
Unsolvable
Unsolvable
(5+(5+2))*2
((5*5)-(2/2))
11 12 10 4
11+(10+(12/4))
11+10+12/4
(11+(10+(12/4)))
(5+(5-4))*4
(4*((5+5)-4))
Unsolvable
Unsolvable
Unsolvable
Unsolvable
Unsolvable
Unsolvable
(2+2)*(12-6)
(6-2)*12/2
(2*(6+(12/2)))
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：459915次
积分：6535
积分：6535
排名：第1205名
原创：182篇
转载：25篇
评论：180条
(1)(10)(2)(12)(3)(5)(3)(5)(2)(1)(6)(8)(4)(5)(2)(6)(20)(9)(5)(9)(7)(15)(8)(9)(5)(25)(1)(3)(12)(4)
() () () () () ()提供各类工作计划书,学生会计划总结,大学生学习计划,大学生学习计划书,大学生学习方法,大学生如何学习,学习生涯规划,大学生应该如何学习 !
您所在的位置：
二十四点游戏技巧
24点游戏技巧
1.利用3&8=24、4&6=24求解。
把牌面上的四个数想办法凑成3和8、4和6,再相乘求解。如3、3、6、10可组成（10-6&3）&3=24等。又如2、3、3、7可组成（7+3-2）&3=24等。实践证明，这种方法是利用率最大、命中率最高的一种方法。
2.利用0、11的运算特性求解。
如3、4、4、8可组成3&8+4-4=24等。又如4、5、J、K可组成11&（5-4）+13=24等。
3.在有解的牌组中，用得最为广泛的是以下六种解法：（我们用a、b、c、d表示牌面上的四个数）
①（a-b）&（c+d）
如（10-4）&（2+2）=24等。
②（a+b）&c&d
如（10+2）&2&4=24等。
③（a-b&c）&d
如（3-2&2）&12=24等。
④（a+b-c）&d
如（9+5-2）&2=24等。
如11&3+l-10=24等。
⑥（a-b）&c+d
如（4-l）&6+6=24等。
所属栏目： &文章来源：& 作者：
>>>更多精彩，请访问大学生校内网 ()首页&&
网站信息推荐
网站相关专题
收藏本站&&
all Rights Reserved. &&你会玩“24点”扑克牌游戏吗？抽出1,4,7,8这四张牌，请使用“+”“-”“*”“/”或括号，组成得数是24算式_百度知道
你会玩“24点”扑克牌游戏吗？抽出1,4,7,8这四张牌，请使用“+”“-”“*”“/”或括号，组成得数是24算式
抽出1你会玩“24点”扑克牌游戏吗，请使用“加”“减”“乘”“除”或括号,7,8这四张牌,4
4×8﹣（7＋1）=24
其他类似问题
按默认排序
其他4条回答
8可组成3×8＋4－4=24等、4、5，每张牌必须用一次且只能用一次、在有解的牌组中，用得最为广泛的是以下六种解法，更不能瞎碰乱凑、J，再相乘求解。如3。计算24点的技巧 “算24点”作为一种扑克牌智力游戏“巧算24点”是一种数学游戏，又如2，实践证明、利用3×8=24，命中率最高的一种方法、便于学习掌握的方法，计算时、3，用加，又如4，9、3、10可组成（10－6÷3）×3=24等、7可组成（7＋3－2）×3=24等，能健脑益智，我们不可能把牌面上的4个数的不同组合形式——去试。 “巧算24点”的游戏内容如下、3，还应注意计算中的技巧问题。 3、11的运算特性求解如3，游戏方式简单易学，8，是一项极为有益的活动，那么算式为（9－8）×8×3或3×8＋（9－8)或（9－8÷8）×3等： 1、b、减，4和6、6，8、乘，这里像大家介绍几种常用的、K可组成11×（5－4）＋13=24等：（我们用a、除（可加括号）把牌面上的数算成24：一副牌中抽去大小王剩下52张（如果初练也可只用1~10这40张牌）任意抽取4张牌（称牌组）、4，这种方法是利用率最大。 利用0、4×6=24求解 把牌面上的4个数想办法凑成3和8，如抽出的牌是3、c
4*8-7-1=24
(7-4)/1*8=24
您可能关注的推广回答者：
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁数据结构课程设计-24点游戏_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
13页免费30页免费56页2下载券30页免费53页3下载券17页免费32页3下载券6页免费2页免费5页免费
喜欢此文档的还喜欢30页免费56页2下载券13页免费2页免费9页免费
数据结构课程设计-24点游戏|
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢