cpp1.cpp

来自「倒酒问题描述： 设有两个能装8两的酒杯（称为１号」· C++ 代码 · 共 467 行

    
#include <stdio.h>
#include <stdlib.h>
#define FULL 1
#define EMPTY 2
#define SOMETHING 3
#define OK 1
#define ERROR -1
#define MAXNUM 50
#define MAXRECORD 880
#define MAXCOL 3 /*MAXCOL+1表示每个装酒的瓶子*/
#define EQL 1
#define NEQ 0
#define OCCUPIED 1
#define UNOCCUPIED 0
 

/*瓶子的数据结构*/
typedef struct Bottle
{
    int capacity;    /*瓶子容量*/
    int used;        /*瓶子使用量*/
}Bottle;

/*最终酒瓶倒的过程*/
Bottle ResultBottleList[MAXNUM][MAXCOL];
/*记录最终酒瓶倒的过程指针*/
Bottle *cy;
/*酒瓶中间状态数组*/
Bottle EndBottleList[MAXNUM][MAXCOL];
/*记录其他容器的装酒量*/
int OtherBottle[MAXNUM];
/*记录其他容器的装酒量数组的下标*/
int cx;
/*记录状态是否出现过*/
int StatusRecord[MAXRECORD];

int min (int value1, int value2)
{
    return ( (value1 < value2) ? value1 : value2);
}

/*计算出bottle能够容纳的容量*/
int BottleLeft(Bottle bottle)
{
    return bottle.capacity-bottle.used;    
}


/*得到bottle的总容量*/
int BottleCapacity(Bottle bottle)
{
    return bottle.capacity;
    
}

/*得到bottle的用去的容量*/
int BottleUsed(Bottle bottle)
{
    return bottle.used;
    
}

/*判断bottle是否为空EMPTY、有SOMETHING、满FULL。*/
int BottleFull(Bottle bottle)
{
    if(BottleLeft(bottle)==0)
        return FULL;
    else if(BottleLeft(bottle)==BottleCapacity(bottle))
        return EMPTY;
        else
                return SOMETHING;
       
}

/*设置bottle的用去的容量*/
void setBottleUsed(Bottle **bottle, int used)
{
    (*bottle)->used=used;

}

/*判断2个8L的瓶子是否状态相等，即是否可以互换*/
int compareBottles(Bottle bottle1, Bottle bottle2)
{
    if(BottleUsed(bottle1)==BottleUsed(bottle2))
        return EQL;
    else
        return NEQ; 
}

/*从bottle1倒入bottle2*/ 
int BottleToBottle(Bottle *bottle1,Bottle *bottle2)
{
    int temp1;
    int temp2;
    int temp3;
    temp1=BottleLeft(*bottle2);
   
   /*如果bottle2满了，或者bottle1空了，则报错。*/
	if(BottleCapacity(*bottle2)==BottleUsed(*bottle2) || BottleUsed(*bottle1)==0)
        return ERROR;
	/*如果2个瓶子都空了，报错。*/
    if(BottleUsed(*bottle1)==0 && BottleUsed(*bottle2)==0)
        return ERROR;
    /*如果bottle1有的比bottle2可倒的空间大，则使bottle2满，bottle1相应减去到出去的。*/
	if(BottleUsed(*bottle1)>=temp1)
    {
        temp3=bottle2->used;
        setBottleUsed(&bottle2,BottleCapacity(*bottle2));
        
        temp2=BottleUsed(*bottle1)-(BottleUsed(*bottle2)-temp3);
        setBottleUsed(&bottle1,temp2);
    }
	/*如果bottle1有的比bottle2可倒的空间小，则使bottle1空，bottle2则倒入相应的酒量。*/
    else
    {
        temp1=BottleUsed(*bottle1);
        temp2=BottleUsed(*bottle2);
        setBottleUsed(&bottle1,0);
        setBottleUsed(&bottle2,temp1+temp2);
    }
    
    return OK;
    
}

