計(jì)算機(jī)程序基礎(chǔ)數(shù)據(jù)算法

第一章算法計(jì)算機(jī)軟件技術(shù)基礎(chǔ)2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法2第一章算法1.1算法的基本概念1.2算法設(shè)計(jì)基本方法1.3算法的復(fù)雜度分析什么是算法；算法的基本特征。1.列舉法；2.遞推法；3.遞歸法；4.減半遞推法；5.回溯法。算法的時(shí)間復(fù)雜度。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法31.1算法的基本概念用計(jì)算機(jī)解決一個(gè)實(shí)際問(wèn)題，首先要進(jìn)行程序設(shè)計(jì)。通常，程序設(shè)計(jì)主要包括兩個(gè)方面：行為特性的設(shè)計(jì)：要求將解決實(shí)際問(wèn)題的每個(gè)細(xì)節(jié)準(zhǔn)確地加以定義，并且還應(yīng)當(dāng)將全部解題過(guò)程完整地描述出來(lái)，這一過(guò)程即是算法的設(shè)計(jì)；結(jié)構(gòu)特性的設(shè)計(jì)：指確定適合的數(shù)據(jù)結(jié)構(gòu)。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法41.1算法的概念定義：“算法”是指解題方案的準(zhǔn)確而完整的描述。算法可解：對(duì)于一個(gè)問(wèn)題，如果可以通過(guò)一個(gè)計(jì)算機(jī)程序，在有限的存儲(chǔ)空間內(nèi)運(yùn)行有限長(zhǎng)的時(shí)間而得到正確的結(jié)果。程序與算法的區(qū)別：程序可以作為算法一種描述，但程序通常還需考慮很多與方法和分析無(wú)關(guān)的細(xì)節(jié)問(wèn)題，因?yàn)樵诰帉?xiě)程序時(shí)要受到計(jì)算機(jī)系統(tǒng)運(yùn)行環(huán)境的限制。結(jié)論：通常，程序設(shè)計(jì)不可能優(yōu)于算法的設(shè)計(jì)。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法51.1.1算法的基本特征能（可）行性(effectiveness)⑴算法中的每一個(gè)步驟必須能夠?qū)崿F(xiàn)。⑵算法執(zhí)行的結(jié)果要能夠達(dá)到預(yù)期的目的。例如：三個(gè)量的和，如果采用不同的運(yùn)算順序，就會(huì)得到不同的結(jié)果：數(shù)據(jù)存儲(chǔ)的實(shí)際范圍2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法6確定性(definiteness)算法中每一個(gè)步驟都必須是有明確定義的，不允許有模棱兩可的解釋?zhuān)膊辉试S有多義性。反映了算法與數(shù)學(xué)公式的明顯差別：針對(duì)某種特殊情況，數(shù)學(xué)公式是正確的，但按此數(shù)學(xué)公式設(shè)計(jì)的計(jì)算過(guò)程可能會(huì)使計(jì)算機(jī)系統(tǒng)無(wú)所適從。因?yàn)闆](méi)有考慮異常情況的出現(xiàn)。舉例：“輸入一個(gè)x，若x比1大很多，則輸出數(shù)字1，否則輸出數(shù)字0?！?023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法7有窮性(finiteness)算法必須能在有限的時(shí)間內(nèi)做完，即算法必須能在執(zhí)行有限個(gè)步驟之后終止。舉例：一個(gè)數(shù)的無(wú)窮級(jí)數(shù)表示只是一個(gè)計(jì)算公式，而根據(jù)精度要求確定的計(jì)算過(guò)程才是有窮的算法。另一種定義：合理的執(zhí)行時(shí)間。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法8補(bǔ)充：無(wú)窮級(jí)數(shù)無(wú)窮級(jí)數(shù)是研究有次序的可數(shù)無(wú)窮個(gè)數(shù)或者函數(shù)的和的收斂性及和的數(shù)值的方法。舉例：假定有一個(gè)無(wú)窮數(shù)列：u1，u2，u3，...，un，...其前n項(xiàng)的和為：Sn=u1+u2+u3+...+un由此得出另一個(gè)新無(wú)窮數(shù)列：S1，S2，S3，…，Sn，...當(dāng)n無(wú)限增加時(shí)，Sn趨向一個(gè)極限；如果極限存在，這個(gè)無(wú)窮數(shù)列就叫做是收斂的無(wú)窮級(jí)數(shù)，如果極限不存在，這個(gè)數(shù)列就是發(fā)散的。只有收斂的無(wú)窮級(jí)數(shù)存在一個(gè)和S。S=u1+u2+u3+...+un+...2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法9擁有足夠的情報(bào)一個(gè)算法是否有效還取決于為算法所提供的情報(bào)是否足夠。通常，算法中的各種運(yùn)算總是要施加到各個(gè)運(yùn)算對(duì)象上，而這些運(yùn)算對(duì)象又可能具有某種初始狀態(tài)，這是算法執(zhí)行的起點(diǎn)或是依據(jù)。因此，一個(gè)算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)，不同的輸入會(huì)有不同的輸出。當(dāng)提供的情報(bào)不夠時(shí)，算法并不是有效的。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法10結(jié)論算法是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。算法是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法111.1.2算法的基本要素算法通常由兩種基本要素組成：一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作；二是算法的控制結(jié)構(gòu)。算法中對(duì)數(shù)據(jù)的運(yùn)算和操作①算術(shù)運(yùn)算：加、減、乘、除、整除、取余等運(yùn)算；②邏輯運(yùn)算：“與”、“或”、“非”等運(yùn)算；③關(guān)系運(yùn)算：“大于”、“小于”、“等于”、“不等于”等運(yùn)算。④數(shù)據(jù)傳輸：賦值、輸入、輸出等操作。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法12算法的控制結(jié)構(gòu)定義：算法中各操作之間的執(zhí)行順序。描述算法的工具：傳統(tǒng)流程圖；N-S結(jié)構(gòu)化流程圖；算法描述語(yǔ)言。三種基本控制結(jié)構(gòu)：順序、選擇、循環(huán)。ABABCTFACTF2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法131.2算法設(shè)計(jì)的基本方法計(jì)算機(jī)解題的過(guò)程實(shí)際上是在實(shí)施某種算法，這種算法通常稱(chēng)為計(jì)算機(jī)算法，與人工處理的算法不同。舉例：2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法14算法設(shè)計(jì)的基本方法人工處理的步驟：找出被積函數(shù)f(x)的源函數(shù)F(x);利用牛頓-萊布尼茲公式計(jì)算。計(jì)算機(jī)處理方式：采用數(shù)值積分法，根據(jù)實(shí)際被積函數(shù)的類(lèi)型以及精度要求選擇相應(yīng)的算法。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法15㈠列舉法基本思想：根據(jù)提出的問(wèn)題，列舉所有可能的情況，并用問(wèn)題中給定的條件檢驗(yàn)?zāi)男┦切枰?，哪些是不需要的。列舉法常用于解決“是否存在”或“有多少種可能”等類(lèi)型的問(wèn)題，例如求解不定方程的問(wèn)題。特點(diǎn)：算法比較簡(jiǎn)單，但當(dāng)列舉的可能情況較多時(shí)，執(zhí)行列舉算法的工作量將會(huì)很大。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法16舉例：百雞百錢(qián)問(wèn)題例1.1：設(shè)每只母雞值3元，每只公雞值2元，兩只小雞值1元?，F(xiàn)要用100元錢(qián)買(mǎi)100只雞，設(shè)計(jì)買(mǎi)雞方案。（百雞百錢(qián)問(wèn)題）

