好sf 你能走到2012吗 ?? 一个恶作剧的编程求解 - fmddlmyy的专栏 - 博客频道 - CSDN.NET强制页面不缓存 --传奇私发服1.76-传奇世界SF

在搜索到这条路径时，程序已经遍历到路径树的第29层，访问到第165278个节点。显然这道题不适合用手工推导。

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

class CNode {public:// 取节点的第一个子节点。如果没有子节点，返回NULL，否则返回指向子节点的指针virtual CNode * GetFirstChild() const = 0;// 取节点的下一个兄弟节点。如果没有下一个兄弟节点，返回false，否则返回truevirtual 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::vectorCLayeredTree;typedef std::stackCNodeStack;// 在按层次创建树的同时实现树的按层次遍历，即从上到下，从左到右class CTreeLayeredTraverse {public:CTreeLayeredTraverse(CNode *root);~CTreeLayeredTraverse();static unsigned int MaxNodeNum;static unsigned int MaxLayerNum;// 创建并遍历树。当以下情况之一发生时会停止创建：// 1. 某一层的所有节点都没有子节点// 2. AfterCreateNode返回false// 3. 已创建节点数量超过MaxNodeNum// 4. 已创建层数超过MaxLayerNumvoid 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函数};

定义过状态后，还要描述状态间的可达关系。CPuzzle2012类通过GetFirstChildState和GetNextBrotherState提供了状态的遍历接口。这两个接口函数又是对实际路由数据route_table的封装。route_table就是前面有向图的数据表示。

AfterCreateNode判断终止条件是否满足。在找到期望路径后，AfterCreateNode调用帮助函数ShowPath打印路径。ShowPath将CTreeLayeredTraverse::GetPath压栈的节点出栈、打印一下就可以了。

2. 分析

3.2.2 CPuzzle2012

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;}

如果这是一道正常的益智题，岳父大人既然做不出来，我是肯定做不出来的。不过看过题目后,电信传奇私服发布网，我觉得这个题目就是一个典型的编程作业。把编程作业当作益智题，显然是个恶作剧了。下面简单介绍一下如何编程求解这道题目。

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 stateint m_value;// current valuevoid ShowPath(const CTreeLayeredTraverse &tree) const;};

CTreeLayeredTraverse::CTreeLayeredTraverse(CNode *root){CLayer *pLayer = new CLayer;root->SetParent(NULL);pLayer->push_back(root);m_tree.push_back(pLayer);m_node_num = 1;}

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 "";}}

void CTreeLayeredTraverse::GetPath(const CNode *pNode, CNodeStack &path) const{path.push(pNode);while (NULL != (pNode = pNode->GetParent())) {path.push(pNode);}}

在使用vector和stack时，如果模板参数不用指针，在离开变量作用域时，模板库就会自动释放内存，比较方便。但在这个问题里，因为CNode是虚类，模板库不知道对象的实际大小，无法分配内存，所以只能用指针。这样我们就需要在析构函数里自己释放对象。当节点数量很大时，这个析构函数相当耗时。如果是现实项目，这个地方还需要优化。

问题很简单：找一条从点(1)到点(3)的路径，要求初始值2011经过沿途的计算后，在点(3)得到2012。可以转圈走，但不能走回头路。即从点A走到点B后，不能立刻从点B走回点A。

在实际编码时，我在写完CNode和CTreeLayeredTraverse的声明后，就开始写应用逻辑了，即所谓面向接口编程和测试驱动开发。尽早让程序可以编译、运行，就可以尽早发现早期设计的缺陷，减少返工。这里为了叙述方便，我还是先介绍CTreeLayeredTraverse的实现。CreateAndTraverse在按层次构建树的同时遍历树的节点。在实现上就是找到前一层中每个节点的子节点放到新层的vector中。

CPuzzle2012Node定义了应用需要的数据成员m_state和m_value。另外实现了CNode类要求的接口：

CPuzzle2012类接着翻译题目。

在区分出所有状态后，我们就可以根据题目的约束条件画出状态的转移图：

与现实世界一样，我们在编程时也要面临各种选择。在节点类型上，我要选择是通过模板还是接口实现。我选择了传统的接口实现：即定义一个节点接口CNode给遍历算法CTreeLayeredTraverse使用。应用程序可以从节点接口派生自己的节点类，增加特定于应用的数据和逻辑。CNode和CTreeLayeredTraverse的声明如下：

