分治算法求解汉诺塔问题

分治算法求解汉诺塔问题

1.什么是分治算法？

分治算法，字面理解“分而治之”，就是把一个复杂的问题分成两个或者更多的相同或者相似的子问题，再把子问题分成更小的子问题...直到最后子问题可以直接简单求解，原问题的解即子问题的解的合并，这个算法是很多高效算法的基础，如排序算法，傅里叶变换。

2.分治算法的基本步骤

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

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

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

3.汉诺塔的分治算法实现

假设有“A”“B”“C” 三个柱子，一开始有5个盘子，把这5个盘子移动到另一个柱子上

package com.company.atguigu.java;
public class hannuoTower {
    public static void main(String[] args){
        hannuoTower(5,'A','B','C');
    }
    // 汉诺塔的移动方法
    // 使用分治算法

    public static void hannuoTower(int num,char a,char b,char c){
        if(num == 1){
            System.out.println("第一个盘从" +a + "->" +c);
        }else{
            // 如果我们有n >= 2的情况，我们总可以看成两个盘
            // 最下面一个盘，上面一个盘
            // 先把最上面的盘A->B，移动过程会使用到c
            hannuoTower(num-1,a,c,b);
            // 把最下面的盘A->C
            System.out.println("第" + num + "个盘从" + a + "->" +c);
            // 把B塔的所有盘从B->C，移动过程中使用到A塔
            hannuoTower(num -1,b,a,c);
        }
    }
}

运算结果：

第一个盘从A->C
第2个盘从A->B
第一个盘从C->B
第3个盘从A->C
第一个盘从B->A
第2个盘从B->C
第一个盘从A->C
第4个盘从A->B
第一个盘从C->B
第2个盘从C->A
第一个盘从B->A
第3个盘从C->B
第一个盘从A->C
第2个盘从A->B
第一个盘从C->B
第5个盘从A->C
第一个盘从B->A
第2个盘从B->C
第一个盘从A->C
第3个盘从B->A
第一个盘从C->B
第2个盘从C->A
第一个盘从B->A
第4个盘从B->C
第一个盘从A->C
第2个盘从A->B
第一个盘从C->B
第3个盘从A->C
第一个盘从B->A
第2个盘从B->C
第一个盘从A->C
 

get!!