首页 > Uncategorized > [旧文] 暴力求解24点

[旧文] 暴力求解24点

2010年09月3日 留下评论 Go to comments

是真正的暴力求解……穷举法。不过这个问题似乎也没有更好的方法了,各种算法除了暴力的程度,似乎也没有其他本质的区别。

好久没写程序,今天写得这个75%是从网上参考过来的。那个产生所有可能的后缀表达式的算法很漂亮,产生所有排列的函数也很简洁。唯一的缺点是,这个方法会搜索大量重复的表达式,总的搜索空间是全排列数乘上Catalan数,比指数增长还要彪悍。但是对一般4个数的24点,这个低效率还体现不出来。此外,输出的表达式是后缀的,看起来不怎么顺眼。但是后缀转中缀又很麻烦,我就懒得再折腾了。

import sys

def add(a,b):
  return a + b
def sub(a,b):
  return a - b
def mul(a,b):
  return a*b
def div(a,b):
  return float(a)/b

ops = {add:’+‘, sub:’-‘, mul:’*‘, div:’/‘}

def permute(seq):
  seqn = [[seq.pop()]]
  while seq:
    newseq = []
    new = seq.pop()
    for i in range(len(seqn)):
      item = seqn[i]
      for j in range(len(item) + 1):
        newseq.append(item[:j] + [new] + item[j:])
    seqn = newseq
  return seqn

def _exprs(expr, stk_depth, vals, ops):
  if not vals and stk_depth == 1:
    yield expr
  if stk_depth > 1:
    for op in ops:
      for e in _exprs(expr + [op], stk_depth - 1, vals, ops):
        yield e
  if vals:
    for e in _exprs(expr + [vals[0]], stk_depth + 1, vals[1:], ops):
      yield e

def exprs(vals, ops):
  return _exprs([], 0, vals, ops)

def eval(expr):
  stack = []
  for e in expr:
    if callable(e):
      b = stack.pop()
      a = stack.pop()
      try:
        stack.append(e(a, b))
      except ArithmeticError:
        return None
    else:
      stack.append(e)
  return stack[0]

def tostr(expr):
  ret = []
  for e in expr:
    if callable(e):
      ret.append(ops[e])
    else:
      ret.append(str(e))
    ret.append(’ ‘)
  return ”.join(ret)

if __name__ == "__main__":
  vals = [int(x) for x in sys.argv[1]]
  goal = int(sys.argv[2])
  for p in permute(vals):
    for e in exprs(p, ops.keys()):
      if eval(e) == goal:
        print tostr(e)
Advertisements
分类:Uncategorized
  1. 还没有评论。
  1. No trackbacks yet.

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: