这种题如何编程解决？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3754 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

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

水壶

池塘

题目

34 条回复 • 2014-08-17 14:35:50 +08:00

yangkeao

2014-08-16 20:02:51 +08:00

wikioi上参见博弈，，很能锻炼思维。//这好像已经不是一个东西啦~~不过如果要求是锻炼思维也还是可以

exoticknight

2014-08-16 20:03:06 +08:00

文章写得很好，算法渣渣表示也看得懂！

kmvan

2014-08-16 20:30:11 +08:00 via Android

gcd是什么函数我已经看不懂了

lcj2class

2014-08-16 20:49:52 +08:00

@yangkeao 谢谢分享，以前还真不知道这个平台

lcj2class

2014-08-16 20:50:23 +08:00

@exoticknight 好不敢当，只希望对大家多少有些启发

jok3r

2014-08-16 20:51:45 +08:00

我感觉在OJ上刷题时遇见过类似的，

fishleen

2014-08-16 20:53:33 +08:00 via iPhone

推荐MIT的教程Mathematics for Computer Science里的Number Theory，其中有详细证明为什么能得到X升的线性组合。只要有高中数学基础都能看懂（小学做过类似奥数题目也能看懂）。
CS学到后面都是算法了，没有离散数学基础很难学下去。

ruoyu0088

2014-08-16 20:55:14 +08:00

接下来可以试试三个水桶互相倒水。

Exin

2014-08-16 21:07:31 +08:00

总结里面的代码用的是什么字体？

lcj2class

2014-08-16 21:08:25 +08:00

@jok3r 我在校期间没怎么玩过OJ，发现浪费了4年的大好光阴呀

lcj2class

2014-08-16 21:11:39 +08:00

@fishleen 赞，天天coding是真码农了，记得当年学离散时的群论那部分最爽了，有空再复习下。

lcj2class

2014-08-16 21:13:30 +08:00

@ruoyu0088 你说的是三桶水平分的哪个吗

lcj2class

2014-08-16 21:14:49 +08:00

@Exin 你用firebug看下就知道了

yangff

2014-08-16 21:16:01 +08:00 via Android

dp[i][j]分别表示第一个桶iL水，第二个桶jL水这个状态能否达到。
然后转移就可以了。

yangff

2014-08-16 21:17:20 +08:00 via Android

然后这个转移的过程就是欧几里德算法求gdc啦。。

GtDzx

2014-08-16 21:25:37 +08:00

http://hihocoder.com 有一个活动叫"hiho一下"，会按照一定的知识体系每周详细讲解一道算法题目，并且要求你写出正确的程序。你可以从第一周的题目开始跟着做。每周的题目结束之后，还会公布所有通过的用户的代码供你学习参考。
另外hihocoder明天刚好有一场模拟赛，是给参加google校招的同学准备的。题目难度接近google去年校招的水平，并且都不是那种需要特定算法/数据结构知识才能做的竞赛题，可以尝试一下。

lcj2class

2014-08-16 21:33:47 +08:00

@yangff 用gcd这个是毫无疑问了，你说的数组怎么用我还不清楚，能否赐教

lcj2class

2014-08-16 21:34:42 +08:00

@GtDzx 谢谢分享，有空可以玩玩

Exin

2014-08-16 21:41:32 +08:00

@lcj2class 不好意思没有安装，你能直接告诉我吗？

lcj2class

2014-08-16 21:46:18 +08:00

@Exin font-family="Monaco,Menlo,Consolas,Courier New,monospace"

pljhonglu

2014-08-16 21:55:11 +08:00

见到校友~赞一个~

yangff

2014-08-16 21:57:00 +08:00 via Android

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

lcj2class

2014-08-16 22:25:04 +08:00

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