“汉诺塔“问题的递归实现

一、汉诺塔

创新互联是专业的南充网站建设公司，南充接单;提供做网站、网站设计,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行南充网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

下面是一段关于汉诺塔游戏的介绍：

/*

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

*/

简单来说，它的规则就是：每个盘之上不能托比当前盘大小还要大的盘。 在满足这个规则的前提下，要将一端(A端)的所有盘移动到另一端（C）

二、游戏思路

假设有1个盘：则经过的步骤为： A -> C 1步即可

而假设有2个盘，则需要： A -> B , A -> C, B -> C ,总共3步

假设有3个盘，则步骤为： 

A -> C, A -> B, C -> B,  A -> C, B -> A, B -> C, A -> C

一共7步。

似乎能总结出层数和最少的如下规律： 

事实上，的确如此。

三、编程思路

现在如果要求实现一个函数，根据输入的层数n，求出将当前汉诺塔从A移动到C的最少步数，则甚至不需要用程序进行推算，直接用上面的公式  ： 2|^ n - 1 即可。

但如果在上述要求的前提下，还要求出具体的做法，或者说要求每一步的具体步骤，则需要让程序自己进行推算，具体过程如下：

当层数为1层的时候，可以直接让当前盘从A移动到C，

当层数为2层的时候，将塔尖移动到B，将底座移动到C，然后将塔尖从B移动到C即可，

而对于大于2层的情况，也可以套用当前的思路：

可以将最上面的一层看作“塔尖”，将剩下的部分看作“底座”

我们要做的仍然是将“塔尖”移动到B，将“底座”移动到C，再将B处的塔尖移动到C。

代码如下：

void HanoiStep(int n, char A, char B, char C)
{
        static int step = 1;
    if(n == 1)
    {
        //A to C
    }
    else
    {
        PseduCode(n - 1, A, C, B); //将A处的“塔尖”移动到B
        std::cout << "step" << step++ <<":" << "move " << A << " to " << C << endl;////将A处的“底座”移动到C
        PseduCode(n - 1, B, A, C);  //将B处的“底座”移动到C
    }
}