1、基礎(chǔ)算法策略長沙市第一中學(xué)曹利國第一部分枚舉策略枚舉策略的基本思想 枚舉法，又稱窮舉法，指在一個(gè)有窮的可能的解的集合中，一一枚舉出集合中的每一個(gè)元素，用題目給定的檢驗(yàn)條件來判斷該元素是否符合條件，若滿足條件，則該元素即為問題的一個(gè)解；否則，該元素就不是該問題的解。枚舉策略的基本思想 枚舉方法也是一種搜索算法，即對問題的所有可能解的狀態(tài)集合進(jìn)行一次掃描或遍歷。在具體的程序?qū)崿F(xiàn)過程中，可以通過循環(huán)和條件判斷語句來完成。枚舉法常用于解決“是否存在”或“有多少種可能”等類型的問題。例如，求解不定方程的問題就可以采用列舉法。 雖然枚舉法本質(zhì)上屬于搜索策略，但是它與回溯法有所不同。因?yàn)檫m用枚舉法求解的問題

2、必須滿足兩個(gè)條件： 可預(yù)先確定每個(gè)狀態(tài)的元素個(gè)數(shù)n； 狀態(tài)元素a1，a2，an的可能值為一個(gè)連續(xù)的值域。設(shè) ai1狀態(tài)元素ai的最小值；aik狀態(tài)元素ai的最大值(1in)，即a11a1a1k，a21a2a2k， ai1aiaik，an1anankfor a1a11 to a1k do fo a2a21 to a2k do for aiai1 to aik do for anan1 to ank do if 狀態(tài)(a1，ai，an)滿足檢驗(yàn)條件 then 輸出問題的解；枚舉策略的基本思想 枚舉法的特點(diǎn)是算法比較簡單，在用枚舉法設(shè)計(jì)算法時(shí)，重點(diǎn)注意優(yōu)化，減少運(yùn)算工作量。將與問題有關(guān)的知識(shí)條理化、

3、完備化、系統(tǒng)化，從中找出規(guī)律，減少枚舉量。 枚舉方法的優(yōu)化枚舉算法的時(shí)間復(fù)雜度：狀態(tài)總數(shù)*單個(gè)狀態(tài)的耗時(shí)主要優(yōu)化方法： 減少狀態(tài)總數(shù) 降低單個(gè)狀態(tài)的考察代價(jià)優(yōu)化過程從以下幾個(gè)方面考慮： 枚舉對象的選取 枚舉方法的確定 采用局部枚舉或引進(jìn)其他算法枚舉算法的應(yīng)用例題1：二進(jìn)制數(shù)的分類若將一個(gè)正整數(shù)轉(zhuǎn)化為二進(jìn)制數(shù)后，0的個(gè)數(shù)多于1的個(gè)數(shù)的這類數(shù)稱為A類數(shù)，否則稱為B類數(shù)。例如： （13）10=（1101）2， 13為B類數(shù)； （10）10=（1010）2 10為B類數(shù)； （24）10=（11000）2 24為A類數(shù)；程序要求：求出11000之中（包括1與1000），全部A、B兩類數(shù)的個(gè)數(shù)。 【分析】

4、此題是一道統(tǒng)計(jì)類題目。解決統(tǒng)計(jì)問題的一個(gè)常用方法是枚舉法：逐一枚舉所有情況，同時(shí)進(jìn)行統(tǒng)計(jì)，枚舉結(jié)束時(shí)，統(tǒng)計(jì)也完成，得到結(jié)果。具體對本題而言，采用枚舉法的正確性與可行性是顯然的，而本題的數(shù)據(jù)規(guī)模又僅為11000，所以采用逐一枚舉方法進(jìn)行統(tǒng)計(jì)的時(shí)間復(fù)雜度是完全可以接受的。枚舉算法的應(yīng)用例題2：01統(tǒng)計(jì)例題4：圓桌騎士（IOI試題） 在一個(gè)8*8的棋盤上，有一個(gè)國王和若干個(gè)武士。其中，國王走一字步，騎士走馬步。若國王與騎士相會(huì)在同一點(diǎn)上，國王可以選擇讓騎士背他走。求一個(gè)點(diǎn)，使所有的騎士和國王相距在這個(gè)點(diǎn)上的所走的步數(shù)最少。枚舉算法的應(yīng)用【分析】此題可從3個(gè)方面考慮： 分治、枚舉、數(shù)學(xué)方法。由于無法將

5、這個(gè)問題劃分為各自獨(dú)立的小問題來解決，分治顯然是不行的。又因武士和國王位置的不固定性和其走法的差異，推導(dǎo)不出一個(gè)數(shù)學(xué)公式。因此考慮使用枚舉，需要枚舉的三個(gè)要點(diǎn)： 1、最后的匯聚點(diǎn)。 2、國王與背他的騎士的匯聚點(diǎn)。 3、國王與背他的騎士。枚舉算法的應(yīng)用國王最多只會(huì)與一個(gè)騎士結(jié)合，因?yàn)轵T士的最終目標(biāo)也是最終匯聚點(diǎn)，一旦國王與某個(gè)騎士匯合后，即馬上可與其結(jié)合，剩下的只需要將所有的騎士匯合就可以了。更沒有必要在中途中有將國王托付給其他的騎士。 這樣我們估算一下時(shí)間為O（8*8*8*8*63）=O（36*104），完全可以承受。另外，我們需要預(yù)先將2點(diǎn)之間走馬字步的距離計(jì)算出來。可以使用Floyd或是B

