本篇主要是圍繞著分治算法的概念、思想、策略以及步驟四個方向敘述，同時通過漢諾塔游戲的講解，促進(jìn)大家對分治算法的理解。

一、基本概念??

在計算機(jī)科學(xué)中，分治法是一種很重要的算法。字面上的解釋是“分而治之”，就是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。這個技巧是很多高效算法的基礎(chǔ)，如排序算法(快速排序，歸并排序)，傅立葉變換(快速傅立葉變換)……

任何一個可以用計算機(jī)求解的問題所需的計算時間都與其規(guī)模有關(guān)。問題的規(guī)模越小，越容易直接求解，解題所需的計算時間也越少。例如，對于n個元素的排序問題，當(dāng)n=1時，不需任何計算。n=2時，只要作一次比較即可排好序。n=3時只要作3次比較即可，…。而當(dāng)n較大時，問題就不那么容易處理了。要想直接解決一個規(guī)模較大的問題，有時是相當(dāng)困難的。

二、基本思想及策略

分治法的設(shè)計思想是：將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。

分治策略是：對于一個規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較?。﹦t直接解決，否則將其分解為k個規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設(shè)計策略叫做分治法。

如果原問題可分割成k個子問題，1<k≤n，且這些子問題都可解并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對孿生兄弟，經(jīng)常同時應(yīng)用在算法設(shè)計之中，并由此產(chǎn)生許多高效算法。

三、使用步驟

（1）使用分治法的基本步驟：

1. 分解

將原問題分解為若干規(guī)模較小，相互獨(dú)立，與原問題相同的子問題。

2. 解決

若干子問題較小而容易被解決則直接解決，否則再繼續(xù)分解為更小的子問題，直到容易解決。

3. 合并

將已求解的各個子問題的解，逐步合并為原問題的解。

（2）分治算法能解決的問題，一般需要滿足下面這幾個條件：

1. 原問題與分解成的小問題具有相同的模式；

2. 原問題分解成的子問題可以獨(dú)立求解，子問題之間沒有相關(guān)性，這一點(diǎn)是分治算法跟動態(tài)規(guī)劃的明顯區(qū)別；

3. 具有分解終止條件，也就是說，當(dāng)問題足夠小時，可以直接求解；

4. 可以將子問題合并成原問題，而且這個合并操作的復(fù)雜度不能太高，否則就起不到減小算法總體復(fù)雜度的效果了。

四、分治算法最佳實踐-漢諾塔

（1）漢諾塔的傳說

漢諾塔：漢諾塔（又稱河內(nèi)塔）問題是源于印度一個古老傳說的益智玩具。大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64 片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

假如每秒鐘一次，共需多長時間呢？移完這些金片需要5845.54 億年以上，太陽系的預(yù)期壽命據(jù)說也就是數(shù)百億年。真的過了5845.54 億年，地球上的一切生命，連同梵塔、廟宇等，都早已經(jīng)灰飛煙滅。

（2）漢諾塔游戲的演示和思路分析:

如果是有一個盤， A->C

如果我們有n >= 2 情況，我們總是可以看做是兩個盤1.最下邊的盤2. 最上面的(所有盤)看成一個盤

1. 先把最上面的所有盤A->B

2. 把最下邊的盤A->C

3. 把B 塔的所有盤從B->C

（3）代碼實現(xiàn)

package com.qf.math;

public class Hanoitower {
    public static void main(String[] args) {
        char [] arr={'A','B','C'};
        hanoitower(4,'A','B','C');
    }

    public static void hanoitower(int num,char a,char b,char c){
        if (num==1){
            //盤數(shù)為1，做一次搬遷，從A移動到C柱
            System.out.println("第1個盤從"+a+"移動到"+c+"盤");
        }else{
            //盤數(shù)大于1
            //先從a盤最上面的盤值最下面的盤之間的所有盤，移動到b盤，C盤作為中間盤
            hanoitower(num-1,a,c,b);

            //把最底下的那個盤，從a盤移動到c盤
            System.out.println("第"+num+"個盤從"+a+"移動到"+c+"盤");

            //把b盤的所有盤，移動到c盤上
            hanoitower(num-1,b,a,c);
        }

    }
}