14.2.1分治算法介紹

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)典問(wèn)題

二分搜索

大整數(shù)乘法

棋盤覆蓋

合并排序

快速排序

線性時(shí)間選擇

最接近點(diǎn)對(duì)問(wèn)題

循環(huán)賽日程

漢諾塔

14.2.2分治算法的基本步驟

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

1.????? 分解:將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題

2.????? 解決:若子問(wèn)題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問(wèn)題

3.????? 合并:將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解。

14.2.3分治(Divide-and-Conquer(P))算法設(shè)計(jì)模式如下:

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

漢諾塔的傳說(shuō)

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

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

?? 漢諾塔游戲的演示和思路分析:

1)????? 如果是有一個(gè)盤，A->C

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

2)????? 先把最上面的盤A->B

3)????? 把最下邊的盤A->C

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

漢諾塔游戲的代碼實(shí)現(xiàn):

代碼演示: