【数据结构与算法】分治算法的介绍和汉诺塔程序实现

1. 分治算法的介绍

分治法即分而治之，把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，不停的进行分解，直到最后的子问题可以简单的直接求解，原问题的解即子问题的解的合并

分治算法求解的经典问题

• 二分搜索
• 大整数乘法
• 棋盘覆盖
• 归并排序
• 快速排序
• 线性时间选择
• 最接近点对问题
• 循环赛日程表
• 傅立叶变换(快速傅立叶变换)
• 汉诺塔

2. 分治算法的基本步骤

分治法在每一层递归上都有三个步骤：

• 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
• 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
• 合并：将各个子问题的解合并为原问题的解

3. 分治(Divide-and-Conquer)算法设计模式

// 将P分解为较小的子问题P1, P2, …..., Pk，然后递归解决Pi
for i -> 1 to k
do Yi -> Divide-and-Conquer(Pi)   

// 解决子问题的方法
if |P| ≤ n0
   then return ADHOC(P)
   
// 合并子问题
T -> MERGE(Y1, Y2, …..., Yk)   
return T
1
2
3
4
5
6
7
8
9
10
11

当问题P的规模不超过阈值n0时，不必继续分解，直接用算法ADHOC§求解。算法MERGE(Y1, Y2, ……, Yk)用于将P的子问题P1, P2, ……, Pk的相应解Y1, Y2, ……, Yk合并为P的解

3. 汉诺塔介绍和程序实现

汉诺塔介绍：汉诺塔(又称河内塔)是一个益智玩具。有三根柱子，在一根柱子上从下往上按照从大到小的顺序堆着64片圆盘。要求圆盘从下往上按照从大到小的顺序重新摆放在另一根柱子上。并且在三根柱子之间一次只能移动一个圆盘，移动时小圆盘上不能放大圆盘

汉诺塔游戏思路分析

• 如果是有一个盘：A -> C
• 如果n >= 2，我们总是可以看做是两个盘，即最下边的一个盘和剩余上面的所有盘
  • 先把剩余最上面的所有盘：A -> B
  • 把最下边的一个盘：A -> C
  • 把B塔的所有盘：B -> C

程序如下：

public class HanoiTower {

    public static void main(String[] args) {

        hanoiTower(4, 'A', 'B', 'C');

    }


    //汉诺塔移动的方法，从A移动到C。使用分治算法
    // 参数num表示盘的数量
    // 参数a、b、c分别表示三个柱子
    public static void hanoiTower(int num, char A, char B, char C) {
        // 如果只有一个盘
        if (num == 1) {
            System.out.println("第1个盘：从" + A + " -> " + C);
        } else {
            // 如果n >= 2，我们总是可以看做是两个盘，即最下边的一个盘和剩余上面的所有盘
            // 先把剩余最上面的所有盘：A -> B。递归过程会使用到C柱子
            hanoiTower(num - 1, A, C, B);
            // 把最下边的一个盘：A -> C
            System.out.println("第" + num + "个盘：从" + A + " -> " + C);
            // 把B塔的所有盘：B -> C。递归过程会使用到A柱子
            hanoiTower(num - 1, B, A, C);

        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

运行程序，结果如下：

第1个盘：从A -> B
第2个盘：从A -> C
第1个盘：从B -> C
第3个盘：从A -> B
第1个盘：从C -> A
第2个盘：从C -> B
第1个盘：从A -> B
第4个盘：从A -> C
第1个盘：从B -> C
第2个盘：从B -> A
第1个盘：从C -> A
第3个盘：从B -> C
第1个盘：从A -> B
第2个盘：从A -> C
第1个盘：从B -> C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15