用Python破解微软面试题|24点游戏

这是菜鸟学Python的第61篇原创文章

阅读本文大概需要5分钟

 

   

     最近对算法很有兴趣，算法是程序的灵魂，对于普通的程序，学会一些基本的招式，背熟了常见的API的用法，也就可以应付一般的问题，但是对于复杂的问题的处理，要想成为高手，一定要对算法深入了解，算法其实很有意思,大体分链表，队列，栈，树和图的运用，前段时间看到一个微软的面试题，讲的是24点游戏，于是拿来练手，破解一下，很有意思，跟大家分享一下

 

 

1

 

24点游戏的简介

1.24点游戏是老少皆宜的游戏，玩法很简单

1).给玩家4张牌，每张牌面值1-13之间，允许有相同的牌，

2).采用加，减，乘，除四则运算

3).允许有小数

4),可以用括号，但每张牌只能使用一次

 

输入:11,8,3,5

输出:(11-8)*(3+5)=24

 

或者难一点的:

输入:1,7,8,3

输出:3/(1-(7/8)) =24

 

 

2

 

问题初步分析

2.最简单的就是采取暴力破解，穷举法

1).先不考虑括号,因为每个数字只能用一次,对4个数字全排列:4!=4*3*2*1=24

 

2).运算符['+','-','*','/']可以选3个，同一个运算符又可以重复出现，对于每一种排列，总共可以有

4*4*4=64

这样的话，就会有64*24=1536种

 

3).接下来考虑括号，对于4个数字而言，括号插入有两种

• 只含1对括号，比如:

(11-8)*3+5

(11-8*3)+5

11-(8*3)+5

 

• 只含2对括号,在原来第一对括号的情况下，再加一对括号,比如

(11-(8*3))+5

11-((8*3)+5)

 

这样的话会有5种，最后有1536*5=7680种

 

 

3

 

算法的初步构思

3.网上对于24点游戏，破解的算法，大多都是降维

• 就是把4个数字，转换为2个数字的四则运算，然后两两组合计算
• 或者是4个数字降到3个数字，成了3个数字的4个之问题之和。这些算法用C,Java都可以解决

 

有没有什么Python特色的算法呢，我昨天晚上苦苦思索一下，发现Python里面有一个特殊的函数，可以天然的处理这个问题，非常方便.我们来看一下到底怎么破~~

 

Python里面有个函数叫eval,这个函数可以计算表达式:

假如我们有一个字符串s1，是一个表达式

 

s1='1+2+3+4'

print eval(s1)

>>10

 

若带些括号呢，一样可以搞定

s2='(11-(8*3))+5'

print eval(s2)

>>-8

 

 

4

 

算法登场

4.既然eval神器这么牛，那我们只要构造一个表达式就可以了

 

1).那么如何构造呢，先化繁为简,一步一步来

表达式=数字组合

表达式=数字组合+运算符号组合

表达式=数字组合+运算符号组合+1对括号组合

表达式=数字组合+运算符号组合+2对括号组合

 

2).执行eval(表达式)就搞定了

 

 

5

 

具体破解的步骤

5.具体的破解步骤大概分7步，下面我们详细说说

 

1).构造4个数字组合

1,7,8,3这样的数字全排列组合，我们利用Python的内置模块itertools轻松搞定，前面我有一篇问题提到过（九宫格用Python怎么破-14行代码搞定），用法很类似

 

 

2).构造运算符的组合

四则运算符一共有4中加，减，乘，除，用一个3层循环轻松搞定

 

 

 

3).构造数字和运算符的混合表达式

上面2步已经得到了数字组合，运算符组合，接下来把这个两个list再组合一下，形成带数字和运算符的表达式

用zip可以方便的构造，比如：

 

nums=[1,7,8,3]

op=['+', '+', '-']

op.append('')

print zip(nums,op)

>>[(1, '+'), (7, '+'), (8, '-'), (3, '')]

 

以此类推，我们用两个大的for循环构造一个庞大的数字加运算符的表达式

 

 

4).构造带括号的表达式

经过前面3步，一个表达式的雏形已近出来了，接着我们要开始继续装修，添加括弧，先插入第一对括号,其实是两个字符，左括弧'(',右括弧')'.

 

思路是变量一个表达式: 比如8*7-3+1

两次循环，第一次循环，从左到右开始插入'('

然后再来一次，从左到右开始插入'）'

 

 

再构造第二对括号,其实也是两个字符，左括弧'(',右括弧')'.只需要在原来的基础上再来一次，就可以了.

 

 

5).过滤不合法的表达式

其实经过上面4步，已经离成功只差一点点了，因为我们是穷举了所以的表达式，必然会有一些不合法的表达式在列表里面，怎么办，运行的时候编译器会报错啊，如何过滤掉呢

 

比如:

()11-8*3+5

11-8)*(3+5

 

我想到一招，用try/except/else 轻松搞定

 

 

6).考虑到四则运算里面有除法

 

若不引入精确除法:

print 1/8

>>0

这样当我们24点计算的，比如是print eval(3/(1/8))就会报错

 

所以需要引入精确除法:

from __future__ import division

1/8

>>0.125

 

7).经过上面的层层分解，我们最后只需要一行搞定结果

我们把得到的列表，用join形成字符串，然后eval就可以了.

def sum(exp_24_points_list):

exp_24_points_str=''.join(exp_24_points_list)

return eval(exp_24_points_str)

 

看一下结果:

 

输入:NUM_EXAMPLE=[1,7,8,3]

输出：

8*(7-(1+3)) =24

8*(7-3-(1)) =24

3/(1-(7/8)) =24

8*((7-1-3)) =24

(8*(7-3-1)) =24

(8*(7-1-3)) =24

8*((7-3-1)) =24

8*(7-(3+1)) =24

3/(1-7/(8)) =24

(3/(1-7/8)) =24

8*(7-1-(3)) =24

3/((1-7/8)) =24

Total:12

 

 

---

好了破解微软的面试题24点游戏就和大家分享到这里，其实解这道题还有一些高招，构造一个树形表达式，不停的递归，其实算法的世界，就像解数学题，没有最好的解法，只有更妙的解法，只是有的时候需要考虑开销和效率而已.

历史人气文章

一道Google的算法题 |Python巧妙破解

Python写个迷你聊天机器人|生成器的高级用法

九宫格用Python怎么破-14行代码搞定

九九乘法，兔子数列，杨辉三角|用Python生成器的妙解

用Python写个弹球的游戏

用Python来写一个男女相亲小程序|码农的情人节

Python入门原创文章,2016年度大盘点

Google推出Python课堂啦