醉汉平均分酒的问题！据说曾经是微软的面试题
有三个酒杯，形状都不规则，分别能装8,8,3升酒。
其中两个8升的杯子里面装满了酒。
现在有四个人要分酒，一个人分4升酒，应该怎么分？
用算法来实现这个功能应该怎么实现？
java,c++都可以。
[解决办法]
假设四个人是甲、乙、丙和丁，以下数字格式：
8斤瓶 8斤瓶 3斤瓶 [甲 乙 丙 丁]
8 8 0[0 0 0 0]
8 5 3[0 0 0 0]
8 5 0[3 0 0 0]
8 2 3[3 0 0 0]
8 0 3[3 2 0 0]
8 3 0[3 2 0 0]
5 3 3[3 2 0 0]
5 6 0[3 2 0 0]
2 6 3[3 2 0 0]
2 8 1[3 2 0 0]
2 8 0[3 2 1 0]
2 5 3[3 2 1 0]
7 0 3[3 2 1 0]
7 3 0[3 2 1 0]
4 3 3[3 2 1 0]
4 6 0[3 2 1 0]
1 6 3[3 2 1 0]
0 6 3[3 2 1 1]
0 8 1[3 2 1 1]
0 8 0[4 2 1 1]
0 5 3[4 2 1 1]
0 5 0[4 2 4 1]
0 2 3[4 2 4 1]
0 2 0[4 2 4 4]
0 0 0[4 4 4 4]
[解决办法]
提供一个C++版本的:
#include <map>
#include <list>
#include <iostream>
using namespace std;
#define NUM_CUPS 3
#define NUM_MEN 4
#define P 11
#define HASH_SIZE 10007
struct State{
char cup[NUM_CUPS];
char man[NUM_MEN];
public:
bool operator<(const State& s)const{
int i;
for(i=0;i<NUM_CUPS;i++){
if(cup[i]<s.cup[i])return true;
if(cup[i]>s.cup[i])return false;
}
for(i=0;i<NUM_MEN;i++){
if(man[i]<s.man[i])return true;
if(man[i]>s.man[i])return false;
}
return false;
}
bool operator!=(const State& s)const{return !(*this == s);}
bool operator==(const State& s)const{
int i;
for(i=0;i<NUM_CUPS;i++){
if(cup[i]!=s.cup[i])return false;
}
for(i=0;i<NUM_MEN;i++){
if(man[i]!=s.man[i])return false;
}
return true;
}
void dump()const{
cout<<(int)cup[0]<<','<<(int)cup[1]<<','<<(int)cup[2]<<'['<<(int)man[0]<<','<<(int)man[1]<<','<<(int)man[2]<<','<<(int)man[3]<<']'<<'\n';
}
};
static char maxsize[3]={8,8,3};
typedef map<State,State> StateMap;
typedef list<State> StateStack;
StateMap sMap;
StateStack sStack;
int _tmain(int argc, _TCHAR* argv[])
{
State s,e;
int i,j,k;
s.cup[0]=8;s.cup[1]=8;s.cup[2]=0;s.man[0]=s.man[1]=s.man[2]=s.man[3]=0;
e.cup[0]=e.cup[1]=e.cup[2]=0;e.man[0]=e.man[1]=e.man[2]=e.man[3]=4;
sMap.insert(make_pair(e,e));
sStack.push_back(e);
while(!sStack.empty()){
State cur = sStack.front();
sStack.pop_front();
for(i=0;i<NUM_CUPS;i++)for(j=0;j<NUM_CUPS;j++){
if(j==i)continue;
//try to that some wine is moving from cup i to cup j
if(cur.cup[j]==0)continue;
//The first case, all wines from i is moved to j
if(cur.cup[i] == 0){
for(k=1;k<=cur.cup[j];k++){
State tmp = cur;
tmp.cup[j]-=k;
tmp.cup[i]=k;
if(sMap.find(tmp)!=sMap.end())continue;
sStack.push_back(tmp);
sMap.insert(make_pair(tmp, cur));
if(tmp == s)goto found;
}
}
//The second case, j is filled
if(cur.cup[j]==maxsize[j]){
for(k=1;k<=cur.cup[j];k++){
if(cur.cup[i]+k>maxsize[i])break;
State tmp=cur;
tmp.cup[j]-=k;
tmp.cup[i]+=k;
if(sMap.find(tmp)!=sMap.end())continue;
sStack.push_back(tmp);
sMap.insert(make_pair(tmp,cur));
if(tmp == s) goto found;
}
}
}
for(k=0;k<NUM_CUPS;k++){
if(cur.cup[k]!=0)continue;//try to find a case that one man drink all wine in the cup
for(i=0;i<NUM_MEN;i++){
if(cur.man[i]>0){
int max_drink = cur.man[i];
if(k==NUM_CUPS-1&&max_drink>3)max_drink=3;//The last cup has at most 3
for(j=1;j<=max_drink;j++){
State tmp = cur;
tmp.man[i]-=j;
tmp.cup[k]=j;
if(sMap.find(tmp)!=sMap.end())continue;
sStack.push_back(tmp);
sMap.insert(make_pair(tmp, cur));
if(tmp==s)goto found;
}
}
}
}
}
found:
if(sMap.find(s)==sMap.end()){
cout<<"Fail to find a result\n";
return -1;
}
State cur = s;
cur.dump();
while(cur!=e){
StateMap::iterator it = sMap.find(cur);
cur=it->second;
cur.dump();
}
return 0;
}
