大家小时候是否做过这样一道题？


现在要用程序解这种题，算出结果示例如下(下面引自hat给出的一个代码的执行答案)（怕影响思路的先不要看）
假设是n升的水平分，最短的步骤是n-1次


其实这道题并不只有一种，还有 12 7 5  的杯子 平分为 6 6 0
16 9 7 的杯子，在第一个杯有16升的水，平分为8升。

整个题目一般类型是  2n n+1 n-1 的杯子 把存的2n的水，平分为 n n 0
但是，像 10 6 4 这样的，不可能平分为 5 5 0 。因为10 6 4 都是偶数，它们之间不可能
加减得出一个奇数5。
所以又有10 7 3的题型， 这类题有无数种，谁能给出一个通用的解法并做出解释。

（小弟在此先谢谢了，通用代码见过，但是没找到解释）



[ 本帖最后由 if_exist 于 2009-10-1 15:35 编辑 ]

这个应该用搜索加记忆就搞定吧。有空帮你写下

等待中

杯子ABC
 
1）
A->B->C的顺序
一开始从A倒B
 
然后满足：
C中满水时倒A，B中有剩水时倒C，B中无水时从A倒B
 
2） （就是BC倒过来）
A->C->B的顺序  
一开始从A倒C  
  
然后满足：  
B中满水时倒A，C中有剩水时倒B，C中无水时从A倒C
 
取1，2中的最少次数
 
在倒的过程中如果A满了则中断
 
 
我的书上是这么做的

/**
    一个队列cup[1000]
    先让初始化的三个数进入队列。
    然后出列一个，这个时候三个杯水量不同，
    在这个基础上，按照不同的倒法倒一次水，并让倒后的状态进入队列，
     这样不停地倒，直到有一个杯中的水是所有水的一半；或者所有的状态都被存到了队列中，即失败了
 */

