算法（Java实现）—

算法（Java实现）—— 分治算法

whystudyjava 2020-12-17 原文

算法（Java实现）—— 分治算法

分治算法

分治算法的设计模式

基本思想

把复杂问题分解成若干互相独立容易求解的子问题

经典问题

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

基本步骤

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

设计模式

Divide-and-Conquer(P){
    if |p| <= n~0
        then return(ADHOC(p))
    //将 p分解为较小的子问题p1，p2，p3...pk
    for i<---1 to k
        do yi<---Divide-and-COnquer(pi) //递归解决pi
    T <---MERGE(y1,y2,...,yk)//合并子问题
    return（T)
}

|p|表示问题p的规模
n0为阈值，表示当问题p的规模不超过n0时，问题已容易直接接触，不必再继续分解
ADHOC（p）时该分治法中的基本子算法，用于直接解小规模的问题p
因此，当p的规模不超过n0时直接用算法ADHOC（p）求解

分治法解决汉诺塔实例

思路分析

如果只有一个盘，A – >C
如果盘n > = 2，总是可看作两个盘1.下面的盘，2.上面的所有盘
先把最上面的盘A – > B
把最下边的盘A – > C
把B塔的所有盘从B – > C

代码实现

package com.why.divide_and_conquer_algorithm;

import java.util.concurrent.CountDownLatch;

/**
 * @Description TODO 分治法解决汉诺塔问题
 * @Author why
 * @Date 2020/11/13 15:34
 * Version 1.0
 **/
public class HanoiTower {
    public static void main(String[] args) {
        hanoiTower(5,'A','B','C');
    }

    /**
     * 汉诺塔的移动方法
     * 使用分治算法
     * @param num
     * @param a
     * @param b
     * @param c
     */
    public static void hanoiTower(int num,char a,char b,char c){
        //如果只有一个盘
        if(num == 1){
            System.out.println("第1个盘从 "+ a + "->" + c);
        }else {
            //最上面的盘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);
        }

    }
}