算法復(fù)習(xí)資料

1、1、算法(Algorithm)：對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。2、算法的五大特性：輸入：一個(gè)算法有零個(gè)或多個(gè)輸入。輸出：一個(gè)算法有一個(gè)或多個(gè)輸出。有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。確定性：算法中的每一條指令必須有確切的含義，對(duì)于相同的輸入只能得到相同的 輸出?？尚行裕核惴枋龅牟僮骺梢酝ㄟ^(guò)已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來(lái)實(shí)現(xiàn)。3、算法的描述方法自然語(yǔ)言優(yōu)點(diǎn)：容易理解缺點(diǎn)：冗長(zhǎng)、二義性使用方法：粗線條描述算法思想注意事項(xiàng)：避免寫(xiě)成自然段流程圖優(yōu)點(diǎn)：流程直觀缺點(diǎn)：缺少嚴(yán)密性、靈活性使用方法：描述簡(jiǎn)單算法注意事項(xiàng)：注意抽象層次程序設(shè)計(jì)語(yǔ)言優(yōu)點(diǎn)：

2、能由計(jì)算機(jī)執(zhí)行缺點(diǎn)：抽象性差，對(duì)語(yǔ)言要求高使用方法：算法需要驗(yàn)證注意事項(xiàng)：將算法寫(xiě)成子函數(shù) 偽代碼一一算法語(yǔ)言偽代碼(Pseudocode)：介于自然語(yǔ)言和程序設(shè)計(jì)語(yǔ)言之間的方法，它采用某一程序設(shè) 計(jì)語(yǔ)言的基本語(yǔ)法，操作指令可以結(jié)合自然語(yǔ)言來(lái)設(shè)計(jì)。優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，抽象性強(qiáng)，容易理解使用方法：7 24、算法設(shè)計(jì)的一般過(guò)程1.理解問(wèn)題2.預(yù)測(cè)所有可能的輸入3.在精確解和近似解間做選擇4.確定適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)5.算法設(shè)計(jì)技術(shù)6.描述算法7.跟蹤算法8.分析算法的效率9.根據(jù)算法編寫(xiě)代碼5、時(shí)間復(fù)雜性分析的關(guān)鍵：?jiǎn)栴}規(guī)模：輸入量的多少；運(yùn)行算法所需要的時(shí)間T是問(wèn)題規(guī)模n的函數(shù)，記作T(n)基本語(yǔ)句：執(zhí)

3、行次數(shù)與整個(gè)算法的執(zhí)行時(shí)間成正比的語(yǔ)句for (i=1; i=n; i+)問(wèn)題規(guī)模：nfor (j=1; j0 & ri!=k)i-；return i;算法3.1的基本語(yǔ)句是i0和ri!=k，其執(zhí)行次數(shù)為：頊 +%c = 1 (n - i +1)+ 1 (n - i +1) = n +1 = 0(n) .1. 1 1 n . n .算法3.2改進(jìn)的順序查找int SeqSearch2(int r , int n, int k) 數(shù)組 r1 rn存放查找集合r0=k; i=n;while (ri!=k)i -;return i;算法3.2的基本語(yǔ)句是ri!=k，其執(zhí)行次數(shù)為: TOC o 1-5

4、 h z 1 n +1，p c = ，(n -1 +1) = 0(n).n2BF C+算法i=1i=1int BF(char S , char T) i=1; j=1;while (i=S0 & j=T0 & jT0) return (i-j+1);else return 0;算法3.6選擇排序void SelectSort(int r , int n) /數(shù)組下標(biāo)從 1 開(kāi)始for (i=1; i=n-1; i+)對(duì)n個(gè)記錄進(jìn)行n-1趟簡(jiǎn)單選擇排序index=i;for (j=i+1; j=n; j+)/在無(wú)序區(qū)中找最小記錄if (rjrindex) index=j;if (index!=i

5、) ri - rindex; /若最小記錄不在最終位置則交換該算法的基本語(yǔ)句是內(nèi)層循環(huán)體中的比較語(yǔ)句rjrindex，其執(zhí)行次數(shù)為: 況元況，.、n(n -1) 乙乙 1 =乙(n i) = O(n2)i=1 j=i+1i=1算法3.7起泡排序void BubbleSort(int r , int n)/數(shù)組下標(biāo)從 1 開(kāi)始for (i=1; i=n-1; i+)for (j=1; jrj+1) rj - rj+1； /如果反序，則交換元素該算法的基本語(yǔ)句是內(nèi)層循環(huán)體中的比較語(yǔ)句rjrj+1，其執(zhí)行次數(shù)為：1 札札,n(n 1)、 乙乙 1 =乙(n i) = O(n 2)i=1 j=1i=1

6、算法3.8改進(jìn)的起泡排序void BubbleSort(int r , int n)/數(shù)組下標(biāo)從 1 開(kāi)始exchange=n;/第一趟起泡排序的范圍是r1到 rnwhile (exchange)僅當(dāng)上一趟排序有記錄交換才進(jìn)行本趟排序bound=exchange; exchange=0；for (j=1; jrj+1) rj-rj+1；exchange=j；記錄每一次發(fā)生記錄交換的位置第四章算法4.7最大子段和問(wèn)題int MaxSum(int a , int left, int right)sum=0;if (left= =right) /如果序列長(zhǎng)度為1,直接求解if (aleft0) su

