計算機程序基礎數(shù)據(jù)算法

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

假設買母雞i只，公雞j只，小雞k只。2023/2/5計算機軟件技術基礎第一章算法17最粗略的列舉算法如下：算法：求解百雞百錢問題。

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

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

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

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

Move(X,n,Z)2023/2/5計算機軟件技術基礎第一章算法42補充舉例之算法：求解n階Hanoi塔問題。

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í)行過程中調用自身的方法叫遞歸調用。遞歸的邊界2023/2/5計算機軟件技術基礎第一章算法43另一個簡單的例子例1.2：編寫一個過程，對于輸入的參數(shù)n，依次打印輸出自然數(shù)1到n。（非遞歸算法）PROCEDUREWRT(n)FORk＝1TOnDOOUTPUTkRETURN2023/2/5計算機軟件技術基礎第一章算法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計算機軟件技術基礎第一章算法45總結一個典型的遞歸算法：自己調用自己。直接遞歸：如果一個算法P顯式地調用自己。間接遞歸：如果算法P調用另一個算法Q，而算法Q又調用算法P。遞歸算法與遞推算法的區(qū)別：兩者的實現(xiàn)方法是大不一樣的。遞推是從初始條件出發(fā)，逐次推出所需求的結果；而遞歸則是從算法本身達到遞歸邊界。2023/2/5計算機軟件技術基礎第一章算法46㈤減半遞推所謂“減半”，是指將問題的規(guī)模減半，而問題的性質不變。所謂“遞推”，是指重復“減半”的過程。將實際問題的規(guī)模逐漸減少，可明顯地降低解決問題的復雜程度。這種方法稱為分治法，即對問題分而治之。工程上常用的分治法是減半遞推技術，這個技術在快速算法的研究中有很重要的使用價值。2023/2/5計算機軟件技術基礎第一章算法47舉例例1.3：二分法求方程f(x)在[a,b]的根設方程f(x)=0在區(qū)間[a,b]內有且只有一個實根，則函數(shù)f(x)在區(qū)間的兩個端點處的函數(shù)值必異號，即2023/2/5計算機軟件技術基礎第一章算法48首先取給定區(qū)間的中點c＝(a＋b)/2。然后判斷f(c)是否為0。若f(c)＝0,則說明c即為所求的根，求解過程結束；如果f(c)≠0,則根據(jù)以下原則將原區(qū)間減半；若f(a)f(c)＜0，則取原區(qū)間的前半部分；若f(b)f(c)＜0，則取原區(qū)間的后半部分。最后判斷減半后的區(qū)間長度是否已經很?。喝魘a－b|＜ε，則過程結束，取(a＋b)/2為根的近似值；若|a－b|≥ε，則重復上述的減半過程。所能接受的誤差2023/2/5計算機軟件技術基礎第一章算法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結束得出準確根f0×f1>0得出近似根a←cb←cTTFFTF2023/2/5計算機軟件技術基礎第一章算法50總結對于有些實際問題，可以設計出直觀的減半遞推算法，經過逐次的減半遞推，直接得到所需求的結果，如例1.3：二分法求方程的根。對于另外一些問題，根據(jù)減半遞推技術設計出的算法是遞歸算法，在執(zhí)行過程中只能靠算法本身到達遞歸邊界。如例子：兩個n階矩陣相乘的快速方法就是遞歸算法（斯特拉森（Strassen）算法）。2023/2/5計算機軟件技術基礎第一章算法51㈥回溯法通過對問題的分析，找出一個解決問題的線索，然后沿著這個線索逐步試探，對于每一步的試探，若試探成功，就得到問題的解，若試探失敗，就逐步回退，換別的路線再進行試探。例1.4求解皇后問題。2023/2/5計算機軟件技術基礎第一章算法52例1.4求解皇后問題。 由n2個方塊排成n行n列的正方形稱為“n元棋盤”。如果兩個皇后位于棋盤上的同一行或同一列或同一對角線上，則稱它們?yōu)榛ハ喙簟，F(xiàn)要求找使n元棋盤上的n個皇后互不攻擊的所有布局。分析：假設棋盤上的每一行放置一個皇后，分別用自然數(shù)進行編號為1，2，…，n。首先，將問題歸結為在n元棋盤的每一行上安置一個皇后，并假設第i個皇后被安置在第i行上。定義一個長度為n的一維數(shù)組q，其中每一個元素q[i]（i=1，2，…，n）用于在安置皇后過程中隨時記錄第i行上的皇后所在列號。2023/2/5計算機軟件技術基礎第一章算法53此時，在安置每一行上的皇后時，只需考慮每兩個皇后不能在同一列或者同一對角線上即可。容易驗證，第i行上的皇后和第j行上的皇后正好在同一列上的充要條件為：

q[i]–q[j]=0

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

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

ELSE{i＝i＋1

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

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