理解汉诺塔递归算法

2019-11-08 02:16:07

字体：大中小

来源：转载

供稿：网友

1. 概述

第一次遇见汉诺塔问题是在数据结构课本上，是一个很经典的递归算子。汉诺塔问题实际上就是要将柱子A上由小到大排列的圆环按照相同的大小顺序移动到柱子C，之间的过程可以使用柱子B。这个问题使用递归和归纳的思想来思考的话就很容易理解了。下面这货就是汉诺塔了

其递归的归纳思想是这样的：（1）首先，当只有一个盘子的时候只需要将A上的1号盘子移动到C上就行了（2）当有2个盘子在A上的时候，需要将A上的1号盘子（由上往下数）移动到B上，再将A上的2号盘子移动到C上，之后将B上的1号盘子移动到C上（3）当有3个盘子在A上的时候，需要将A上的1号和2号盘子移动到B上（需要借助C），之后将A上的3号盘子移动到C上，再将B上的盘子移动到C上（需要借助A）（...）以此类推（N）当有N个盘子在A上的时候，需要将A上的N-1个盘子移动到B上（需要借助C），之后将A上的第N个盘子移动到C上，再将B上的盘子移动到C上（需要借助A）

2. 实现

CHanoi::CHanoi(){	this->m_stepCount = 0;			//设置步数为0}//************************************************************************// 函数名称:    	CHanoi// 访问权限:    	public // 创建日期:		2016/12/27// 创 建 人:		// 函数说明:		汉诺塔类构造函数// 函数参数: 	unsigned int plate_num	定义圆盘的个数// 返 回 值:   	//************************************************************************CHanoi::CHanoi(unsigned int plate_num){	this->m_plateNum = plate_num;	//设置圆盘的个数	this->m_stepCount = 0;			//设置步数为0}CHanoi::~CHanoi(){}//************************************************************************// 函数名称:    	Hanoi_Move// 访问权限:    	public // 创建日期:		2016/12/27// 创 建 人:		NPC// 函数说明:		递归汉诺塔算法// 函数参数: 	unsigned int plate_num	放置的盘子的数目// 函数参数: 	std::string from		盘子的初始放置位置// 函数参数: 	std::string depend		盘子移动需要借助的位置// 函数参数: 	std::string to			盘子移动的目标位置// 返 回 值:   	void//************************************************************************void CHanoi::Hanoi_Move(unsigned int plate_num, std::string from, std::string depend, std::string to){	if (1 == plate_num)	{		cout << "第 " << ++this->m_stepCount << " 步: " << "将盘子" << plate_num << "由 " << from << " 移动到 " << to << endl;		return;	}	else	{		this->Hanoi_Move(plate_num-1, from, to, depend);		cout << "第 " << ++this->m_stepCount << " 步: " << "将盘子" << plate_num << "由 " << from << " 移动到 " << to << endl;		this->Hanoi_Move(plate_num-1, depend, from, to);	}}class CHanoi{public:	CHanoi();	CHanoi(unsigned int plate_num);	~CHanoi();PRivate:	unsigned int m_plateNum;	unsigned int m_stepCount;public:	void Hanoi_Move(unsigned int plate_num, std::string from, std::string depend, std::string to);	//递归汉诺塔算法};调用：	CHanoi* p = new CHanoi();	p->Hanoi_Move(3, "A", "B", "C");3. 结果