分治法基本思想（汉诺塔问题 Tower of Hanoi）

古城微笑少年丶 2023-03-13 05:24 22阅读 0赞

### 文章目录 ###

*   *   *  前言
         *  基本思想
         *  适用的问题
         *  求解步骤
         *  分治法要点
         *  时间复杂性分析
         *  举例-汉罗塔问题（Tower of Hanoi）
         *   *  问题描述
             *  解决步骤
             *  java代码

### 前言 ###

分治法来源于孙子兵法谋攻篇中写道——十则围之，五则攻之，倍则战之，敌则能分支。讲述的是敌军对战时用兵的原则，如果有十倍的兵力围殴他，五倍的兵力仅供他，在兵力相当的情况下，应该考虑分而治之，各个击破，其体现出来的思想，**称为分治法**

### 基本思想 ###

那么分治法的基本思想是什么呢？将一个难以直接解决的大问题，分割成一些规模较小的相同的问题，以便各个击破，分而治之。 通俗的来说就是大事化小，小事化了。大事不好解决，那么我们就把它分成若干个小事，小到什么程度呢？非常容易解决的时候。

### 适用的问题 ###

1、该问题可以分解为若干个规模较小的相同问题。  
2、该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。  
3、该问题的规模缩小到一定的程度的时候容易解决。  
4、利用该问题分解出的子问题的解可以合并俄日该问题的解。

### 求解步骤 ###

1、**分解：** 把原问题分解为若干个规模较小，相互独立，与原问题相同的子问题  
2、**求解**：若子问题规模较小且容易被解决则直接解，否则在继续分解为更小的问题，知道容易解决。  
3、**合并**：将已经求解的各个子问题的解，逐步合并为原问题的解。

### 分治法要点 ###

1、分几个？子问题规模多大？  
2、子问题如何求解？  
3、合并原问题的解？  
4、分析时间复杂性  
**最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。**

### 时间复杂性分析 ###

从分支法的代码中可以看出，分治法解决问题P(n)时，边界条件为n-0=1，此时问题的规模足够小，求解P（1）的时间耗费为O（1），在一般的情况下，将规模为n的大问题，分解为k个规模为n/m的子问题进行求解。将P（n）分解以及合并成原问题的时间为f（n）。中间for循环k次，解决每个子问题的时间复杂性为T(n/m),那么解决k个子问题所需要的时间为kT（n/m）  
![在这里插入图片描述][2020051115595671.png]  
分治法解规模为n的问题最坏时间复杂性函数T(n)满足：  
![在这里插入图片描述][20200511160511458.png]

### 举例-汉罗塔问题（Tower of Hanoi） ###

#### 问题描述 ####

传说在婆罗门庙里有三座钻石宝塔塔台A,B和C，在A上有n=64个金盘，每一个都比下面的略小一点。那么如何通过柱子b将所有盘子挪到柱子C上？  
![在这里插入图片描述][20200511161011321.png]  
移动要求：  
1、一次只能移动一个金盘。  
2、移动过程中大金盘不能放在小金盘上面。

#### 解决步骤 ####

第一步：将（n-1）个盘子从A搬到B（借助C）  
![在这里插入图片描述][20200511162012980.png]  
第二步：将A宝塔中，最低端的大盘子从A搬到C  
![在这里插入图片描述][20200511162234380.png]  
第三步将B上的（n-1）盘子，借助A移动到C  
![在这里插入图片描述][2020051116243970.png]  
边界条件n=1的时候，将这一个盘子直接从A移动到C，一次移动时间记为1，否则的话执行以下三部：  
1、用C做过渡，将A上的（n-1）个盘子移动到B上。  
2、将A上最后一个盘子直接移动到C上。  
3、用A柱做过渡，将B柱上的（n-1）个盘子移到C上。

#### java代码 ####

package com.Xiang;
    
    public class Hanoi {
        
    
        public static void main(String[] args) {
        
                hanoiTower(4, '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 情况，我们总是可以看做是两个盘 1.最下边的一个盘 2. 上面的所有盘
                        //1. 先把 最上面的所有盘 A->B， 移动过程会使用到 c
                        hanoiTower(num - 1, a, c, b);
                        //2. 把最下边的盘 A->C
                        System.out.println("第" + num + "个盘从 " + a + "->" + c);
                        //3. 把B塔的所有盘 从 B->C , 移动过程使用到 a塔  
                        hanoiTower(num - 1, b, a, c);
                        
                }
        }
    
    }
    /*
     * 第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
    
     */

[2020051115595671.png]: /images/20230312/56edc1d8716f4be38ee70c7d618cf680.png
[20200511160511458.png]: /images/20230312/de333cf682d44e3ca06085be8ac14f98.png
[20200511161011321.png]: /images/20230312/ea8bdda8c91546d7bf2f1224ed38f78b.png
[20200511162012980.png]: /images/20230312/4b6a2f4e68d74a10a8e1e69c8472d9fb.png?
[20200511162234380.png]: /images/20230312/5398e38cdf074a9fb5be67e95d97d378.png
[2020051116243970.png]: /images/20230312/71c8c7d4b63e456ab7a02c9eabccc73b.png