[[398991]]

算法介紹

1. 分治法是一種很重要的算法。字面上的解釋是“分而治之”，就是把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多相同或相似的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題…直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題解即是子問(wèn)題的解的合并。這個(gè)技巧是很多高效算法的基礎(chǔ)，如排序算法(快速排序、歸并排序)，傅里葉變換(快速傅里葉變換)...
2. 分支算法可以求解的一些經(jīng)典文圖：二分搜索、大整數(shù)乘法、棋盤覆蓋、合并排序、快速排序、線性時(shí)間選擇、最接近點(diǎn)對(duì)問(wèn)題、循環(huán)賽日程表、漢諾塔。

分治算法的基本步驟

分治法在每一層遞歸上都有三個(gè)步驟：

1. 分解：將原有問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題
2. 解決：若干子問(wèn)題規(guī)模較小而容易被解決則直接解決，否則遞歸地解決各個(gè)子問(wèn)題
3. 合并：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解

分治算法設(shè)計(jì)模式

分治(Divide-and-Conquer(P))算法模式如下圖，

其中|P| 表示問(wèn)題P的規(guī)模，n0為一閥值，表示當(dāng)問(wèn)題p的規(guī)模不超過(guò)n0時(shí)，問(wèn)題已容易直接解出，不必再繼續(xù)分解。ADHOC(P)是該分治算法中的基本子算法，用于直接解小規(guī)模的問(wèn)題P。因此，當(dāng)P的規(guī)模不超過(guò)n0時(shí)直接用ADHOC(P)求解。算法MERGE(y1,y2,…yk)是該分治法中的合并子算法，用于將P的子問(wèn)題P1,P2,…Pk的相應(yīng)解y1,y2…yk合并為P的解。

分治算法實(shí)踐-漢諾塔

在一根柱子上從下往上按照大小順序放著64片黃金圓盤，把圓盤從下面開(kāi)始按大小順序重新擺放在另一根柱子上，并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動(dòng)一個(gè)盤。

思路分析：

1. 如果是有一個(gè)盤，A->C
2. 如果是 n>=2 盤情況，我們總是可以看成兩個(gè)盤，一個(gè)是最下邊的一個(gè)盤，一個(gè)是上面的所有盤：先把最上面的所有盤從A移動(dòng)到B，把最下面的一個(gè)盤從A移動(dòng)到C，把B塔的所有盤從B移動(dòng)到C。

package com.xie.algorithm; 
 
public class Hanoitower { 
    public static void main(String[] args) { 
        hanoiTower(3, 'A', 'B', 'C'); 
        /** 
         * 第1個(gè)盤從A->C 
         * 第2個(gè)盤從A->B 
         * 第1個(gè)盤從C->B 
         * 第3個(gè)盤從A->C 
         * 第1個(gè)盤從B->A 
         * 第2個(gè)盤從B->C 
         * 第1個(gè)盤從A->C 
         */ 
    } 
 
    public static void hanoiTower(int num, char a, char b, char c) { 
        //如果只有一個(gè)盤 
        if (num == 1) { 
            System.out.println("第1個(gè)盤從" + a + "->" + c); 
        } else { 
            //如果是 n>=2 盤情況，我們總是可以看成兩個(gè)盤，一個(gè)是最下邊的一個(gè)盤，一個(gè)是上面的所有盤 
            //1.先把最上面的盤從A移動(dòng)到B，移動(dòng)過(guò)程會(huì)使用到C 
            hanoiTower(num - 1, a, c, b); 
            //2.把最下面的一個(gè)盤從A移動(dòng)到C 
            System.out.println("第" + num + "個(gè)盤從" + a + "->" + c); 
            //3.把B塔的所有盤從B移動(dòng)到C，移動(dòng)過(guò)程使用到A塔 
            hanoiTower(num - 1, b, a, c); 
        } 
    } 
} 

 【編輯推薦】