岳父大人拿来一张去年的报纸,说有一道很难做的益智题,让我看看,就是下图中的题目:
如果这是一道正常的益智题,岳父大人既然做不出来,我是肯定做不出来的。不过看过题目后,我觉得这个题目就是一个典型的编程作业。把编程作业当作益智题,显然是个恶作剧了。下面我简单介绍一下如何编程求解这道题目。
问题很简单:找一条从点(1)走到点(3)的路径,初始值2011经过沿途的计算后,在点(3)得到2012。可以转圈走,但不能走回头路。即从点A走到点B后,不能立刻从点B走回点A。
程序员解题的第一步就是从适合编程的角度重新描述问题。这道题虽然看上去只有3个点,但考虑到下一步可以走的路,在同一个点会有多个状态。例如:如果从(+7)走到点(2),下一步可以走(+7)以外的3条路;如果从(/2)走到点(2),下一步可以走(/2)以外的3条路。因此,我们可以区分出以下状态:
状态 | 说明 |
(1.0) | 从点(1)出发 |
(1.7) | 从(+7)到点(1) |
(1.2) | 从(/2)到点(1) |
(2.7) | 从(+7)到点(2) |
(2.2) | 从(/2)到点(2) |
(2.3) | 从(*3)到点(2) |
(2.5) | 从(-5)到点(2) |
(3.3) | 从(*3)到点(3) |
(3.5) | 从(-5)到点(3) |
在区分出所有状态后,我们就可以根据题目的约束条件画出状态的转移图:
在有了这张有向图后,我们就可以重新描述问题:从点(1.0)出发,遍历这张图的所有路径。在点(3.3)和(3.5)检查当前路径是否满足要求。满足则停止,不满足就接着走。有向图只是给出了路径的约束条件,我们要遍历的所有路径显然会构成了一棵树:
我们从上到下、从左到右遍历这棵树,找到符合条件的节点:这个节点的状态应该是(3.3)或(3.5),值是2012。如果这是一个编程作业,这个作业的题目应该是“树的按层次遍历”或者“树的广度优先搜索”。我写了一个小程序算了一下,我搜索了2千万个节点,只找到了一条符合条件的路径:
2011+7=2018 2018/2=1009 1009+7=1016 1016/2=508 508+7=515 515-5=510 510*3=1530 1530/2=765
765+7=772 772/2=386 386+7=393 393*3=1179 1179-5=1174 1174/2=587 587+7=594 594/2=297
297+7=304 304-5=299 299*3=897 897-5=892 892*3=2676 2676/2=1338 1338+7=1345 1345-5=1340
1340*3=4020 4020/2=2010 2010+7=2017 2017-5=2012
在搜索到这条路径时,程序已经遍历到路径树的第29层,访问到第165278个节点。显然这道题不适合用手工推导。
在编程实现时,我们首先做的是区分可以复用的部分和应用特定的部分。在这个问题中,可以复用的部分就是“树的按层次遍历”。应用特定部分就是这道题目的描述了。
实现“树的按层次遍历”的思路很简单。就是按层次构建树,在构建的同时完成遍历。每一层的节点可以用一个vector保存。如果我们不用回溯经过的路径,那就只要保存最后一层节点就可以了。这个问题需要回溯路径,所以我们需要保存每层节点。每个节点还要有一个指向parent的指针。这样在找到期望节点后,我们就可以从下向上回溯出经过的路径。回溯时将可以节点压栈,这样再取出后就是由上到下的顺序了。
与现实世界一样,我们在编程时总是面临各种选择。在节点类型上,我要选择是通过模板还是接口实现。我选择了传统的接口实现:即定义一个节点接口CNode给遍历算法CTreeLayeredTraverse使用。应用程序可以从节点接口派生自己的节点类,增加特定于应用的数据和逻辑。CNode和CTreeLayeredTraverse的声明如下:
class CNode { public: // 取节点的第一个子节点。如果没有子节点,返回NULL,否则返回指向子节点的指针 virtual CNode * GetFirstChild() const = 0; // 取节点的下一个兄弟节点。如果没有下一个兄弟节点,返回false,否则返回true virtual CNode * GetNextBrother() const = 0; // 在创建节点后调用。如果返回false,就停止树的构建 virtual bool AfterCreateNode(const CTreeLayeredTraverse &tree) const = 0; void SetParent(CNode *parent) {m_parent = parent;} const CNode * GetParent() const {return m_parent;} protected: const CNode *m_parent; }; typedef std::vectorCLayer; typedef std::vector CLayeredTree; typedef std::stack CNodeStack; // 在按层次创建树的同时实现树的按层次遍历,即从上到下,从左到右 class CTreeLayeredTraverse { public: CTreeLayeredTraverse(CNode *root); ~CTreeLayeredTraverse(); static unsigned int MaxNodeNum; static unsigned int MaxLayerNum; // 创建并遍历树。当以下情况之一发生时会停止创建: // 1. 某一层的所有节点都没有子节点 // 2. AfterCreateNode返回false // 3. 已创建节点数量超过MaxNodeNum // 4. 已创建层数超过MaxLayerNum void CreateAndTraverse(); // 通过栈返回从根节点到指定节点的路径 void GetPath(const CNode *pNode, CNodeStack &path) const; private: CLayeredTree m_tree; unsigned int m_node_num; // 记录已创建节点数 bool AddNode(CLayer *pLayer, CNode * pNode, CNode * pParent); // helper函数 };
在使用vector和stack时,如果不用指针,在离开变量作用域时,模板库就会自动释放内存。但在这个问题里,因为CNode是虚类,模板库不知道对象的实际大小,无法分配内存,所以只能用指针。这样我们就需要在析构函数里自己释放对象。当节点数量很大时,这个析构函数相当耗时。如果是现实项目,这个地方还需要优化。
CTreeLayeredTraverse::~CTreeLayeredTraverse() { CLayeredTree::iterator layer_pos; CLayer::iterator node_pos; for (layer_pos = m_tree.begin(); layer_pos != m_tree.end(); ++layer_pos) { for (node_pos = (*layer_pos)->begin(); node_pos != (*layer_pos)->end(); node_pos++) { delete (*node_pos); } delete (*layer_pos); } }
构造函数创建树的第一层。第一层只有一个根节点:
CTreeLayeredTraverse::CTreeLayeredTraverse(CNode *root) { CLayer *pLayer = new CLayer; root->SetParent(NULL); pLayer->push_back(root); m_tree.push_back(pLayer); m_node_num = 1; }
在实际编码时,我在写完CNode和CTreeLayeredTraverse的声明后,就开始写应用逻辑了,即所谓面向接口编程和测试驱动开发。尽早让程序可以编译、运行,就可以尽早发现早期设计的缺陷,避免返工。这里为了叙述方便,我先介绍CTreeLayeredTraverse的实现。CreateAndTraverse在按层次构建树的同时遍历树的节点。在实现上就是找到前一层中每个节点的子节点放到新层的vector中。
void CTreeLayeredTraverse::CreateAndTraverse() { CLayer::iterator node_pos; CLayer *pLastLayer; CLayer *pLayer; while (1) { pLastLayer = *(m_tree.end() - 1); // 前一层 pLayer = NULL; // 找出前一层中每个node的所有子节点,并放入新的layer for (node_pos = pLastLayer->begin(); node_pos != pLastLayer->end(); ++node_pos) { CNode * pNode; if (NULL == (pNode = (*node_pos)->GetFirstChild())) continue; // 这个节点没有子节点 if (NULL == pLayer) { pLayer = new CLayer; m_tree.push_back(pLayer); } if (!AddNode(pLayer, pNode, (*node_pos))) return; while (1) { if (NULL == (pNode = pNode->GetNextBrother())) break; // 没有下一个兄弟节点了 if (!AddNode(pLayer, pNode, (*node_pos))) return; } } if (NULL == pLayer) { break; // 没有下一层节点 } else { if (m_tree.size() >= MaxLayerNum) { break; } } } }
AddNode是一个帮助函数。CNode的成员m_parent是由CTreeLayeredTraverse类更新的。应用代码只要负责维护自己增加的成员。
bool CTreeLayeredTraverse::AddNode(CLayer *pLayer, CNode * pNode, CNode * pParent) { bool ret; pNode->SetParent(pParent); pLayer->push_back(pNode); m_node_num++; ret = pNode->AfterCreateNode(*this); if (m_node_num >= MaxNodeNum) { return false; } return ret; }
最后一个GetPath函数很简单,它演示了std::stack的压栈。后面的CPuzzle2012Node::ShowPath会演示std::stack的出栈。
void CTreeLayeredTraverse::GetPath(const CNode *pNode, CNodeStack &path) const { path.push(pNode); while (NULL != (pNode = pNode->GetParent())) { path.push(pNode); } }
简单说:应用部分就是把前面的问题描述翻译成代码。
首先是状态的定义:
enum CPuzzle2012State { S10 = 0x001, // beginning S17 = 0x002, // back to beginning from +7 S12 = 0x004, // back to beginning from /2 S27 = 0x008, // go to middle point from +7 S22 = 0x010, // go to middle point from /2 S23 = 0x020, // go to middle point from *3 S25 = 0x040, // go to middle point from -5 S33 = 0x080, // go to the end from *3 S35 = 0x100, // go to the end from -5 SINVALID };
CPuzzle2012类接着翻译题目。
class CPuzzle2012 { public: static const int VINVALID; static CPuzzle2012State GetFirstChildState(CPuzzle2012State state); static CPuzzle2012State GetNextBrotherState(CPuzzle2012State parent, CPuzzle2012State prev); static int GetValue(int old_value, int state); static const char * GetExp(CPuzzle2012State state); private: static const unsigned int route_table[][2]; };
定义过状态后,还要描述状态间的可达关系。CPuzzle2012类通过GetFirstChildState和GetNextBrotherState提供了状态的遍历接口。这两个接口函数又是对实际路由数据route_table的封装。route_table就是前面有向图的数据表示。
// 每个元素第一个成员指定一个状态,第二个成员是该状态所有前向可达的状态 const unsigned int CPuzzle2012::route_table[][2] = { S10, S27|S22, S17, S22, S12, S27, S27, S33|S35|S12, S22, S33|S35|S17, S23, S35|S12|S17, S25, S33|S12|S17, S33, S25, S35, S23, }; CPuzzle2012State CPuzzle2012::GetFirstChildState(CPuzzle2012State state) { int i, j; int snum = sizeof(route_table)/sizeof(route_table[0]); for (i = 0; i < snum; i++) { if (route_table[i][0] != state) { continue; } // 先找到指定状态 for (j = 0; j < snum; j++) { // 找到指定状态的第一个子状态 if (route_table[i][1] & route_table[j][0]) { return (CPuzzle2012State)route_table[j][0]; } } } // 没有子状态 return SINVALID; } CPuzzle2012State CPuzzle2012::GetNextBrotherState(CPuzzle2012State parent, CPuzzle2012State prev) { int i, j; bool prev_found; int snum = sizeof(route_table)/sizeof(route_table[0]); for (i = 0; i < snum; i++) { if (route_table[i][0] != parent) { continue; } // 先找到父状态 // 然后在父状态的子状态中找前一个子状态 prev_found = false; for (j = 0; j < snum; j++) { if (route_table[i][1] & route_table[j][0]) { if (route_table[j][0] == prev) { prev_found = true; continue; } // 前一个子状态后的下一个子状态 if (prev_found) { return (CPuzzle2012State)route_table[j][0]; } } } } // 没有下一个兄弟状态 return SINVALID; }
除了状态外,树的每个节点还有一个随路径变化的当前值。因为前面定义的状态同时描述了刚经过的路径,所以GetValue函数可以根据状态计算当前值。
const int CPuzzle2012::VINVALID = -1; int CPuzzle2012::GetValue(int old_value, int state) { switch (state) { case S17: case S27: old_value += 7; break; case S12: case S22: // 如果不能被2整除,下面就不可能再算出整数了。可以忽略这个节点。 if ((old_value % 2) != 0) { return VINVALID; } old_value /= 2; break; case S23: case S33: old_value *= 3; break; case S25: case S35: old_value -= 5; break; default: return VINVALID; } return old_value; }
最后一个GetExp函数返回算式的字符串表示。
const char * CPuzzle2012::GetExp(CPuzzle2012State state) { switch (state) { case S17: case S27: return "+7"; case S12: case S22: return "/2"; case S23: case S33: return "*3"; case S25: case S35: return "-5"; break; default: return ""; } }
为了使用CTreeLayeredTraverse,我定义了CNode的派生类CPuzzle2012Node:
class CPuzzle2012Node : public CNode { public: CPuzzle2012Node(CPuzzle2012State state, int value) : m_state(state), m_value(value) {}; virtual CNode * GetFirstChild() const; virtual CNode * GetNextBrother() const; virtual bool AfterCreateNode(const CTreeLayeredTraverse &tree) const; private: CPuzzle2012State m_state; // current state int m_value; // current value void ShowPath(const CTreeLayeredTraverse &tree) const; };
CPuzzle2012Node定义了应用需要的数据成员m_state和m_value。另外实现了CNode类要求的接口:
CNode * CPuzzle2012Node::GetFirstChild() const { CPuzzle2012State state = CPuzzle2012::GetFirstChildState(m_state); if (state == SINVALID) { return NULL; } int value = CPuzzle2012::GetValue(m_value, state); // 如果刚才的状态无效,就要找下一个子状态 while (value == CPuzzle2012::VINVALID) { state = CPuzzle2012::GetNextBrotherState(m_state, state); if (state == SINVALID) { return NULL; } value = CPuzzle2012::GetValue(m_value, state); } return new CPuzzle2012Node(state, value); } CNode * CPuzzle2012Node::GetNextBrother() const { const CPuzzle2012Node * parent = dynamic_cast(m_parent); if (!parent) { return NULL; } CPuzzle2012State state = CPuzzle2012::GetNextBrotherState(parent->m_state, m_state); if (state == SINVALID) { return NULL; } int value = CPuzzle2012::GetValue(parent->m_value, state); // 如果刚才的状态无效,就要找下一个子状态 while (value == CPuzzle2012::VINVALID) { state = CPuzzle2012::GetNextBrotherState(parent->m_state, state); if (state == SINVALID) { return NULL; } value = CPuzzle2012::GetValue(parent->m_value, state); } return new CPuzzle2012Node(state, value); } bool CPuzzle2012Node::AfterCreateNode(const CTreeLayeredTraverse &tree) const { if ((m_state == S33) || (m_state == S35)) { if (m_value == 2012) { ShowPath(tree); return false; } } return true; }
AfterCreateNode判断终止条件是否满足。在找到期望路径后,调用帮助函数ShowPath打印路径。将CTreeLayeredTraverse::GetPath压栈的节点出栈、打印一下就可以了。
void CPuzzle2012Node::ShowPath(const CTreeLayeredTraverse &tree) const { CNodeStack path; tree.GetPath(this, path); const CPuzzle2012Node *pNode; const CPuzzle2012Node *pParent; while (!path.empty()) { pNode = dynamic_cast(path.top()); if (NULL != (pParent = dynamic_cast (pNode->m_parent))) { printf("%d%s=%d ", pParent->m_value, CPuzzle2012::GetExp(pNode->m_state), pNode->m_value); } path.pop(); } printf("\n"); }
面向对象编程的主要工作是类的定义。类定义对所涉及问题的客观实体进行高度抽象,得到与具体问题相符合的类的层次结构和操作。主函数只是对类定义的调用,通常是很简单的:
int main() { CTreeLayeredTraverse tree(new CPuzzle2012Node(S10, 2011)); tree.CreateAndTraverse(); return 0; }
将一个编程作业作为一道数学益智题,显然是一个无聊的恶作剧。程序员可以通过编程解题,只是因为这是一道编程题,并不说明程序员这个职业有任何特殊之处。事实上,在现实世界中,有太多问题是无法通过编程解决的,而大多数程序员都必须具备各个领域的专业知识。编程是一种手工技能,在对这种技能熟悉到一定程度后,进一步的提高通常是在编程之外了。
本文源代码可以从这里下载。