算法簡(jiǎn)述加強(qiáng)版

1、算法簡(jiǎn)述：第一章：1考試分值30%，題型選擇、填空占90%，其他以附屬形式出現(xiàn)2了解四個(gè)漸近階（ 、）含義，運(yùn)算，簡(jiǎn)單判斷簡(jiǎn)單描述如下，設(shè)有正函數(shù)f(n)和g(n)，I、存在正常數(shù)、，使得當(dāng)n時(shí)，有f(n) *g(n) 記為f(n)= (g(n)，函數(shù)的 一般上界II、存在正常數(shù)、，使得當(dāng)n時(shí)，有f(n) *g(n) 記為f(n)= (g(n)，函數(shù)的一般下界III、同時(shí)滿足上兩條，記為f(n)= (g(n)，IV、至于，即，記為f()=(g();參考習(xí)題1.1， 1.3, 1.6(重點(diǎn)，答案不全，理由自己補(bǔ)充)。習(xí)題1.6理由參照以上說(shuō)明即可搞定第二章：分治思想第一部分：課堂筆記一：二：遞歸

2、樹(shù)：計(jì)算時(shí)間最后一層1 1 1 1 1 1 1 1完全二叉樹(shù)，推得層數(shù)為logn，那么時(shí)間復(fù)雜度為不對(duì)稱遞歸樹(shù)解法與上述一致，只是對(duì)不對(duì)稱處理注一點(diǎn)即可分治法，將一個(gè)規(guī)模為n的問(wèn)題分為k個(gè)的子問(wèn)題，這些子問(wèn)題相互獨(dú)立且與原問(wèn)題相同遞歸的求解的這些子問(wèn)題；不妨設(shè)k個(gè)子問(wèn)題規(guī)模為n/m,分解發(fā)值為n0=1，設(shè)k個(gè)子問(wèn)題解合并為原問(wèn)題的解需f(n)個(gè)單位時(shí)間遞歸式：=推導(dǎo)式1：，簡(jiǎn)化一下注簡(jiǎn)化式只在求時(shí)間復(fù)雜度使用，其他狀況勿用！以分治發(fā)派生出：大整數(shù)的乘法、棋盤(pán)覆蓋、矩陣乘法、合并排序、快速排序、線性時(shí)間排序，這些雖然不會(huì)原題出現(xiàn)，但其中兩個(gè)的思想方法會(huì)在考試中出現(xiàn)，分析分析，他們的思想遞歸式、時(shí)

3、間復(fù)雜度即可最好會(huì)用！(以上面遞歸式和推導(dǎo)式1很容易搞定)參考習(xí)題2.3 ，2.9習(xí)題2.9第三章：解題形式，四步一、 算法策略（以什么思想解題，是動(dòng)態(tài)規(guī)劃還是貪心算法或是分治算法）；二、 算法思想（按第一步往下分析，按套路走下去。列如，第一步說(shuō)是動(dòng)態(tài)規(guī)劃，那么把題目帶進(jìn)動(dòng)態(tài)規(guī)劃套路，段分成多少子問(wèn)題，假定某個(gè)方向最優(yōu)，自低向上分析等等相似的貪心算法也如此，最后最好加一點(diǎn)遞歸式推導(dǎo)式什么等等，）；三、 算法實(shí)現(xiàn)；（程序，比一般程序簡(jiǎn)單多，不要求寫(xiě)出得合乎語(yǔ)法結(jié)構(gòu)，形式化東西，漢語(yǔ)加程序語(yǔ)言敘述）四、 算法時(shí)間復(fù)雜度分析（即大O()多少什么）。3.1矩陣相乘33最長(zhǎng)公共子序列3.4最大子段和3.

4、7圖像壓縮3.10 0-1背包問(wèn)題（課堂有例子，找出來(lái)！做做?。┱n后參考習(xí)題算法分析題第三章，算法實(shí)現(xiàn)題：習(xí)題.3.2算法實(shí)現(xiàn)題3.3.注以上解法勿用：簡(jiǎn)潔解法如下：注意時(shí)間復(fù)雜度算法實(shí)現(xiàn)題3.5算法實(shí)現(xiàn)題3.6分析：給出的算法是自低向上，那么遞歸式必定為自上而下，其實(shí)就是上三角問(wèn)題，貪心確實(shí)很好用，每次選取的都是最大的，整個(gè)不就最大。但這題要?jiǎng)討B(tài)解，換個(gè)角度，這也是最優(yōu)子結(jié)構(gòu)問(wèn)題，采用動(dòng)態(tài)規(guī)劃中的順推解法。按三角形的行劃分階段。若行數(shù)為n, 則可把問(wèn)題看作一個(gè)n-1個(gè)階段的決策問(wèn)題。從始點(diǎn)出發(fā)，依順向求出第一階段、第二階段，第n-1階段中各決策點(diǎn)至始點(diǎn)的最佳路徑，最終求出始點(diǎn)到終點(diǎn)的最佳路徑

5、。即在上三角每行選個(gè)數(shù)求，row代表行，col代表列；以一個(gè)二維數(shù)組來(lái)trangle保存當(dāng)前最大和，遞歸式如下：算法描述如下：（原答案有誤，已改?。┧惴▽?shí)現(xiàn)：（c版）#include stdio.h#include math.hmain()FILE *fp1,*fp2;int a105105;int i,j;int n;char c105;fp1=fopen(numr.txt,rt);fscanf(fp1,%d,&n);for(i=1;i=n;i+) for(j=1;j=1;i-) for(j=1;j=ai+1j+1) aij=aij+ai+1j;ci=L;elseaij=aij+ai+1j+

6、1;ci=R;/*倒推。判斷從（i，j）這個(gè)點(diǎn)開(kāi)始往下走的最大的和，并存在這個(gè)點(diǎn)上。*/fp2=fopen(numw.txt,wt);fprintf(fp2,%dn,a11);/*循環(huán)完畢后，三角形最頂端的點(diǎn)所存的值即為最大的和，輸出這個(gè)值*/for(i=1;i=n;i+)fprintf(fp2,%c,ci);fclose(fp2);時(shí)間復(fù)雜度第四章：貪心算法考試分值20%左右第四題問(wèn)答題出現(xiàn)，加一道選擇題或一題填空考試內(nèi)容：活動(dòng)安排、哈弗曼編碼、單源最短路徑，最小生成樹(shù)、多級(jí)調(diào)度雖然列了多條，分開(kāi)來(lái)看：多級(jí)調(diào)度調(diào)度必考，但是只是一道填空或是選擇，解題方法書(shū)P121哈弗曼編碼、單源最短路徑，最

7、小生成樹(shù)此三者，數(shù)據(jù)結(jié)構(gòu)，翻開(kāi)看看，加一點(diǎn)算法知識(shí)（即上課老師說(shuō)的思想分析，著重點(diǎn)，看看筆記），解決最后一個(gè)，活動(dòng)安排，考到按部就班解，解- 貪心算法解此題一般步驟：一、 按某種屬性排序二、 貪心選擇這種屬性（最大、最小或是最長(zhǎng)之類(lèi)的）三、 對(duì)于活動(dòng)安排采取的貪心為迭代法，選取的是最大相容子集（即最優(yōu)解）四、 時(shí)間復(fù)雜度什么滴簡(jiǎn)述一下。參考習(xí)題算法實(shí)現(xiàn)題4.1說(shuō)明：此程序是調(diào)用活動(dòng)安排算法（函數(shù)，書(shū)103頁(yè)），每次求一個(gè)最大相容子集，放入一會(huì)場(chǎng)，函數(shù)名與書(shū)上不相同注意改寫(xiě)!以下是擴(kuò)展：算法實(shí)現(xiàn)題4.9 汽車(chē)加油問(wèn)題算法描述：1.貪心算法解決方案l 貪心算法的基本思想該題目求加油最少次數(shù)，即求最

8、優(yōu)解的問(wèn)題，可分成幾個(gè)步驟，一般來(lái)說(shuō)，每個(gè)步驟的最優(yōu)解不一定是整個(gè)問(wèn)題的最優(yōu)解，然而對(duì)于有些問(wèn)題，局部貪心可以得到全局的最優(yōu)解。貪心算法將問(wèn)題的求解過(guò)程看作是一系列選擇，從問(wèn)題的某一個(gè)初始解出發(fā)，向給定目標(biāo)推進(jìn)。推進(jìn)的每一階段不是依據(jù)某一個(gè)固定的遞推式，而是在每一個(gè)階段都看上去是一個(gè)最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。不斷地將問(wèn)題實(shí)例歸納為更小的相似的子問(wèn)題，并期望做出的局部最優(yōu)的選擇產(chǎn)生一個(gè)全局得最優(yōu)解。l 貪心算法的適用的問(wèn)題貪心算法適用的問(wèn)題必須滿足兩個(gè)屬性：（） 貪心性質(zhì)：整體的最優(yōu)解可通過(guò)一系列局部最優(yōu)解達(dá)到，并且每次的選擇可以依賴以前做出的選擇，但不能依賴于以后的選擇。（） 最優(yōu)子結(jié)構(gòu)：

9、問(wèn)題的整體最優(yōu)解包含著它的子問(wèn)題的最優(yōu)解。l 貪心算法的基本步驟（） 分解：將原問(wèn)題分解為若干相互獨(dú)立的階段。（） 解決：對(duì)于每一個(gè)階段求局部的最優(yōu)解。（） 合并：將各個(gè)階段的解合并為原問(wèn)題的解。問(wèn)題分析由于汽車(chē)是由始向終點(diǎn)方向開(kāi)的,我們最大的麻煩就是不知道在哪個(gè)加油站加油可以使我們既可以到達(dá)終點(diǎn)又可以使我們加油次數(shù)最少。提出問(wèn)題是解決的開(kāi)始.為了著手解決遇到的困難,取得最優(yōu)方案。我們可以假設(shè)不到萬(wàn)不得已我們不加油，即除非我們油箱里的油不足以開(kāi)到下一個(gè)加油站，我們才加一次油。在局部找到一個(gè)最優(yōu)的解。卻每加一次油我們可以看作是一個(gè)新的起點(diǎn)，用相同的遞歸方法進(jìn)行下去。最終將各個(gè)階段的最優(yōu)解合并為原

10、問(wèn)題的解得到我們?cè)瓎?wèn)題的求解。加油站貪心算法設(shè)計(jì)（C）：includeincludeint add(int b ,int m,int n) /求一個(gè)從m到n的數(shù)列的和 int sb; for(int i=m;iN) return ERROR; /如果某相鄰的兩個(gè)加油站間的距離大于N，則不能到達(dá)終點(diǎn) if(add(ai, 0, n)N) /如果這段距離小于N，則不需要加油 bi=0; return add(bi,0,n); if(ai=aj&ai=N) /如果每相鄰的兩個(gè)加油站間的距離都是N，則每個(gè)加油站都需要加油 bi=1; return add(bi,0,n); if(ai=aj&aiN)

