2 qq 21534851 qq_21534851 于 2016.05.10 23:42 提问

倒水算法,c或者c++都可 10C

题目:倒水算法
1.指定水杯个数;
2.指定各个水杯的容量;
3.指定各水杯的当前水量;
4.倒水时遵循两个原则:a)将杯子倒满;b)将有水的杯子中的水全部倒干净。
5.最后达到指定的水平。

如有4个水杯,每个水杯的容量分别为21、11、8和5,目前装水分别为21、0、0和0,最终要求装水7、7、7和0.

3个回答

havedream_one
havedream_one   2016.05.11 08:09
baidu_39301973
baidu_39301973 回复多思心: https://wenku.baidu.com/view/8d43d5ad6aec0975f46527d3240c844769eaa06b.html
6 个月之前 回复
qq_21534851
qq_21534851 感谢回复,对于百度和bing的答案我都看了,目标都是一个杯子的状态,根据网上的代码,我用了一个数组去作为目标水位,用来匹配节点,但没成功
一年多之前 回复
qq423399099
qq423399099   Ds   Rxr 2016.05.11 09:17
 //热门智力题 - 打水问题
//基本思想:用小桶容量的倍数对大桶的容量进行取余。
//指导方针:不断用小桶装水倒入大桶,大桶满了立即清空,
//每次判断下二个桶中水的容量是否等于指定容量。
#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

qq_21534851
qq_21534851 大哥,我对百度上的,博客园的,acm的都看了,目前只看懂了3个杯子求一个杯子的,对于四个杯子求四个杯子的我就不会了
一年多之前 回复
ZGZ1002
ZGZ1002   2016.05.11 13:46

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 );
            }
    }

}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!