6、fs。 枚舉算法的應(yīng)用 算法流程： disx1，y1，x2，y2-（x1，y1）（x2，y2）之間的距離。 For I：=1 to 8 do枚舉匯合點(diǎn) For j：=1 to 8 do begin All ：=所有騎士到這一點(diǎn)的和； Best:=min(best,all+國王到匯聚點(diǎn)的步數(shù)) For x：=1 to 8 do 枚舉武士國王的相會(huì)點(diǎn) For y：=1 to 8 do begin For kk：=1 to k do 枚舉與國王結(jié)合的武士 If disknightkk.x,knightkk.y,x,ymin then begin Min:= disknightkk.x,knightk

7、k.y,x,y; Mink:=k; End; End； Now:= all-mink武士走到匯合點(diǎn)的距離+ mink武士走到匯聚點(diǎn)的距離+ 國王走到匯聚點(diǎn)的距離+從匯聚點(diǎn)到匯合點(diǎn)的距離； Best：=min（best，now） End；局部枚舉例題5：求第一、第二、第三最短路問題局部枚舉例題6：新年好 重慶城里有n個(gè)車站，m條雙向公路連接其中的某些車站。每兩個(gè)車站最多用一條公路直接相連，從任何一個(gè)車站出發(fā)都可以經(jīng)過一條或多條公路到達(dá)其他車站，但不同的路徑需要花費(fèi)的時(shí)間可能不同。在一條路上花費(fèi)的時(shí)間等于路徑上所有公路需要的時(shí)間之和。佳佳的家在車站1，他有五個(gè)親戚，分別住在車站a,b,c,d,e。

8、過年了，他需要從自己的家出發(fā)，拜訪每個(gè)親戚（順序任意），給他們送去節(jié)日的祝福。怎樣走，才需要最少的時(shí)間？分析這一題中的邊數(shù)遠(yuǎn)小于n2，所以復(fù)雜度也只有nlogn+m算法框架是：（1）用5次最短路，計(jì)算出6個(gè)點(diǎn)兩兩之間的距離（2）枚舉5個(gè)結(jié)點(diǎn)的全排列，找到一個(gè)使得總路程長度最短的方案。最大子矩陣的求解方法第二部分貪心方法貪心方法的基本思想 貪心是一種解題策略，也是一種解題思想使用貪心方法需要注意局部最優(yōu)與全局最優(yōu)的關(guān)系，選擇當(dāng)前狀態(tài)的局部最優(yōu)并不一定能推導(dǎo)出問題的全局最優(yōu)利用貪心策略解題，需要解決兩個(gè)問題：該題是否適合于用貪心策略求解如何選擇貪心標(biāo)準(zhǔn)，以得到問題的最優(yōu)解 適用于貪心策略求解的問題

9、的特點(diǎn) 適用于貪心策略求解的問題必須具有最優(yōu)子結(jié)構(gòu)的性質(zhì)，但并不是所有具有最優(yōu)子結(jié)構(gòu)的問題都可以用貪心策略求解。因?yàn)樨澬耐敲つ康模枰褂酶硇缘姆椒▌?dòng)態(tài)規(guī)劃（例如“0-1背包問題”與“部分背包問題”） 貪心方法的應(yīng)用例題1：節(jié)點(diǎn)網(wǎng)絡(luò)。現(xiàn)有一個(gè)N！個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)的編號(hào)都是編號(hào)（A1A2A3AN）序列的一個(gè)置換。對于任意兩個(gè)節(jié)點(diǎn)S和T，如果T的編號(hào)是由S編號(hào)的首位與除首位外的編號(hào)中任一位交換所得 ，則S和T之間有一條邊，求從給定節(jié)點(diǎn)S走到節(jié)點(diǎn)（A1A2A3AN）所需經(jīng)過的最少邊數(shù)。其中，n100。 貪心方法的應(yīng)用例如n=3的情況：(A1A2A3)(A1A3A2)(A2A3A1)(A2

10、A1A3)(A3A1A2)(A3A2A1)貪心方法的應(yīng)用【分析】從題意表面上看，本題是一個(gè)求最短路徑的問題，但題設(shè)中的N100，也就是說圖中最多有100！個(gè)節(jié)點(diǎn)，采用二維關(guān)系的圖結(jié)構(gòu)根本無法存貯這眾多的狀態(tài)。通過問題的本質(zhì)分析，可以將問題轉(zhuǎn)化為一個(gè)序列的最優(yōu)轉(zhuǎn)化問題。貪心方法的應(yīng)用采用貪心策略：每次讓一個(gè)節(jié)點(diǎn)歸位或?yàn)橄乱徊焦ぷ髯鰷?zhǔn)備。其具體步驟為：若序列中第一個(gè)點(diǎn)為Ax (x1)，則將第一個(gè)點(diǎn)和第x個(gè)點(diǎn)交換。這便完成了讓一個(gè)點(diǎn)歸位的工作；若第一個(gè)是A1，則任找一個(gè)編號(hào)與位置不相符的點(diǎn)，并與之交換。這樣下一步便可讓交換到1號(hào)位置的點(diǎn)歸位。貪心方法的應(yīng)用(A3A4A1A2)(A1A4A3A2)第一