/*将酒瓶的状态转换成整数*/ 
int ConvertInteger(Bottle a, Bottle b, Bottle c)
{
    return a.used*100+b.used*10+c.used;
}    

/*清除EndBottleList中间态的所有状态*/
void ClearEndBottleList()
{
    int i,j;
    for(i=0; i<MAXNUM ; i++)
    {
        for(j=0; j<MAXCOL ; j++)
        {
                EndBottleList[i][j].used=0;
        }    
    }    
    
    for(i=0; i<MAXNUM ; i++)
    {
        for(j=0; j<MAXCOL-1 ; j++)
        {
                EndBottleList[i][j].capacity=8;
        }    
    }    
    
    for(i=0; i<MAXNUM ; i++)
    {
        EndBottleList[i][MAXCOL-1].capacity=3;
    }    
}    

/*找到所有状态中酒量最小的那个瓶，0不算*/
void FindPopBottle()
{
    int minInteger;
    Bottle *pt;
    Bottle *ptmin;
    pt=EndBottleList[0];
    ptmin=pt;
    
    if(pt[0].used==0)/*1号为0*/
        minInteger=min(pt[1].used,pt[2].used);
    if(pt[1].used==0)/*2号为0*/
        minInteger=min(pt[0].used,pt[2].used);
    if(pt[2].used==0)/*3号为0*/
        minInteger=min(pt[0].used,pt[1].used);
    if(pt[0].used+pt[1].used==0)/*1号、2号为0*/
        minInteger=pt[2].used;
    if(pt[0].used+pt[2].used==0)/*1号、3号为0*/
        minInteger=pt[1].used;
    if(pt[1].used+pt[2].used==0)/*2号、3号为0*/
        minInteger=pt[0].used;
    if(pt[0].used*pt[1].used*pt[2].used!=0)/*三个酒瓶都不为0*/
    {
        minInteger=min(pt[0].used,pt[1].used);
        minInteger=min(pt[2].used,minInteger);
    }    
        
    /*查找EndBottleList所有的状态*/
	while((pt[0].used+pt[1].used+pt[2].used)!=0)
    {
         if(pt[0].used!=0 && pt[0].used<minInteger)/*1号无为0，且比最小酒量minInteger小*/
         {
           minInteger=pt[0].used;
           ptmin=pt;												/*ptmin指针指向改状态，下同*/
         }
         if(pt[1].used!=0 && pt[1].used<minInteger)/*2号无为0，且比最小酒量minInteger小*/
         {
           minInteger=pt[1].used;
           ptmin=pt;
         }
         if(pt[2].used!=0 && pt[2].used<minInteger)/*3号无为0，且比最小酒量minInteger小*/
         {
           minInteger=pt[2].used;
           ptmin=pt;
         } 
         pt=pt+3; 
    }
    /*1号酒量不是最小，则指向最终显示状态的ResultBottleList的指针指向的相应酒瓶赋值*/
    if(ptmin[0].used!=minInteger)
        cy[0].used=ptmin[0].used;
    else                                     /*1号酒量是最小，则指向最终显示状态的ResultBottleList的指针指向的相应酒瓶置0，放入其他容器中*/
    {
        cy[0].used=0;
        OtherBottle[cx++]=minInteger;
    }
    /*2号酒量不是最小，则指向最终显示状态的ResultBottleList的指针指向的相应酒瓶赋值*/    
    if(ptmin[1].used!=minInteger)
        cy[1].used=ptmin[1].used;
    else                                       /*2号酒量是最小，则指向最终显示状态的ResultBottleList的指针指向的相应酒瓶置0，放入其他容器中*/
    {
        cy[1].used=0;
        OtherBottle[cx++]=minInteger;
    }    
    /*3号酒量不是最小，则指向最终显示状态的ResultBottleList的指针指向的相应酒瓶赋值*/
    if(ptmin[2].used!=minInteger)
        cy[2].used=ptmin[2].used;
    else                                     /*3号酒量是最小，则指向最终显示状态的ResultBottleList的指针指向的相应酒瓶置0，放入其他容器中*/
    {
        cy[2].used=0;
        OtherBottle[cx++]=minInteger;
    }    
    
    ClearEndBottleList();/*清除所有的中间状态*/
    EndBottleList[0][0]=cy[0];/*赋值新状态，就是刚才得到的最小值所在的状态*/
    EndBottleList[0][1]=cy[1];
    EndBottleList[0][2]=cy[2];  
    cy=cy+3;/*指向最终结果的指针下移*/
        
}    

