汉诺塔问题的递归算法_C语言递归汉诺塔每一步详解「建议收藏」

一、问题描述

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

二、递归算法

        个人认为递归算法核心主要有以下几点：递归变量、递归过程、递归结束条件，其中难点在于怎么模拟递归过程以及如何寻找递归变量，对于不同的问题这两个核心所呈现的具体代码都是不一样的，但都有共同的特点。所以，建议读者不仅仅以解决汉诺塔问题为目标，更要理解递归思想，掌握递归算法在各种问题中的使用。

1.递归变量

        在每一个能够使用递归算法解决的问题中，题目会提供关键信息，我们需要在其中找到递归变量，这取决于你对信息解剖能力，如果一开始无法快速找到递归变量不用过于伤心，在往后的不断学习中，你会慢慢提高自己的编程能力，能够快速分析现实问题和程序之间的关系，从而找到递归变量，那些变量是在递归函数中表示递归层数或者起到其它作用，例如汉诺塔问题中，层数n，以及柱子位置A,B,C则是递归开始。

2.递归过程

        递归过程是递归算法中的关键行为，这个关键行为在解决问题中可以不断重复循环，最后递归变量达到结束条件就退出递归函数。如何在问题中找到这个关键行为是较难的，但这也是区分您是否理解递归思想。在分析汉诺塔问题，我们可以借助位置B，先把n-1层以上的圆盘放到B位置，然后把第n个圆盘放到C位置上，最后将n-1层以上的圆盘放到C位置上，那么就能够轻松解决问题了，但是，对于n-1层是如何移动B位置上的的呢？聪明的你可能已经发现n-1层圆盘从A移动到B上其实与n层圆盘移动到C位置上是一样的过程，即先把n-2层圆盘放到位置C上再把第n-1个圆盘放到位置B 上，最后n-2层圆盘放到B上，那么对于n-2层圆盘是如何放到C上的呢?其实这是一个重复性的过程。

        在这里为了将问题简单化，我们设置了三个变量：开始位置A、辅助位置B、目标位置C，开始位置A放置所有圆盘，将n-1层圆盘放置辅助位置B后，再将第n个圆盘放置目标位置C，然后将n-1层圆盘的位置B作为开始位置A，原来的开始位置A作为辅助位置B，将所有圆盘放到目标位置C。这个过程的关键点在于什么时候开始位置A和辅助位置B互换？

         我们最开始需要把n-1层圆盘放到辅助位置B，在放置n-1层圆盘时，我们把辅助位置B当作是目标位置C，将其将第n-1个圆盘放到它的目标位置，那么如此一来n-2层圆盘需要一个辅助位置所以此时辅助位置B与目标位置互换，按照这个想法不断寻找上一层圆盘，直至第一层圆盘时我们将其放置在目标位置C上即可（注意：此时的目标位置C可能不是原来的C），然后在回溯的过程中不断输入移动的圆盘（作用是看到圆盘移动的过程）。当n-1层圆盘移动到辅助位置B时，将第n个移动到目标位置C后，需要将第n-1个圆盘移动到目标位置C，此时则借助开始位置A，所以在这里，开始位置A需要与辅助位置B互换，原本n-1层圆盘所在的位置变成开始位置，然后重复搬圆盘的过程，直至所有圆盘放入目标圆盘，完成递归。

3.递归结束条件

        递归结束条件是用以结束递归过程的重复，如果没有结束条件，函数将会一直递归下去，使得程序陷入死循环中。那么如何找到递归结束条件呢？可以从递归变量中寻找，例如汉诺塔问题中，递归结束条件语句在于层数，当发现递归到第一层圆盘时，我们可以直接将它放到目标位置上，然后就是回溯的过程，这个工作就交给计算机，我们只需分析问题，写出解决问题的代码。

三、汉诺塔问题具体代码

#include <iostream>
using namespace std;
void move(int n, char A, char B, char C) {      //n代表现在需要将第n个圆盘放到目标位置C
    if (n == 1)                                 //当递归到第1个圆盘时，直接将其放到目标位置C
        cout << A << "->" << C << endl;
    else {
        move(n - 1,A,C,B);    //1.将n-1层圆盘放到辅助位置B
                              //2.对于第n-1个圆盘，把B当作目标位置，C当作辅助位置，所以BC互换
        cout << A << "->" << C << endl;         //将第n个圆盘放到目标位置C上
        move(n - 1,B,A,C);         //1.将n-1层圆盘放到目标位置C
                                   //2.对于n-2层圆盘，A当作辅助位置，B当作开始位置，所以AB互换
    }
}
int main()
{
    move(64,'A', 'B', 'C');            //开始时，A是开始位置，B是辅助位置，C是目标位置
    return 0;
}

  注意：本代码以64层圆盘移动，若需要其他层圆盘，只需修改64数字即可。

今天的文章汉诺塔问题的递归算法_C语言递归汉诺塔每一步详解「建议收藏」分享到此就结束了，感谢您的阅读。