论坛首页 编程语言技术论坛

C++用递归解决汉诺塔问题

浏览 3969 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2009-05-18  
C++
递归确实是一个不错的算法,可以将原来很复杂的问题简化.这里要注意的就是要确定一个出口条件.不然会出现段错误,,也就是栈溢出.
  汉诺塔问题这里不再赘述,而它的出口条件也就是移动一个盘子,从源地址移动到目的位置.而如果要用递归的方法来实现就要将移动的方法简化,我们先考虑移动n-1个盘子,从源移动到临时位置,然后还剩下一个盘子,就将其移动到目的位置即可.
   但是用递归也有一定的缺点,它比较占用资源,虽然算法简单.
#include <iostream.h>
//use namespace std;

//num:个数   src:源  dst:目的地  tmp: 临时位置
void hano(unsigned int num,char src,char dst,char tmp);

int main(void)
{
	int t;
	cout << "Please input an integer : ";
	cin >> t;
	hano(t,'A','C','B');
}

void hano(unsigned int num,char src,char dst,char tmp)
{
	if(1==num)	cout << src << " --> " << dst << endl;
	else
	{
		hano(num-1,src,tmp,dst);
		hano(1,src,dst,tmp);
		hano(num-1,tmp,dst,src);
	}

}
论坛首页 编程语言技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics