1

一个 Lua 的凑24程序

 2 years ago
source link: https://blog.henix.info/blog/lua-program-solve-24-game/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

一个 Lua 的凑24程序

最后更新日期：2011-02-18

　　上次看到一个“凑24”的题目但想不出来- -b，所以蛋疼地写了个程序来算。。。现在终于知道答案了。。。

　　这个凑24程序没有用搜索或递归之类，想法就是先用逆波兰式枚举所有可能的表达式的形式（这个直接手算枚举），共 5 种：

11+1+1+
11+11++
111++1+
111+1++
1111+++

　　上面是由 4 个数字和 3 个运算符组成的所有合法的逆波兰式的模式。“1”表示一个数字，而“+”表示一个运算符。然后枚举每一个数字和运算符。总枚举量为：5 * 4! * 4^3 = 7680，枚举量很小，所以直接穷举即可。

-- 计算逆波兰式
-- (table) -> number
function evalPo(e)
    local s = {} -- a stack
    local a, b, c
    for i, v in ipairs(e) do
        if type(v) == "number" then
            table.insert(s, v)
        elseif type(v) == "string" then
            if #s < 2 then
                error('not enough values')
            end
            b = table.remove(s)
            a = table.remove(s)
            if v == '+' then
                c = a + b
            elseif v == '-' then
                c = a - b
            elseif v == '*' then
                c = a * b
            elseif v == '/' then
                if b == 0 then
                    return nil, 'divided by 0'
                else
                    c = a / b
                end
            else
                error('bad operator: '..v)
            end
            table.insert(s, c)
        end
    end
    if #s ~= 1 then
        return nil, 'not enough operators'
    end
    return s[1]
end

-- 将逆波兰式转换成普通表达式，用于输出
-- (table) -> string
function RPNtoExp(e)
    local s = {} -- a stack
    local a, b, c
    for i, v in ipairs(e) do
        if type(v) == "number" then
            table.insert(s, v)
        elseif type(v) == "string" then
            if #s < 2 then
                error('not enough values')
            end
            b = table.remove(s)
            a = table.remove(s)
            table.insert(s, '('..a..v..b..')')
        end
    end
    if #s ~= 1 then
        return nil, 'not enough operators'
    end
    return s[1]
end

-- 前4列表示4个数字在逆波兰式中的位置，后3列表示3个运算符在逆波兰式中的位置
-- 这个表是手算出来的
local RPN_patterns = {
    {1, 2, 4, 6, 3, 5, 7},
    {1, 2, 4, 5, 3, 6, 7},
    {1, 2, 3, 6, 4, 5, 7},
    {1, 2, 3, 5, 4, 6, 7},
    {1, 2, 3, 4, 5, 6, 7}
}

local ar = {}
io.write('Please input 4 numbers: ')
for i = 1, 4 do
    ar[i] = io.read('*n')
end

local operators = {'+', '-', '*', '/'}

-- 逆波兰式
local exp = {}

for a = 1, 4 do
    for b = 1, 4 do
        if b ~= a then
            for c = 1, 4 do
                if c ~= a and c ~= b then
                    for d = 1, 4 do
                        if d ~= a and d ~= b and d ~= c then
                            for i = 1, 4 do
                                for j = 1, 4 do
                                    for k = 1, 4 do
                                        for m = 1, 5 do
                                            exp[RPN_patterns[m][1]] = ar[a]
                                            exp[RPN_patterns[m][2]] = ar[b]
                                            exp[RPN_patterns[m][3]] = ar[c]
                                            exp[RPN_patterns[m][4]] = ar[d]
                                            exp[RPN_patterns[m][5]] = operators[i]
                                            exp[RPN_patterns[m][6]] = operators[j]
                                            exp[RPN_patterns[m][7]] = operators[k]
                                            local t = evalPo(exp)
                                            if t == 24 then
                                                io.write(RPNtoExp(exp), '\n')
                                                os.exit()
                                            end
                                        end
                                    end
                                end
                            end
                        end
                    end
                end
            end
        end
    end
end
print('Maze24 has no idea.')

　　如果你的电脑上没有 Lua 解释器，也可以用 codepad 来在线运行这段代码。但 codepad 无法输入，所以你需要稍微修改一下代码：

　　把 ‘Please input 4 numbers:’ 后面的那个 for 循环去掉，改成：

ar = {5, 5, 5, 1}

　　或者填入其他你想要凑 24 的 4 个数字。

　　PS. 顺便附 3 组收藏的凑 24 题目：

  • 6 7 -6 2 // 还负数呢，我勒个去
  • 4 4 10 10

　　如果想不出来，用上面的程序看答案吧:P

评论邮箱 评论帮助

请按照如下格式发邮件：
[email protected]
[复制]
评论 / 回复内容，只支持纯文本

写了个去掉多余括号的版本：https://gist.github.com/rangercyh/43b60594cfd1247cb141

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK