这题原来在智力题里看过，现在要编程写，情况更一般了，感觉也不一样，要找到内在的规律。
其实规律很简单，对于容量为a的容器A和容量为b的容器B，只要稍稍模拟一下就能发现，两者是严格分开的，即如果采用pour A B，则在同一个解决方案里不可能出现pour B A，下面对其中一种情况给出示意，用(x,y)表示当前两容器内水量：
(0,0)->(a,0)->(0,a)->(a,a)->(0,2a)->(a,2a)->... ;b>2a
->(2a-b,b)->(2a-b,0)->(0,2a-b)->... ;b<2a
...->(na-b,b)->(na-b,0)->(0,na-b)->... ;b<na
由此就可以简单的进行推导，对于pour A B的情况，可能产生的水的容量为：ia+k*(na-b),n=b/a+1,i<=n
对于pour B A的情况，可能产生的水的容量为：b-ia+k*(b-(n-1)a)
具体步骤就略去了，但是注意到可能两种方法都能得到最终的结果，比如3 5 4的情况，因此要判断哪种用的步骤最少，注意到两种方法是对称的，因此可以设计出下面的方法来判断：
while( true ){
c+= a;
d-= a;
if( c> b ){
c-= b;
d+= b;
}
if( d==x ) goto C1;
if( c==x ) goto C2;
}
posted on 2009-04-22 12:31
古月残辉 阅读(287)
评论(0) 编辑 收藏 引用 所属分类:
POJ