程式員常用十大算法(二):分治算法解決漢諾塔問題

分治算法

介紹:分而治之,把一個複雜的問題分成兩個或者更多的相同或相似的問題,再把子問題分成更小的子問題…直到最後子問題可以簡單的求解,原問題的解即子問題的解的合并.這個技巧時很多高效算法的基礎.

可以求解:

二分搜尋

棋盤覆寫

合并排序

快速排序

漢諾塔

等…

基本步驟:

分治法在每一層遞歸上都有三個步驟:

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

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

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

案例:

分治算法解決漢諾塔問題:

漢諾塔問題：

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

可去體驗一下這種遊戲：漢諾塔遊戲

一個盤：

直接将盤從A到C，一步

兩個盤：

先将小盤移動到B塔，再将大盤移動到C塔，再将小盤放到大盤上。

三個盤：

可将上面兩個盤看成一個整體，将上面兩個盤按照第二步移動到B塔，将最下面的盤移動到c塔，再按第二步的走法将兩個盤移動到C塔上。

思路分析：

1）如果隻有一個盤，A->C

2) 如果有n>=2情況，我們總是可以看作兩個盤：1.最下面的盤 2.最上面的盤

2.1）先把最上面的盤A->B

2.2) 把最喜愛按的盤A->C

2.3)把B塔的所有盤從B->C

代碼示範：

public class DAC {
	public static void main(String[] args) {
		hanoiTower(3,'A','B','c');
	}
	
	//漢諾塔的移動方法
	//使用分治算法
	/**
	 * @param num 盤子的個數
	 * @param a 塔a
	 * @param b 塔b
	 * @param c 塔c
	 */
	public static void hanoiTower(int num,char a,char b,char c) {
		//如果隻有一個盤
		if(num==1) {
			System.out.println("第一個盤從"+a+"->"+c);
		}else {//num>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);
		}
	}
}

           

三個盤為例，走的步分别為：

共7步