随笔 - 51, 文章 - 1, 评论 - 41, 引用 - 0
数据加载中……

计算24点

      计算24点有不同版本,这里规定:运用加减乘除计算四个整数使它的结果为24。当然这个算法经过适当的修改适合所有的二元运算符,也能计算超过四个整数。
      
计算24点的算法较简单,就是穷举法。由于一般计算表达式含有括号,这使得穷举无从下手。所以本文使用另一种表达式——后缀表达式。 
      后缀表达式就是数字放前运算符放后的表达式。如:a+b表示为a b+,(a+b)*c-d表示为a b + c * d -。用这样表达式可以去掉括号,这对本文的算法很关键。
      任何一个计算24点的算式都可以化成7位的后缀表达式
假设给定的四个整数:a b c d。给定的运算符号集{+,-,*,/}。首先从符号集中取出三个运算符,然后加上a b c d。这七个单位的每一个排列都可以当成一个后缀表达式:或者是不合法的,或者是合法的。穷举并计算这样的排列,就可找出答案。
      上面的方法是先取定7个单位,然后判断这7个单位组成的表达式是否合法。换一种思路,先取定一个合法的表达式,即确定数字和符号的位置,然后确定7个单位,对应数字和符号的位置。
      这两种枚举方法都可行,第二种会快一些,它把判断后缀表达式合法性放在最外层循环,从而省去了不少的判断。
      注:这个里用的枚举集合的方法参见另一篇文章《从集合中枚举子集》
      具体实现见代码
      编译方式:
      g++ Calc24.cpp SetIter.cpp   得到第一种方法。
      g++ Calc24.cpp SetIter.cpp -DCALC24_ADV   得到第二种方法。

posted on 2007-09-21 22:02 lemene 阅读(721) 评论(2)  编辑 收藏 引用

评论

# re: 计算24点  回复  更多评论   

您好!我觉得您的这个关于24点计算的想法很好!我想问个问题,就是说我要第二种方法,事先算出有五种后缀表达式的格式是正确的,之后我应该怎样列举出这些表达式呢?我觉得不停的迭代循环套的层太多了。请问您有什么好方法吗
2012-05-30 03:55 | jjx

# re: 计算24点[未登录]  回复  更多评论   

@jjx
这里只嵌套三层循环:
第一层确定表达式的样式,次数为C(3,7).
第二层确定操作符,次数为P(3,5).
第三层确定数字,如果数字没有相同的,则次数为P(4,4).
2012-06-10 22:22 | lemene

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理