算法倒水问题,求教高手。
好久没来,有时真想休学一年,好好学学算法,离散数学等。今天来请交大神们,是在算法书上看到的。
题目是:
有装满水的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??求解~