/*请设计程序解决“波松分酒问题”问题如下：某人有12品脱啤酒一瓶，想从中倒出6品脱，但他没有6品脱的容器，仅有一个8品脱和一个5品脱的容器，怎样才能将啤酒分为两个6品脱？抽象分析:b = 大容器,也表示容积s = 小容器,也表示容积(f),(h),(e) 状态f=满, e=空, h=数字,表示容量运算一: b(f) - s(e) => b(b - s), s(f)变例 b(h) - s(e) => b(h - s), s(f)运算二: b(e) + s(f) => b(s), s(e)变例 b(h) + s(f) => b(f), s(s - b + h)引出 b(f) - s(h) b(h) - s(h) b(e) + s(h) b(h) + s(h) 如果以瓶中酒的数量为节点, 通过一次以上运算可达到节点之间认为连通.此题可转化为一个有向图的搜索问题.即找出.指定节点(12, 0, 0) 和 (6, 6, 0)之间的最小路径. */#include <cstdio>#include <deque>#include <map>#include <utility>#include <queue>static int big_max_value[] ={ 12, 8, 12};static int small_max_value[] ={ 8, 5, 5};static const int big_offset[] ={ 0, 1, 0};static const int small_offset[] ={ 1, 2, 2};//节点定义class Node{ unsigned char mBig; unsigned char mMid; unsigned char mSmall;public: static void InitMaxValue(int max1, int max2, int max3) { big_max_value[0] = max1; big_max_value[1] = max2; big_max_value[2] = max1; small_max_value[0] = max2; small_max_value[1] = max3; small_max_value[2] = max3; } Node() : mBig(0), mMid(0), mSmall(0) { } Node(unsigned char a, unsigned char b, unsigned char c) : mBig(a), mMid(b), mSmall(c) { } enum OPCODE { BIG_OP_MIDDLE = 0, MIDDLE_OP_SMALL, BIG_OP_SMALL, OP_LAST }; //减运算 void sub(OPCODE op) { int big_max = big_max_value[op]; int small_max = small_max_value[op]; char& big = *(reinterpret_cast<char*>(this) + big_offset[op]); char& small = *(reinterpret_cast<char*>(this) + small_offset[op]); if (big > (small_max - small)) { big -= (small_max - small); small = small_max; } else { small += big; big = 0; } } //加运算 void add(OPCODE op) { int big_max = big_max_value[op]; int small_max = small_max_value[op]; char& big = *(reinterpret_cast<char*>(this) + big_offset[op]); char& small = *(reinterpret_cast<char*>(this) + small_offset[op]); if (small > big_max - big) { small -= big_max - big; big = big_max; } else { big += small; small = 0; } } bool check(int value) { if (mBig == value || mMid == value || mSmall == value) { return true; } return false; } void print() const { printf("status [%d]=%2d, [%d]=%2d, [%d]=%2dn", big_max_value[0], mBig, big_max_value[1], mMid, small_max_value[2], mSmall); } //相等性判定 friend bool operator==(Node const & a, Node const & b) { return memcmp(&a, &b, sizeof(Node)) == 0; } friend bool operator <(Node const & a, Node const & b) { return memcmp(&a, &b, sizeof(Node)) < 0; }};template <class T>void Search(T start, int value){ typedef std::pair<T, T> NodeValueType; typedef std::map<T, T> NodeSet; typedef NodeSet::iterator NodeSetIter; typedef std::queue<NodeValueType, std::deque<NodeValueType> > NodeQueue; NodeSet visited; NodeQueue searchQueue; NodeValueType last; searchQueue.push(std::make_pair(start, start)); while (!searchQueue.empty()) { NodeValueType cur = searchQueue.front(); searchQueue.pop(); visited.insert(cur); if (cur.first.check(value)) { last = cur; break; } for (int i = 0; i < Node::OP_LAST; i++) { Node next1 = cur.first; next1.sub(static_cast<Node::OPCODE>(i)); if (visited.find(next1) == visited.end()) { searchQueue.push(std::make_pair(next1, cur.first)); } Node next2 = cur.first; next2.add(static_cast<Node::OPCODE>(i)); if (visited.find(next2) == visited.end()) { searchQueue.push(std::make_pair(next2, cur.first)); } } } NodeSetIter cur = visited.find(last.first); while (!(cur->first == start)) { cur->first.print(); cur = visited.find(cur->second); } cur->first.print();}int main(){ puts("某人有12品脱啤酒一瓶，想从中倒出6品脱，但他没有6品脱的容器，n" "仅有一个8品脱和一个5品脱的容器，怎样才能将啤酒分为两个6品脱？n"); for (int i = 0; i < 12; i++) { printf("---查找取得%d品脱的最少步骤,逆序------------n", i); Search(Node(12, 0, 0), i); } puts("再解一个由13品脱啤酒，却一个9品脱和一个5品脱的容器n"); Node::InitMaxValue(13, 9, 5); for (int i = 0; i < 12; i++) { printf("---查找取得%d品脱的最少步骤,逆序------------n", i); Search(Node(13, 0, 0), i); } return 0;}实际上的最后一步,结果应是(6,6,0)但事实上我只做到出现一个6的情况.原因是并非所有结果都有两个相同的值.以下是我做出来的12,8,5的最优解法:某人有12品脱啤酒一瓶，想从中倒出6品脱，但他没有6品脱的容器，仅有一个8品脱和一个5品脱的容器，怎样才能将啤酒分为两个6品脱？---查找取得0品脱的最少步骤,逆序------------status [12]=12, [8]= 0, [5]= 0---查找取得1品脱的最少步骤,逆序------------status [12]= 1, [8]= 8, [5]= 3status [12]= 9, [8]= 0, [5]= 3status [12]= 9, [8]= 3, [5]= 0status [12]= 4, [8]= 3, [5]= 5status [12]= 4, [8]= 8, [5]= 0status [12]=12, [8]= 0, [5]= 0---查找取得2品脱的最少步骤,逆序------------status [12]= 2, [8]= 5, [5]= 5status [12]= 7, [8]= 5, [5]= 0status [12]= 7, [8]= 0, [5]= 5status [12]=12, [8]= 0, [5]= 0---查找取得3品脱的最少步骤,逆序------------status [12]= 4, [8]= 3, [5]= 5status [12]= 4, [8]= 8, [5]= 0status [12]=12, [8]= 0, [5]= 0---查找取得4品脱的最少步骤,逆序------------status [12]= 4, [8]= 8, [5]= 0status [12]=12, [8]= 0, [5]= 0---查找取得5品脱的最少步骤,逆序------------status [12]= 7, [8]= 0, [5]= 5status [12]=12, [8]= 0, [5]= 0---查找取得6品脱的最少步骤,逆序------------status [12]= 1, [8]= 6, [5]= 5status [12]= 1, [8]= 8, [5]= 3status [12]= 9, [8]= 0, [5]= 3status [12]= 9, [8]= 3, [5]= 0status [12]= 4, [8]= 3, [5]= 5status [12]= 4, [8]= 8, [5]= 0status [12]=12, [8]= 0, [5]= 0---查找取得7品脱的最少步骤,逆序------------status [12]= 7, [8]= 0, [5]= 5status [12]=12, [8]= 0, [5]= 0---查找取得8品脱的最少步骤,逆序------------status [12]= 4, [8]= 8, [5]= 0status [12]=12, [8]= 0, [5]= 0---查找取得9品脱的最少步骤,逆序------------status [12]= 9, [8]= 3, [5]= 0status [12]= 4, [8]= 3, [5]= 5status [12]= 4, [8]= 8, [5]= 0status [12]=12, [8]= 0, [5]= 0---查找取得10品脱的最少步骤,逆序------------status [12]=10, [8]= 2, [5]= 0status [12]= 5, [8]= 2, [5]= 5status [12]= 5, [8]= 7, [5]= 0status [12]= 0, [8]= 7, [5]= 5status [12]= 7, [8]= 0, [5]= 5status [12]=12, [8]= 0, [5]= 0---查找取得11品脱的最少步骤,逆序------------status [12]=11, [8]= 0, [5]= 1status [12]= 3, [8]= 8, [5]= 1status [12]= 3, [8]= 4, [5]= 5status [12]= 8, [8]= 4, [5]= 0status [12]= 8, [8]= 0, [5]= 4status [12]= 0, [8]= 8, [5]= 4status [12]= 4, [8]= 8, [5]= 0status [12]=12, [8]= 0, [5]= 0注意这个解法通用性很强,还可以解其它的组合:如最后的13,9,5.
评论