Java十大算法之分治算法

1.分治(Divide-and-Conquer)算法介紹

分治算法是一種很重要的算法,字面上的解釋是’分而治之’,就是把一個複雜的問題分解成兩個或更多的相同或相似的問題,再把子問題分成更小的子問題…,直到最後子問題可以簡單的直接求解,原問題的解即是子問題解的合并,這個技巧是很多高校算法的基礎

分治算法可以求解的一些經典問題:二分搜尋,大整數乘法,棋盤覆寫,合并排序,快速排序,線性時間選擇,最接近點對問題,循環賽日程表,漢若塔…

2.分治算法的基本步驟

(1)分解:将原問題分解成若幹個規模較小,互相獨立,與原問題形式相同的子問題

(2)解決:若子問題規模較小而容易被解決則直接解決,否則遞歸地解各個子問題

(3)合并:将各個子問題的解合并為原問題的解

3.分治算法的設計模式

(設計模式看不懂可以忽略)

4.分治算法的實際應用

這個遊戲的玩法最好在百度上玩一下,友善對下文了解

漢若塔遊戲代碼實作思路分析

(1)如果隻有一個盤,A->C

(2)如果有n>=2,我們總是可以看做是兩個盤,一個是最下邊的盤,一個是除最下面盤的其他盤

1)先把上面的盤A->B

2)把最下面的盤A->C

3)把B塔的盤從B->C

代碼實作:

package com.self.tenAlgorithm;

public class Hannoitower {
    public static void main(String[] args) {
        hanoitower(2,'a','b','c');
    }
    public static void hanoitower(int num,char a,char b,char c){
        if(num == 1){   //如果隻有一個盤
            System.out.println("第一個盤" + a + "->" + c);
        }else{
            hanoitower(num - 1, a, c, b);
            System.out.println("第" + num + "個盤子" + a + "->" + c);
            hanoitower(num - 1, b, a, c);
        }
    }
}