11、/如果每相鄰的兩個(gè)加油站間的距離相等且都小于N if( add(ai,m,k) N ) bk=1; m+=k; return add(bi,0,n); if(ai!=aj) /如果每相鄰的兩個(gè)加油站間的距離不相等且都小于N if( add(ai,m,k) N ) bk=1; m+=k; return add(bi,0,n); viod main( ) int a ; scanf(%d,a); scanf(/n); scanf(/d,&N); Tanxin(a ,0,n);以下也是這題程序，C+模板形式貪心算法正確性證明：l 貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部

12、最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。對(duì)于一個(gè)具體的問(wèn)題，要確定它是否具有貪心性質(zhì)，我們必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的一個(gè)整體最優(yōu)解。該題設(shè)在加滿油后可行駛的N千米這段路程上任取兩個(gè)加油站、，且距離始點(diǎn)比距離始點(diǎn)近，則若在加油不能到達(dá)終點(diǎn)那么在加油一定不能到達(dá)終點(diǎn)，如圖：由圖知：因?yàn)閙+Nn+N，即在B點(diǎn)加油可行駛的路程比在A點(diǎn)加油可行駛的路程要長(zhǎng)n-m千米，所以只要終點(diǎn)不在B、C之間且在C的右邊的話，根據(jù)貪心選擇，為使加油次數(shù)最少就會(huì)選擇距離加滿油得點(diǎn)遠(yuǎn)一些的加油站去加油，因此，加油次數(shù)最少滿足貪心選擇性質(zhì)。l 最優(yōu)子結(jié)構(gòu)性質(zhì)：當(dāng)一個(gè)問(wèn)題大的最優(yōu)解包含著它的子問(wèn)題的最優(yōu)解時(shí)，稱該問(wèn)題具有

