经典问题之汉诺塔

末蓝、 2022-05-19 04:13 172阅读 0赞

# 问题描述： #

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

# 思路： #

![70][]

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

# 结果： #

![70 1][]

![70 2][]

![70 3][]

![70 4][]

![70 5][]

[70]: /images/20220519/0fc6540ba4ac453ea6db8c341765bb76.png
[70 1]: /images/20220519/88936f65973f4337944e41fb0e808e81.png
[70 2]: /images/20220519/0116bddb16db4df0b94719a985d282db.png
[70 3]: /images/20220519/f6b5ce0a82274399b867c7bdb956e83e.png
[70 4]: /images/20220519/6807569e00ad43489bd2c94fab0e23c0.png
[70 5]: /images/20220519/f50ecff417074892a6af25701155f823.png