11、個(gè)點(diǎn)A1已歸位，但第二個(gè)點(diǎn)為A4A2，將第2個(gè)點(diǎn) A4與A1交換第一個(gè)點(diǎn)為A3A1，將第3個(gè)點(diǎn)A1與A3交換(A4A1A3A2)第一個(gè)點(diǎn)為A4A1，將第4個(gè)點(diǎn)A2與A4交換(A2A1A3A4)第一個(gè)點(diǎn)為A2A1，將第2個(gè)點(diǎn)A1與A2交換(A1A2A3A4)已經(jīng)符合要求了一共經(jīng)過4步完成。下面看一個(gè)n=4，初始序列為(A3A4A1A2)的推演過程：貪心方法的應(yīng)用例題2：d-規(guī)則問題。對任意給定的m(mN+)和n(nN+)，滿足m1，使得KaP，則修改P為：P=P-y|y=sa,sN+ ，并稱該d規(guī)則具有分值a。現(xiàn)要求編制一個(gè)程序，對輸入的m,n值，構(gòu)造相應(yīng)的初始集合P，對P每應(yīng)用一次d規(guī)則就累加

12、其相應(yīng)的分值，求能得到最大累加分值的d規(guī)則序列，輸出每次使用d規(guī)則時(shí)的分值和集合p的變化過程。 貪心方法的應(yīng)用【分析】初看這一問題，很容易想到用貪心策略來求解，即選擇集合中最大的可以刪除的數(shù)開始刪起，直到不能再刪除為止，而且通過一些簡單的例子來驗(yàn)證，這一貪心標(biāo)準(zhǔn)似乎也是正確的，例如，當(dāng)m=3，n=10時(shí)，集合P3,10，運(yùn)用上述“貪心標(biāo)準(zhǔn)”可以得到這一問題的正確的最優(yōu)解d=54312，即其d-規(guī)則過程如下：1. a=5 P=3,4,6,7,8,9d=52. a=4 P=3,6,7,9d=5+4=93. a=3 p=7 d=5+4+3=12貪心方法的應(yīng)用但是，如果再仔細(xì)地分析一個(gè)例子，當(dāng)m=3，

13、n18時(shí)，如果還是使用上述“貪心標(biāo)準(zhǔn)”，則得到問題的d-規(guī)則總分為d=35，其d-規(guī)則序列為（9,8,7,6,5），而實(shí)際上可以得到最大d-規(guī)則總分為d38，其對應(yīng)的d-規(guī)則序列為（9,8,7,6,3,5）。為什么會(huì)出現(xiàn)這樣的反例呢？這是因?yàn)椋瑔栴}中要使得d-規(guī)則總分d值越大，不光是要求每一個(gè)d分值越大越好，也要求取得的d分值越多越好。因此，本題不能采用純粹的貪心策略求解。貪心方法的應(yīng)用【改進(jìn)】將原算法基礎(chǔ)上進(jìn)行改進(jìn)。下面給出新的算法：建立集合P=m.n從n div 2到m每數(shù)構(gòu)造一個(gè)集合ci，包含該數(shù)在P中的所有倍數(shù)（不包括i本身）從n div 2起找到第一個(gè)元素個(gè)數(shù)最少但又不為空的集合ci

14、在d分值中加上i把i及ci集合從P集中刪除，更新所有構(gòu)造集合的元素檢查所有構(gòu)造集合，若還有非空集合，則繼續(xù)3步驟，否則打印、結(jié)束貪心方法的應(yīng)用下面看m=3, n=18時(shí)的推演過程：初始P=3.18找到i=9, ci=18, P=3.8,10.17找到i=8, ci=16, P=3.7,10.15,17找到i=7, ci=14, P=3.6,10.13,15,17找到i=6, ci=12, P=3.5,10,11,13,15,17找到i=3, ci=15, P=4,5,10,11,13,17找到i=5, ci=10, P=4,11,13,17到此所有構(gòu)造集合全部為空，d=9+8+7+6+3+5=

