汉诺塔问题（递归，含图解）

青旅半醒 2022-05-27 02:12 136阅读 0赞

# 1）递归 #

在计算机内的递归是利用**栈**技术实现的（栈也就是先进后出，过两天会出介绍，别错过），递归也就是函数的调用问题，**后调用先返回**，所以我们写递归函数都是从最末尾的过程往前面写。就有一个思想递归就是一个复杂的过程从最后面往前推到最简单的情况，借由计算机从简单到复杂一层一层返回推导。

# 2）经典问题：Hanoi #

## 1.抽象出实现的步骤（递归的思想，一般看n和n-1之间的关系） ##

**1）将n-1块从A以C为临时柱移到B**

**2）此时就将第n块移动到终点柱C**

**3）然后把此时处在B的那n-1块借A移动到C**

## 2.可得公式 ##

不难看出整个过程**将n-1块整体移动了两次，加上第n块自身移动了一次**

**Hanoi(n)=2Hanoi(n-1)+1**

## 3.过程图解 ##

![20180409204008715][]

![20180409204021199][]

![20180409204034387][]![20180409204041442][]

# 3）代码实现Hanoi #

/* 2018/4/6  by SZU—Crayon*/
    #include<iostream>	
    using namespace std;
    int cnt = 0;
    void move(char x, int Num, char z)    //输出移动的步骤
    {
    	cout << "the [" << ++cnt << "] operator:" << endl;
    	cout << "take the No.[" << Num << "] from [ " << x << " ] to [ " << z << " ]" << endl;
    }
    void hanoi(int n, char x, char y, char z)
    {
    	if (n == 1)            //递归结束标志，将最小的一片从X移到Z
    		move(x, 1, z);
    	else
    	{
    		hanoi(n - 1, x, z,  y);     //将n-1片从X经过Z移到Y
    		move(x, n, z);              //最大的一片移到Z
    		hanoi(n - 1, y, x, z);      //n-1片借由X，从Y移到Z
    	}
    }
    int main()
    {
    	int t, size;
    	char x, y, z;
    	cin >> t;
    	while (t--)
    	{
    		cnt = 0;
    		cin >> size;  //输入汉诺塔的片数
    		cin >> x >> y >> z;      //三柱子对应名称
    		hanoi(size, x, y, z);
    	}
    	return 0;
    }

# 4）代码实现过程 #

1  
3  
A B C  
the\[1\] operator:  
take the No.\[1\] from\[A\] to\[C\]  
the\[2\] operator :  
take the No.\[2\] from\[A\] to\[B\]  
the\[3\] operator :  
take the No.\[1\] from\[C\] to\[B\]  
the\[4\] operator :  
take the No.\[3\] from\[A\] to\[C\]  
the\[5\] operator :  
take the No.\[1\] from\[B\] to\[A\]  
the\[6\] operator :  
take the No.\[2\] from\[B\] to\[C\]  
the\[7\] operator :

take the No.\[1\] from\[A\] to\[C\]

# 5）BB #

害怕，我记得上篇的时候我说要出List（STL）的，但这周真的比较忙，不是我渣真的~随笔篇，试水画图将来出树会比较熟悉一点，写这篇汉诺塔是为了引出栈的内容哦！

[20180409204008715]: /images/20220527/e27587c242c3443d84cfcc1f75451010.png
[20180409204021199]: /images/20220527/d3ec482b6840453ebaba7d5573e6fe5f.png
[20180409204034387]: https://img-blog.csdn.net/20180409204034387
[20180409204041442]: /images/20220527/886a118ce16c4d1aa8d6d545a23b5c12.png