开头先讲一下自己的亲身经历,05 年的时候,也就是 12 年前,我去 T 公司面试,当时 T 公司在这个城市非常有名, 有很多高手 (号称小微软). 我当时也是抱着初生牛犊不怕虎,想去会一会. 在通过第一轮的笔试(当时考算法, 程序, 还有 IQ) 和初级面试后,进入第二轮, 来了一个台湾技术经理,问了一些问题之后出了一道题, 要求 3 分钟给出答案,这道题就是今天下面要讲的~~ 这 3 分钟我当时是又惊又囧,10 多年过去了我现在依然记忆犹新(也许我以后会写一篇"10 年了外企面试的那些往事 ")
今天先说正题,没有想到十多年后,我无意中浏览硅谷的一些网站时候,竟然又碰到了这道题,太有缘了. 这次是一个 Google 大牛分析这道题,而且是用 Python 解的 (Python 在 Google 里号称是最喜欢的语言之一), 我觉得太过瘾了, 力道雄厚而刚劲,招式非常巧妙, 我加上自己的理解一起分享给大家.
题目 #翻译成中文:
一个和尚去河边挑水,带了两个桶,一个是能装 4 斤水,一个能装 9 斤水
1), 要求写出算法,目标是如何装出 6 斤水
2), 假设两个桶容量任意,比如 X 斤和 Y 斤, 目标是 Z 斤; 要求写出算法
AB 两个桶: 一个能装 3 斤水,一个能装 5 斤水 => 目标 4 斤
上面只是一个很简单的实例,我相信一个 4 斤水,一个 9 斤,大家也能类似的推导出 6 斤水,只是步骤多一点而已,不是很难.
那么如果用计算机算法来解决任意 X,Y 的问题的, 这个就很有意思了. 我们接着分析~~
二. 好有了这个感性的认识之后,我们开始抽象化,建模成算法.我们发现穷举所有的组合, 无非就这下面 6 种操作:
1.B->A
2.A->B
3.Fill A
4.Fill B
5.Empty A
6.Empty B
假设 A 桶容量是 X,B 桶容量是 Y,A 桶里面倒入的水是 x,B 桶倒入的是 y
数据结构, 很容易就想到我们应该用字典: 我们用元组来表示两个桶的水, 用字符串表示操作步骤
我们先从易到难开始说:
1.Empty B(x,0)=>'Empty Y' #把 B 桶的水倒空
2.Empty A(0,y)=>'Empty X' #把 A 桶的水倒空
3.Fill A(X,y)=>'Fill X' #把 A 桶的水加满
4.Fill B(x,Y)=>'Fill Y' #把 B 桶的水加满
5.A 倒水到 B这个时候分两种情况
1). 若 A 里的水倒入 B,若把 B 倒满了,这个时候 B 就的值 Y,A 倒了 Y-y 的水进入,那么 A 剩下的就是 X-(Y-y)
if x+y>=Y:
(X-(Y-y),Y):"X->Y"
2). 若 A 里的水倒入 B,若没有把 B 倒满了,这个时候 B 的值 x+y,A 为了 0(A 的水已经全部倒进 B 了,还是没有倒满)
if x+y
(0,x+y):"X->Y"
6.B 倒水到 A这个时候分两种情况
1). 若 B 里的水倒入 A,若把 A 倒满了,这个时候 A 就的值 X,B 倒了 X-x 的水进入,那么 B 剩下的就是 Y-(X-x)
if x+y>=X:
(X,Y-(X-x))
2). 若 B 里的水倒入 A,若没有把 A 倒满了,这个时候 A 的值 x+y,B 为了 0(B 的水已经全部倒进 A 了,还是没有倒满)
if x+y
(x+y,0):
三. 好了上面的铺垫之后,我们来进入主旋律我们定义一个函数叫 def solutions(x,y,X,Y), 里面会 return (state,action)
就是我们定义的 6 种情况的数据格式. 所以的操作都在这个 6 种状态机里面转
思路:其实就是 6 步就是 6 个状态机,也就是我们整个的操作始终都在这 6 个状态机里面操作转圈,我们需要做的就是遍历每一种状态机的下一个状态, 除了自己之外一共有 5 种, 看下面的图:
start 是起始状态, 假设起始的时候两桶水都是空的, 然后 start 可以操作如下操作:
然后到了 Fill X 这个状态机之后,又可以有其他 5 种状态,接着转起来,就这样不断的探索下去, 我们举个最简单的例子, 一桶容量是 3 斤的水和一桶容量是 5 斤的水,倒出 4 斤,看一下状态机的图:
经过 6 步,到了第 7 步的时候,就找到了 4 斤的水了. 那么代码的设计是如何呢:1). 存放所有的有效的探索步骤我们用一个 set() 来存,大家有没有注意到每一步里面发散下去,会有重复的状态~~
比如第二次的 (0,5), 和第三次的(0,5) 是一样的,所以我们用 set 很巧妙的过滤掉重复的状态,这样大大优化了我们的代码和搜索的速度.
见如下的图: 红色的实心圈是 set() 要存的,空心的是重复的状态:
set() 里面其实就是存的最后我们搜索到的两个桶的状态:
set([(3, 2), (0, 0), (3, 0), (2, 0), (0, 5), (2, 5), (3, 4), (0, 2), (3, 5)])
若 4 在里面就说明找到了.
2). 外面有一个 while 循环,去遍历所有的状态3). 我们一开始有一个 start 状态比如 (0,0) 进入 solutions 函数,它会返回 6 种状态机,是用字典表示的
4). 我们去判断每一种状态,(state,action), 比如 (3,4,"Y->X"), 如果 4 出现在 state 里面,就算找到了 break 出去
5). 若没有找到,我们继续循环搜索, 大家一定想问 while 的入口是什么, 也是一个列表:
比如 (0,0) 状态下可能要操作的所有步骤 Path:
[[(0, 0), 'fill X', (3, 0)], [(0, 0), 'empty y', (0, 0)], [(0, 0), 'fill Y', (0, 5), 'Y->X', (3, 2), 'empty x', (0, 2), 'Y->X', (2, 0), 'fill Y', (2, 5)]]
6). 每次从这个列表中取一个继续下次的搜索,直到找到目标为止.
看一下结果:一桶 4 斤,一桶 9 斤,如何倒出 6 斤水 [(0, 0), 'fill X', (4, 0), 'X->Y', (0, 4), 'fill X', (4, 4), 'X->Y', (0, 8), 'fill X', (4, 8), 'X->Y', (3, 9), 'empty y', (3, 0), 'X->Y', (0, 3), 'fill X', (4, 3), 'X->Y', (0, 7), 'fill X', (4, 7), 'X->Y', (2, 9), 'empty y', (2, 0), 'X->Y', (0, 2), 'fill X', (4, 2), 'X->Y', (0, 6)]结论:
其实题目并不是很难,关键是解题的思路, 学 Python 招式掌握之后,关键是心法,而心法其实就是算法和软件技巧, 这个没有什么好的诀窍,一半靠悟,一半靠练. 以后我还会分享一些精妙而又有趣的 Python 算法题.
今天也给大家分享几个 Python 的定位:
1, 网站业务逻辑的开发
Python 有一个优良的网页开发框架 django, django 支持各种主流数据库,有好用的 orm 系统和模板系统,完善的第三方库能帮助解决遇到的大部分问题。 并且支持各种操作系统。
2, 数据分析和科学计算
Python 有 numpy,scipy 等一大批科学计算库,有 pandas 数据分析库 还有 matplotlib 等绘图库,在科学计算和数据分析领域已经成为主流语言。
3, 网络爬虫
scrapy 做为 Python 实现的爬虫库,被广泛使用,同时 Python 还拥有 beatifulsoup, pyquery 等 html 解析库 requests 网络库可以用来做爬取和分析用途。
4, 自动化运维
主流的操作系统都集成有 Python, 同时自动化运维领域主流技术栈 saltstack 和 ansible 也是基于 Python 技术开发。可以使用 Python 打造强大的自动化运维工具。
关于自学 Python,个人最大的 3 点经验:
然而,别人的经验未必能完全复制。比如我没有说的是,在自学 Python 之前,我已经系统学习过其他的编程语言。
对于完全没有编程经验的初学者,在学习 Python 的时候,面对的不仅仅是 Python 这门语言,还需要面临 "编程" 的一些普遍问题,比如:
所以除了前面说的 3 点经验,给初学编程者的额外建议:
我是张杨,今天的文章就分享到这里。
来源: http://blog.csdn.net/cH3RUF0tErmB3yH/article/details/78869260