【算法】分治算法以及用分治算法解决汉诺塔问题

介绍

分治算法的思想是 “ 分而治之 ” ，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题......知道最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础

分治算法基本思想

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

1.分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题

2.解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

3.合并：将各个子问题的解合并为原问题的解

分治算法实例——汉诺塔问题

思路分析

1.如果只有一个盘 A -> C

2.如果有 n >= 2 的情况，我们总是可以看作两个部分，一部分是最下面的盘，一部分是上面的所有盘

        ①先把上面的所有盘  A -> B

        ②把最下面的盘 A -> C

        ③把 B 塔的所有盘 B -> C

代码实现 

public class Hanoitower {
    public static void main(String[] args) {
        hanoiTower(5,'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
            hanoiTower(num - 1, a, c, b);
 
            //②把最下面的盘 A -> C
            System.out.println("第 " + num + " 个盘从" + a + "->" + c);
 
            //③把 B 塔的所有盘 B -> C
            hanoiTower(num - 1, b, a, c);
        }
    }
}