分治算法(汉诺塔问题)

一. 算法介绍：

分治算法，其实就是把一个大问题看成若干个小问题，解决了所有的小问题，那么大问题就解决了，原问题的解就是子问题解的合并，之前说的归并排序、快速排序，都用到了分治思想。

二. 分治算法的基本步骤：

• 分解：将原问题分解成若干个相互独立的、规模较小的、容易求解的、与原问题形式相同的子问题；

• 解决：直接求解子问题或者递归求解子问题；

• 合并：将各个子问题的解合并为原问题的解。

三. 分治算法经典应用：汉诺塔问题

1. 汉诺塔问题介绍：

汉诺塔 汉诺塔问题介绍

2. 怎么玩？

玩法

3. 思路分析：

我们先给3根针标上号，左边的是A，中间的是B，右边的是C。

• 假如只有一个盘，那就直接从A移动到C；

• 假如有两个盘，那就把上面那个从A移动到B，把底下那个从A到C，再把B中的移到C；

• 假如有多个盘，我们也可以按照两个盘的方式处理。即把最下边的看成一个盘，其他所有的看成一个盘；当然这里其他所有的还可以按照这种方式再进行分治。

4. 代码实现：

public class HanoiTower {
    
    /**
     * 汉诺塔问题
     * @param plateNum 盘子的数量
     * @param a 出发地，初始的时候是A
     * @param b 中转地，初始的时候是B
     * @param c 目的地，初始的时候是C
     */
    public static void hanoiTower(int plateNum, String a, String b, String c) {
        if (plateNum == 1) {
            System.out.println("从 " + a + " 到 " + c);
        } else { // 盘子数量大于等于2的情况
            // 上面的从A到B
            hanoiTower(plateNum - 1, a, c, b);
            // 最下面那个从A到C
            System.out.println("从 " + a + " 到 " + c);
            // B针上的所有搬到C
            hanoiTower(plateNum - 1, b, a, c);
        }
    }
    
    public static void main(String[] args) {
        hanoiTower(5, "A", "B", "C");
    }

}

怎么验证对不对呢？打开4399或者7k7k，搜索汉诺塔，选择盘子的数量，运行代码，按照代码打印的结果去玩这个游戏，就知道对不对了。