oil.cpp

分油问题的一种VC实现的方法 分油问题的一种VC实现的方法

#include<iostream.h>
#include<iomanip.h>
#include<malloc.h>
#include<conio.h>
#include <stdlib.h>
 

#define ERROR 0
#define OVERFLOW -1
#define MAXSTACKSIZE 100
#define STACKINCREMENT 10
int n=0;
bool success=0;
 

typedef struct State      //定义3元组的结构体
{    int big;
     int normal;
     int small;
};

State exist[100];          //最大的搜索深度设定为100
State result[100];


class Stack
{  private :
           State *base;
		   State *top;
           int stacksize;
   public: 
	       bool InitStack(Stack &s);
           bool DestoryStack();
		   bool ClearStack();
		   bool StackEmpty();       
		   bool Push(Stack &S,State e);   //栈存在，则插入元素e为新的栈顶元素
		   void Out();                    //栈存在且非空，则栈顶元素出栈 
           State Pop(State *e);           //栈存在且非空，则栈顶元素出栈,并用e返回其值
};

//--------------------------------栈的类定义-------------------------------

bool Stack::InitStack(Stack &S)
{   
   S.base=(State*)malloc(MAXSTACKSIZE*sizeof(State));
   if(!S.base) exit(OVERFLOW);
   S.top=S.base;
   S.stacksize=MAXSTACKSIZE;
   return 1;
}

bool Stack::DestoryStack()
{  free(base); 
   return 1;
}
bool Stack::ClearStack()
{ stacksize=0;
   return 1;
}

bool Stack::StackEmpty()
{  if(stacksize==0) return true;
   else  return false;
}

 
bool Stack::Push(Stack &S,State e)
{    if(S.top-S.base>=S.stacksize)
     { S.base=(State*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(State));
      if(!S.base)  exit(OVERFLOW);
      S.top=S.base+S.stacksize;
      S.stacksize+=STACKINCREMENT;
   }
  *top=e;  top++;
   stacksize++;
   return 1;
}

void Stack::Out()
{     if(top==base)
        {  cerr<<"空栈!\n";  exit(1);}

       --top;
	  stacksize--;
	   
}

State Stack::Pop(State *e)
{     if(top==base)
        {  cerr<<"空栈!\n";  exit(1);}
      *e=*--top;
      stacksize--;
	  return *e;
}
//----------------------------------栈的类定义------------------------------------


bool ExistState(State s)        //判定是否已经访问过该结点
{   bool existstate=0; 
	for(int i=0;i<=n;i++)
	{       if ((s.big==exist[i].big)&&(s.small==exist[i].small)&&(s.normal==exist[i].normal))
		     existstate=1;
	     
         }
	  
	 
     return existstate;
}



bool Compare(State a)             //判断是否已经得到目标结点(只需要在一个瓶子中出现5)
{   if((a.big==5)||(a.normal==5))
       return 1;
    else return 0;
}


void Search(State s,Stack &Stk)   //深度优先遍历
{    
   
   State sn,st;                    //st用于接收栈里弹出的元素。
   if(success==1)                  //success＝1表示已经找到目标，把栈里面的元素输出。
   {    while(!Stk.StackEmpty())
	{   Stk.Pop(&st);
	    cout<<"("<<st.big<<",";
		cout<<st.normal<<",";
		cout<<st.small<<")"<<endl;
	}   
		return;
   }
    
   if((s.big>0)&&(s.normal<7))               //用10的瓶子中油装满7瓶
   {   sn.big=s.big-(7-s.normal);
       sn.normal=7;
       sn.small=s.small;
       if(!ExistState(sn))
	   {   success=Compare(sn);
	        
	      exist[n+1].big=sn.big;
		  exist[n+1].normal=sn.normal;
	      exist[n+1].small=sn.small;  n++; 
		                                  
	      Stk.Push(Stk,sn);
	      Search(sn,Stk);
	      Stk.Out();
	   }
	   else
	   {  sn.big=s.big; 
	      sn.normal=s.normal;
	      sn.small=s.small;
	   }
   }
 
   if((s.big>0)&&(s.normal<3))             //用10的瓶子中油装满3瓶
   {   
	   sn.big=s.big-(3-s.small);
       sn.normal=s.normal;
	   sn.small=3;

	   success=Compare(sn);
       if(!ExistState(sn))
	   {   success=Compare(sn);
	        
	       exist[n+1].big=sn.big;
		   exist[n+1].normal=sn.normal;
	       exist[n+1].small=sn.small;  n++; 
		                                    
	      Stk.Push(Stk,sn);
	      Search(sn,Stk);
	      Stk.Out();
	   }
        else
	   {  sn.big=s.big;
		  sn.normal=s.normal;
	      sn.small=s.small;
	   }
   }

   if(s.normal>0)                        //将7瓶子中油倒回10瓶
   {   
	   sn.big=s.big+s.normal;
       sn.normal=0;
       sn.small=s.small;
	   
	   success=Compare(sn);
       if(!ExistState(sn))
	   {   success=Compare(sn);
	        
	       exist[n+1].big=sn.big;
		   exist[n+1].normal=sn.normal;
	       exist[n+1].small=sn.small;  n++; 
	      Stk.Push(Stk,sn);
	      Search(sn,Stk);
	      Stk.Out();
	   }
	   else
	   {  sn.big=s.big;
	      sn.normal=s.normal;
	      sn.small=s.small;
	   }
   }

   if((s.normal>0)&&(s.normal+s.small>3))         // 将7瓶中的油倒满3瓶，
   {    
	    sn.big=s.big;
        sn.normal=s.normal+s.small-3;
        sn.small=3;
		success=Compare(sn);
      if(!ExistState(sn))
	   {   success=Compare(sn);
	        
	       exist[n+1].big=sn.big;
		   exist[n+1].normal=sn.normal;
	       exist[n+1].small=sn.small;  n++; 
	      Stk.Push(Stk,sn);
	      Search(sn,Stk);
	      Stk.Out();
	   }
	   else
	   {  sn.big=s.big;
	      sn.normal=s.normal;
	      sn.small=s.small;
	   }
   }

   if((s.normal>0)&&(s.normal+s.small<=3))      // 7瓶中的油倒入3瓶，未装满3瓶
   {   
	   sn.big=s.big;
       sn.normal=0;
       sn.small=s.normal+s.small;
	   success=Compare(sn);
       if(!ExistState(sn))
	   {   success=Compare(sn);
	        
	       exist[n+1].big=sn.big;
		   exist[n+1].normal=sn.normal;
	       exist[n+1].small=sn.small;  n++; 
	      Stk.Push(Stk,sn);
	      Search(sn,Stk);
	      Stk.Out();
	   }
	   else
	   {  sn.big=s.big;
	      sn.normal=s.normal;
	      sn.small=s.small;
	   }
   }

   if(s.small>0)             //  将3瓶子中油倒回10瓶
   {    
	    
        sn.big=s.big+s.small;
		sn.normal=s.normal;
		sn.small=0;
	success=Compare(sn);
       if(!ExistState(sn))
	   {   success=Compare(sn);
	        
	       exist[n+1].big=sn.big;
		   exist[n+1].normal=sn.normal;
	       exist[n+1].small=sn.small;  n++; 
	      Stk.Push(Stk,sn);
	      Search(sn,Stk);
	      Stk.Out();
	   }
	   else
	   {  sn.big=s.big;
	      sn.normal=s.normal;
	      sn.small=s.small;
	   }
   }

   if((s.small>0)&&(s.normal+s.small>7))    //用3的瓶子中油装满7瓶
   {   
	   sn.big=s.big;
       sn.normal=7;
	   sn.small=s.normal+s.small-7;
	   success=Compare(sn);
       if(!ExistState(sn))
	   {   success=Compare(sn);
	        
	       exist[n+1].big=sn.big;
		   exist[n+1].normal=sn.normal;
	       exist[n+1].small=sn.small;  n++; 
	      Stk.Push(Stk,sn);
	      Search(sn,Stk);
	      Stk.Out();
	   }
	   else
	   {  sn.big=s.big;
	      sn.normal=s.normal;
	      sn.small=s.small;
	   }
   }

   if((s.small>0)&&(s.normal+s.small<=7))    //用3的瓶子中油装7瓶,未装满
   {   
       sn.big=sn.big;
	   sn.normal=s.normal+s.small;
	   sn.small=0;
	   success=Compare(sn);
      if(!ExistState(sn))
	   {   success=Compare(sn);
	        
	       exist[n+1].big=sn.big;
		   exist[n+1].normal=sn.normal;
	       exist[n+1].small=sn.small;  n++; 
	      Stk.Push(Stk,sn);
	      Search(sn,Stk);
	      Stk.Out();
	   }
	  else
	   {  sn.big=s.big;
	      sn.normal=s.normal;
	      sn.small=s.small;
	   }
   }

}

Stack Stk;     
void main()
{    
   State st;
   State begin;
   begin.big=10;
   begin.normal=0;
   begin.small=0;

   if(Compare(begin)) 
   {   cout<<"Alread Done!"<<endl;
       return;
   }

   Stk.Push(Stk,begin);
   
   exist[0].big=0;
   exist[0].small=0;
  
   Search(begin,Stk);

   Stk.DestoryStack();
   
    
}