[技术| 编程·课件·Linux] ACM趣题天天练5 24点游戏

simon3322 · 发布于 2012-08-28 20:57 · 1850 次阅读

24点游戏我想大家都玩过吧？它的具体玩法如下：
给玩家四张牌，每张牌在1~13之间，允许其中有数值相同的牌，通过加减乘除四则运算，运算过程中允许小数，且可以使用括号，但每张牌只能使用一次，尝试构造一个表达式，使其运算结果为24.

具体要求如下。
输入：n1 n2 n3 n4
输出：若能得到运算结果为24，则输出一个表达式。

如:
输入：11,8,3,5
输出：(11-8)*(3+5)=24

注：此题为微软一道面试题，能在有限的面试时间内解出，还是很厉害的。请上传正确程序，或者写明你的算法。

顶分享收藏回复

转载文章时务必注明原作者及原始链接，并注明「发表于软院网 RuanYuan.Net 」，并不得对作品进行修改。

共收到 5 条回复

justcx · #2 · 2012-8-28 23:03:20 回复支持反对

终于更新题目了~先占个沙发

justcx · #3 · 2012-8-28 23:25:48 回复支持反对

本帖最后由 justcx 于 2012-8-28 23:27 编辑

目前才想到个笨方法：第一步：首先4个数字是确定了，4个数字算24不管用不用括号肯定是要用到三个运算符（当然可能重复），也就是说给这4个数字挑选3个运算符（有220种组合）；
               第二步：符号有了，下面就是如果运算了，假设四个数字是A、B、C、D，肯定是经过三步运算就可以得结果的，也就是要先两两组合，然后再把组合运算的结果通过第三个运算符计算得值，4个数字两两组合分组有3种可能（AB和CD、AC和BD、AD和BC）
               第三步：依次给第二步中的三种组合分配第一步中选的3个运算符，每运算一次判断结果是否等于24(这里可以通过判断3个运算符相同的个数来减少次数)；
               第四步：判断格式问题，然后输出表达式；

hslx111 · #4 · 2012-8-29 00:02:13 回复支持反对

上学的时候实验课做的就是这个,当时还有图形化界面,VC6.0啊.
记得当时用的是消元的思想,在4个数中随机选2个数进行运算然后所有结果与剩下的2个数组成N个新的集合,再从集合里选2个数进行计算,结果与剩下的1个数再进行计算.如果计算的结果为24,则输出运算过程.
我们当时做的时候还不允许有多余括号,十分蛋疼= =