【一道有趣的益智题】你能走到2012吗? —— 一个恶作剧的编程求解

曾巧文 发布于:2012-2-8 18:27 分类:学习笔记 标签: 编程

一张去年的报纸,说有一道很难做的益智题,让我看看,就是下图中的题目:

如果这是一道正常的益智题,岳父大人既然做不出来,我是肯定做不出来的。不过看过题目后,我觉得这个题目就是一个典型的编程作业。把编程作业当作益智题,显然是个恶作剧了。下面简单介绍一下如何编程求解这道题目。
2. 分析问题很简单:找一条从点(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个节点。显然这道题不适合用手工推导。
3. 实现在编程实现时,我们首先做的是区分可以复用的部分和应用特定的部分。在这个问题中,可以复用的部分就是“树的按层次遍历”。应用特定部分就是这道题目的描述了。
3.1 树的按层次遍历实现“树的按层次遍历”的思路很简单。就是按层次构建树,在构建的同时完成遍历。每一层的节点可以用一个vector保存。如果我们不用回溯经过的路径,那就只要保存最后一层节点就可以了。这个问题需要回溯路径,就要保存每层节点了。每个节点还要有一个指向parent的指针。这样在找到期望节点后,就可以从下向上回溯出经过的路径。回溯时将可以节点压栈,再取出后就是由上到下的顺序了。
与现实世界一样,我们在编程时也要面临各种选择。在节点类型上,我要选择是通过模板还是接口实现。我选择了传统的接口实现:即定义一个节点接口CNode给遍历算法CTreeLayeredTraverse使用。应用程序可以从节点接口派生自己的节点类,增加特定于应用的数据和逻辑。CNode和CTreeLayeredTraverse的声明如下:
[cpp] view plaincopyprint?

  • 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::vector CLayer;  
  • 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函数  
  • };  

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::vector        CLayer;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是虚类,模板库不知道对象的实际大小,无法分配内存,所以只能用指针。这样我们就需要在析构函数里自己释放对象。当节点数量很大时,这个析构函数相当耗时。如果是现实项目,这个地方还需要优化。
[cpp] view plaincopyprint?

  • 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(){        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);        }}
构造函数创建树的第一层。第一层只有一个根节点: 

[cpp] view plaincopyprint?

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

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中。
[cpp] view plaincopyprint?

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

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类更新的。应用代码只要负责维护自己增加的成员。
[cpp] view plaincopyprint?

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

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的出栈。

[cpp] view plaincopyprint?

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

void CTreeLayeredTraverse::GetPath(const CNode *pNode, CNodeStack &path) const{        path.push(pNode);        while (NULL != (pNode = pNode->GetParent())) {                path.push(pNode);        }}
3.2 应用部分简单说:应用部分就是把前面的问题描述翻译成代码。 
3.2.1 状态首先是状态的定义:

[cpp] view plaincopyprint?

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

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

3.2.2 CPuzzle2012CPuzzle2012类接着翻译题目。

[cpp] view plaincopyprint?

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

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就是前面有向图的数据表示。

[cpp] view plaincopyprint?

  • // 每个元素第一个成员指定一个状态,第二个成员是该状态所有前向可达的状态  
  • 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[0] != state) {  
  •             continue;  
  •         }  
  •   
  •         // 先找到指定状态  
  •         for (j = 0; j < snum; j++) {  
  •             // 找到指定状态的第一个子状态  
  •             if (route_table[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[0] != parent) {  
  •             continue;  
  •         }  
  •   
  •         // 先找到父状态  
  •         // 然后在父状态的子状态中找前一个子状态  
  •         prev_found = false;  
  •         for (j = 0; j < snum; j++) {  
  •             if (route_table[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;  
  • }  

// 每个元素第一个成员指定一个状态,第二个成员是该状态所有前向可达的状态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[0] != state) {                        continue;                }                // 先找到指定状态                for (j = 0; j < snum; j++) {                        // 找到指定状态的第一个子状态                        if (route_table[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[0] != parent) {                        continue;                }                // 先找到父状态                // 然后在父状态的子状态中找前一个子状态                prev_found = false;                for (j = 0; j < snum; j++) {                        if (route_table[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函数可以根据状态计算当前值。 

[cpp] view plaincopyprint?

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

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函数返回算式的字符串表示。 

[cpp] view plaincopyprint?

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

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 "";        }}
3.2.3 CPuzzle2012Node为了使用CTreeLayeredTraverse,需要定义CNode的派生类CPuzzle2012Node: 
[cpp] view plaincopyprint?

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

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类要求的接口: 
[cpp] view plaincopyprint?

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

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判断终止条件是否满足。在找到期望路径后,AfterCreateNode调用帮助函数ShowPath打印路径。ShowPath将CTreeLayeredTraverse::GetPath压栈的节点出栈、打印一下就可以了。
[cpp] view plaincopyprint?

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

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");}
3.2.4 主函数面向对象编程的主要工作是类的定义。类定义对所涉及问题的客观实体进行高度抽象,得到与具体问题相符合的类的层次结构和操作。主函数只是对类定义的调用,通常是很简单的:
[cpp] view plaincopyprint?

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

int main(){        CTreeLayeredTraverse tree(new CPuzzle2012Node(S10, 2011));        tree.CreateAndTraverse();        return 0;}
4. 结束语将一个编程作业作为一道数学益智题,显然是一个无聊的恶作剧。程序员可以通过编程解题,只是因为这是一道编程题,并不说明程序员这个职业有任何特殊之处。事实上,在现实世界中,有太多问题是无法通过编程解决的,同时大多数程序员都必须具备各个领域的专业知识。编程是一种手工技能,在对这种技能熟悉到一定程度后,进一步的提高通常是在编程之外了。
本文源代码可以从这里下载。

ps:觉得很有意思就转来了:http://blog.csdn.net/fmddlmyy/article/details/7234119

版权所有:《曾巧文博客-关注互联网IT技术,记录生活点滴》 => 《【一道有趣的益智题】你能走到2012吗? —— 一个恶作剧的编程求解
本文地址://qiaowen.net/post-1095.html
除非注明,文章均为 《曾巧文博客-关注互联网IT技术,记录生活点滴》 原创,欢迎转载!转载请注明本文地址,谢谢。

有 5620 人浏览,获得评论 0 条

发表评论:

Powered by emlog 粤ICP备12040901号

>>本作品采用-知识共享署名-非商业-禁止演绎-协议-进行许可 |站点地图 | | | | 开放分类目录 |