数据结构之栈与递归的应用（汉诺塔递归解法）

冷不防 2022-05-31 06:12 151阅读 0赞

上一节简单的讲述了递归的实现与简单应用，接下来我们说一下另一个经典应用。

汉诺塔递归解法

一．起源：

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

二．抽象为数学问题：

如下图所示，从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数。

![70][]

实现这个算法可以简单分为三个步骤：

1.把n-1个盘子由A 移到 B；

2.把第n个盘子由 A移到 C；

3.把n-1个盘子由B 移到 C；

从这里入手，在加上上面数学问题解法的分析，我们不难发现，移到的步数必定为奇数步：

1.中间的一步是把最大的一个盘子由A移到C上去；

2.中间一步之上可以看成把A上n-1个盘子通过借助辅助塔（C塔）移到了B上，

3.中间一步之下可以看成把B上n-1个盘子通过借助辅助塔（A塔）移到了C上；

![v2-a3c945db9b5a2e8fd455bbc4c7fbce35_hd.jpg][] ![v2-4d14e3c3e893135a9d26fdf11984b493_hd.jpg][] ![v2-7a2c13480cf2c9ab79aa490df4a642ac_hd.jpg][] ![v2-24990a5accb631335dc665f6356b8e55_hd.jpg][] ![v2-fc54c46260c35a0e894a26f74b1735af_hd.jpg][]

通过以上的算法模型可以编写如下函数：

void hanoi(int n, char a, char b, char c)
    {
    	 static int cnt = 0;
        if( n > 0 )
        {
            if( n == 1 )
               	printf("%d times ==> %c -> %c\n", ++cnt,a, c);
            else{
                hanoi(n-1, a, c, b);            
                printf("%d times ==> %c -> %c\n", ++cnt,a, c);            
                hanoi(n-1, b, a, c);
            }
        }
    }

[如何理解汉诺塔的递归？（比较经典）][Link 1]  
[C语言实现代码下载地址：][C]

[70]: /images/20220531/f8ef181d41214628a22177f44c41245a.png
[v2-a3c945db9b5a2e8fd455bbc4c7fbce35_hd.jpg]: https://pic3.zhimg.com/80/v2-a3c945db9b5a2e8fd455bbc4c7fbce35_hd.jpg
[v2-4d14e3c3e893135a9d26fdf11984b493_hd.jpg]: https://pic3.zhimg.com/80/v2-4d14e3c3e893135a9d26fdf11984b493_hd.jpg
[v2-7a2c13480cf2c9ab79aa490df4a642ac_hd.jpg]: https://pic1.zhimg.com/80/v2-7a2c13480cf2c9ab79aa490df4a642ac_hd.jpg
[v2-24990a5accb631335dc665f6356b8e55_hd.jpg]: https://pic4.zhimg.com/80/v2-24990a5accb631335dc665f6356b8e55_hd.jpg
[v2-fc54c46260c35a0e894a26f74b1735af_hd.jpg]: /images/20220531/850597ff769d4bcdbb6e2ae20305641a.png
[Link 1]: https://www.zhihu.com/question/24385418
[C]: http://download.csdn.net/download/u014754841/10246751