题目：倒水算法
1.指定水杯个数；
2.指定各个水杯的容量；
3.指定各水杯的当前水量；
4.倒水时遵循两个原则：a)将杯子倒满；b)将有水的杯子中的水全部倒干净。
5.最后达到指定的水平。
如有4个水杯，每个水杯的容量分别为21、11、8和5，目前装水分别为21、0、0和0，最终要求装水7、7、7和0.
http://www.cnblogs.com/cyq1162/archive/2007/08/07/846552.aspx
//热门智力题 - 打水问题
//基本思想：用小桶容量的倍数对大桶的容量进行取余。
//指导方针：不断用小桶装水倒入大桶，大桶满了立即清空，
//每次判断下二个桶中水的容量是否等于指定容量。
#include<iostream>
#include <vector>
#include<string>
using namespace std;
const string OPERATOR_NAME[7] = {
"装满A桶","装满B桶",
"将A桶清空","将B桶清空",
"A桶中水倒入B桶","B桶中水倒入A桶",
"成功"
};
int main()
{
cout<<"热门智力题 - 打水问题"<<endl;
cout<<" --by MoreWindows( http://blog.csdn.net/MoreWindows )--\n"<<endl;
int a_volume, b_volume, goal_volume;
vector<string> record; //记录操作步数
int ai;
int i, a_water, b_water;
cout<<"请输入A桶容量，B桶容量，目标容量：";
cin>>a_volume>>b_volume>>goal_volume;
a_water = b_water = 0; //A桶，B桶中有多少升水
char szTemp[30];
while (true)
{
if (a_water == 0)//A桶没水,就装满水
{
a_water = a_volume;
sprintf(szTemp, " A:%d B:%d", a_water, b_water);
record.push_back(OPERATOR_NAME[0] + szTemp);//fill A
}
else
{
//如果A桶的水比(B桶容量-B桶的水)要多
if (a_water > b_volume - b_water)
{
//A桶的水==A桶的水+B桶的水-B桶容量
a_water = a_water + b_water- b_volume;
b_water = b_volume; //B桶的水装满了
sprintf(szTemp, " A:%d B:%d", a_water, b_water);
record.push_back(OPERATOR_NAME[4] + szTemp);//A->B
if (a_water == goal_volume)
break;
b_water = 0; //将B桶清空
sprintf(szTemp, " A:%d B:%d", a_water, b_water);
record.push_back(OPERATOR_NAME[3] + szTemp);
}
else
{
//B桶的水==A桶的水+B桶的水
b_water += a_water;
a_water = 0;
sprintf(szTemp, " A:%d B:%d", a_water, b_water);
record.push_back(OPERATOR_NAME[4] + szTemp);//A->B
if (b_water == goal_volume)
break;
}
}
}
record.push_back(OPERATOR_NAME[6]); //success
cout<<"\n---------------------------------------------------"<<endl;
cout<<"一个可行的倒水方案如下"<<endl;
vector<string>::iterator pos;
for (pos = record.begin(); pos != record.end(); pos++)
cout<<*pos<<endl;
cout<<"---------------------------------------------------"<<endl;
return 0;
}
参考：http://www.acmerblog.com/pour-water-problem-5615.html
package
{
public class PourWater
{
public function PourWater()
{
}
public static const TAP:int = -1; // 水龙头
public static const OUT:int = -2; // 倒掉水
public static var vCupWater:Vector.<int>;
public static var vVolume:Vector.<int>;
public static var vTargetState:Vector.<int>;
public static var iTargetWater:int;
public static var iTargetCup:int;
public static var vPath:Vector.<Path>;
public static var bFind:Boolean;
public static function findShortPathEx( targets:Array, cupVolume:Array ):void
{
vCupWater = new Vector.<int>( targets.length );
vTargetState = new Vector.<int>( targets.length );
vVolume = new Vector.<int>( cupVolume.length );
bFind = false;
for ( var i:int = 0; i < targets.length; ++i )
{
vTargetState[i] = targets[i];
vVolume[i] = cupVolume[i];
}
InitBfsState();
}
private static var vvAppearedState:Vector.<Vector.<int>>;
private static var vvBfsQueue:Vector.<Vector.<int>>;
private static var vvBfsPath:Vector.<Vector.<Path>>;
private static var iBfsDepth:int = 15;
public static var iCurSteps:int = 0;
private static function InitBfsState():void
{
vvAppearedState = new Vector.<Vector.<int>>;
vvBfsQueue = new Vector.<Vector.<int>>;
vvBfsPath = new Vector.<Vector.<Path>>;
for ( var i:int = 0; i < vVolume.length; ++i )
{
var tempstate:Vector.<int> = copyState( vCupWater );
pourWater( TAP, i, tempstate );
var tempVPath:Vector.<Path> = new Vector.<Path>;
tempVPath.push( new Path( TAP, i ) );
vvAppearedState.push( copyState( tempstate ) );
vvBfsQueue.push( tempstate );
vvBfsPath.push( tempVPath );
if ( isFind( tempstate ) )
{
vPath = copyPath( tempVPath );
bFind = true;
return;
}
}
bfs();
}
private static function bfs():void
{
while( vvBfsQueue.length > 0 )
{
var tempState:Vector.<int> = vvBfsQueue.shift();
var tempPath:Vector.<Path> = vvBfsPath.shift();
iCurSteps = tempPath.length;
if ( tempPath.length > iBfsDepth )
return;
for ( var i:int = TAP; i < vVolume.length; ++i )
{
for ( var j:int = 0; j < vVolume.length; ++j )
{
if ( i == j )
continue;
var nextState:Vector.<int> = copyState( tempState );
if ( pourWater( i, j, nextState ) && !isAppearedState( nextState ) )
{
var nextPath:Vector.<Path> = copyPath( tempPath );
nextPath.push( new Path( i, j ) );
vvAppearedState.push( copyState( nextState ) );
vvBfsQueue.push( nextState );
vvBfsPath.push( nextPath );
trace("------------------------");
traceCurPath( nextPath );
traceCurState( nextState );
trace("------------------------");
if ( isFind( nextState ) )
{
vPath = copyPath( nextPath );
bFind = true;
return;
}
}
}
}
// 从杯子里往外倒水
for ( i = 0; i < vVolume.length; ++i )
{
nextState = copyState( tempState );
if ( nextState[i] > 0 )
{
nextState[i] = 0;
if ( !isAppearedState( nextState ) )
{
nextPath = copyPath( tempPath );
nextPath.push( new Path( i, OUT ) );
vvAppearedState.push( copyState( nextState ) );
vvBfsQueue.push( nextState );
vvBfsPath.push( nextPath );
}
}
}
tempState.length = 0;
tempPath.length = 0;
tempState = null;
tempPath = null;
}
}
private static function pourWater( iFromCup:int, iToCup:int, vCup:Vector.<int> ):Boolean
{
// 目标满了
if ( vCup[iToCup] == vVolume[iToCup] )
return false;
if ( iFromCup != TAP )
{
// 源是空的
if ( vCup[iFromCup] == 0 )
return false;
// 倒水
if ( vCup[iFromCup] >= ( vVolume[iToCup] - vCup[iToCup] ) )
{
vCup[iFromCup] = vCup[iFromCup] - ( vVolume[iToCup] - vCup[iToCup] );
vCup[iToCup] = vVolume[iToCup];
}
else
{
vCup[iToCup] = vCup[iToCup] + vCup[iFromCup];
vCup[iFromCup] = 0;
}
}
else
vCup[iToCup] = vVolume[iToCup];
return true;
}
private static function isFind( state:Vector.<int> ):Boolean
{
for ( var i:int = 0; i < state.length; ++i )
if ( vTargetState[i] != 0 && vTargetState[i] != state[i] )
return false;
return true;
}
private static function isAppearedState( state:Vector.<int> ):Boolean
{
for ( var i:int = 0; i < vvAppearedState.length; ++i )
if ( isEqualState( state, vvAppearedState[i]) )
return true;
return false;
}
private static function isEqualState( stateSrc:Vector.<int>, stateDes:Vector.<int> ):Boolean
{
for ( var i:int = 0; i < stateSrc.length; ++i )
if ( stateSrc[i] != stateDes[i] )
return false;
return true;
}
private static function copyState( state:Vector.<int> ):Vector.<int>
{
var resState:Vector.<int> = new Vector.<int>( state.length );
for ( var i:int = 0; i < state.length; ++i )
resState[i] = state[i];
return resState;
}
private static function copyPath( path:Vector.<Path> ):Vector.<Path>
{
var resPath:Vector.<Path> = new Vector.<Path>( path.length );
for ( var i:int = 0; i < path.length; ++i )
resPath[i] = new Path( path[i].iCupFrom, path[i].iCupTo );
return resPath;
}
public static function tracePath():String
{
var res:String = "";
if ( bFind )
{
res += "找到长度为" + vPath.length + "的路径！" + "\n";
for ( var i:int = 0; i < vPath.length; ++i )
{
if ( vPath[i].iCupFrom == TAP )
res += vVolume[vPath[i].iCupTo] + "L杯子到水龙头接水！" + "\n";
else if( vPath[i].iCupTo == OUT )
res += vVolume[vPath[i].iCupFrom] + "L杯子倒掉水！" + "\n";
else
res += vVolume[vPath[i].iCupFrom] + "L杯子往"+ vVolume[vPath[i].iCupTo] + "L杯子倒水！" + "\n";
}
}
else
res += "经过深度为" + iCurSteps + "的广度优先搜索，没有找到结果！" + "\n";
return res;
}
public static function traceCurState( state:Vector.<int> ):void
{
var resStr:String = new String;
for ( var i:int = 0; i < state.length; ++i )
resStr += state[i] + "L#" + vVolume[i] + "L杯子,";
trace( resStr );
}
public static function traceCurPath( path:Vector.<Path> ):void
{
var resStr:String = new String;
for ( var i:int = 0; i < path.length; ++i )
{
if ( path[i].iCupFrom == TAP )
resStr += "水龙头" + "->" + vVolume[path[i].iCupTo] + "L杯子,";
else if( path[i].iCupTo == OUT )
resStr += vVolume[path[i].iCupFrom] + "L杯子" + "倒掉水,";
else
resStr += vVolume[path[i].iCupFrom] + "L杯子->" + vVolume[path[i].iCupTo] + "L杯子,";
}
trace( resStr );
}
}
}