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
大约一年之前 回复
qq_21534851
qq_21534851 感谢回复,对于百度和bing的答案我都看了,目标都是一个杯子的状态,根据网上的代码,我用了一个数组去作为目标水位,用来匹配节点,但没成功
大约 2 年之前 回复
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个杯子求一个杯子的,对于四个杯子求四个杯子的我就不会了
大约 2 年之前 回复
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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
倒水问题C++实现
量水问题方案 [量水问题]: 有三个分别装有a升水,b升水,c升水的量筒,其中a,b互质,c>b>a>0,现在c筒装满水,问能否在c筒中量出d升水(c>d>0)。若可以,给出方案。 解答: 所谓模数方程,就是模线性方程,即形如 ax ≡ b (mod c) 形式的方程,其中a,b,c是常数,x是自变量,这个方程表示ax mod c = b  mod c,即ax和b模c同余。 这个量水
经典问题----倒水(详细解析)
倒水   有两个容器,容积分别为A升和B升,有无限多的水,现在需要C升水。 我们还有一个足够大的水缸,足够容纳C升水。起初它是空的,我们只能往水缸里倒入水,而不能倒出。 可以进行的操作是: 把一个容器灌满; 把一个容器清空(容器里剩余的水全部倒掉,或者倒入水缸); 用一个容器的水倒入另外一个容器,直到倒出水的容器空或者倒入水的容器满。     问是否能够通过有限次操作,使得水缸最后恰好有C升水。
倒水问题(算法挑战)
我想我们都做过这么一道题: 有两个容器,容积分别为A升和B升,有无限多的水,现在需要C升水。 我们还有一个足够大的水缸,足够容纳C升水。起初它是空的,我们只能往水缸里倒入水,而不能倒出。 可以进行的操作是: 把一个容器灌满; 把一个容器清空(容器里剩余的水全部倒掉,或者倒入水缸); 用一个容器的水倒入另外一个容器,直到倒出水的容器空或者倒入水的容器满。 问是否能够通过有限次操作,使得
算法实战6:倒水问题
题目详情 有两个容器,容积分别为A升和B升,有无限多的水,现在需要C升水。 我们还有一个足够大的水缸,足够容纳C升水。起初它是空的,我们只能往水缸里倒入水,而不能倒出。 可以进行的操作是: 把一个容器灌满; 把一个容器清空(容器里剩余的水全部倒掉,或者倒入水缸); 用一个容器的水倒入另外一个容器,直到倒出水的容器空或者倒入水的容器满。     问是否能够通过有
倒水问题(三个水杯)
设大,中,小3个杯子的容量分别为a,b,c,最初只有大杯子装满水,其他两个杯子为空。最少需要多少步才能让某一个杯子中的水有x升呢?你需要打印出每步操作后各个杯子中的水量 /* 因为给出条件后3个杯子中水的总量同时确定,所以可以减少用于记录的数组维数。使用递归的方法遍历可能经过的所有路径并记录可到达的最短步数 */ #include #include using namespace std; s
对于"容量分别为A与B的两个水桶,是否能够通过互相倒水可以得到1~MAX(A,B)所有容量的水"问题的分析
    此问题与数论息息相关,结论如下:对于所有最大公因数为1 的A,B,都能产生任意的1~max(A,B)之间的容量,反之则不成立。证明:先证明一个需要用到的数论中的定理如果a,b为任意整数,但不全为0,那么a,b的最小公约数为满足s = ax+by (x,y 为任意整数)的最小的正整数s。证明如下:令s = ax + by (x,y为任意整数)的最小正整数,令q=floor(a/s),那么有如
【BFS练习】倒水问题程序源代码(pascal)
题目: 有三个分别容量分别为a升、b升和c升的杯子(c>b>a>0,且b与a互质) 初始时:c杯装满水有10升,a与b均为空,容量分别为:3升、7升。 规则: 1、三个杯子相互倒水且不准把水倒往三个杯子之外, 2、每次倒水必须是把目标杯装满或是倒出水的杯子已空才能停止。 要求:给出各杯子的容量,请用最少的倒水次数,使C杯中剩余d升水。 程序:
【面试题】:两水桶倒水问题
如果你有无穷多的水,一个3 公升的提捅,一个5 公升的提捅,两只提捅形状上下都不均 匀,问你如何才能准确称出4 公升的水?嘿嘿,这个问题特别的考思路- -大致是能拼出来4的 5 + 5 -3*2 = 4,大致就是这个思路解出来这个题的 那就是 5倒进 3里面 剩 2 然后 3倒光,把5里面剩的 2倒进3里面 这时候:3里面剩 2 升水把5倒满,然后用5的水把3倒满,这时候 5 里面剩 4L
3个水杯倒水问题(广度优先搜索)
三个水杯 时间限制:1000 ms  |  内存限制:65535 KB 难度:4 描述给出三个水杯,大小不一,并且只有最大的水杯的水是装满的,其余两个为空杯子。三个水杯之间相互倒水,并且水杯没有标识,只能根据给出的水杯体积来计算。现在要求你写出一个程序,使其输出使初始状态到达目标状态的最少次数。 输入第一行一个整数N(0 接下来每组测试数据有两行,第一行给出三
倒水问题题解(勿喷)
倒水问题 总时间限制: 1000ms内存限制: 65536kB 描述 有三个分别容量分别为a升、b升和c升的杯子(a>b>c>0,且b与c互质)。 a杯装满水,b与c均为空。 三个筒相互倒水且不准把水倒往三个筒之外。 请用最少的倒水次数,倒出d升水(任一杯中正好水量为d 即可),并输出倒水的过程。 输入只有一行:a、b、c、d 四个整数。输出第一行为倒水过程的总步