题目描述：
一个桶中有12斤油，要求倒出6斤，可现在另外只有两个桶，分别可装8斤与5斤，请问应如何来倒？
思路：
广度优先搜索
c#代码：
private void button5_Click(object sender, EventArgs e)
{
//初始状态和结束状态
int[] begin = new int[] { 12, 0, 0 };
int end = 6;
int[][] allStatus = new int[][] { begin };
//所有步骤都记录在logHash里面
Dictionary<int, int> logHash = new Dictionary<int, int>();
int hashCode = GetHashCode(begin);
logHash.Add(hashCode, hashCode);
PouringStep(allStatus, end, logHash);
hashCode = -1;
int value = 0;
List<string> logStep = new List<string>();
while (true)
{
logHash.TryGetValue(hashCode, out value);
if(hashCode != -1)
logStep.Add(hashCode.ToString("000000"));
if (hashCode == value)
break;
hashCode = value;
}
logStep.Reverse();
}
//获取所有下一步的状态
private void PouringStep(int[][] allPouringStatus, int end, Dictionary<int, int> logHash)
{
List<int[]> allStatus = new List<int[]>();
int hashcode;
int[] newStatus;
foreach (int[] status in allPouringStatus)
{
for (int i = 0; i < status.Length; i++)
{
for (int j = 0; j < status.Length; j++)
{
if (j == i)
continue;
newStatus = PouringFromTo(status, i, j);
if (newStatus == null)
continue;
hashcode = GetHashCode(newStatus);
if (logHash.ContainsKey(hashcode))
continue;
allStatus.Add(newStatus);
logHash.Add(hashcode, GetHashCode(status));
if (CompareArray(newStatus, end))
{
//如果满足了条件,加入-1标识
logHash.Add(-1, hashcode);
return;
}
}
}
}
PouringStep(allStatus.ToArray(), end, logHash);
}
//查找是否有符合条件的结果
private bool CompareArray(int[] Array1, int end)
{
for (int i = 0; i < Array1.Length; i++)
{
if (Array1[i] == end)
return true;
}
return false;
}
//倒油
private int[] PouringFromTo(int[] currentStatus, int fromBottle, int toBottle)
{
//桶的容量写在这里
int[] bottleVol = new int[] { 12, 8, 5 };
//如果from为0或者to已经满了
if (currentStatus[fromBottle] <= 0 || currentStatus[toBottle] == bottleVol[toBottle])
return null;
int[] newStatus = (int[])currentStatus.Clone();
//要么把当前桶倒空,要么把目标桶倒满
if (currentStatus[fromBottle] + currentStatus[toBottle] <= bottleVol[toBottle])
{
newStatus[toBottle] += newStatus[fromBottle];
newStatus[fromBottle] = 0;
}
else
{
newStatus[fromBottle] -= (bottleVol[toBottle] - currentStatus[toBottle]);
newStatus[toBottle] = bottleVol[toBottle];
}
return newStatus;
}
//计算状态的hash
private int GetHashCode(int[] status)
{
//如果桶的容积较大,需要对baseArray做相应的调整
int[] baseArray = new int[] { 1, 100, 10000 };
int code = 0;
for (int i = 0; i < status.Length; i++)
{
code += status[i] * baseArray[status.Length - i - 1];
}
return code;
}
结果是:
120000
040800
040305
090300
090003
010803
010605
c++代码：
#include <iostream>
#include <string>
#include <hash_map>
#include <deque>
#include <vector>
using namespace std;
using namespace stdext;
typedef struct StatusNode
{
int data[3];
StatusNode* next;
StatusNode* parent;
}StatusNode,StatusList;
const int N=3;
const int CAP[N]={12,8,5};
const int INIT[N]={12,0,0};
const int DEST=6;
int for_hash[N]={10000,100,1 };
hash_map<int,int> status_hash;
deque<StatusNode*> bfsq;
StatusNode* SList;
vector<int> solvepath;
int StatusHash(int status[])
{
int hashsum=0;
for(int i=0;i<N;i++)
{
hashsum+=for_hash[i]*status[i];
}
return hashsum;
}
bool BeHandled(int status[])
{
int hashnum=StatusHash(status);
hash_map<int,int>::const_iterator iter;
iter=status_hash.find(hashnum);
if(iter!=status_hash.end())
return true;
else
return false;
}
void StatusCopy(const int* src,int* dst)
{
for(int i=0;i<N;i++)
{
dst[i]=src[i];
}
}
bool GenerateStatus(StatusNode* src,StatusNode* dst,int from,int to)
{
if(src->data[from]<=0 || src->data[to]>=CAP[to])
return false;
StatusCopy(src->data,dst->data);
if(src->data[from]+src->data[to]<=CAP[to])
{
dst->data[from]=0;
dst->data[to]+=src->data[from];
}
else
{
dst->data[to]=CAP[to];
dst->data[from]-=(CAP[to]-src->data[to]);
}
dst->parent=src;
return true;
}
void InsertStatusNode(StatusNode* node)
{
node->next=SList->next;
SList->next=node;
}
bool IsEndStatus(StatusNode* node)
{
for(int i=0;i<N;i++)
{
if(node->data[i]==DEST)
return true;
}
return false;
}
bool BFSFind()
{
StatusNode *p,*q;
SList=(StatusNode*)malloc(sizeof(StatusNode));
SList->next=NULL;
StatusNode* initnode=(StatusNode*)malloc(sizeof(StatusNode));
StatusCopy(INIT,initnode->data);
initnode->parent=NULL;
InsertStatusNode(initnode);
bfsq.push_back(initnode);
status_hash[StatusHash(initnode->data)]=1;
/////////////
while(!bfsq.empty())
{
StatusNode* curnode=bfsq.front();
bfsq.pop_front();
if(IsEndStatus(curnode))
{
while(curnode->parent!=NULL)
{
solvepath.push_back(StatusHash(curnode->data));
curnode=curnode->parent;
}
solvepath.push_back(StatusHash(curnode->data));
p=SList->next;
SList->next=NULL;
while(p!=NULL)
{
q=p->next;
free(p);
p=q;
}
return true;
}
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
if(i==j)
continue;
StatusNode* newnode=(StatusNode*)malloc(sizeof(StatusNode));
if(GenerateStatus(curnode,newnode,i,j) && !BeHandled(newnode->data))
{
InsertStatusNode(newnode);
bfsq.push_back(newnode);
status_hash[StatusHash(newnode->data)]=1;
}
else
free(newnode);
}
}
}
p=SList->next;
SList->next=NULL;
while(p!=NULL)
{
q=p->next;
free(p);
p=q;
}
return false;
}
int _tmain(int argc, _TCHAR* argv[])
{
if(BFSFind())
{
cout<<"可行解:"<<endl;
for(int i=(int)solvepath.size()-1;i>=0;i--)
{
int hashnum=solvepath[i];
for(int j=0;j<N;j++)
{
cout<<hashnum/for_hash[j]<<"/t";
hashnum%=for_hash[j];
}
cout<<endl;
}
}
else
cout<<"没有找到可行解"<<endl;
system("pause");
return 0;
}