这种题如何编程解决？

[lcj2class]

题目要求是这样的：
假设有一个池塘，里面有无穷多的水。现有2个空水壶，容积分别为5升和6升。如何只用这2个水壶从池塘里取得3升的水**（最后，这三升水，在其中一个壶里）


我这里尝试进行了总结，
http://liujiacai.net/blog/2014/08/16/two-pot-question/

大家谁还有这种题目，可以分享出来，我觉得这种题很能锻炼思维，谢谢。

[pljhonglu]

见到校友~赞一个~

[yangff]

@lcj2class 你这样考虑，最开始的时候两个桶都是空的显然是可以的为1，
每个时刻有4种操作可以做，把某个桶装满，把一个桶的水倒进另一个桶。
直接搜索的话当然可以，但是你会发现，如果你已经知道ij这个状态的结果，就不用再去计算了，用数组记一下某个状态是否到达过就可以了，最后可以发现这个转移的过程其实就是在mod x意义下做扩展欧几里德。

[lcj2class]

@yangff 我大概知道你的意思了，那这个数组应该怎么构造呢？

[asmore]

算法表述非常清晰~~

[bengol]

@jok3r hackerrank 出过

[yhf]

acm里一般都会有这种题吧，描述题。

[yangff]

@lcj2class 搜索的时候记录一下当前的ij是否被算过，如果算过了就直接return这样最后得到的就是这个数组了。。

[yangff]

http://codeforces.com/problemset/problem/343/A
这题和你这题做法差不多。。

[heganj]

core.logic

[bombless]

也许可以参考一下张景中的书…他研究的一个方向就是用程序证明几何命题。

[monkeylyf]

gcd

[lcj2class]

@yangff 你这不就是动态规划嘛，不过lisp中一般都是直接用递归或迭代解决问题的，怎么保存中间状态我还不清楚

[yangff]

@lcj2class 囧我写的就是dp啊

[tushiner]

弱弱的说，ACM里面不是有很多这种东东么。。。