网易游戏校招笔试)"/>
宝石商人(2016网易游戏校招笔试)
题目描述:小金同学是某个游戏内的商人,他在游戏中只买一种叫做‘月亮石’的宝石,为了方便,他有三个游戏账号即三个仓库,然后在不同账号间转月亮石。其规矩为要么清仓,要么把仓库填满。给出初始化三个账号的容量,假设初始状态A、B仓库无月亮石,C仓库满仓月亮石。小金同学不停地在账号间转月亮石,输出当A账号为空时,C账号可能的月亮石个数,每种情况以‘,’隔开。
样例输入:7 8 9
样例输出:1,2,7,8,9
其仓库的状态总共有一下几种:
其代码如下,不足之处请交流指正:
#include<iostream>
#include<string>
#include<sstream>
#include<set>
struct state
{
int anum; int bnum; int cnum;
state(int x, int y, int z) :anum(x), bnum(y), cnum(z){};
bool operator <(const state &in) const
{
if (anum < in.anum)
return true;
else if (anum == in.anum)
{
if (bnum < in.bnum)
return true;
else if (bnum == in.bnum)
{
if (cnum < inum)
return true;
else return false;
}
else return false;
}
else return false;
}
};
int Asize, Bsize, Csize;
set<state> statelist;
set<int> possibleAnswer;
//递归实现
void getQTY_basic(const int x, const int y, const int z)
{
if (statelist.find(state(x, y, z)) == statelist.end()) //如果集合已是出现的状态,这个递归分支则结束
{
statelist.insert(state(x, y, z));
if (x == 0)
possibleAnswer.insert(z);
if (x != 0)
{
if (Bsize - y > x)
getQTY_basic(0, x + y, z);
else
getQTY_basic(x - Bsize + y, Bsize, z);
if (Csize - z > x)
getQTY_basic(0, y, z + x);
else
getQTY_basic(x - Csize + z, y, Csize);
}
if (y!=0)
{
if (Asize - x > y)
getQTY_basic(x + y, 0, z);
else
getQTY_basic(Asize, y - Asize + x, z);
if (Csize - z > y)
getQTY_basic(x, 0, z + y);
else
getQTY_basic(x, y - Csize + z, Csize);
}
if (z != 0)
{
if (Asize - x > z)
getQTY_basic(x + z, y, 0);
else
getQTY_basic(Asize, y, z - Asize + x);
if (Bsize - y > z)
getQTY_basic(x, z + y, 0);
else
getQTY_basic(x, Bsize, y - Bsize + z);
}
}
}
string getQTY(int x, int y, int z)
{
possibleAnswer.clear();
statelist.clear();
getQTY_basic(x, y, z);
stringstream s;
string buf;
for (set<int>::iterator i = possibleAnswer.begin(); i != possibleAnswer.end(); i++)
s << *i << ',';
s >> buf;
return buf;
}
int main()
{
cin >> Asize >> Bsize >> Csize;
cout << getQTY(0, 0, Csize)<<endl;
// for each (state var in statelist) //此处是输出每种可能的状态
// cout << var.anum << ' ' << var.bnum << ' ' << varum << endl;
}
更多推荐
宝石商人(2016网易游戏校招笔试)
发布评论