假設(shè)買(mǎi)母雞i只，公雞j只，小雞k只。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法17最粗略的列舉算法如下：算法：求解百雞百錢(qián)問(wèn)題。

fori＝0to100doforj＝0to100dofork＝0to100do{m=i＋j＋kn=3i＋2j＋0.5kif((m＝100)and(n＝100))thenoutputi，j，k}returni表示購(gòu)買(mǎi)的母雞個(gè)只數(shù)j表示購(gòu)買(mǎi)的公雞個(gè)只數(shù)k表示購(gòu)買(mǎi)的小雞個(gè)只數(shù)計(jì)算購(gòu)買(mǎi)雞的總數(shù)m以及總價(jià)格n2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法18i=0i≤100j=0j≤100Tk=0k≤100T計(jì)算雞的總只數(shù)m和購(gòu)買(mǎi)雞的總價(jià)格nm==100&&n==100輸出m和nTk++j++i++TFF結(jié)束F1013F2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法19改進(jìn)算法：求解百雞百錢(qián)問(wèn)題。

fori＝0to33doforj＝0to50－1.5ido{k=100－i－jif(3i＋2j＋0.5k＝100)thenoutputi，j，k}return總循環(huán)次數(shù)為：運(yùn)行結(jié)果如下：02306805257008207211157414107617578200802023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法20㈢遞推基本思想：從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。補(bǔ)充舉例：計(jì)算下列定積分遞推算法在數(shù)值計(jì)算中極為常見(jiàn)，但對(duì)于數(shù)值型的遞推算法必須要注意數(shù)值計(jì)算的穩(wěn)定性問(wèn)題。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法21對(duì)上式稍作分析，可以發(fā)現(xiàn)相鄰兩個(gè)積分之間存在以下關(guān)系：從而得到遞推公式：2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法22利用牛頓-萊布尼茲公式可以計(jì)算出積分I0的值：從而得到21個(gè)積分的遞推算法如下：近似值就意味著有誤差假定初始值（情報(bào)）的誤差為α2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法23表1.1第一種遞推公式得到的結(jié)果2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法24實(shí)際上，根據(jù)關(guān)系式還可以得到另一個(gè)遞推公式2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法25如果要使用遞推公式(1.5)時(shí)，需要確定初始值I20。有如下不等式：可以得到：最后可得：當(dāng)n=21時(shí)，有由于很接近，因此可用它們的平均值作為I20的近似值，即近似值就意味著有誤差2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法26根據(jù)之前的推論，可以得到第二種21個(gè)積分的遞推算法：假定初始值（情報(bào)）的誤差為β2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法27表1.2第二種遞推公式得到的結(jié)果遞推算法在數(shù)值計(jì)算中極為常見(jiàn)，但對(duì)于數(shù)值型的遞推算法必須要注意數(shù)值計(jì)算的穩(wěn)定性問(wèn)題。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法28㈣遞歸基本思想：將一個(gè)復(fù)雜的問(wèn)題歸結(jié)為若干個(gè)較簡(jiǎn)單的問(wèn)題，然后將這些較簡(jiǎn)單的每一個(gè)問(wèn)題再歸結(jié)為更簡(jiǎn)單的問(wèn)題，這個(gè)過(guò)程可以一直做下去，直到最簡(jiǎn)單的問(wèn)題為止。補(bǔ)充舉例：求解Hanoi塔問(wèn)題。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法29補(bǔ)充舉例：求解Hanoi（漢諾）塔問(wèn)題。 設(shè)有三個(gè)塔座分別為X、Y、Z?，F(xiàn)有n個(gè)直徑各不相同的圓盤(pán)，且按直徑從小到大用自然數(shù)編號(hào)為1，2，…，n。開(kāi)始時(shí)，此n個(gè)圓盤(pán)依下大上小的順序放在塔盤(pán)X上。先要根據(jù)下列原則將X塔座上的這n個(gè)圓盤(pán)移動(dòng)到Z塔座上：每次只允許移動(dòng)一個(gè)圓盤(pán)（從一個(gè)塔座到另一個(gè)塔座）；移動(dòng)時(shí)可用Y塔座作為中間塔座；在移動(dòng)過(guò)程中，任何一個(gè)塔座上均不允許出現(xiàn)大壓小的情況發(fā)生。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法30圖示Hanoi塔問(wèn)題XYZ起始塔柱中間塔柱目的塔柱每次只允許移動(dòng)一個(gè)圓盤(pán)（從一個(gè)塔座到另一個(gè)塔座）；移動(dòng)時(shí)可用Y塔座作為中間塔座；在移動(dòng)過(guò)程中，任何一個(gè)塔座上均不允許出現(xiàn)大壓小的情況發(fā)生。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法31三階Hanoi塔問(wèn)題分析：起始塔座X上有三個(gè)圓盤(pán)，所以該問(wèn)題被稱(chēng)為三階Hanoi塔問(wèn)題。塔座X塔座Y塔座Z321需要完成：Hanoi(3,X,Y,Z)；其中，參數(shù)1表示一共需要移動(dòng)幾個(gè)圓盤(pán)；參數(shù)2表示起始塔座；參數(shù)3表示中間塔座；參數(shù)4表示目的塔座。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法32三階Hanoi塔問(wèn)題分析：完成Hanoi(3,X,Y,Z)的工作可以分解成如下三個(gè)步驟：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和Hanoi(2,Y,X,Z)。塔座X塔座Y塔座Z321需要先完成：Hanoi(2,X,Z,Y)；該工作又可分解成：①Hanoi(1,X,Y,Z)；②MOVE(X,2,Y)；③Hanoi(1,Z,X,Y)。完成Hanoi(1,X,Y,Z)；工作等價(jià)于MOVE(X,1,Z)。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法33三階Hanoi塔問(wèn)題塔座X塔座Y塔座Z321分析：完成Hanoi(3,X,Y,Z)的工作可以分解成如下三個(gè)步驟：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和Hanoi(2,Y,X,Z)。需要先完成：Hanoi(2,X,Z,Y)；該工作又可分解成：①Hanoi(1,X,Y,Z)；②MOVE(X,2,Y)；③Hanoi(1,Z,X,Y)。完成MOVE(X,2,Y)。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法34三階Hanoi塔問(wèn)題塔座X塔座Y塔座Z321分析：完成Hanoi(3,X,Y,Z)的工作可以分解成如下三個(gè)步驟：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和Hanoi(2,Y,X,Z)。需要先完成：Hanoi(2,X,Z,Y)；該工作又可分解成：①Hanoi(1,X,Y,Z)；②MOVE(X,2,Y)；③Hanoi(1,Z,X,Y)。完成Hanoi(1,Z,X,Y)；工作等價(jià)于MOVE(Z,1,Y)。Hanoi(2,X,Z,Y)完成!2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法35三階Hanoi塔問(wèn)題分析：完成Hanoi(3,X,Y,Z)的工作可以分解成如下三個(gè)步驟：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和Hanoi(2,Y,X,Z)。塔座X塔座Y塔座Z321完成：MOVE(X,3,Z)；接下來(lái)需要完成：Hanoi(2,Y,X,Z)。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法36三階Hanoi塔問(wèn)題分析：完成Hanoi(3,X,Y,Z)的工作可以分解成如下三個(gè)步驟：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和Hanoi(2,Y,X,Z)。塔座X塔座Y塔座Z321最后完成：Hanoi(2,Y,X,Z)；該工作又可分解成：①Hanoi(1,Y,Z,X)；②MOVE(Y,2,Z)；③Hanoi(1,X,Y,Z)。完成Hanoi(1,Y,Z,X)；其工作等價(jià)于MOVE(Y,1,X)。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法37三階Hanoi塔問(wèn)題分析：完成Hanoi(3,X,Y,Z)的工作可以分解成如下三個(gè)步驟：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和Hanoi(2,Y,X,Z)。塔座X塔座Y塔座Z312最后完成：Hanoi(2,Y,X,Z)；該工作又可分解成：①Hanoi(1,Y,Z,X)；②MOVE(Y,2,Z)；③Hanoi(1,X,Y,Z)。完成MOVE(Y,2,Z)。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法38三階Hanoi塔問(wèn)題分析：完成Hanoi(3,X,Y,Z)的工作可以分解成如下三個(gè)步驟：Hanoi(2,X,Z,Y)、MOVE(X,3,Z)和Hanoi(2,Y,X,Z)。塔座X塔座Y塔座Z321最后完成：Hanoi(2,Y,X,Z)；該工作又可分解成：①Hanoi(1,Y,Z,X)；②MOVE(Y,2,Z)；③Hanoi(1,X,Y,Z)。完成Hanoi(1,X,Y,Z)；其工作等價(jià)于MOVE(X,1,Z)。Hanoi(2,Y,X,Z)完成!Hanoi(3,X,Y,Z)完成!2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法39總結(jié)：三階Hanoi塔問(wèn)題將一個(gè)復(fù)雜的問(wèn)題（三階Hanoi塔問(wèn)題）歸結(jié)為若干個(gè)較簡(jiǎn)單的問(wèn)題（二階Hanoi塔問(wèn)題）；然后將這些較簡(jiǎn)單的每一個(gè)問(wèn)題（二階Hanoi塔問(wèn)題）再歸結(jié)為更簡(jiǎn)單的問(wèn)題，直到最簡(jiǎn)單的問(wèn)題（一階Hanoi塔問(wèn)題）為止。塔座X塔座Y塔座Z3212023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法40再分析：n階Hanoi塔問(wèn)題求解的步驟：如果n=1，則可直接將這一個(gè)圓盤(pán)移動(dòng)到目的柱上，過(guò)程結(jié)束。如果n>1，則進(jìn)行步驟2。設(shè)法將起始柱的上面n-1個(gè)圓盤(pán)（編號(hào)1到n-1）按移動(dòng)原則移動(dòng)到中間柱上。將起始柱上的最后一個(gè)圓盤(pán)（編號(hào)為n）移到目的柱上。設(shè)法將中間柱上的n-1圓盤(pán)按移動(dòng)原則移到目的柱上。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法41步驟2與步驟4實(shí)際上還是Hanoi塔問(wèn)題，只不過(guò)其規(guī)模小一些而已。如果最原始的問(wèn)題為n階Hanoi塔問(wèn)題，且表示為Hanoi(n,X,Y,Z)則步驟2與步驟4為n-1階Hanoi塔問(wèn)題分別表示為：

