倒水经典问题

xyh · 发表于 2009-1-19 22:07:58

作者：异调www.ddhw.com

倒水经典问题是这样的：

假设有一个池塘，里面有无穷多的水。现有2个空水壶，容积分别为5升和6升。问题是如何只用这2个水壶从池塘里取得3升的水。

这个应该比较容易，大家都会。

那么下面两题有解吗？如果有解请给出解答；如果无解，请给出原因。

1。假设有一个池塘，里面有无穷多的水。现有3个空水壶，容积分别为6升，10升和45升。问题是如何只用这3个水壶从池塘里取得31升的水。

2。假设有一个池塘，里面有无穷多的水。现有2个空水壶，容积分别为65升和78升。问题是如何只用这2个水壶从池塘里取得38升的水。www.ddhw.com

本贴由[xyh]最后编辑于：2009-1-19 14:8:35

开开心心 · 发表于 2009-1-20 01:03:51

1、(10升滿壶X4次+6升滿壶中的5升)水，装满45升壶，6升壶中剩下的1升水

2、先清空45升壶內的水，在用(10升滿壶X3次+6升壶中剩下的1升)水，装入45升壶里，45升壶里就有31升水！

冷眼看戏的Lili · 发表于 2009-1-20 03:08:32

您的（３）的证明无效。反例：有３升和７升两个壶，想要得到５升水，按您的方法，可以“证明”不行，但实际上是可以的。

正确的证明方法之一是：

把１３升叫做１斗，那么现在手头有５斗和６斗两个壶。想要得到３８／１３=２.９２...斗水，......不用俺再说下去啦。

xxxxxxxxxxxxx · 发表于 2009-1-20 04:47:42

太简单了!不要再倒了!

xxxxxxxxxxxxx · 发表于 2009-1-20 04:52:04

第一题有解的!第二题是错误的!

xxxxxxxxxxxxx · 发表于 2009-1-20 05:03:08

第一题:45-16=29

10升桶加入6升水还空4升,将升6灌满倒入,还余2升,后面不写了!

第二题无解!

xxxxxxxxxxxxx · 发表于 2009-1-20 05:03:55

第一题:45-16=29

10升桶加入6升水还空4升,将升6灌满倒入,还余2升,后面不写了!

第二题无解!

0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">

冷眼看戏的Lili · 发表于 2009-1-20 05:13:18

这脑筋一动坛子是老幼皆宜、适合各种不同水平的人来动脑子、找乐趣的地方。俺认为，只要不至于误导，什么水平的动脑问题都可以贴上来。您要是觉得新新大哥的帖子水平低，您可以不做啊。俺水平也不高，所以就跟了个帖子。

只需填入未经注册笔名 · 发表于 2009-1-20 06:06:51

假设有N水壶,容积分别为c1, c2, ..., cn, 整数。。

从池塘里取得W升的水，

等价于

W可以表示成c1, ..., cn的线性组合，系数都是整数。

等价于
GCD（c1, ..., cn）整除 W。

1. GCD(3, 6, 10, 45) = 1, W = 31. yes

2. GCD(65, 78) = 13, W = 38. No

冷眼看戏的Lili · 发表于 2009-1-20 06:24:42

不充分吧。

例如，１升和２升两个水壶，能折腾出５升的水来，但往哪里放呀？再加点条件吧。

只需填入未经注册笔名 · 发表于 2009-1-20 06:49:56

你说的对

只需填入未经注册笔名 · 发表于 2009-1-20 06:51:08

地上挖个坑可以吗？

beisnack · 发表于 2009-1-20 07:52:20

1、78注满倒入65中，剩13

2、65倒空，然后把78中13倒如65中，65中有13

3、78再注满，倒入65中，然后78内还剩26

3、继续把65倒空，然后把78中剩余的26倒如65中，65内有26

4、78再注满，继续倒入65中，这时，78中就剩余39了

beisnack · 发表于 2009-1-20 07:58:30

1、78中注满水，倒入空的65中，78中剩13

2、倒空65，把78中的13倒入65，65中有13

3、78再注满水，然后再次倒入65中，78中还剩26

4、再进行一次，78中就剩39了

xyh · 发表于 2009-1-21 20:19:06

感谢各位的讨论，大家回答都很正确。特别是“只需填入未经注册笔名”，外加“冷眼看戏的Lili®” 的补充，是我最希望看到的结果。也是出这题的最终目的

本贴由[xyh]最后编辑于：2009-1-21 12:47:53

发贴帮助 · 发表于 2009-1-23 21:00:23

6升、10升、45升取31升水
1、将6升、45升两壶装满；

2、从45升壶中两次倒满10升壶；

3、再将6升壶中水倒入45升壶即可

		自动登录	找回密码
密码			立即注册

动态微博

倒水经典问题

（2）6升、10升、45升取31升水

回复：回复：倒水经典问题

回复：倒水经典问题

回复：回复：回复：倒水经典问题

回复：倒水经典问题

答案

俺水平不高[:>]

这个题目跟 GCD有关

等价？[;)]

你说的对[:-Q][:-Q][:-Q][:-Q][:-Q]

开个玩笑

回复：答案

回复：倒水经典问题

看到这么多回复

回复：回复：倒水经典问题