7、m=aleft;else sum=0;else center=(left+right)/2;劃分leftsum=MaxSum(a, left, center);對(duì)應(yīng)情況，遞歸求解rightsum=MaxSum(a, center+1, right);對(duì)應(yīng)情況，遞歸求解s1=0; lefts=0;以下對(duì)應(yīng)情況，先求解s1for (i=center; i=left; i-)lefts+=ai;if (leftss1) s1=lefts;s2=0; rights=0;再求解 s2for (j=center+1; js2) s2=rights;sum=s1+s2;計(jì)算情況的最大子段和if (sumle

8、ftsum) sum=leftsum;/合并，在sum、leftsum和rightsum中取較大者 if (sumrightsum) sum=rightsum;return sum;算法4.8一棋盤(pán)覆蓋void ChessBoard(int tr, int tc, int dr, int dc, int size)/ tr和tc是棋盤(pán)左上角的下標(biāo)，dr和dc是特殊方格的下標(biāo)，/ size是棋盤(pán)的大小，t已初始化為0if (size = = 1) return; /棋盤(pán)只有一個(gè)方格且是特殊方格t+; / L型骨牌號(hào)s = size/2; /劃分棋盤(pán)/覆蓋左上角子棋盤(pán)if (dr tr + s &

9、 dc tc + s) /特殊方格在左上角子棋盤(pán)中ChessBoard(tr, tc, dr, dc, s);遞歸處理子棋盤(pán)else /用t號(hào)L型骨牌覆蓋右下角，再遞歸處理子棋盤(pán)boardtr + s - 1tc + s - 1 = t;ChessBoard(tr, tc, tr+s-1, tc+s-1, s);/覆蓋右上角子棋盤(pán)if (dr = tc + s) /特殊方格在右上角子棋盤(pán)中ChessBoard(tr, tc+s, dr, dc, s);/遞歸處理子棋盤(pán)else /用t號(hào)L型骨牌覆蓋左下角，再遞歸處理子棋盤(pán)boardtr + s - 1tc + s = t;ChessBoard(

10、tr, tc+s, tr+s-1, tc+s, s); /覆蓋左下角子棋盤(pán)if (dr = tr + s & dc = tr + s & dc = tc + s) /特殊方格在右下角子棋盤(pán)中ChessBoard(tr+s, tc+s, dr, dc, s);/遞歸處理子棋盤(pán)else /用t號(hào)L型骨牌覆蓋左上角，再遞歸處理子棋盤(pán)boardtr + stc + s = t;ChessBoard(tr+s, tc+s, tr+s, tc+s, s); 算法4.9 環(huán)賽日程表void GameTable(int k, int a)/ n=2k(kN1)個(gè)選手參加比賽，二維數(shù)組a表示日程安排，數(shù)組下標(biāo)從

11、1開(kāi)始n=2;/k=0，2個(gè)選手比賽日程可直接求得/求解2個(gè)選手比賽日程，得到左上角元素a11=1; a1=2;a21=2; a22=1;for (t=1; tk; t+)迭代處理，依次處理22,2k個(gè)選手比賽日程temp=n; n=n*2;/填左下角元素fOr (i=temp+1; i=n; i+ )for (j=1; j=temp; j+)aij=ai-tempj+temp;/佐下角元素和左上角元素的對(duì)應(yīng)關(guān)系/；填右上角元素for (i=1; i=temp; i+)for (j=temp+1; j=n; j+) aij=ai+temp(j+temp)% n;/填右下角元素for (i=te

12、mp+1; i=n; i+)for (j=temp+1; j=n; j+)aij=ai-tempj-temp;第五章算法5.1一半查找偽代碼：low=1； high=n；設(shè)置初始查找區(qū)間測(cè)試查找區(qū)間】low，high是否存在，若不存在，則查找失??；否則取中間點(diǎn)mid=(low+high)/2;比較k與rmid，有以下三種情況：3.1若krmid，則low=mid+1；查找在右半?yún)^(qū)進(jìn)行，轉(zhuǎn)2；3.3若k=rmid，則查找成功，返回記錄在表中位置mid；判定樹(shù)一述折半查找的判定過(guò)程。長(zhǎng)度為n的判定樹(shù)的構(gòu)造方法為：當(dāng)n=0時(shí)，判定樹(shù)為空；當(dāng)n0時(shí)，判定樹(shù)的根結(jié)點(diǎn)是有序表中序號(hào)為mid=(n+1)/2

13、的記錄，根結(jié)點(diǎn)的左子樹(shù) 是與有序表r1 rmid-1相對(duì)應(yīng)的判定樹(shù)，根結(jié)點(diǎn)的右子樹(shù)是與rmid+1 rn 相對(duì)應(yīng)的 判定樹(shù)。動(dòng)態(tài)規(guī)劃法與分治法類(lèi)似，當(dāng)問(wèn)題不能分解為獨(dú)立的子問(wèn)題,但又符合最優(yōu)化原理(最優(yōu)子結(jié)構(gòu)性質(zhì)）時(shí)，用動(dòng)態(tài)規(guī)劃，通過(guò)多階段決策過(guò)程從逐步找出子問(wèn)題的最優(yōu)解，從而決策出問(wèn)題 的結(jié)果?！胺种畏ā迸c“動(dòng)態(tài)規(guī)劃法”都是遞歸思想的應(yīng)用之一，是找出大問(wèn)題與小的子問(wèn)題之間的關(guān)系, 直到小的子問(wèn)題很容易解決，再由小的子問(wèn)題的解導(dǎo)出大問(wèn)題的解。區(qū)別在于：分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：1）該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；2）該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有。3）利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；4）該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。第一條特征是絕大多數(shù)問(wèn)題都可以滿足的；第二條特征是應(yīng)用分治法的前提，它也是大多數(shù)問(wèn)題可以滿足的；第三條特征是關(guān)鍵。第四條特征涉及到分治法的效率。動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余。動(dòng)態(tài)規(guī)劃法是將問(wèn)題實(shí)例歸納為更小的、相似的子問(wèn)題，并