Hanoi(n-1,X,Z,Y) Hanoi(n-1,Y,X,Z)

其中第一個(gè)參數(shù)表示問(wèn)題的階數(shù)，第二、三、四個(gè)參數(shù)分別表示起始柱、中間柱與目的柱。將X塔座上的n號(hào)圓盤(pán)移到Z塔座上

Move(X,n,Z)2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法42補(bǔ)充舉例之算法：求解n階Hanoi塔問(wèn)題。

Hanoi(n,X,Y,Z) IFn=1THENmove(X,1,Z) ELSE {Hanoi(n-1,X,Z,Y)

move(X,n,Z)

Hanoi(n-1,Y,X,Z) }RETURN函數(shù)在執(zhí)行過(guò)程中調(diào)用自身的方法叫遞歸調(diào)用。遞歸的邊界2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法43另一個(gè)簡(jiǎn)單的例子例1.2：編寫(xiě)一個(gè)過(guò)程，對(duì)于輸入的參數(shù)n，依次打印輸出自然數(shù)1到n。（非遞歸算法）PROCEDUREWRT(n)FORk＝1TOnDOOUTPUTkRETURN2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法44輸出自然數(shù)1到n的遞歸算法。

PROCEDUREWRT1(n)IF(n≠0)THEN{WRT1(n－1)OUTPUTn}RETURNWRT1(3)WRT1(2)WRT1(1)WRT1(0)OUTPUT2OUTPUT1OUTPUT3遞歸的邊界√√√√√√√☆☆☆1232023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法45總結(jié)一個(gè)典型的遞歸算法：自己調(diào)用自己。直接遞歸：如果一個(gè)算法P顯式地調(diào)用自己。間接遞歸：如果算法P調(diào)用另一個(gè)算法Q，而算法Q又調(diào)用算法P。遞歸算法與遞推算法的區(qū)別：兩者的實(shí)現(xiàn)方法是大不一樣的。遞推是從初始條件出發(fā)，逐次推出所需求的結(jié)果；而遞歸則是從算法本身達(dá)到遞歸邊界。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法46㈤減半遞推所謂“減半”，是指將問(wèn)題的規(guī)模減半，而問(wèn)題的性質(zhì)不變。所謂“遞推”，是指重復(fù)“減半”的過(guò)程。將實(shí)際問(wèn)題的規(guī)模逐漸減少，可明顯地降低解決問(wèn)題的復(fù)雜程度。這種方法稱(chēng)為分治法，即對(duì)問(wèn)題分而治之。工程上常用的分治法是減半遞推技術(shù)，這個(gè)技術(shù)在快速算法的研究中有很重要的使用價(jià)值。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法47舉例例1.3：二分法求方程f(x)在[a,b]的根設(shè)方程f(x)=0在區(qū)間[a,b]內(nèi)有且只有一個(gè)實(shí)根，則函數(shù)f(x)在區(qū)間的兩個(gè)端點(diǎn)處的函數(shù)值必異號(hào)，即2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法48首先取給定區(qū)間的中點(diǎn)c＝(a＋b)/2。然后判斷f(c)是否為0。若f(c)＝0,則說(shuō)明c即為所求的根，求解過(guò)程結(jié)束；如果f(c)≠0,則根據(jù)以下原則將原區(qū)間減半；若f(a)f(c)＜0，則取原區(qū)間的前半部分；若f(b)f(c)＜0，則取原區(qū)間的后半部分。最后判斷減半后的區(qū)間長(zhǎng)度是否已經(jīng)很?。喝魘a－b|＜ε，則過(guò)程結(jié)束，取(a＋b)/2為根的近似值；若|a－b|≥ε，則重復(fù)上述的減半過(guò)程。所能接受的誤差2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法49算法1.3二分法求方程的根輸入：根所在區(qū)間[a,b]，精度要求輸出：滿足精度要求的根的近似值cf0←f(a)WHILE|b-a|≥εDO {c←(a+b)/2;f1←f(c) IFf1=0THEN {OUTPUTc

RETURN} IFf0×f1>0THENa←c ELSEb←c}c←(a+b)/2OUTPUTc

RETURNf0←f(a)|b-a|≥εc←(a+b)/2;f1←f(c)f1==0OUTPUTc結(jié)束得出準(zhǔn)確根f0×f1>0得出近似根a←cb←cTTFFTF2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法50總結(jié)對(duì)于有些實(shí)際問(wèn)題，可以設(shè)計(jì)出直觀的減半遞推算法，經(jīng)過(guò)逐次的減半遞推，直接得到所需求的結(jié)果，如例1.3：二分法求方程的根。對(duì)于另外一些問(wèn)題，根據(jù)減半遞推技術(shù)設(shè)計(jì)出的算法是遞歸算法，在執(zhí)行過(guò)程中只能靠算法本身到達(dá)遞歸邊界。如例子：兩個(gè)n階矩陣相乘的快速方法就是遞歸算法（斯特拉森（Strassen）算法）。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法51㈥回溯法通過(guò)對(duì)問(wèn)題的分析，找出一個(gè)解決問(wèn)題的線索，然后沿著這個(gè)線索逐步試探，對(duì)于每一步的試探，若試探成功，就得到問(wèn)題的解，若試探失敗，就逐步回退，換別的路線再進(jìn)行試探。例1.4求解皇后問(wèn)題。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法52例1.4求解皇后問(wèn)題。 由n2個(gè)方塊排成n行n列的正方形稱(chēng)為“n元棋盤(pán)”。如果兩個(gè)皇后位于棋盤(pán)上的同一行或同一列或同一對(duì)角線上，則稱(chēng)它們?yōu)榛ハ喙簟，F(xiàn)要求找使n元棋盤(pán)上的n個(gè)皇后互不攻擊的所有布局。分析：假設(shè)棋盤(pán)上的每一行放置一個(gè)皇后，分別用自然數(shù)進(jìn)行編號(hào)為1，2，…，n。首先，將問(wèn)題歸結(jié)為在n元棋盤(pán)的每一行上安置一個(gè)皇后，并假設(shè)第i個(gè)皇后被安置在第i行上。定義一個(gè)長(zhǎng)度為n的一維數(shù)組q，其中每一個(gè)元素q[i]（i=1，2，…，n）用于在安置皇后過(guò)程中隨時(shí)記錄第i行上的皇后所在列號(hào)。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法53此時(shí)，在安置每一行上的皇后時(shí)，只需考慮每?jī)蓚€(gè)皇后不能在同一列或者同一對(duì)角線上即可。容易驗(yàn)證，第i行上的皇后和第j行上的皇后正好在同一列上的充要條件為：