#include<iostream>
using namespace std;
struct Cup //存储倒水过程中的状态
{
public:
    Cup():cupa(0),cupb(0),cupc(0),father(-1){}
    Cup(int a,int b,int c,int f):cupa(a),cupb(b),cupc(c),father(f){}
    int cupa;
    int cupb;
    int cupc;
    int father;
};
class divide
{
public:
    divide(int aa,int bb,int cc);
    void doDivide();
    bool isOver();
    bool isContain(const Cup &pp);
    void print();
    bool atob();//从a倒到b
    bool atoc();//从a倒到c
    bool btoc();//从b倒到c
    bool btoa();//从b倒到a
    bool ctob();//从c倒到b
    bool ctoa();//从c倒到a
private:
    struct Cup p;
    int a;
    int b;
    int c;
    Cup cup[1000];
    void push(const Cup&p);
    int count;
    int first;
};
divide::divide(int aa,int bb,int cc):a(aa),b(0),c(0),count(0),first(0)
{
    p.cupa = a;
    p.cupb = bb;
    p.cupc = cc;
    p.father= -1;
    push(p);
}
void divide::push(const Cup&p)
{
    if(count>1000)
    {
        cout<<"堆栈溢出\n";
        return;
    }
    else
        cup[count++] = p;
}
void divide::doDivide()
{
    int f =0;
    while(first<count&&!isOver())
    {
        if(first!=0) //表示不是第一次倒水
        {
            a = cup[first].cupa;
            b = cup[first].cupb;
            c = cup[first].cupc;
        }
        if(atob()|atoc()|btoc()|btoa()|ctoa()|ctob())
        {
            f = 1;
            first ++;
        }
        else
        {
            f=0;
            break;
        }
    }
      
    if(f==0)
        cout<<"不能完成均分\n";
    else
        print();   
}
bool divide::isOver()
{
    if(a==p.cupa/2||b==p.cupa/2||c==p.cupa/2)
        return true;
    return false;
}
bool divide::isContain(const Cup& pp)
{
    for(int i=0;i<count;i++)
    {
        if(pp.cupa==cup[i].cupa&&pp.cupb==cup[i].cupb&&pp.cupc==cup[i].cupc)
            return true;
    }
    return false;
}
bool divide::atob()
{
    int tempa,tempb,tempc;
    if(a>0&&b<p.cupb)
    {
        if(a>(p.cupb-b)) //b中容纳不下a中剩余的水
        {
            tempa = a-(p.cupb-b);
            tempb = p.cupb;
            tempc = c;
        }
        else//b能够容纳a中剩余的水
        {
            tempa = 0;
            tempb = b + a;
            tempc = c;
        }
        struct Cup tempp(tempa,tempb,tempc,first);
        if(!isContain(tempp)) //如果队列中没有
        {
            push(tempp);
            return true;
        }
        return false;
    }
}
bool divide::atoc()
{
    int tempa,tempb,tempc;   
    if(a>0&&c<p.cupc)
    {
        if(a>(p.cupc-c)) //c中容纳不下a中剩余的水
        {
            tempa = a-(p.cupc-c);
            tempb = b;
            tempc = p.cupc;
        }
        else//c能够容纳a中剩余的水
        {
            tempa = 0;
            tempb = b;
            tempc = c + a;
        }
        struct Cup tempp(tempa,tempb,tempc,first);
        if(!isContain(tempp)) //如果队列中没有
        {
            push(tempp);
            return true;
        }
        return false;
    }
}
bool divide::btoc()
{
    int tempa,tempb,tempc;   
    if(b>0&&c<p.cupc)
    {
        if(b>(p.cupc-c)) //c中容纳不下b中剩余的水
        {
            tempa = a;
            tempb = b-(p.cupc-c);
            tempc = p.cupc;
        }
        else//c能够容纳b中剩余的水
        {
            tempa = a;
            tempb = 0;
            tempc = c+b;
        }
        struct Cup tempp(tempa,tempb,tempc,first);
        if(!isContain(tempp)) //如果队列中没有
        {
            push(tempp);
            return true;
        }
        return false;
    }
}
bool divide::btoa()
{
    int tempa,tempb,tempc;   
    if(b>0&&a<p.cupa)
    {
        tempa = a+b;
        tempb = 0;
        tempc = c;
        struct Cup tempp(tempa,tempb,tempc,first);
        if(!isContain(tempp)) //如果队列中没有
        {
            push(tempp);
            return true;
        }
        return false;
    }
}
bool divide::ctoa()
{
    int tempa,tempb,tempc;   
    if(c>0&&a<p.cupa)
    {
        tempa = a+c;
        tempb = b;
        tempc = 0;
        struct Cup tempp(tempa,tempb,tempc,first);
        if(!isContain(tempp)) //如果队列中没有
        {
            push(tempp);
            return true;
        }
        return false;
    }
}
bool divide::ctob()
{
    int tempa,tempb,tempc;   
    if(c>0&&b<p.cupb)
    {
        if(c>(p.cupb-b)) //b中容纳不下c中剩余的水
        {
            tempa = a;
            tempb = p.cupb;
            tempc = c-(p.cupb-b);
        }
        else//b能够容纳c中剩余的水
        {
            tempa = a;
            tempb = b+c;
            tempc = 0;
        }
        struct Cup tempp(tempa,tempb,tempc,first);
        if(!isContain(tempp)) //如果队列中没有
        {
            push(tempp);
            return true;
        }
        return false;
    }
}
void divide::print()
{
    Cup temp_cup[count];
    int temp_count = 0;
    int i;
    for(i = count-1;cup[i].father!=-1;i=cup[i].father)
        temp_cup[temp_count++] = cup[i];
    cout<<"a "<<"b "<<"c "<<'\n';
    for(i= temp_count-1;i>=0;i--)
        cout<<temp_cup[i].cupa<<" "<<temp_cup[i].cupb<<" "<<temp_cup[i].cupc<<'\n';
}
main(void)
{
    divide d1(12,7,5),d2(16,9,7),d3(8,5,3),d4(10,6,4);
    d1.doDivide();
    d2.doDivide();
    d3.doDivide();
    d4.doDivide();   
}

谢谢楼上的各位，上面一楼由于我用的Tc所以就暂时没得看结果了。

我上次看到的那个批处理的代码很短，希望能够有人能告诉我这样操作的“原理”。

下面是我在中国dos联盟见到的批处理代码,没有标上原创，应该是按照出现过的算法做的吧，就是不知道操作根据。
（倒水题型可以从前面x y z处修改。）

@echo off 
setlocal EnableDelayedExpansion 
set x=10 
set y=7 
set z=3 
echo Your containers: %x%   %y%   %z% 
echo. 
set a=%x% 
set b=0 
set c=0 
set n=0 
:water1 
if %a% neq %b% ( 
  set /a n+=1 
  if %b% equ 0 ( 
    set /a a-=y 
    set /a b=y 
  ) else ( 
    if %c% equ %z% ( 
      set /a a+=z 
      set c=0 
    ) else ( 
      set /a t=z-c 
      if %b% gtr !t! ( 
        set /a b-=t 
        set /a c=z 
      ) else ( 
        set /a c+=b 
        set b=0 
      ) 
    ) 
  ) 
  echo Solution1 step%n%: %a%--^>%b%--^>%c% 
  goto :water1 
) 
echo Solution1 step%n%: %a%--^>%b%--^>%c% 
echo. 
pause

再次感谢各位热心的bccn会员。

[ 本帖最后由 if_exist 于 2009-10-3 09:56 编辑 ]

我找到简洁的描述了，现在剩下原理

你这个代码，他的思路就是按照4楼那位说的那样去写的。
我没有规定倒水的顺序，直接用搜索得到最后结果，不过貌似最后结果跟你的一样

如果按照这样的顺序，那么代码会简单很多，只要判断就好了

谢谢。
1，我先慢慢消化下先~   
2，寻找那个规律解法的原理……