汉诺塔问题求解

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

核心思想-----递归：

汉诺塔问题通过简单的递归进行求解，代码比较简洁，通俗易懂。其实汉诺塔问题的移动次数是有规律可寻的，通过递归代码找出相应的规律，并通过数学方法得到结果效率才是最高的。

• 当n=1时，a柱子只有一个圆盘，直接移至c柱
• 当n>1时，根据规则1和2，将a柱子n-1个圆盘移动到b柱子，然后将a剩下的一个圆盘移动到c，接着再把b上暂时放着的n-1个圆盘移动到c

递归求解其实就是不断降低问题规模的过程，将b柱子的n-1个圆盘移至c何尝不重复上述两点的过程。

/** * Created by ${wuyupku} on 2019/3/14 16:23 */

    public class Hannota {         public static void moveDish(int level, char from, char inter, char to) {             if (level == 1) {                 System.out.println("从 " + from + " 移动盘子 1 到 " + to);             }             else {                 moveDish(level - 1, from, to, inter);                 System.out.println("从 " + from + " 移动盘子 " + level + " 到 " + to);                 moveDish(level - 1, inter, from, to);             }         }

        public static void main(String[] args) {             int nDisks = 3;             moveDish(nDisks, 'A', 'B', 'C');         }     }

从 A 移动盘子 1 到 C 从 A 移动盘子 2 到 B 从 C 移动盘子 1 到 B 从 A 移动盘子 3 到 C 从 B 移动盘子 1 到 A 从 B 移动盘子 2 到 C 从 A 移动盘子 1 到 C