13、最優(yōu)子結(jié)構(gòu)性質(zhì)。由于（b1,b2,bn）是這段路程加油次數(shù)最少的一個(gè)滿足貪心選擇性質(zhì)的最優(yōu)解，則易知若在第一個(gè)加油站加油時(shí)，b1=1,則（b2,b3,bn）是從 a2到an這段路程上加油次數(shù)最少且這段路程上的加油站個(gè)數(shù)為（a2,a3,an）的最優(yōu)解,即每次汽車(chē)中剩下的油不能在行駛到下一個(gè)加油站時(shí)我們才在這個(gè)加油站加一次油，每個(gè)過(guò)程從加油開(kāi)始行駛到再次加油滿足貪心且每一次加油后相當(dāng)于與起點(diǎn)具有相同的條件，每個(gè)過(guò)程都是相同且獨(dú)立，也就是說(shuō)加油次數(shù)最少具有最優(yōu)子結(jié)構(gòu)性質(zhì)。貪心算法時(shí)間復(fù)雜度分析由于若想知道該在哪個(gè)加油站加油就必須遍歷所有的加油站，且不需要重復(fù)遍歷，所以時(shí)間復(fù)雜度為O(n)。算法實(shí)現(xiàn)題

14、4.10 區(qū)間覆蓋問(wèn)題（待續(xù)）貪心策略：每次覆蓋盡可能多的點(diǎn)算法思想：對(duì)n個(gè)點(diǎn)坐標(biāo)排序，從小到大，每次選取未被覆蓋且坐標(biāo)最小的點(diǎn)，以此點(diǎn)為起始位置，用長(zhǎng)度K覆蓋，直到所有點(diǎn)被覆蓋。#include#includeint cmp(const void*a,const void*b) return *(int*)a-*(int*)b;int main() int i,j=0,a100000,m=1,n,k; cinnk; for(i=0;iai; qsort(a,n,sizeof(int),cmp); for(i=0;iaj+k) m+; j=i; coutmendl;；另版#include #i

