蓝桥学院2019算法题2.6

汉诺塔题目要求：

解题思路：

1~N从A移动到B，C作为辅助

　　等价于：

　　1、1~N-1从A移动到C，B作为辅助

　　2、把N从A移动到B

　　3、1~N-1从C移动到B，A为辅助

算法实现：

 1 package recursion;
 2 
 3 /**
 4  * @author zsh
 5  * @company wlgzs
 6  * @create 2019-02-16 8:53
 7  * @Describe 汉诺塔
 8  */
 9 public class TowerOfHanoi {
10 
11     /**
12      *  将N个盘子从原始柱子移动到目标柱子的路径打印
13      * @param N 初始的盘子大小，N为最大编号
14      * @param from 原始柱子
15      * @param to 目标柱子
16      * @param help 辅助柱子
17      * 解题思路：
18      * 找重复：1到N-1个盘子移动到辅助空间，N移动到目标柱子。
19      * 找变化量：N
20      * 找出口：N == 1
21      */
22     static void printHanoiTower(int N,String from,String to,String help){
23         if (N == 1){
24             System.out.println("move" + N +from+"to"+to);
25             return;
26         }
27         //先把N-1个盘子挪到辅助空间上去
28         printHanoiTower(N -1 ,from,help,to);
29         //N可以顺利到达目标柱子
30         System.out.println("move" + N +from+"to"+to);
31         //让N-1个盘子回到源空间上去
32         printHanoiTower(N-1,help,to,from);
33     }
34 
35     public static void main(String[] args) {
36         printHanoiTower(3,"A","B","C");
37     }
38 }