15、38貪心方法的應(yīng)用討論：能否證明此貪心策略是正確的？能否找到其他更好的算法？貪心方法的應(yīng)用例題3：射擊競賽射擊的目標(biāo)是一個(gè)由RC(2RC1000)個(gè)小方格組成的矩形網(wǎng)格。每一列恰有2個(gè)白色的小方格和R-2個(gè)黑色的小方格。行從頂至底編號(hào)為1R，列從左至右編號(hào)為1C。射擊者可射擊C次。在連續(xù)的C次射擊中，若每列恰好有一個(gè)白色的方格被射中，且不存在無白色方格被射中的行，這樣的射擊才是正確的。如果存在正確的射擊方法，則要求找到它。貪心方法的應(yīng)用射擊的選擇有2C種，符合要求的卻很少。要解決問題，還需從正確的射擊方法的特征入手。貪心方法的應(yīng)用【方法一】網(wǎng)絡(luò)流算法我們將表示列的點(diǎn)編號(hào)為1到C，表示行的點(diǎn)編號(hào)

16、為C+1到C+R，如果一個(gè)白色方格處在第i行第j列，那么從點(diǎn)j向點(diǎn)C+i連一條弧，弧的容量為1。再增設(shè)一個(gè)源點(diǎn)S，從點(diǎn)S往點(diǎn)1到C間各連一條弧，弧的容量為1，又設(shè)一個(gè)匯點(diǎn)T，從點(diǎn)C+1到點(diǎn)C+R向匯點(diǎn)T連一條弧，弧的容量為1，那么從源點(diǎn)S到匯點(diǎn)T求最大流，求出的最大流量即為最多可以射擊到的行數(shù)。各條流的路線則描述了具體的射擊方案。可以看出，如果用網(wǎng)絡(luò)流求出的最大流量比R小，則問題無解，否則我們可以先根據(jù)網(wǎng)絡(luò)流的結(jié)果求出該二分圖的具體匹配方案。貪心方法的應(yīng)用紅色的連線流量為1藍(lán)色的連線流量為0選擇的射擊格即為：(1,3), (2,1), (3,2), (4,4)S21432143T列:行:源:匯

17、:貪心方法的應(yīng)用網(wǎng)絡(luò)流算法經(jīng)過優(yōu)化，時(shí)間復(fù)雜度可以達(dá)到O(C(n+4C+4R) 上述網(wǎng)絡(luò)流算法雖然可以通過全部數(shù)據(jù)，但編程復(fù)雜度很高，而且極易出錯(cuò)，一不小心就會(huì)因?yàn)橐粋€(gè)小錯(cuò)誤影響整個(gè)程序。貪心方法的應(yīng)用【方法二】貪心方法統(tǒng)計(jì)所有行包含的白格數(shù)從還沒有射擊格的行中選出一個(gè)白格數(shù)最少的檢查所選的行若所選行的白格數(shù)為0，則輸出無解；否則從所選行的白格中任選一個(gè)作為射擊格，并將與該格同列的另一個(gè)白格所處行的白格數(shù)減1返回到第2步，直到所有的行都有射擊格。若還有列沒有選射擊格，則在該列任選一白格作為射擊格即可貪心方法的應(yīng)用上面的貪心方法非常高效：時(shí)間復(fù)雜度為O(RC)，如果在程序中使用堆優(yōu)化，時(shí)間復(fù)雜度

18、將降為O(Rlog2C)。空間復(fù)雜度是線性的，而且非常容易實(shí)現(xiàn)。現(xiàn)在關(guān)鍵的問題就是如何證明它的正確性？貪心方法的應(yīng)用【證明】用hi表示第i行的白格數(shù)。如果最開始的時(shí)候：minhi=0: 第i行已經(jīng)沒有辦法找到可作為射擊格的白格，那么問題只能無解。minhi=1: 那么第i行的這一個(gè)白格必須要作為射擊格，否則將因第i行沒有射擊格而造成問題無解。minhi2: 那么在這一行任選一個(gè)白格，頂多只會(huì)造成剩余行中有一行h值為1，再處理那一行，最多也只會(huì)再造成剩余行中有一行h值為1，如此往復(fù)，將保持h值為1的行數(shù)不超過1行，最后最壞的情況也是造成最后一行的h值為1，繼續(xù)下去所有行就都已選取了射擊格了。因此

19、，如果原問題有解，該貪心方法一定能找到一種正確的方案。由此可以證明，此貪心方法是正確的。貪心方法的應(yīng)用例題4：Transversal 有一個(gè)(2n+1)(2n+1)的矩陣，每個(gè)單元格中有符號(hào)“+”或“-”。定義一種取反操作：將1至2n+1這2n+1個(gè)整數(shù)任意排列，得到序列A1,A2,A2n+1，然后將(1,A1),(2,A2),(2n+1,A2n+1)這2n+1個(gè)單元格中的符號(hào)取反。求一種操作組合，使得在完成求得的操作組合后，表中“+”的個(gè)數(shù)不超過2n個(gè)。(n20)+-+-貪心方法的應(yīng)用一種操作組合：(1,1), (2,2), (3,3),(1,2), (2,3), (3,1),(1,1),