q[i]–q[j]=0

正好在某一對(duì)角線上的充要條件為： |q[i]–q[j]|-|i-j|=0在初始時(shí)，將每一行的皇后均放在第一列，即初始狀態(tài)為：

q[i]=1,i=1,2,3,…,n。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法54然后從第一行（即i=1）開(kāi)始進(jìn)行以下過(guò)程：設(shè)前i-1行行的皇后已經(jīng)布局好，即它們互不攻擊?，F(xiàn)考慮安排第i行上的皇后位置，使之與前i-1行上的皇后也互不攻擊。為了實(shí)現(xiàn)這一點(diǎn)，需要從第i行皇后的當(dāng)前位置開(kāi)始向右搜索：2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法55若q[i]≤n，則需檢查第i行皇后與前i-1行的皇后是否互不攻擊。若無(wú)攻擊，則考慮安排下一行皇后的位置；若有攻擊，則將第i行皇后右移一個(gè)位置，重新進(jìn)行這個(gè)過(guò)程。若q[i]>n，則說(shuō)明在前i-1行皇后的當(dāng)前布局下，第i行皇后無(wú)法安置。此時(shí)，將第i行皇后重新放在第一列，且回退一行，考慮第i-1行皇后與前i-2行皇后均互不攻擊的下一個(gè)位置。在這種情況下，如果已經(jīng)退到第0行（n元棋盤(pán)不存在第0行），則過(guò)程結(jié)束。若當(dāng)前安置好的皇后是在最后一行（即第n行），則說(shuō)明已找到了n個(gè)皇后互不攻擊的一個(gè)布局，將這個(gè)布局打印輸出。然后將第n行的皇后右移一個(gè)位置，重新進(jìn)行這個(gè)過(guò)程，以便進(jìn)一步尋找出另外的布局。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法56舉例：5階皇后問(wèn)題初始狀態(tài)：五粒皇后棋子最初均被放置在每一行的第1列，即，數(shù)組q[5]中的五個(gè)元素均取初值1。12345123452023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法57舉例：5階皇后問(wèn)題皇后1：前面沒(méi)有其它皇后，所以保留其初始值1，表示該皇后棋子被放置在第1行（1號(hào)皇后）第1列。q[1]=1。12345123452023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法58舉例：5階皇后問(wèn)題皇后2：前面有皇后1，從第1列開(kāi)始尋找和前面的所有皇后棋子均不相互攻擊的位置，第一個(gè)合適的位置在第3列，q[2]=3。12345123452023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法59舉例：5階皇后問(wèn)題皇后3：前面有皇后1和皇后2，尋找到第一個(gè)合適的位置（與皇后1、2均不相互攻擊）為第2列，q[3]=2。12345123452023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法60舉例：5階皇后問(wèn)題皇后4：前面有皇后1、2和3，尋找到第一個(gè)合適的位置為第5列，q[4]=5。12345123452023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法61舉例：5階皇后問(wèn)題皇后5：前面有皇后1～4，尋找到第一個(gè)合適的位置為第4列，q[5]=4。1234512345找到一個(gè)布局！找到一個(gè)5元棋盤(pán)上的5個(gè)皇后互不攻擊布局，即這5粒棋子相互均不在同一行、同一列和同一對(duì)角線上。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法62舉例：5階皇后問(wèn)題重新開(kāi)始查找新布局：從上一布局最后一粒皇后棋子開(kāi)始。將皇后5右移動(dòng)一格，q[5]=5。1234512345原來(lái)的位置新的位置2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法63舉例：5階皇后問(wèn)題發(fā)現(xiàn)問(wèn)題：皇后5找不到一個(gè)合適的新位置，所以說(shuō)明前四個(gè)皇后棋子的位置不合適，所以問(wèn)題回溯到皇后4的重新找位上，其皇后5回到第1列。12345123452023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法64舉例：5階皇后問(wèn)題又發(fā)現(xiàn)新問(wèn)題：皇后4也找不到一個(gè)合適的新位置，所以說(shuō)明前三個(gè)皇后棋子的位置不合適，所以問(wèn)題回溯到皇后3的重新找位上，其皇后4回到第1列。12345123452023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法65舉例：5階皇后問(wèn)題重找新布局之皇后3：通過(guò)皇后3不斷后移，又發(fā)現(xiàn)了第4列是一個(gè)合適的位置，q[3]=4。此時(shí)皇后3與皇后1、2均不相互攻擊。1234512345原來(lái)的位置新的位置2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法66舉例：5階皇后問(wèn)題重找新布局之皇后4：皇后4右移動(dòng)，發(fā)現(xiàn)新的合適位置第2列，即q[4]=2。12345123452023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法67舉例：5階皇后問(wèn)題重找新布局之皇后5：皇后5右移動(dòng)，發(fā)現(xiàn)只能放在第5列，但顯然不合適，所以重新回溯到皇后4尋找！同時(shí)皇后5回到第1列。12345123452023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法68舉例：5階皇后問(wèn)題重找新布局之回溯皇后4：皇后4右移動(dòng)，發(fā)現(xiàn)新位置第5列，q[4]=5。12345123452023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法69舉例：5階皇后問(wèn)題重找新布局之皇后5：皇后5右移動(dòng)，發(fā)現(xiàn)新位置第2列，q[5]=2，此時(shí)找到第二個(gè)布局。1234512345又找到一個(gè)布局！找到一個(gè)5元棋盤(pán)上的5個(gè)皇后互不攻擊布局，即這5粒棋子相互均不在同一行、同一列和同一對(duì)角線上。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法70總結(jié)綜合以上過(guò)程，可以形象地概括成一句話：“向前走，碰壁回頭”。這種方法也稱(chēng)為深度優(yōu)先搜索DFS（DepthFirstSearch）技術(shù)。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法71算法1.4求解皇后問(wèn)題。輸入：n。輸出：n個(gè)皇后互不攻擊的各種布局，即數(shù)組元素q[i]（i=1，2，…，n）。FORi＝1TOnDOq[i]＝1i＝1loop:

