分治算法介紹
分治法是一種很重要的算法。字面上的解釋是“分而治之”租幕，就是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題献雅，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解退渗，原問題的解即子問題的解的合并梢卸。這個技巧是很多高效算法的基礎(chǔ)累魔，如排序算法(快速排序摔笤，歸并排序)，傅立葉變換(快速傅立葉變換)……
分治算法可以求解的一些經(jīng)典問題
二分搜索
大整數(shù)乘法
棋盤覆蓋
合并排序
快速排序
線性時間選擇
最接近點對問題
循環(huán)賽日程表
漢諾塔
前面的幾種包括合并排序垦写，快速排序前面的幾篇文章我已經(jīng)整理過了吕世，今天主要是要講如何解決漢諾塔的問題的代碼實現(xiàn)的。
基礎(chǔ)步驟
治算法的基本步驟
分治法在每一層遞歸上都有三個步驟：
分解：將原問題分解為若干個規(guī)模較小梯投，相互獨立命辖，與原問題形式相同的子問題
解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子問題
合并：將各個子問題的解合并為原問題的解分蓖。
分治算法
分治(Divide-and-Conquer(P))算法設(shè)計模式如下
其中|P|表示問題P的規(guī)模尔艇；n0為一閾值，表示當(dāng)問題P的規(guī)模不超過n0時么鹤，問題已容易直接解出终娃，不必再繼續(xù)分解。ADHOC(P)是該分治法中的基本子算法午磁，用于直接解小規(guī)模的問題P尝抖。因此，當(dāng)P的規(guī)模不超過n0時直接用算法ADHOC(P)求解迅皇。算法MERGE(y1,y2,…,yk)是該分治法中的合并子算法昧辽，用于將P的子問題P1 ,P2 ,…,Pk的相應(yīng)的解y1,y2,…,yk合并為P的解。
漢諾塔問題
漢諾塔的傳說
漢諾塔：漢諾塔（又稱河內(nèi)塔）問題是源于印度一個古老傳說的益智玩具登颓。大梵天創(chuàng)造世界的時候做了三根金剛石柱子搅荞，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定咕痛，在小圓盤上不能放大圓盤痢甘，在三根柱子之間一次只能移動一個圓盤。
假如每秒鐘一次茉贡，共需多長時間呢塞栅？移完這些金片需要5845.54億年以上，太陽系的預(yù)期壽命據(jù)說也就是數(shù)百億年腔丧。真的過了5845.54億年放椰，地球上的一切生命，連同梵塔愉粤、廟宇等砾医，都早已經(jīng)灰飛煙滅。
思路分析
1.分解
- 如果只有一個盤衣厘，直接把A->c
- 如果我們有 n >= 2 情況如蚜，我們總是可以看做是兩個盤
1.最下邊的盤 2. 上面的盤
先把 最上面的盤 A->B
把最下邊的盤 A->C
把B塔的所有盤 從 B->C
2.解決
分解為只有一個塔的情況。
3.合并
代碼實現(xiàn)
public class Hanoitower {
public static void main(String[] args) {
hanoiTower(5, '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);
}
}
}
結(jié)果:
大家可以參照以下這張圖自己去做實現(xiàn)，
