spareoil.cpp

经典的分油问题

// SpareOil.cpp : Defines the entry point for the console application.
// written by WUFAN，February 23th--24th,2006
#include "stdafx.h"
#include<iostream.h>
//node是队列的元素结点
struct node{
 int container1;
 int container2;
 int container3;
 int father;
};
//record是记录已经创建结点的链表元素结点
struct  record{
 int vol1;
 int vol2;
 record *next;
};
//记录最后结点所在路径的元素结点
struct element{
 int bottle1;
 int bottle2;
 int bottle3;
};
//判断新状态是否能成为结点，可以就创建，并返回true，否则返回false
bool judge(int x1,int x2,record *list)
{
 record *p=list;
 record *pre=p;
 while(p&&(p->vol1!=x1||p->vol2!=x2))//链表未到尾部且新状态的数据和原来链表任何一个结点数据都不一样
 {
	 pre=p;
	 if(p->next)	 p=p->next;
	 else p=NULL;
 }
 if(p==NULL)//创建新链表结点
 {
	 record* q=new record;
     q->vol1=x1;
	 q->vol2=x2;
	 q->next=NULL;
	 pre->next=q;
	 return true;
 }
 else return false;
}
//主函数，执行过程
int main( )
{
	int i=0,j=1,k=0;
	int c1,c2,c3;//中间变量
	char c;
    //创建队列，给出足够空间
	node* queue=new node[1000];
	queue[0].container1=10;
    queue[0].container2= 0;
    queue[0].container3= 0;
    queue[0].father=-1;
	//创建已产生结点的链表头
    record* table=new record;
	table->vol1=10;
	table->vol2=0;
	table->next=NULL;
	//广度优先遍历
    while(queue[i].container1||queue[i].container2)
	{
		if(queue[i].container2)//情况1：7两瓶中有油，全倒入10两瓶
		{
		 c1=queue[i].container1+queue[i].container2;	  
         c2=0;
		 c3=queue[i].container3;
		 if(judge(c1,c2,table))//判断是否是新状态 
		 {
		  queue[j].container1=c1;
          queue[j].container2=c2;
		  queue[j].container3=c3;
          queue[j].father=i;
		  if(c1==5&&c2==5)  break;//如果到最终状态则停止
		  j++;
		 }//if
		}//if
        if(queue[i].container3)//情况2：3两瓶中有油，全倒入10两瓶
		{
		 c1=queue[i].container1+queue[i].container3;	  
         c2=queue[i].container2;
		 c3=0;
		 if(judge(c1,c2,table)) 
		 {
		  queue[j].container1=c1;
          queue[j].container2=c2;
		  queue[j].container3=c3;
          queue[j].father=i;
          if(c1==5&&c2==5)  break;
		  j++;
		 }//if
		}//if
	    if(queue[i].container1+queue[i].container2>=7)//情况3：10两瓶向7两瓶倒，7两瓶和10两瓶中油加起来大于7两
		{
		 c1=queue[i].container1+queue[i].container2-7;	  
         c2=7;
		 c3=queue[i].container3;
		 if(judge(c1,c2,table)) 
		 {
		  queue[j].container1=c1;
          queue[j].container2=c2;
		  queue[j].container3=c3;
          queue[j].father=i;
          if(c1==5&&c2==5)  break;
		  j++;
		 }//if
		}//if
        if(queue[i].container2+queue[i].container3>=7)//情况4：3两瓶向7两瓶倒，7两瓶和3两瓶中油加起来大于7两
		{
		 c1=queue[i].container1 ;	  
         c2=7;
		 c3=queue[i].container2+queue[i].container3-7;
		 if(judge(c1,c2,table)) 
		 {
		  queue[j].container1=c1;
          queue[j].container2=c2;
		  queue[j].container3=c3;
          queue[j].father=i;
          if(c1==5&&c2==5)  break;
		  j++;
		 }//if
		}//if
        if(queue[i].container2+queue[i].container3<=7)//情况5：3两瓶向7两瓶倒，7两瓶和3两瓶中油加起来不大于7两
		{
		 c1=queue[i].container1 ;	  
         c2=queue[i].container2+queue[i].container3;
		 c3=0;
		 if(judge(c1,c2,table)) 
		 {
		  queue[j].container1=c1;
          queue[j].container2=c2;
		  queue[j].container3=c3;
          queue[j].father=i;
		  if(c1==5&&c2==5)  break;
		  j++;
		 }//if
		}//if
       if(queue[i].container1+queue[i].container3>=3)//情况6：10两瓶向3两瓶倒，10两瓶和3两瓶中油加起来大于等于3两
		{
		 c1=queue[i].container1+queue[i].container3-3 ;	  
         c2=queue[i].container2;
		 c3=3;
		 if(judge(c1,c2,table)) 
		 {
		  queue[j].container1=c1;
          queue[j].container2=c2;
		  queue[j].container3=c3;
          queue[j].father=i;
		  if(c1==5&&c2==5)  break;
		  j++;
		 }//if
		}//if
       if(queue[i].container2+queue[i].container3>=3)//情况7：7两瓶向3两瓶倒，7两瓶和3两瓶中油加起来大于3两
		{
		 c1=queue[i].container1 ;	  
         c2=queue[i].container2+queue[i].container3-3;
		 c3=3;
		 if(judge(c1,c2,table)) 
		 {
		  queue[j].container1=c1;
          queue[j].container2=c2;
		  queue[j].container3=c3;
          queue[j].father=i;
		  if(c1==5&&c2==5)  break;
		  j++;
		 }//if
		}//if
       if(queue[i].container2+queue[i].container3<=3)//情况8：7两瓶向3两瓶倒，7两瓶和3两瓶中油加起来不大于3两
		{
		 c1=queue[i].container1 ;	  
         c2=0;
		 c3=queue[i].container2+queue[i].container3;
		 if(judge(c1,c2,table)) 
		 {
		  queue[j].container1=c1;
          queue[j].container2=c2;
		  queue[j].container3=c3;
          queue[j].father=i;
		  if(c1==5&&c2==5)  break;
		  j++;
		 }//if
		}//if
       i++;
	}//while
	cout<<"题目：一个1斤的油瓶内装满了油，有两个空瓶，容量分别是7两和3两。要求在三个瓶子间进行倒油，使一斤油平分为两个五两。"<<endl;
	cout<<endl<<endl;
	 
	//设置一个数组，存入目标结点所在路径，不包括初始状态（10，0，0）
    element *array=new element[j];
	while(queue[j].father!=-1)
	{
	 array[k].bottle1=queue[j].container1;
     array[k].bottle2=queue[j].container2;
	 array[k].bottle3=queue[j].container3;
	 j=queue[j].father;
	 k++;
	}
	//打印出路径，即倒油的过程
    cout<<"开始输出分油过程"<<endl;
	cout<<"10"<<' '<<"0"<<' '<<"0"<<endl;
	for(i=k-1;i>=0;i--)
		cout<<array[i].bottle1<<' '<<array[i].bottle2<<' '<<array[i].bottle3<<endl;
	//结束
	cout<<"PRESS   e   TO QUIT"<<endl;
	cin>>c;
	while(c!='e') {cout<<"PRESS   e   TO QUIT";cin>>c;}
	return 0;
}
// written by WUFAN，February 23th--24th,2006