你能走到2012吗? —— 一个恶作剧的编程求解

1. 缘起

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

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

2. 分析

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

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

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

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

3.2 应用部分

简单说：应用部分就是把前面的问题描述翻译成代码。

3.2.1 状态

首先是状态的定义：

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 CPuzzle2012

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

3.2.3 CPuzzle2012Node

为了使用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");
}

3.2.4 主函数

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

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

4. 结束语

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

本文源代码可以从这里下载。