20、(2,3), (3,2),(1,3), (2,1), (3,2),紅色符號(hào)為上一次取反操作后的結(jié)果+-+-+-+-+-+-+-+-+-+-+僅剩一個(gè)“+”。貪心方法的應(yīng)用討論：是否可以用貪心法解決此題？貪心方法的推廣貪心與其它算法結(jié)合搜索的最優(yōu)化剪枝（ 生日蛋糕）優(yōu)化動(dòng)態(tài)規(guī)劃（ Peter的快餐店）貪心方法與解題策略最優(yōu)方法不一定是最好方法想不到最優(yōu)解法就用較優(yōu)解法貪心與其它算法結(jié)合例題5：Peter的快餐店（貪心與動(dòng)態(tài)規(guī)劃）Peter最近在R市新開了一家快餐店。 該快餐店準(zhǔn)備推出一種套餐，每套由A個(gè)漢堡、B個(gè)薯?xiàng)l和C個(gè)飲料組成。為了提高產(chǎn)量，Peter引進(jìn)了N條生產(chǎn)線。所有生產(chǎn)線都可以生產(chǎn)漢

21、堡、薯?xiàng)l和飲料，由于每條生產(chǎn)線一天能工作的時(shí)間是有限的、不同的，而漢堡、薯?xiàng)l和飲料的單位生產(chǎn)時(shí)間又不同，Peter需要知道，怎樣安排才能是一天中生產(chǎn)的套餐量最大。假設(shè)一天中漢堡、薯?xiàng)l和飲料的產(chǎn)量均不超過100個(gè)，且生產(chǎn)線總數(shù)小于等于10。貪心與其它算法結(jié)合【分析】用p1、p2、p3分別表示漢堡、薯?xiàng)l和飲料的單位生產(chǎn)時(shí)間，ti表示第i條生產(chǎn)線每天的生產(chǎn)時(shí)間，pi,j,k表示用前i條生產(chǎn)線生產(chǎn)j個(gè)漢堡、k個(gè)薯?xiàng)l的情況下，最多能生產(chǎn)的飲料數(shù)，ri,j,k表示用第i條生產(chǎn)線生產(chǎn)j個(gè)漢堡、k個(gè)薯?xiàng)l的情況下，最多能生產(chǎn)的飲料數(shù)，則pi,j,k=maxpi-1,j1,k1+ri,j-j1,k-k1 (j-j

22、1)p1+(k-k1)p2ti)通過對該算法的時(shí)間復(fù)雜度分析，最壞的情況下時(shí)間復(fù)雜度將達(dá)到109，是相當(dāng)費(fèi)時(shí)的。貪心與其它算法結(jié)合現(xiàn)在加入貪心方法，用貪心方法作預(yù)處理 ：首先計(jì)算出一天生產(chǎn)套數(shù)的上限值：min100 div A,100 div B,100 div C接著，用貪心方法計(jì)算出這N條生產(chǎn)線可以生產(chǎn)的套數(shù)，并與上限比較，大于或等于則輸出上限值并退出，否則再調(diào)用動(dòng)態(tài)規(guī)劃。因?yàn)樨澬姆椒ǖ拇鷥r(jià)很低，這里甚至可以使用多次貪心標(biāo)準(zhǔn)不同的貪心方法，取其最大值。在運(yùn)行動(dòng)態(tài)規(guī)劃的過程中，也可以每完成一階段工作便與上限值進(jìn)行比較，將貪心思想充分融入到動(dòng)態(tài)規(guī)劃過程中，這樣以來，便可望在動(dòng)態(tài)規(guī)劃完成前提前結(jié)

23、束程序。貪心方法小結(jié)貪心作為一種解題思路，雖然有時(shí)無法證明它的正確性，但在無法找到其他算法的時(shí)候，不失為一種好方法。并且，貪心與其他算法的結(jié)合，可以對其他算法起到優(yōu)化作用。第三部分歸納策略歸納法的基本思想 歸納法的基本思想是通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。從本質(zhì)上講，歸納就是通過觀察一些簡單而特殊的情況，最后總結(jié)出有用的結(jié)論或解決問題的有效途徑。 歸納法解題的過程細(xì)心的觀察；豐富的聯(lián)想；繼續(xù)嘗試；總結(jié)歸納出結(jié)論。歸納法解題的過程歸納是種抽象，即從特殊現(xiàn)象中找出一般關(guān)系。由于在歸納的過程中不可能對所有的可能情況進(jìn)行枚舉，因而最后得到的結(jié)論還只是一種猜測(即歸納假設(shè))。所以，

24、嚴(yán)格說來對于歸納假設(shè)還必須加以嚴(yán)格的證明。歸納策略解題應(yīng)注意的問題：從問題的簡單具體狀態(tài)分析入手，目的是去尋求可以推廣的一般性規(guī)律，因此應(yīng)考慮簡單狀態(tài)與一般性狀態(tài)之間的聯(lián)系。從簡單狀態(tài)中分析出來的規(guī)律特征應(yīng)能夠被驗(yàn)證是正確的，不能想當(dāng)然或任意地提出猜想，否則歸納出來的結(jié)論是錯(cuò)誤的，必然導(dǎo)致整個(gè)問題的解是錯(cuò)解。歸納策略的應(yīng)用例題1： 求前n個(gè)自然數(shù)的平方之和： S=12+22+32+n2 歸納策略的應(yīng)用【分析】這本是一道很簡單的題目，但如果能找出S值與n的關(guān)系，則此題將更進(jìn)一步得到簡化，由數(shù)學(xué)證明得知：(12+22+32+n2)/(1+2+3+n) =(2n+1)/3又由于 1+2+3+n=n(

25、n+1)/2，因此得到： 12+22+32+n2=n(n+1) (2n+1)/6 但這只是通過總結(jié)歸納而得到的一種猜測，是否正確還需證明，對歸納假設(shè)的證明通常采用數(shù)學(xué)歸納法（證略）。歸納策略的應(yīng)用例題2：若干個(gè)正整數(shù)之和為n，其中：n1，因此排除了n3和n4存在的可能性.又由于n和m是整數(shù)，因此1和2應(yīng)為整數(shù)。由于m2n2單調(diào)遞增，從mk出發(fā)，按遞減方向?qū)值代入n的求根公式。只要1（或2）為整數(shù)、n1（或n2）為整數(shù)且小于k，則得出的一組m和n一定使 m2n2的值最大。【算法描述】 mk；while mi do begin 求1 if 1為整數(shù) then begin 求n1； if (n1為

26、整數(shù)) and (n1k) Then begin 輸出m和n1；halt; end end; then 求2； if 2為整數(shù) then begin 求n2； if（n2為整數(shù)）and（n2k） then begin 輸出m和n2; halt; end end;then mml; end;while歸納策略的應(yīng)用上述算法從數(shù)學(xué)意義上來說，是一定可以出得出正確解的。但是該算法疏漏了一個(gè)重要條件 1k109 。如果K值超過105，上述算法不可能在限定的15秒內(nèi)出解。歸納策略的應(yīng)用【分析】方法二分析小數(shù)據(jù)會(huì)發(fā)現(xiàn)：m,n是Fibonacci數(shù)列的相鄰兩項(xiàng)。因?yàn)椋?（n 2mnm2）2 1故： （ m2

27、 + mn n 2 ）2 1又： m 2mnn2(mn)2mn2n2 (mn)2(mn)nn2 故： （m2mnn2）2(mn)2(mn)nn22 即： （n2mnm2）2(mn)2(mn)nn22歸納策略的應(yīng)用【分析】由上述數(shù)學(xué)變換式可以得出，如果m和n為一組滿足條件和條件的解，設(shè)nmn，m n那么n，m 也是一組滿足條件和條件的一組解。將所有滿足條件和條件的m和n 按遞增順序排成一個(gè)Fibomacci數(shù)列 1，1，2，3，5，8， 數(shù)列中小于k的最大兩個(gè)相鄰數(shù)即為試題所要求的一組m和n。算法：利用Fibomacci數(shù)列順推m,n，求出在條件范圍內(nèi)的m,n最大值，此時(shí)m2n2的值最大。歸納策

28、略的應(yīng)用例題4：“王”棋子遍歷問題。題目大意：在nn格（2n=20）棋盤上的任一格子中放置一個(gè)棋子，棋子每次只能往其上、下、左、右相鄰方格移動(dòng)一步，求一種遍歷方法，使得棋子走n2-1步遍歷整個(gè)棋盤，每個(gè)方格只能被訪問一次。歸納策略的應(yīng)用【分析】此題很容易想到采用搜索回溯的方法去求解，即從起點(diǎn)位置出發(fā)，擴(kuò)展其相鄰四個(gè)方格的狀態(tài)節(jié)點(diǎn)，生成一個(gè)狀態(tài)樹，利用深度搜索的方法求解，但這種純搜索的方法效率太低，因此可以考慮一些簡單的情況時(shí)的遍歷方法：歸納策略的應(yīng)用【分析】當(dāng)n=2時(shí)，該棋盤存在一條回路，所以任意一點(diǎn)作為起點(diǎn)均能遍歷整個(gè)棋盤，考慮到當(dāng)n=4,6時(shí)的情況，進(jìn)而推廣到n為偶數(shù)時(shí)，均可以按規(guī)律產(chǎn)生回

29、路，從給定的起點(diǎn)開始沿著該回路均可遍歷整個(gè)棋盤。歸納策略的應(yīng)用【分析】再考慮n為奇數(shù)時(shí)的情況，先設(shè)定n=3時(shí)，棋盤可劃分成5個(gè)白格和4個(gè)黑格，人工可以推出，從任一黑格出發(fā)將無法遍歷整個(gè)棋盤，然后考慮n=5時(shí)的情況，同樣可推出，從棋盤中的任一黑格出發(fā)無法遍歷整個(gè)棋盤。規(guī)律：當(dāng)n為奇數(shù)時(shí)，棋子的起始位置若滿足其橫坐標(biāo)和縱坐標(biāo)之和為奇數(shù)時(shí)（即圖中所示的任一黑格位置），問題將無解。歸納策略的應(yīng)用 這一規(guī)律很容易能夠得到驗(yàn)證,因?yàn)榘凑找?guī)則，從任一黑格出發(fā)，必走一白格再走一黑格，所以白格數(shù)目與黑格數(shù)目應(yīng)相等，而圖中兩者數(shù)目并不相等，如n=5時(shí)，圖中共有黑格12個(gè)，白格共有13個(gè)。歸納策略的應(yīng)用【總結(jié)】通過

30、上述歸納，我們在搜索求解問題時(shí)，將會(huì)較大地提高算法效率，尤其是在一些問題的無解判定時(shí)，運(yùn)用歸納策略的作用將會(huì)十分明顯。歸納策略的應(yīng)用例題5：Kathy函數(shù)(HNCOI) Tiger非常喜歡數(shù)學(xué)，所以他參加了學(xué)校組織的數(shù)學(xué)課外興趣小組。在興趣小組的學(xué)習(xí)當(dāng)中，老師向Tiger介紹了Kathy函數(shù)，Kathy函數(shù)是這樣定義的：歸納策略的應(yīng)用例題5：Kathy函數(shù)(HNCOI)Tiger對Kathy函數(shù)產(chǎn)生了濃厚的興趣，他通過研究發(fā)現(xiàn)有很多的數(shù)n都滿足對于一個(gè)給定的數(shù)m，他希望你求出所有的滿足 的自然數(shù)n的個(gè)數(shù)，其中m8 then begin 分解成四小塊； 對于其中一塊devide(n-3) end

31、 else case n of 6: 按n=6分割； 7: 按n=7分割； 8: 按n=8分割； end;End;分治思想如果在將規(guī)模為n的問題分成k個(gè)不同子集合的情況下，能得到k個(gè)不同的可分別求解的子問題，其中1k=n，而且在求出了這些子問題的解之后，還可找到適當(dāng)?shù)姆椒ò阉鼈兒喜⒊烧麄€(gè)問題的解，那么，具備上述特性的問題可考慮使用分治策略設(shè)計(jì)求解。這種設(shè)計(jì)求解的思想就是將整個(gè)問題分成若干個(gè)小問題后分而治之。 分治思想分治(divide-and-conquer)就是“分而治之”的意思，其實(shí)質(zhì)就是將原問題分成n個(gè)規(guī)模較小而結(jié)構(gòu)與原問題相似的子問題；然后遞歸地解這些子問題，最后合并其結(jié)果就得到原問題

32、的解。其三個(gè)步驟如下；分解(Divide)：將原問題分成一系列子問題。解決(Conquer)：遞歸地解各子問題。若子問題足夠小，則可直接求解。合并(combine)；將子問題的結(jié)果合并成原問題的解。 分治思想問題S問題S問題SS的解問題S1問題S2問題Si問題SnS1的解S2的解Si的解Sn的解問題的分解子集解的合并子問題求解分治思想由分治法所得到的子問題與原問題具有相同的類型。如果得到的子問題相對來說還太大，則可反復(fù)使用分治策略將這些子問題分成更小的同類型子問題，直至產(chǎn)生出不用進(jìn)一步細(xì)分就可求解的子問題。分治求解可用一個(gè)遞歸過程來表示。要使分治算法效率高，關(guān)鍵在于如何分割？一般地，出于一種平

