| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3866 人关注过本帖
标题:算法倒水问题,求教高手。
只看楼主 加入收藏
fourleaves
Rank: 2
等 级:论坛游民
帖 子:194
专家分:99
注 册:2010-5-8
结帖率:95.65%
收藏
已结贴  问题点数:20 回复次数:14 
算法倒水问题,求教高手。
好久没来,有时真想休学一年,好好学学算法,离散数学等。
今天来请交大神们,是在算法书上看到的。

题目是:
有装满水的6升的杯子、空的3升杯子和1升杯子,3个杯子中都没有刻度。在不使用其他道具的情况下,是否可以量出4升的水呢?倒水问题的一种方法为:
                      (6,0,0)->(3,3,0)->(3,2,1)->(4,2,0)
   注意:由于没有刻度,用杯子x给杯子y倒水时必须一直把杯子y倒满或者把杯子x倒空,而不能中途停止。
你的任务是解决一般性的问题:设大、中、小3个杯子的容量分别为a,b,c,最初只有大杯子装满水,其他两个杯子为空。最少需要多少步才能让某一个杯子中的水有x升呢?(0<c<b<a<1000)。

Input
   输入数据包括多组数据,每组数据占一行,分别为a,b,c,x,四个数间用一个空格隔开。

Output
   每行输入对应一行输出,即完成目标所需的最小步数。如果不能完成目标,输出"NO"。

Sample Input
6 3 1 4
9 6 3 1

Sample Output
3
NO



我的基本思路是,建立的模型是个树形结构,从头结点开始状态为(a,0,0)。然后用队列按照层拓展下去,这样应该可以求出最少步骤吧?
但是书上分析的是图模型,而且有点不明白边数不超过6*10^6是怎么估算出来的,我只知道结点数是不会超过10^6??求解~
搜索更多相关主题的帖子: 杯子 离散数学 
2013-03-13 21:49
fourleaves
Rank: 2
等 级:论坛游民
帖 子:194
专家分:99
注 册:2010-5-8
收藏
得分:0 

再复杂的问题也基于最简单的原理。耐心,耐心!丰富自己!等待时机!
2013-03-13 21:58
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:10 
这个问题在这里讨论了太多次了。该问题的模型是图,而且是有向图,不是树。只不过应用其上的最短路径搜索算法在搜索过程中去掉了其中的环,相当于广度优先遍历树。

关于节点和边的估算,你的值还是有点粗糙。三个瓶子,每个瓶子的容积是整数升,最多1000升水,抛开倒法不管,最多相当于把1000份相同的水装进3个不同的瓶子里,这不是组合数学里的经典命题么,共有C(1002,2)=501501种。而实际上远比这少。一个状态下可能的倒水方式最多6种(那三个瓶子来回倒呗),也就是每个节点最多6条边,又因为是有向图,所以总边数最多为节点数乘6。

这道原题我好像就做过,好像还在论坛里帖了代码。在百度里搜我的名字加倒水保不齐就能找到。

重剑无锋,大巧不工
2013-03-13 23:37
fourleaves
Rank: 2
等 级:论坛游民
帖 子:194
专家分:99
注 册:2010-5-8
收藏
得分:0 
回复 3楼 beyondyf
谢谢B版了,搜到了。先保存下来。大概浏览下,好简短,觉得思路应该特别清晰,佩服你的功力啊,明天再看,小菜我自己先写写。

再复杂的问题也基于最简单的原理。耐心,耐心!丰富自己!等待时机!
2013-03-13 23:52
shmilyflf
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:5
帖 子:356
专家分:1008
注 册:2012-12-9
收藏
得分:0 
回复 3楼 beyondyf
还真没搜到%%…………
2013-03-13 23:55
shmilyflf
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:5
帖 子:356
专家分:1008
注 册:2012-12-9
收藏
得分:0 
回复 4楼 fourleaves
你肿么搜的?求指教搜索方法¥##¥%……
2013-03-13 23:58
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
呃,其实我也想知道楼主搜到的是哪一篇

重剑无锋,大巧不工
2013-03-14 09:32
oldhouse66
Rank: 2
等 级:禁止发言
帖 子:18
专家分:39
注 册:2013-3-13
收藏
得分:0 
提示: 作者被禁止或删除 内容自动屏蔽

.NET免费视频教程/c#交流学习/qq号:2393938376
2013-03-14 09:36
fourleaves
Rank: 2
等 级:论坛游民
帖 子:194
专家分:99
注 册:2010-5-8
收藏
得分:0 
回复 7楼 beyondyf
https://bbs.bccn.net/viewthread.php?tid=359744&extra=&page=2

不过B版的代码无法编译过啊~。

再复杂的问题也基于最简单的原理。耐心,耐心!丰富自己!等待时机!
2013-03-15 20:46
fourleaves
Rank: 2
等 级:论坛游民
帖 子:194
专家分:99
注 册:2010-5-8
收藏
得分:0 
回复 3楼 beyondyf
b版什么时候在线啊,我把自己写的代码贴出来,能不能赐教。加了大量注释了,不知道有还有没有什么错。

再复杂的问题也基于最简单的原理。耐心,耐心!丰富自己!等待时机!
2013-03-15 21:51
快速回复:算法倒水问题,求教高手。
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.024957 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved