倒水问题-广度搜索(带源程序).doc

一、 课程设计的主要内容题目描述：如何解决m加仑的桶和n加仑的桶倒出k加仑的水？功能要求及说明：（1）m，n，k为任意的正整数，mk或者nk；（2）动态显示每一个桶的当前水量；（3）如有解至少给出一种解决方案，能给出多种解决方案的可以适当加分。测试用例：若m=3，n=5，k=4，则可以采用如下方法：用三加仑的桶装满水倒入五加仑的桶，再用三加仑桶装一次，倒进五加仑的桶直到装满，这时三加仑的桶里剩下一加仑，然后把五加仑桶的水倒掉，把三加仑里剩下的一加仑倒进五加仑的桶，再用三加仑打一桶水倒进五加仑的桶里，这样五加仑的桶里就装了四加仑水了。每一个桶的当前水量如下：三加仑的桶当前水量 五加仑的桶当前水量 3 0 0 3 3 3 1 5 1 0 0 1 3 1 0 4源文件：#include /C+头文件#include#include#includetypedef struct Node /定义结点前指针和后指针struct Node* parent;int m;int n;char msg100;struct Node* pnext;NODE,*pNode;void traverse(pNode p);/声明遍历函数int a,b,k,i=0;pNode front; /定义队列pNode rear;pNode first;pNode ptail;pNode root=new NODE;/定义根节点void BFS()cout ;coutm=:a n=:b k=:kendl;cout ;cout开始搜索.m=0;root-n=0;strcpy(root-msg,最开始的状态);root-parent=root-pnext=NULL;ptail=p=front=rear=root;while(NULL!=p) /核心while循环 实现广度搜索if(p-mparent=p;pnew1-pnext=NULL;pnew1-n=p-n; pnew1-m=a;strcpy(pnew1-msg,把m倒满 );for(front=root;front!=NULL;front=front-pnext) /for循环用来避免死循环，提高效率，剪枝叶if(front-m=pnew1-m&front-n=pnew1-n)if(pnew1-m!=4 | pnew1-n!= 0)delete pnew1; break;if(front=NULL)ptail-pnext=pnew1; ptail=pnew1;if(p-nparent=p;pnew2-pnext=NULL;pnew2-m=p-m; pnew2-n=b;strcpy(pnew2-msg,把n倒满 );for(front=root;front!=NULL;front=front-pnext)if(front-m=pnew2-m&front-n=pnew2-n)if(pnew2-m!=4 | pnew2-n!= 0)delete pnew2; break;if(front=NULL)ptail-pnext=pnew2; ptail=pnew2;if(p-m!=0)pNode pnew3=new NODE;pnew3-parent=p;pnew3-pnext=NULL;pnew3-n=p-n; pnew3-m=0;strcpy(pnew3-msg,把m倒空 );for(front=root;front!=NULL;front=front-pnext)if(front-m=pnew3-m&front-n=pnew3-n)if(pnew3-m!=4 | pnew3-n!= 0)delete pnew3; break;if(front=NULL)ptail-pnext=pnew3; ptail=pnew3;if(p-n!=0)pNode pnew4=new NODE;pnew4-parent=p;pnew4-pnext=NULL;pnew4-n=0; pnew4-m=p-m;strcpy(pnew4-msg,把n倒空 );for(front=root;front!=NULL;front=front-pnext)if(front-m=pnew4-m&front-n=pnew4-n)if(pnew4-m!=4 | pnew4-n!= 0)delete pnew4; break;if(front=NULL)ptail-pnext=pnew4; ptail=pnew4;if(p-m!=0)pNode pnew5=new NODE;pnew5-parent=p;pnew5-pnext=NULL;pnew5-m=p-m;pnew5-n=p-n;if(p-m = b-p-n) pnew5-n=p-n+(b-p-n); pnew5-m=p-m-(b-p-n);elsepnew5-n=pnew5-n+p-m;pnew5-m=0;strcpy(pnew5-msg,把m倒给n );for(front=root;front!=NULL;front=front-pnext)if(front-m=pnew5-m&front-n=pnew5-n)if(pnew5-m!=4 | pnew5-n!= 0)delete pnew5; break;if(front=NULL)ptail-pnext=pnew5; ptail=pnew5;if(p-n!=0)pNode pnew6=new NODE;pnew6-parent=p;pnew6-pnext=NULL;pnew6-m=p-m;pnew6-n=p-n;if(p-n = a-p-m)pnew6-m=p-m+(a-p-m); pnew6-n=p-n-(a-p-m);elsepnew6-m=pnew6-m+p-n;pnew6-n=0;strcpy(pnew6-msg,把n倒给m );for(front=root;front!=NULL;front=front-pnext)if(front-m=pnew6-m&front-n=pnew6-n)if(pnew6-m!=k | pnew6-n!= 0)delete pnew6; break;if(front=NULL)ptail-pnext=pnew6; ptail=pnew6;if(p-m=k &p-n=0)cout ;cout*endl;cout ;cout已获得第i+1种答案 m nendl;cout ;coutpnext;cout ;cout搜索完成，共有i种答案endl;cout ;cout*parent;p-parent=NULL;pNode r;while(q!=NULL)r=q-parent;q-parent=p;p=q;q=r;q=root;while(q!=NULL)cout ;coutmsg9 &k99)coutsetw(