IF(q[i]≤n)THEN{k＝1WHILE((k＜i)and((q[k]－q[i])*(|q[k]－q[i]|－|k－i|))≠0)DOk＝k＋1

IF(k＜i)THENq[i]＝q[i]＋1當(dāng)循環(huán)是因?yàn)閗≥i而停止的時(shí)候說(shuō)明：第i個(gè)皇后棋和之前的i-1個(gè)皇后棋中的某一個(gè)發(fā)生了相互攻擊的情況。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法72

ELSE{i＝i＋1

//考慮下一行皇后的位置IF(i＞n)THEN{OUTPUTq[i](i＝1，2，…，n)

q[n]＝q[n]＋1//重新考慮新的棋盤(pán)布局i＝n}}}2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法73ELSE//前i-1行的棋盤(pán)布局不能保證第i行皇后//可以找到合適的位置{q[i]＝1i＝i－1IF(i＜1)THENRETURNq[i]＝q[i]＋1}GOTOloopRETURN說(shuō)明已經(jīng)回退到第1個(gè)皇后棋處還找不到新的布局，則目前所有的布局已經(jīng)全部找到。結(jié)束程序。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法741.3算法的復(fù)雜度分析算法的復(fù)雜度主要是指時(shí)間復(fù)雜度與空間復(fù)雜度。1.3.1算法的時(shí)間復(fù)雜度定義：執(zhí)行這個(gè)算法的計(jì)算工作量，即算法的時(shí)間代價(jià)。面臨的問(wèn)題：如何分析一個(gè)算法的工作量。簡(jiǎn)單的解決辦法：執(zhí)行算法所需的時(shí)間作為算法工作量的度量。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法75另一種對(duì)于時(shí)間復(fù)雜度的度量用算法程序中所執(zhí)行的的指令條數(shù)或語(yǔ)句條數(shù)來(lái)度量算法的工作量。缺點(diǎn)：程序中各種指令或者語(yǔ)句的執(zhí)行速度是極不相同的，而且這種方法又很大程度上取決于所使用的程序設(shè)計(jì)語(yǔ)言以及編制程序者的水平和風(fēng)格。所以這種方法也是不可取的。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法76結(jié)論為了能夠客觀地反映出一個(gè)算法的效率，度量算法工作量的方法必須與所使用的計(jì)算機(jī)、程序設(shè)計(jì)語(yǔ)言以及編制程序者無(wú)關(guān)；應(yīng)該與算法實(shí)現(xiàn)過(guò)程中的許多細(xì)節(jié)（包括循環(huán)控制變量的計(jì)算、數(shù)組下標(biāo)的計(jì)算、設(shè)置數(shù)據(jù)結(jié)構(gòu)指針等“簿記”bookkeeping）無(wú)關(guān)。用算法在執(zhí)行過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量算法的工作量。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法77如何選擇基本運(yùn)算應(yīng)該遵循的兩個(gè)原則：算法執(zhí)行的運(yùn)算總次數(shù)與基本運(yùn)算的次數(shù)大體上要成正比；基本運(yùn)算以外的其它運(yùn)算其運(yùn)算量可以忽略。舉例：在一維數(shù)組中順序查找值為x的元素，可以選取“x和數(shù)組元素的比較”作為基本運(yùn)算。在兩個(gè)實(shí)矩陣相乘的算法中，可以選取“兩個(gè)實(shí)數(shù)的乘法”作為基本運(yùn)算。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法78舉例：順序查找一維數(shù)組L[10]，該形式被稱(chēng)為是長(zhǎng)度為10的線性表的順序存儲(chǔ)（順序?qū)崿F(xiàn)）。要求：在該數(shù)組中分別查找并分別輸出元素29和元素48的位置，如果該元素不在其中則輸出-1。結(jié)果：查找成功、查找失敗。3516788543293321544612345678910L[10]元素29在數(shù)組L中查找成功，位置為6。順序與數(shù)組L中的所有元素比較后得出查找失敗的結(jié)論，輸出結(jié)果-1。該算法的基本操作應(yīng)為：兩兩元素的比較。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法79舉例：矩陣相乘兩個(gè)4階的矩陣相乘：×由于計(jì)算機(jī)在進(jìn)行實(shí)數(shù)運(yùn)算時(shí)，乘法運(yùn)算的時(shí)間代價(jià)要遠(yuǎn)遠(yuǎn)高于加法運(yùn)算的時(shí)間代價(jià)，該算法的基本操作應(yīng)為：實(shí)數(shù)間的乘法運(yùn)算。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法80算法所執(zhí)行的基本運(yùn)算次數(shù)有時(shí)與問(wèn)題的規(guī)模有關(guān)。舉例：兩個(gè)20階矩陣相乘與兩個(gè)10階矩陣相乘。算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問(wèn)題規(guī)模n的函數(shù)，即f(n)。同時(shí)，一個(gè)算法的具體工作量，即對(duì)于一個(gè)固定的規(guī)模n，算法所執(zhí)行的基本運(yùn)算次數(shù)還可能與特定的輸入有關(guān)。舉例：“在長(zhǎng)度為n的一個(gè)維數(shù)組中查找值為x的元素?！保ú捎庙樞虿檎曳ǎ?023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法81兩種分析算法工作量的方法(1)平均性態(tài)(AerageBehavior)當(dāng)問(wèn)題的規(guī)模為n時(shí)，算法執(zhí)行的基本運(yùn)算次數(shù)取決于某一特定的輸入?？梢杂酶鞣N特定輸入下的基本運(yùn)算次數(shù)的帶權(quán)平均值來(lái)度量算法的工作量。設(shè)x為所有可能輸入中某個(gè)特定輸入，p(x)是x出現(xiàn)的概率（即輸入為x的概率），T(x)是算法在輸入為x時(shí)所執(zhí)行的基本運(yùn)算次數(shù)，則算法的平均性態(tài)：2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法82最壞情況復(fù)雜性(Worst-CaseComplexity)含義：在規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法83舉例說(shuō)明例1.5設(shè)L是包含n個(gè)元素的一維數(shù)組。對(duì)于指定的輸入x，如果x在數(shù)組中，則順序找到它第一次出現(xiàn)處的下標(biāo)；如果x不在數(shù)組中，則以下標(biāo)0作為查找結(jié)果。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法84算法：順序搜索法（SequentialSearch）。輸入：一維數(shù)組L(1:n)，被查項(xiàng)x。輸出：第一次使L(j)=x的j，若x不在數(shù)組L中，則輸出j=0。j←1WHILE(j≤n)and(L(j)≠x)DOj←j+1IFj>nTHENj←0OUTPUTjRETURN2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法85（1）平均性態(tài)分析設(shè)被查項(xiàng)x在數(shù)組L中的概率為q。當(dāng)輸入的x為L(zhǎng)(i)時(shí)，算法所做的比較次數(shù)為：其中x=L(n+1)表示x不在數(shù)組L中的情況。再假設(shè)輸入的x出現(xiàn)在數(shù)組中的每個(gè)位置上的可能性是一樣的，即2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法86于是有2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法87（2）最壞情況分析最壞情況發(fā)生在當(dāng)x是數(shù)組的最后一個(gè)元素或者x不在數(shù)組中的時(shí)候，這時(shí)有即，在這兩種情況下，要和數(shù)組中所有的元素進(jìn)行比較。2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法88補(bǔ)充：時(shí)間頻度與時(shí)間復(fù)雜度1.時(shí)間頻度一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱(chēng)為語(yǔ)句頻度或時(shí)間頻度。記為T(mén)(n)。基本操作的執(zhí)行次數(shù)2023/2/5計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第一章算法892.時(shí)間復(fù)雜度在時(shí)間頻度中，n稱(chēng)為問(wèn)題的規(guī)模，當(dāng)n不斷變化時(shí)，時(shí)間頻度T(n)也會(huì)不斷變化。為了知道其變化的規(guī)律引入了時(shí)間復(fù)雜度概念。若有某個(gè)輔助函數(shù)f(n)，使得當(dāng)n趨近于無(wú)窮大時(shí)，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱(chēng)f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作