15、nclude #include using namespace std;int n , m , i ;double greedy(vector x , int s )vector st(s+1,0);vector su(s+1,0);int n = x.size();sort(x.begin(),x.end() );int i = 0 , j = 0 ;while(in)stj += xi;suj +=stj;i + ; j + ;if( j = s ) j = 0 ;double t = 0 ;for ( i = 0 ; i n m ;vector x;for ( i = 0 ; i ai;

16、 x.push_back(ai);coutgreedy(x,m)endl; return 0;算法實(shí)現(xiàn)題4.12 刪數(shù)問(wèn)題（待續(xù)）n n位數(shù)a可表示為：x1x2x3xixjxkxm xn 要?jiǎng)h去k位數(shù)，使得剩下的數(shù)字組成的整數(shù)最小。設(shè)本問(wèn)題位T，其最優(yōu)解A=(y1,y2, ,yk)表示依次刪去k個(gè)數(shù)，在刪去k個(gè)數(shù)后剩下的數(shù)字按原次序排成的新數(shù)。即，最優(yōu)值極為T(mén)A。貪心選擇策略求解n 對(duì)于a的前r位數(shù)： x1x2xpxq；若xqxr 則刪去xq，即得到一個(gè)n-1位的數(shù)a1，a1為a去掉一位后，數(shù)字按原次序排列最小的一個(gè)新正整數(shù)，可表示為：x1x2x3xpxrxs xn n 例:a=45372，其

