算法簡述加強版

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

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

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

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

5、。即在上三角每行選個數(shù)求，row代表行，col代表列；以一個二維數(shù)組來trangle保存當前最大和，遞歸式如下：算法描述如下：（原答案有誤，已改?。┧惴▽崿F(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）這個點開始往下走的最大的和，并存在這個點上。*/fp2=fopen(numw.txt,wt);fprintf(fp2,%dn,a11);/*循環(huán)完畢后，三角形最頂端的點所存的值即為最大的和，輸出這個值*/for(i=1;i=n;i+)fprintf(fp2,%c,ci);fclose(fp2);時間復(fù)雜度第四章：貪心算法考試分值20%左右第四題問答題出現(xiàn)，加一道選擇題或一題填空考試內(nèi)容：活動安排、哈弗曼編碼、單源最短路徑，最小生成樹、多級調(diào)度雖然列了多條，分開來看：多級調(diào)度調(diào)度必考，但是只是一道填空或是選擇，解題方法書P121哈弗曼編碼、單源最短路徑，最

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

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

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

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

11、/如果每相鄰的兩個加油站間的距離相等且都小于N if( add(ai,m,k) N ) bk=1; m+=k; return add(bi,0,n); if(ai!=aj) /如果每相鄰的兩個加油站間的距離不相等且都小于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ì)是指所求問題的整體最優(yōu)解可以通過一系列局部

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

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

14、4.10 區(qū)間覆蓋問題（待續(xù)）貪心策略：每次覆蓋盡可能多的點算法思想：對n個點坐標排序，從小到大，每次選取未被覆蓋且坐標最小的點，以此點為起始位置，用長度K覆蓋，直到所有點被覆蓋。#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;算法實現(xiàn)題4.12 刪數(shù)問題（待續(xù)）n n位數(shù)a可表示為：x1x2x3xixjxkxm xn 要刪去k位數(shù)，使得剩下的數(shù)字組成的整數(shù)最小。設(shè)本問題位T，其最優(yōu)解A=(y1,y2, ,yk)表示依次刪去k個數(shù)，在刪去k個數(shù)后剩下的數(shù)字按原次序排成的新數(shù)。即，最優(yōu)值極為TA。貪心選擇策略求解n 對于a的前r位數(shù)： x1x2xpxq；若xqxr 則刪去xq，即得到一個n-1位的數(shù)a1，a1為a去掉一位后，數(shù)字按原次序排列最小的一個新正整數(shù)，可表示為：x1x2x3xpxrxs xn n 例:a=45372，其

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

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