【面试题 08.06. 汉诺塔问题】

解题思路：

1. 递归结束条件：只剩下最后一个盘子需要移动
2. 递归函数主功能：
   1.首先将 n-1 个盘子，从第一个柱子移动到第二个柱子
   2.然后将最后一个盘子移动到第三个柱子上
   3.最后将第二个柱子上的 n-1 个盘子，移动到第三个柱子上 函数的等价关系式： f(n,A,B,C) 表示将n个盘子从A移动到Cf(n,A,B,C)=f(n-1,A,C,B)+f(1,A,B,C)+f(n-1,B,A,C)

视频讲解连接：https://www.bilibili.com/video/BV1dx411S7sY?spm_id_from=333.1007.top_right_bar_window_history.content.click

解题代码：

class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A.size(), A, B, C);
    }

    /**
     * 汉诺塔解题方法
     * @param n：表示要整体移动的盘子个数
     * @param z1：第一个柱子为 起始柱
     * @param z2：第二个柱子为 辅助柱
     * @param z3：第三个柱子为 终点柱
     */
    public void move(int n, List<Integer> z1, List<Integer> z2, List<Integer> z3) {
        // 1. 递归边界条件
        if(n == 1) {
            z3.add(z1.remove(z1.size()-1));   // 柱1 -> 柱3，顶部元素 （这里z1.size()-1一定注意，取得是最顶部的元素）
        }else {

            // 2.1 递归调用 将上面n-1个看成整体 从z1 整体移动到 z2  （子问题）
            move(n-1, z1, z3, z2);

            // 2.2 将 柱1 -> 柱3， 顶部元素
            z3.add(z1.remove(z1.size()-1));

            // 2.3 递归调用 将上面n-1个看成整体 从z2 整体移动到 z3  （子问题）
            move(n-1, z2, z1, z3);
        }
    }
}

白话版代码：

public class Hanoi {

    /**
     * 汉诺塔白话版
     * @param n：上面要整体移动的盘子数量
     * @param z1：起始柱
     * @param z2：辅助柱
     * @param z3：目标柱
     */
    public static void hanoi(int n, char z1, char z2, char z3) {
        if(n == 1) {
            System.out.println(z1 +" -> " + z3);
        } else {
            hanoi(n-1, z1, z3, z2);
            System.out.println(z1 +" -> " + z3);
            hanoi(n-1, z2, z1, z3);
        }
    }

    public static void main(String[] args) {
        hanoi(3, 'A', 'B', 'C');
    }
}

输出结果：

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

Process finished with exit code 0

总结：

• 递归的思想，从n的大问题 分解成 n-1的小问题

• 解题步骤（递归部分）：

• 先将n-1个盘子从 起始柱子 移动到 中间柱子

• 再将最后1个盘子移动到 终点柱子

• 最后将 中间柱子 上的所有盘子移动到 终点柱子