17、中453，則刪去5，得a1=4372n a=45732，其中4573，則刪去7，得a1=4532 n 對(duì)于a1，原問(wèn)題T變成了對(duì)n-1位數(shù)刪去k-1位數(shù)的新問(wèn)題T，新問(wèn)題與原問(wèn)題相同，只是規(guī)模減一?；诖朔N刪數(shù)策略，對(duì)新問(wèn)題T，仍可按照上述采用最近下降點(diǎn)刪除的貪心選擇策略，如此進(jìn)行下去，直至刪去k個(gè)數(shù)為止。n 設(shè)問(wèn)題T已按照最近下降點(diǎn)的方法刪除，A=(y1,y2, ,yk)是刪數(shù)問(wèn)題的一個(gè)最優(yōu)解。易知，若問(wèn)題有解，則1 k n。n (1)當(dāng)k=1時(shí)，由前得證，A=(y1,A)是問(wèn)題的最優(yōu)解；n (2)當(dāng)k=q時(shí)，由反證法，可得 A=(y1,y2 ,yq)是最優(yōu)解； 當(dāng)k=q+1時(shí)，由前得證，

18、A=(y1,y2 ,yq+ yq+1)是最優(yōu)解。所以，最優(yōu)裝在問(wèn)題具有貪心選擇性質(zhì)。時(shí)間復(fù)雜度分析：O（n）第五章、第六章回溯法與分支界限法的異同點(diǎn)，及優(yōu)缺點(diǎn)二者相同點(diǎn)：都是解空間樹(shù)上搜索解的算法。不同點(diǎn)：一、 一般情況下，二者求解的目標(biāo)不同?；厮莘ㄇ蠼獾哪繕?biāo)是找出樹(shù)中滿足約束條件的所有解，二分治界限發(fā)求解目標(biāo)是找出滿足約束條件的一個(gè)解，或是在滿足約束條件找出使用某一目標(biāo)函數(shù)達(dá)到極大或極小的解，即某種意義下的最優(yōu)解。二、 回溯法只通過(guò)約束條件減去非可行解，而分支界限法不僅通過(guò)約束條件，也通過(guò)目標(biāo)函數(shù)的界限來(lái)減少無(wú)效搜索。三、 搜索方式：回溯法，采用深度優(yōu)先搜索，開(kāi)始結(jié)點(diǎn)為活結(jié)點(diǎn)，也為當(dāng)前擴(kuò)展節(jié)點(diǎn)搜索縱向生成一個(gè)新結(jié)點(diǎn)，新結(jié)點(diǎn)為活結(jié)點(diǎn)，也為當(dāng)前擴(kuò)展結(jié)點(diǎn)，不能縱向移動(dòng)時(shí)，此點(diǎn)定為死結(jié)點(diǎn)，回移到最近的結(jié)點(diǎn)，直到?jīng)]有活結(jié)點(diǎn)為止；分支界限法，分支定界算法采用廣度優(yōu)先或最小耗費(fèi)優(yōu)先的方法搜索解空間樹(shù)，并且，在分支定界算法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。 策略是：在擴(kuò)展節(jié)點(diǎn)處，先生成其所有的兒子節(jié)點(diǎn)（分支），然后再?gòu)漠?dāng)前的活結(jié)點(diǎn)