算法问题：汉诺塔问题理解

题目：

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

 

分析：

  设柱子为A B C。共有n张盘子。

  首先假如只有一个盘子时，只需直接移动A到C。而n = 2时，需要经过A-B，A-C，B-C的过程。

  其实问题的解法是将最大的盘子想方设法移动到C柱上。然后不管它，将其余盘子放在C柱上。步骤：

  1.将n-1盘子移动到B柱上。

  2.将最大的盘子移动到C柱上。

  3.将B柱上盘子移动到C柱上。

 

 实际上就是将问题从宏观整体上来描述解决方案，在代码运行的时候，用递归算法实现，通过将大问题化解为一个个递归的子问题解决，其中涉及到起始柱A，辅助柱B，目标柱C的不断变化因为子问题中盘子的目标不同。

 

代码：

void hanoi(int num,char a,char b,char c)
{
    if(n == 1)
    {
        move(a,c);
    }
    else
    {
        hanoi(num-1,a,c,b);//借助C柱移动n-1盘子到B柱上去。
        move(a,c);//移动最大盘子到C柱上
        hanoi(num-1,b,a,c);//移动B柱上的盘子到C柱上去。
    }
}

void move(char object1,char object2)
{
    std::cout << object1 << "->" << object2 << std::endl;
}