Shell's Home

Jan 20, 2009 - 1 minute read - Comments

24点计算原理和程序

最近开心上狂算24点,于是贝壳搞了一个24点计算程序,并且说明原理。

我们将24点问题一般化,变成一个搜索问题。假定从一个初始表开始,里面有一些原子。我们定义一个操作,结合。每次操作任意从中选择出两个(或者以上)原子,使用算符连接,成为一个新的原子。那么,一般来说,24点就是计算所有可能的路径,从初始表开始,持续进行结合,直到只剩下一个原子,并且对这个原子求值得24。

有人可能在算符优先级上想不开,其实不用考虑这个问题,每次求值的时候,按照求值顺序优先就可以。你想到的另外一种优先级可能,会在穷举的时候被列举出来算掉,不用担心遗漏。

同时,算子必须是两目以上算子,因为单目算子可以持续作用于同一个对象,因此原子表中的原子个数并不严格单调减少,造成无法肯定路径收敛于有限步骤上。并且,如果允许单目算子,那么我只需要求导和阶乘就可以对任何数字求24点。

((a')!+(b')!+(c')!+(d')!)!=24

因此,单目算符是没有意义的。

另外,注意算符分可交换和非可交换的。例如:a+b=b+a,但是a-b!=b-a。如果不注意这点,倒是不会漏算,但是会造成搜索空间增大,并且有重复结果。

以下是24点计算程序,python版本的。有兴趣的朋友可以用scheme重写,相信会更简洁有效。回头会用django封装一下,做成网页给大家玩玩。

#!/usr/bin/python
import sys

symbol_list = [
    ("%s+%s", True),
    ("%s-%s", False),
    ("%s*%s", True),
    ("%s/%s", False),
    ("%s**%s", False),
]


def diff_seq(length):
    for i in range(0, length):
        for j in range(i + 1, length):
            yield (i, j)


def get_less_state(input_state):
    for i, j in diff_seq(len(input_state)):
        temp = input_state[:]
        del temp[j]
        del temp[i]

        for s in symbol_list:
            rslt = s[0] % (input_state[i], input_state[j])
            rslt = "(%s)" % rslt
            temp.append(rslt)
            yield temp
            temp.remove(rslt)
            if s[1]:
                continue
            rslt = s[0] % (input_state[j], input_state[i])
            rslt = "(%s)" % rslt
            temp.append(rslt)
            yield temp
            temp.remove(rslt)


def do_node(input_state, output):
    for i in get_less_state(input_state):
        if len(i) > 1:
            do_node(i, output)
            continue
        try:
            rslt = eval(i[0])
        except:
            continue
        if rslt == 24.0:
            output.add(i[0].replace(".0", ""))


if __name__ == "__main__":
    rslt = []
    for i in sys.argv[1:]:
        rslt.append(float(i))
        output = set([])
        do_node(rslt, output)
        for i in list(output):
            print("%s=24" % i)