将一个编程作业作为一道数学益智题，显然是一个无聊的恶作剧。程序员可以通过编程解题，只是因为这是一道编程题，并不说明程序员这个职业有任何特殊之处。事实上，在现实世界中，有太多问题是无法通过编程解决的，同时大多数程序员都必须具备各个领域的专业知识。编程是一种手工技能，在对这种技能熟悉到一定程度后，进一步的提高通常是在编程之外了。

除了状态外，树的每个节点还有一个随路径变化的当前值。因为前面定义的状态包含了刚经过的路径,传奇私服教程，所以GetValue函数可以根据状态计算当前值。

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];};

AddNode是一个帮助函数。CNode的成员m_parent是由CTreeLayeredTraverse类更新的。应用代码只要负责维护自己增加的成员。

面向对象编程的主要工作是类的定义。类定义对所涉及问题的客观实体进行高度抽象，得到与具体问题相符合的类的层次结构和操作。主函数只是对类定义的调用，通常是很简单的：

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);}}

3.2 应用部分

构造函数创建树的第一层。第一层只有一个根节点：

3.1 树的按层次遍历

首先是状态的定义：

最后一个GetPath函数很简单,好sf，它演示了std::stack的压栈,合击传奇。后面的CPuzzle2012Node::ShowPath会演示std::stack的出栈。

程序员解题的第一步就是从适合编程的角度重新描述问题。这道题虽然看上去只有3个点，但考虑到下一步可以走的路，在同一个点会有多个状态。例如：如果从(+7)走到点(2)，下一步可以走(+7)以外的3条路；如果从(/2)走到点(2)，下一步可以走(/2)以外的3条路。因此，我们可以区分出以下状态：

在有了这张有向图后，我们可以重新描述问题：从点(1.0)出发，遍历这张图的所有路径。在点(3.3)和(3.5)检查当前路径是否满足要求。满足则停止，不满足就接着走。有向图只是给出了路径的约束条件，我们要遍历的所有路径显然会构成了一棵树：

3.2.4 主函数

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) ,<a href="http://WWW.HXYGG.COM/">今日新开传奇私服</a>!= 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;}

// 每个元素第一个成员指定一个状态，第二个成员是该状态所有前向可达的状态const unsigned int CPuzzle2012::route_table[][2] = {S10, S27S22,S17, S22,S12, S27,S27, S33S35S12,S22, S33S35S17,S23, S35S12S17,S25, S33S12S17,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;}

1. 缘起

int main(){CTreeLayeredTraverse tree(new CPuzzle2012Node(S10, 2011));tree.CreateAndTraverse();return 0;}

岳父大人拿来一张去年的报纸，说有一道很难做的益智题，让我看看，就是下图中的题目：

实现“树的按层次遍历”的思路很简单。就是按层次构建树，在构建的同时完成遍历。每一层的节点可以用一个vector保存。如果我们不用回溯经过的路径，那就只要保存最后一层节点就可以了。这个问题需要回溯路径，就要保存每层节点了。每个节点还要有一个指向parent的指针。这样在找到期望节点后，就可以从下向上回溯出经过的路径。回溯时将可以节点压栈，再取出后就是由上到下的顺序了。

我们从上到下、从左到右遍历这棵树，找到符合条件的节点：这个节点的状态应该是(3.3)或(3.5)，值是2012。如果这是一个编程作业，这个作业的题目应该是“树的按层次遍历”或者“树的广度优先搜索”。我写了一个小程序算了一下，我搜索了2千万个节点，只找到了一条符合条件的路径：

状态	说明
(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)

enum CPuzzle2012State {S10 = 0x001,// beginningS17 = 0x002,// back to beginning from +7S12 = 0x004,// back to beginning from /2S27 = 0x008,// go to middle point from +7S22 = 0x010,// go to middle point from /2S23 = 0x020,// go to middle point from *3S25 = 0x040,// go to middle point from -5S33 = 0x080,// go to the end from *3S35 = 0x100,// go to the end from -5SINVALID};

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");}

为了使用CTreeLayeredTraverse，需要定义CNode的派生类CPuzzle2012Node：

4. 结束语

3.2.1 状态