阅读本文大概需要15分钟+

开头先讲一下自己的亲身经历，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(把A桶打满)

Fill Y(把B桶打满)

Empty X(把A桶的水倒掉)

Empty Y(把A桶的水倒掉)

然后到了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算法题.