/*
 * 有a,b,c,d四个人,现在有三个酒杯X,Y,Z三个不规则酒杯, 
 * X,Y容量为8两,现在已装满酒,Z容量为3两,为空杯.现在要
 * 求四个人每人都能平均喝到4两酒,请说出该怎么喝?写出算
 * 法,并打印出每步X,Y,Z杯内的酒多少和四个人每人所喝的酒? 
 * */

解决方案 »

  1.   

    import java.util.HashSet;  
    import java.util.Stack;  
      
    public class Drink {  
        //  state 为32位整数,每4bit表示一个cup  
        //  cup 0-2 : cup x,y,z  
        //  cup 3-6 : people a,b,c,d  
        //  state := [D][C][B][A][Z][Y][X]  
      
        int[] maxVol = {8, 8, 3, 4, 4, 4, 4};   // 最大容量  
        int stopState = makeState(new int[]{0, 0, 0, 4, 4, 4, 4});  // 最终状态  
      
        Stack<Integer> stateStack = new Stack<Integer>();  
        HashSet<Integer> stateStackCache = new HashSet<Integer>();  
        HashSet<Integer> failStates = new HashSet<Integer>();  
      
        public static void main(String[] args) {  
            new Drink().start();  
        }  
      
        static int getCup(int state, int i) {  
            return (state & (0xF << (i * 4))) >> (i * 4);  
        }  
      
        static int makeState(int curState, int cupIdx, int value) {  
            return value << (4 * cupIdx) | (curState & (~(0xF << (4 * cupIdx))));  
        }  
      
        static int makeState(int curState, int cupIdx1, int value1, int cupIdx2, int value2) {  
            return makeState(makeState(curState, cupIdx1, value1), cupIdx2, value2);  
        }  
      
        // cup.length MUST == 7  
        static int makeState(int[] cup) {  
            int state = 0;  
            for (int i = 6; i >= 0; i--) {  
                state |= cup[i];  
                if (i > 0)  
                    state <<= 4;  
            }  
            return state;  
        }  
      
      
        void start() {  
            boolean r = testState(makeState(new int[]{8, 8, 0, 0, 0, 0, 0}));  
            System.out.println(r ? "found" : "not found");  
        }  
      
        boolean testState(int curState) {  
            if (stateStackCache.contains(curState) || failStates.contains(curState))  
                return false;  
      
            pushState(curState);  
            try {  
                if (curState == stopState) {  
                    printStack();  
                    return true;  
                }  
      
                if (testMoves(curState)) {  
                    return true;  
                } else {  
                    failStates.add(curState);  
                    return false;  
                }  
            } finally {  
                popState(curState);  
            }  
        }  
      
        private boolean testMoves(int curState) {  
            for (int from = 0; from < 3; from++) {  
                int curCupFrom = getCup(curState, from);  
                if (curCupFrom == 0)  
                    continue;  
      
                for (int to = 6; to >= 0; to--) {  
                    if (to == from)  
                        continue;  
      
                    int curCupTo = getCup(curState, to);  
                    int maxTo = maxVol[to] - curCupTo;  
                    if (maxTo == 0)  
                        continue;  
      
                    int moveValue = curCupFrom;  
                    if (curCupFrom > maxTo) {  
                        if (to >= 3)    //people  
                            continue;  
                        moveValue = maxTo;  
                    }  
      
                    int newCupFrom = curCupFrom - moveValue;  
                    int newCupTo = curCupTo + moveValue;  
      
                    if (from < 2 && to < 2 && newCupTo == curCupFrom) {  
                        //两个同样的杯子倒来倒去  
                        continue;  
                    }  
      
                    final int newState = makeState(curState, from, newCupFrom, to, newCupTo);  
      
                    if (testState(newState))  
                        return true;  
                }  
            }  
            return false;  
        }  
      
        private void printStack() {  
            System.out.println("Success! all steps: " + stateStack.size());  
            int step = 0;  
            for (Integer state : stateStack) {  
                System.out.print("\t" + (++step) + ":\t");  
                for (int i = 0; i < 7; i++) {  
                    System.out.print(getCup(state, i));  
                    if (i == 2)  
                        System.out.print(" | ");  
                }  
                System.out.println();  
            }  
        }  
      
        private void popState(int newState) {  
            stateStack.pop();  
            stateStackCache.remove(newState);  
        }  
      
        private void pushState(int newState) {  
            stateStack.push(newState);  
            stateStackCache.add(newState);  
        }  
    }  
      

  2.   

    C++代码 
    // Mianshi.cpp : Defines the entry point for the console application.  
    //  
      
    #include "stdafx.h"  
    #include "stdio.h"  
    #define Maxstate 1024  
    int SumMyprint=0;  
    int state[Maxstate]={0};  
    void Myprint(int *Arr,int N,char *Str);  
    bool CheckState(int *Arr,int Sum);  
    void StateAdd(int *state,int add);  
    void MyCopy(int *A,int*B,int N);  
      
    #define CheckSucc(STR) Sum=Arr[0]*1000000+Arr[1]*100000+Arr[2]*10000+Arr[3]*1000+  Arr[4]*100+Arr[5]*10+Arr[6];\  
    if(!CheckState(state, Sum))\  
    {\  
        StateAdd(state,Sum);\  
        /*Myprint(Arr,7,STR);*/\  
        if (Iterative( Arr ))\  
    {return true;}\  
    }\  
    if (Arr[0]==4&&Arr[1]==4&&Arr[2]==4&&Arr[3]==4)\  
    {\  
            Myprint(Arr,7,"True");\  
            return true;\  
    }\  
      
      
    bool Iterative(int *realArr)  
    {  
        int i=0,j=0,k=0,Sum=0;char SS[10];int tmpArr[7]={0};int Arr[7]={0};  
        //***检测是否重复的状态,不是的话就添加进状态数组***  
          
          
        /*  
        if (CheckState(state, Sum))  
        {  
            printf(" CheckState Fail!\n");  
            return false;  
        }  
        if (Arr[4]==4&&Arr[5]==4&&Arr[6]==4)  
        {    
            Myprint(Arr,7,"True");  
            return true;  
        }  
        StateAdd(state,Sum);  
        CheckSucc();*/  
        //--------------------------------------------  
        for (j=4;j<=6;j++)  
        {  
          for (i=0;i<=3;i++)  
          {  
            if (realArr[i]+realArr[j]<=4&&realArr[j])  
            {  
                  
                MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");  
                Arr[i]+=Arr[j];Arr[j]=0;  
                if (Arr[0]==4&&Arr[1]==4&&Arr[2]==4&&Arr[3]==4)  
                {    
                    Myprint(Arr,7,"True");  
                    return true;  
                }  
                //sprintf(SS,"%d=>%d",j,i);  
                //Myprint(Arr,7,SS);  
                if (Iterative( Arr ))  
                {  
                    Myprint(Arr,7,"True");  
                    return true;   
                }  
      
            }  
          }  
        }  
    //----------------------------------------  
        if (realArr[5]<8&&realArr[4])//4=>5 1  
        {  
            if (realArr[4]+realArr[5]>8)  
            {  
                MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");  
                Arr[4]=Arr[4]-8+Arr[5];Arr[5]=8;  
                CheckSucc("4=>5");  
      
            }  
            else  
            {  
                MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");  
                Arr[5]+=Arr[4];Arr[4]=0;  
                CheckSucc("4=>5");  
      
            }  
      
        }  
        if (realArr[6]<8&&realArr[4])//4=>6 2  
        {  
            if (realArr[4]+realArr[6]>3)  
            {  
                MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");  
                Arr[4]=Arr[4]-3+Arr[6];Arr[6]=3;  
                CheckSucc("4=>6");  
      
            }  
            else  
            {  
                MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");  
                Arr[6]+=Arr[4];Arr[4]=0;  
                CheckSucc("4=>6");  
      
            }  
        }  
      
        if (realArr[4]<8&&realArr[5])//4<=5 3  
        {  
            if (realArr[4]+realArr[5]>8)  
            {  
                MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");  
                Arr[5]=Arr[5]-8+Arr[4];Arr[4]=8;  
                CheckSucc("5=>4");  
      
            }  
            else  
            {  
                MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");  
                Arr[4]+=Arr[5];Arr[5]=0;  
                CheckSucc("5=>4");  
            }  
        }  
        if (realArr[4]<8&&realArr[6])//4<=6 4  
        {  
            if (realArr[4]+realArr[6]>8)  
            {  
                MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");  
                Arr[6]=Arr[6]-8+Arr[4];Arr[4]=8;  
                CheckSucc("6=>4");  
            }  
            else  
            {  
                MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");  
                Arr[4]+=Arr[6];Arr[6]=0;  
                CheckSucc("6=>4");  
              
            }  
        }  
        if (realArr[6]<3&&realArr[5])//5=>6 5  
        {  
            if (realArr[5]+realArr[6]>3)  
            {  
                MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");  
                Arr[5]=Arr[5]-3+Arr[6];Arr[6]=3;  
                CheckSucc("5=>6");  
      
            }  
            else  
            {  
                MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");  
                Arr[6]+=Arr[5];Arr[5]=0;  
                CheckSucc("5=>6");  
            }  
        }  
        if (realArr[5]<8&&realArr[6])//5<=6 6  
        {  
            if (realArr[5]+realArr[6]>8)  
            {  
                MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");  
                Arr[6]=Arr[6]-8+Arr[5];Arr[5]=8;  
                CheckSucc("6=>5");  
            }  
            else  
            {  
                MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");  
                Arr[5]+=Arr[6];Arr[6]=0;  
                CheckSucc("6=>5");  
            }  
        }  
        return false;  
    }  
    void MyCopy(int *A,int*B,int N)  
    {  
        for(int i=0;i<N;i++)  
        {  
            A[i]=B[i];  
        }  
    }  
    void StateAdd(int *state,int add)  
    {  
      
        for (int j=0;j<Maxstate;j++)  
        {  
            if (!state[j])  
            {  
                state[j]=add;  
                if (state[4]==53)  
                {  
                    int asdfasdf=12;      
                }  
                return;  
            }  
        }  
    }  
    bool CheckState(int *state,int Sum)//Sum在Arr中则返回true  
    {  
        int SumTemp=(Sum/1000)*1000;SumTemp=Sum-SumTemp;//SumTemp=323...  
        int Sum_th=SumTemp/100,Sum_te=(SumTemp/10)%10,Sum_ge=SumTemp%10,Sum_P=(Sum/1000)*1000;//Sum_P=3233000  
        for (int j=0;j<Maxstate;j++)  
        {  
            //int state_th=state[j]/100,state_te=(state[j]/10)%10,state_ge=state[j]%10;  
            int staTemp=(state[j]/1000)*1000;staTemp=state[j]-staTemp;//staTemp=323...  
            int state_th=staTemp/100,state_te=(staTemp/10)%10,state_ge=staTemp%10,state_P=(state[j]/1000)*1000;//state_P=3233000  
            if (state[j]==Sum &&state_P==Sum_P)  
            {  
                return true;  
            }  
            if (state_ge==Sum_te&&state_th==Sum_th&&state_te==Sum_ge &&state_P==Sum_P)  
            {  
                return true;  
            }  
        }  
        return false;  
    }  
    void Myprint(int *Arr,int N,char *Str)  
    {  
        printf("       a b c d 4 5 6\n");  
        printf("Arr is ");  
        for (int j=0;j<N;j++)  
        {  
            printf("%d ",Arr[j]);  
        }  
        if (SumMyprint==6)  
        {  
            int asas=1;  
        }  
        printf("%s S:%d\n\n",Str,SumMyprint++);  
    //  if (Arr[0]==4 &&Arr[1]==2 &&Arr[2]==1 &&Arr[3]==1 &&Arr[4]==0 &&Arr[5]==8 &&Arr[6]==0 )  
    //  {  
    //          for (int j=0;j<N;j++)  
    //          {  
    //              printf("%d ",Arr[j]);  
    //          }  
    //          printf("\n");  
    //  }  
    }  
      
      
    int main(int argc, char* argv[])  
    {  
      
        int Arr[7]={0,0,0,0,8,8,0};  
      
        Iterative(Arr);   
      
        printf("Hello World!\n");  
        return 0;  
    }  
    // 有a,b,c,d四个人,现在有三个酒杯X,Y,Z三个不规则酒杯, X,Y容量为8两,现在已装满酒,Z容量为3两,  
    // 为空杯.现在要求四个人每人都能平均喝到4两酒,请说出该怎么喝?写出算法,并打印出每步X,Y,Z杯内的  
    // 酒多少和四个人每人所喝的酒?   
    //   
    // X Y Z a b c d   
    // 8 8 0 0 0 0 0   
    // 8 5 3 0 0 0 0   
    // 8 5 0 3 0 0 0   
    // 8 2 3 3 0 0 0   
    // 8 0 3 3 2 0 0   
    // 8 3 0 3 2 0 0   
    // 5 3 3 3 2 0 0   
    // 5 6 0 3 2 0 0   
    // 2 6 3 3 2 0 0   
    // 2 8 1 3 2 0 0   
    // 2 8 0 4 2 0 0   
    // 2 5 3 4 2 0 0   
    // 0 7 3 4 2 0 0 !  
    // 3 7 0 4 2 0 0 !  
    // 3 4 3 4 2 0 0 !  
    // 6 4 0 4 2 0 0 !  
    // 6 1 3 4 2 0 0 !  
    // 6 0 3 4 2 1 0 !  
    // 8 0 1 4 2 1 0 !  
    // 8 0 0 4 2 1 1 !  
    // 5 0 3 4 2 1 1   
    // 5 0 0 4 2 4 1   
    // 2 0 3 4 2 4 1   
    // 2 0 0 4 2 4 4   
    // 0 0 0 4 4 4 4   
      

  3.   

    就这样喝啊// X Y Z a b c d   
    // 8 8 0 0 0 0 0   
    // 8 5 3 0 0 0 0   
    // 8 5 0 3 0 0 0   
    // 8 2 3 3 0 0 0   
    // 8 0 3 3 2 0 0   
    // 8 3 0 3 2 0 0   
    // 5 3 3 3 2 0 0   
    // 5 6 0 3 2 0 0   
    // 2 6 3 3 2 0 0   
    // 2 8 1 3 2 0 0   
    // 2 8 0 4 2 0 0   
    // 2 5 3 4 2 0 0   
    // 0 7 3 4 2 0 0 !   
    // 3 7 0 4 2 0 0 !   
    // 3 4 3 4 2 0 0 !   
    // 6 4 0 4 2 0 0 !   
    // 6 1 3 4 2 0 0 !   
    // 6 0 3 4 2 1 0 !   
    // 8 0 1 4 2 1 0 !   
    // 8 0 0 4 2 1 1 !   
    // 5 0 3 4 2 1 1   
    // 5 0 0 4 2 4 1   
    // 2 0 3 4 2 4 1   
    // 2 0 0 4 2 4 4   
    // 0 0 0 4 4 4 4
      

  4.   

    http://j2se.phpchinaz.cn/archives/608659
      

  5.   

    你没见   http://j2se.phpchinaz.cn/archives/608659 和 当前页面是同一页面吗?
      

  6.   

    那孩子好强悍,java、C++///....................
      

  7.   


    http://www.javaeye.com/topic/187778?page=2这也是一个页面么??
      

  8.   

    NND  想了快个把小时了
    步骤算是弄出来了
    但代码不知咋写
    a b c d    甲     乙      丙
    0 0 0 0    8/8   8/8    0/3
    ===>
    0 0 0 0    5/8   8/8    3/3
    ===>
    3 0 0 0    5/8   8/8    0/3
    ===>
    3 0 0 0    2/8   8/8    3/3
    ===>
    3 2 0 0    0/8   8/8    3/3
    ===>
    3 2 0 0    3/8   8/8    0/3
    ===>
    3 2 0 0    3/8   5/8    3/3
    ===>
    3 2 0 0    6/8   5/8    0/3
    ===>
    3 2 0 0    6/8   2/8    3/3
    ===>
    3 2 0 0    8/8   2/8    1/3
    ===>
    4 2 0 0    8/8   2/8    0/3
    ===>
    4 2 0 0    5/8   2/8    3/3
    ===>
    4 2 0 0    0/8   7/8    3/3
    ===>
    4 2 0 0    3/8   7/8    0/3
    ===>
    4 2 0 0    3/8   4/8    3/3
    ===>
    4 2 0 0    6/8   4/8    0/3
    ===>
    4 2 0 0    6/8   1/8    3/3
    ===>
    4 2 1 0    6/8   0/8    3/3
    ===>
    4 2 1 0    8/8   0/8    1/3
    ===>
    4 2 1 1    8/8   0/8    0/3
    ===>
    4 2 1 1    5/8   0/8    3/3
    ===>
    4 2 4 1    5/8   0/8    0/3
    ===>
    4 2 4 1    2/8   0/8    3/3
    ===>
    4 4 4 4    0/8   0/8    0/3