必威体育Betway必威体育官网
当前位置:首页 > IT技术

经典问题之汉诺塔

时间:2019-06-10 13:44:10来源:IT技术作者:seo实验室小编阅读:71次「手机版」
 

汉诺塔

问题描述:

相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。

思路:

以3层的汉诺塔为例:

1、我们可以先将上面两个盘子,借助Z柱移动到Y柱

2、将最后一个盘子移动到Z柱

3、将Y柱的两个盘子,借助X柱移动到Z柱

一切搬圆盘都是在重复上面三个步骤,因此,这三步便是一个递归体,我们可以采用递归的方式实现,至于它到底怎么移动的,我们并不需要知道。

代码实现:

#include <iOStream>
using namespace std;

int count = 0;
//将 n 个盘子从 x 借助 y 移动到 z
int move(int n,char x,char y,char z)
{
	if(1 == n){
		count++;  //将最下面的盘子,从x移动到z
		cout << x << "->" << z << endl;
	}
	else{
		move(n-1, x, z, y); //将n-1个盘子,借助z从x移动到y
		cout << x << "->" << z << endl;
		move(n-1, y, x, z); //将n-1个盘子,借助x从y移动到z
		count++;
	}
	return count;
}

int main()
{
	int n;
	cout << "请输入汉诺塔层数:";
        cin >> n;
	move(n,'X','Y','Z');  // X,Y,Z分别表示3个柱子
	cout << "共需要移动:" <<  count << "次" << endl;
	return 0;
}

结果:

相关阅读

分享到:

栏目导航

推荐阅读

热门阅读