void Arithmetic_Bottle()
{
    int temp;
    Bottle a, b, c;
    Bottle *head, *tail;
    head=EndBottleList[0];
    tail=EndBottleList[1];
    
    a=head[0];
    b=head[1];
    c=head[2];
    
    /*采用散列查找，以酒瓶转换成一个三位数的数字作为下标标示StatusRecord的状态*/
	temp=ConvertInteger(head[0],head[1],head[2]);
    StatusRecord[temp-1]=OCCUPIED;
	/*850和580一个状态，所以当850出现时，580也要置1，表示改状态出现过*/
    temp=ConvertInteger(head[1],head[0],head[2]);
    StatusRecord[temp-1]=OCCUPIED;
    
    /*直到最初三个酒瓶中的酒全部倒出为止*/
    while((head[0].used+head[1].used+head[2].used)!=0)
    {
        /*一个状态衍生出的所有的状态，当head与tail重合时结束最初状态的衍生，开始查找最小酒量所在的瓶子*/
		while(head!=tail)
        {
    
            /*下面是4种不同的倒法*/

			/*a瓶倒入c瓶*/
			if(BottleToBottle(&a,&c)!=ERROR)
            {
                temp=ConvertInteger(a,b,c);/*新状态转换成数字，查找是否出现过该状态*/
            
                if(StatusRecord[temp-1]==UNOCCUPIED)/*没出现过*/
                {
                    StatusRecord[temp-1]=OCCUPIED;/*置1，表示出现过了*/
                    temp=ConvertInteger(b,a,c);        /*a瓶，b瓶交换位置*/
                    StatusRecord[temp-1]=OCCUPIED;/*置1，表示出现过了*/
                    /*新状态赋值到tail指向的位置*/
					tail[0]=a;
                    tail[1]=b;
                    tail[2]=c;
                    tail=tail+3;/*指针移动*/
                
                } 
                    a=head[0];
                    b=head[1];
                    c=head[2];  
            }     

            /*b瓶倒入c瓶*/
            if(BottleToBottle(&b,&c)!=ERROR)
            {
                temp=ConvertInteger(a,b,c);
            
                if(StatusRecord[temp-1]==UNOCCUPIED)
                {
                    StatusRecord[temp-1]=OCCUPIED;
                    temp=ConvertInteger(b,a,c);
                    StatusRecord[temp-1]=OCCUPIED;
                    tail[0]=a;
                    tail[1]=b;
                    tail[2]=c;
                    tail=tail+3;
                
                } 
                    a=head[0];
                    b=head[1];
                    c=head[2];   
            }    
    
			/*c瓶倒入a瓶*/
            if(BottleToBottle(&c,&a)!=ERROR)
            {
                temp=ConvertInteger(a,b,c);
                
                if(StatusRecord[temp-1]==UNOCCUPIED)
                {
                    StatusRecord[temp-1]=OCCUPIED;
                    temp=ConvertInteger(b,a,c);
                    StatusRecord[temp-1]=OCCUPIED;
                    tail[0]=a;
                    tail[1]=b;
                    tail[2]=c;
                    tail=tail+3;
                
                } 
                    a=head[0];
                    b=head[1];
                    c=head[2];   
            }    
            
			/*c瓶倒入b瓶*/
            if(BottleToBottle(&c,&b)!=ERROR)
            {
                temp=ConvertInteger(a,b,c);
                
                if(StatusRecord[temp-1]==UNOCCUPIED)
                {
                    StatusRecord[temp-1]=OCCUPIED;
                    temp=ConvertInteger(b,a,c);
                    StatusRecord[temp-1]=OCCUPIED;
                    tail[0]=a;
                    tail[1]=b;
                    tail[2]=c;
                    tail=tail+3;
                
                } 
                    a=head[0];
                    b=head[1];
                    c=head[2];   
            }    
     
           head=head+3;
           a=head[0];
           b=head[1];
           c=head[2];
           
        }  
        for(head=EndBottleList[0];head!=tail;head+=3)
                printf("%d\t%d\t%d\n",head[0].used,head[1].used,head[2].used);
        system("PAUSE");

        /*找出最小的那个酒瓶，并将这个状态写入ResultBottleList中*/
		FindPopBottle();

        /*得到新的状态，等待4种倒法的派生*/
		head=EndBottleList[0];
        tail=EndBottleList[1];
        a=head[0];
        b=head[1];
        c=head[2];
    }    
    
}


/*初始化酒瓶*/ 
void InitBottle(int bottle1, int bottle2, int bottle3)
{
    int i,j;
    cx=1;
    cy=ResultBottleList[1];
    for(i=0; i<MAXNUM ; i++)
    {
        for(j=0; j<MAXCOL ; j++)
        {
                EndBottleList[i][j].used=0;
                ResultBottleList[i][j].used=0;
        }    
        OtherBottle[i]=0;
    }    
    
    for(i=0; i<MAXNUM ; i++)
    {
        for(j=0; j<MAXCOL-1 ; j++)
        {
                EndBottleList[i][j].capacity=bottle1;
                ResultBottleList[i][j].capacity=bottle1;
        }    
    }    
    
    for(i=0; i<MAXNUM ; i++)
    {
        EndBottleList[i][MAXCOL-1].capacity=bottle3;
        ResultBottleList[i][MAXCOL-1].capacity=bottle3;  
    }    
    
    for(i=0; i<MAXRECORD; i++)
    {  
        StatusRecord[i]=UNOCCUPIED;
    }
    
    EndBottleList[0][0].capacity=bottle1;
    EndBottleList[0][0].used=bottle1;
    
    EndBottleList[0][1].capacity=bottle2;
    EndBottleList[0][1].used=bottle1;
    
    EndBottleList[0][2].capacity=bottle3;
    EndBottleList[0][2].used=0;
    
    ResultBottleList[0][0].capacity=bottle1;
    ResultBottleList[0][0].used=bottle1;
    
    ResultBottleList[0][1].capacity=bottle2;
    ResultBottleList[0][1].used=bottle1;
    
    ResultBottleList[0][2].capacity=bottle3;
    ResultBottleList[0][2].used=0;
    
    OtherBottle[0]=0;
    
    
}

/*打印酒瓶的使用情况*/
void PrintBottle()
{
    int i,j,k,l;
    printf("最后状态，最后一个数字是其他容器的酒量\n");
    for(i=0,l=0; i<MAXNUM ; i++,l++)
    {
        if(ResultBottleList[i][0].used!=0 ||
           ResultBottleList[i][1].used!=0 ||
           ResultBottleList[i][2].used!=0 
           )
        {
            for(j=0; j<MAXCOL; j++)
                printf("%d\t",ResultBottleList[i][j].used);
            for(k=0; k<i; k++)
                printf("%d\t",OtherBottle[k]);
            printf("\n");   
        }    
    }    
  
}

int main(int argc, char *argv[])
{
    InitBottle(8,8,3);
    Arithmetic_Bottle();
    PrintBottle();
    system("PAUSE");	
    return 0;
}