33、衡原則，總是把大問題分成K個(gè)規(guī)模盡可能相等的子問題，但也有例外，如求表的最大最小元問題的算法，當(dāng)n6時(shí)，等分定量成兩個(gè)規(guī)模為3的子表L1和L2不是最佳分割。分治的應(yīng)用舉例例題2： 一元三次方程求解 有形如：ax3+bx2+cx+d=0這樣的一個(gè)一元三次方程。給出該方程中各項(xiàng)的系數(shù)(a，b，c，d均為實(shí)數(shù))，并約定該方程存在三個(gè)不同實(shí)根(根的范圍在-100至100之間)，且根與根之差的絕對值=1。要求由小到大依次在同一行輸出這三個(gè)實(shí)根(根與根之間留有空格)，并精確到小數(shù)點(diǎn)后4位。提示：記方程f(x)=ax3+bx2+cx+d，若存在2個(gè)數(shù)x1和x2，且x1x2，f(x1)*f(x2)0，則在(x

34、1，x2)之間一定有一個(gè)根。樣例輸入：1 -5 -4 20輸出：-2.00 2.00 5.00分治的應(yīng)用舉例如果精確到小數(shù)點(diǎn)后兩位，可用簡單的枚舉法：將x從-100.00 到100.00（步長0.01） 逐一枚舉，得到20000個(gè) f(x)，取其值與0最接近的三個(gè)f(x)，對應(yīng)的x即為答案。而題目已改成精度為小數(shù)點(diǎn)后4位，枚舉算法時(shí)間復(fù)雜度將達(dá)不到要求。直接使用求根公式，極為復(fù)雜。加上本題的提示給我們以啟迪：采用二分法逐漸縮小根的范圍，從而得到根的某精度的數(shù)值。具體方法如下：分治的應(yīng)用舉例A、當(dāng)已知區(qū)間(a,b)內(nèi)有一個(gè)根時(shí)，用二分法求根，若區(qū)間(a,b)內(nèi)有根，則必有f(a)f(b)b或f(

35、a+b)/2)=0，則可確定根為(a+b)/2并退出過程； (2)若f(a)* f(a+b)/2)0 ，則必然有f(a+b)/2)* f(b)=1。因此可知：在-100,-99、-99,-98、99，100、100，100這201個(gè)區(qū)間內(nèi)，每個(gè)區(qū)間內(nèi)至多只能有一個(gè)根。即：除區(qū)間100，100外，其余區(qū)間a,a+1，只有當(dāng)f(a)=0或f(a)f(a+1)0時(shí)，方程在此區(qū)間內(nèi)才有解。若f(a)=0 ，解即為a；若f(a)f(a+1)0 ，則可以利用A中所述的二分法迅速出找出解。如此可求出方程的所有的解。分治的應(yīng)用舉例例題3： 旅行家的預(yù)算 一個(gè)旅行家想駕駛汽車以最少的費(fèi)用從一個(gè)城市到另一個(gè)城市（

36、假設(shè)出發(fā)時(shí)油箱是空的）。給定兩個(gè)城市之間的距離D1、汽車油箱的容量C（以升為單位）每升汽油能行駛的距離D2、出發(fā)點(diǎn)每升汽油價(jià)格P和沿途油站數(shù)N（N可以為零），油站i離出發(fā)點(diǎn)的距離Di、每升汽油價(jià)格 Pi（ il，2，.N）。 計(jì)算結(jié)果四舍五入至小數(shù)點(diǎn)后兩位。如果無法到達(dá)目的地，則輸出“No solution”。樣例： INPUT ( D1 C D2 P N) 275.6 11.9 27.4 2.8 2油站號(hào)I 離出發(fā)點(diǎn)的距離Di 每升汽油價(jià)格 1 102.0 2.9 2 220.0 2.2 OUTPUT 26.95（該數(shù)據(jù)表示最小費(fèi)用）分析 首先找到(從后向前)油價(jià)最低的加油站，顯然車至該站油

37、箱應(yīng)為空，這樣就可將起點(diǎn)至該站與該站至終點(diǎn)作為兩段獨(dú)立考慮，分別求其最小費(fèi)用，二者之和即為總費(fèi)用，這樣一直分下去，若某段只有起點(diǎn)與終點(diǎn)兩個(gè)加油站時(shí)無需再分，如某一段油價(jià)最低的加油站即為起點(diǎn)，則如能一次加油即到達(dá)該段終點(diǎn)則最好，若不能，則加滿油再考慮油箱有油情況下的二分法，考慮起點(diǎn)之外所有的加油站中從后往前油價(jià)最低的加油站，若該加油站位于起點(diǎn)加滿油后不能到達(dá)之處，則到達(dá)該站時(shí)油箱應(yīng)該為空，以該站為界將全程分為兩個(gè)獨(dú)立段考慮，前半段為有油情況，后半段為無油情況。 第二種情況，若該加油站處于起點(diǎn)加滿油后能到達(dá)之處，則將該段總路程縮短為該加油站至終點(diǎn)的情況，該加油站在該段路程中最便宜，若從該站加滿油仍

38、不能到達(dá)終點(diǎn)，則繼續(xù)分治即可，程序被設(shè)計(jì)成一個(gè)遞歸函數(shù)money，形式參數(shù)start表示起點(diǎn)站，形式參數(shù)stop表示終點(diǎn)站，形式參數(shù)rest表示到達(dá)加油站start時(shí)汽車油箱余下的油的容量，money函數(shù)最終計(jì)算出從加油站start到stop區(qū)間內(nèi)的最小費(fèi)用。 function money (start，stop:longint；rest:real):real；Var k：longint；beginif stop-starl=1 then money:=(dstop-dstar1)/d2-rest)*pstartelse begin k:=minp(start，stop-1)； minp(b，

39、e:longint):longint；在b站到e 站之間從后往前找油價(jià)最低的站 if kstart 油價(jià)最低的加油站不是起點(diǎn)站 then money:=money(start，k，rest)+money(k，stop，0) else if dstop-dstart=d2*c 在起點(diǎn)加滿油能直接到達(dá)該段終點(diǎn) then money:=(dstop-dstart)/d2-rest) * pstart else begin k:=minp(start+1 , stop-1) ; if dk - dstart = d2 * c then 在起點(diǎn)加滿油能到達(dá)加油站k money:=(c-rest) * pstart + money(k, st