安徽工業(yè)大學《算法設計與分析》考試內(nèi)容

1、算法的定義：算法是解某一特定問題的一組有窮規(guī)則的集合。算法的性質(zhì)：有限性、確定性、輸入、輸出、能行性算法的時間復雜性越高，算法的執(zhí)行時間越長；反之，執(zhí)行時間越短。算法的空間復雜性越高，算法所需的存儲空間越多；反之越少。初等操作：所有的操作都具有相同的固定字長；所有操作的時間花費都是一個常數(shù)時間間隔。算法分析的目的：分析算法占用計算機資源的情況，對算法做出比較和評價，設計出額更好的算法算法的時間復雜性與問題的規(guī)模相關，是問題大小n的函數(shù)。因此可以用T(n)的數(shù)量級(階)評價算法。時間復雜度T(n)的數(shù)量級(階)稱為漸進時間復雜性。設算法 執(zhí)行時間為T(n)，如果存在T()*，使得：lim丁()

2、T( = 0T (n)ns就稱T (n)*為算法的漸進時間復雜性。運行時間的上界：令N為自然數(shù)集合，R+為正實數(shù)集合。函數(shù)f： N-R+，函數(shù)g： N-R+。若存在自 然數(shù)n0和正常數(shù)c，使得對所有的n，n0都有，f (n)Wcg (n)，就稱函數(shù)f (n)的階至多是O (g (n)f (n)的增長最多像g (n)的增長那樣快。這時稱O (g (n)是f (n)的上界。第二章堆可以看做一課完全二叉樹，假設高度為d，具有如下性質(zhì)：所有葉節(jié)點不是處于第d層，就是處于d-1層當dN1時，第d-1層上有2d-1個結(jié)點第d-1層上如果有分支節(jié)點，則這些分支節(jié)點都集中在樹的最左邊每個結(jié)點所存放元素的關鍵字

3、，都大于或者小于它的孩子結(jié)點的關鍵字元素上移操作：Void sift_up(Type H,int i) BOOL done=false;if(i!=1)while(!done&i!=1) if(HiHi/2)swap(Hi,Hi/2);else done=true;i=i/2;元素下移操作void sift_down(Type H,intn,int i)BOOL done=false;if(2*i)=n)while(!done&(i=2*i=n) if(i+1Hi) i=i+1;if(Hi/2Hi) swap(Hi/2,Hi); else done=true;堆的建立1.void make_h

4、eap1(Type A,TypeH,int n)int i,m=0;for(i=0;i=1;i-)sift_down(A,n,i);第四章對于一個規(guī)模為n的問題p(n)，歸納法的思想方法是：基礎步：al是問題p(1)的解。 歸納步：對所有的k，1vkvn，若b是問題p(k)的解，則p(b)是問題p(k+1)的解。其中，p(b)是對 問題的某種運算或處理。遞歸指算法自己調(diào)用自己，相應的算法稱為遞歸算法。遞歸分類：直接遞歸與間接遞歸遞歸本質(zhì)：對原問題的求解可轉(zhuǎn)化為對其性質(zhì)相同的子問題的求解。分治法就是把問題劃分成多個子問題來進行處理，這些子問題互相獨立，在結(jié)構上和原來的問題一樣， 但在規(guī)模上比原來

5、的小。第5章貪婪法解決問題時，并不能保證它能找到最優(yōu)解。但是，當問題滿足下面兩個性質(zhì)時，貪婪法可以找 到問題的最優(yōu)解。1.1貪婪選擇性質(zhì)1.2最優(yōu)子結(jié)構性質(zhì)貪婪法設計思想：類似于登山法，一步步向前推進，從某一個初始狀態(tài)出發(fā)，根據(jù)當前局部最優(yōu)而不是 全局最優(yōu)策略，以滿足約束條件，使目標函數(shù)的值增加最快或者最慢為準則，選擇一個能夠最快達到要求 的輸入元素，以便盡快構成問題的可行解算法思想：S=u，T=V-u0對T中的所有頂點x，如果u到x存在邊，置du,x=cu,x；否則置du,x=8。然后對T中的所有頂點x，尋找du,x最小的頂點t，即/ = mind |x g T則du,t就是頂點t到頂點u的

6、最短距離。同時頂點t也是篥合T中的所有頂點中距離u最近的頂點。把頂 點t從T中刪去，并入、。接著對T中與t相鄰接的所有頂點x，更新du,x的值d = mind , d + c u, xu, x u ,tt, x克魯斯卡爾算法算法思想：避環(huán)法。圖的所有頂點作為孤立頂點，構成一個只有根結(jié)點的樹，這些樹構 成一個森林To所有的邊按權的非降順序排列，構成邊集的一個非降序列，從邊集中取出權最小的一條邊， 該邊加入森林T，不構成回路，就加入森林否則放棄它，兩種情況下，都把它從邊集中刪去。重復這個過 程直到n-1條邊都放到森林中，就構成了最小生成樹。普里姆算法算法思想：類似于求最短路徑的狄斯奎諾算法，IJ構

7、成的便是ei,j，權值用cij表示，T是 最小花費生成樹的邊集，兩個點集S和N，令T=q,S=0,N=V-S，進行貪婪選擇的時候選取iSJN， 并且使cij最小的i和j，S中加入J,N中除去j，重復上述過程直到N為空，或者找到n-1條邊為止。動態(tài)規(guī)劃的思想方法：對問題進行全面的規(guī)劃處理，彌補貪婪法局部最優(yōu)的缺點。動態(tài)規(guī)劃最優(yōu)決策原理：將活動過程劃分為若干個階段，每一階段決策依賴于前一階段的狀態(tài)，由決策所 采取的動作使狀態(tài)發(fā)生轉(zhuǎn)移，成為下一階段的決策依據(jù)。即每一階段的策略會有改變。最優(yōu)性原理：解決這類問題多階段決策特性，無論過程的初始狀態(tài)和初始決策如何，其余決策必須相對初 始決策所產(chǎn)生的狀態(tài)，構

8、成一個最優(yōu)決策序列。一、分支與限界法基本思想:1、在e _結(jié)點估算沿著它的各兒子結(jié)點搜索時，目標函數(shù)可能取得的“界”，2、把兒子結(jié)點和目標函數(shù)可能取得的“界”，保存在優(yōu)先隊列或堆中，3、從隊列或堆中選取“界”最大或最小的e_結(jié)點向下搜索，直到葉子結(jié)點，4、若葉子結(jié)點的目標函數(shù)的值，是結(jié)點表中的最大值或最小值，則沿葉子結(jié)點到根結(jié)點的路徑所確 定的解，就是問題的最優(yōu)解，由該葉子結(jié)點所確定的目標函數(shù)的值，就是解這個問題所得到的最大值或最 小值二、狀態(tài)空間樹結(jié)點總數(shù)為：1+3+9+27+81+243=364。而在搜索過程中所訪問的結(jié)點數(shù)只有14個。(a)1.漢諾塔：void move(int n,ch

9、ar a,char b,char c)if(n=1)printf(t%c-%cn,a,c);elsemove(n-1,a,c,b);printf(t%c-%cn,a,c);move(n-1,b,a,c);main()int n;printf(請輸入要移動的塊數(shù)：)；scanf(%d,&n);move(n,a,b*,c,);getch();4.分治法的實際步驟：divide-and-conquer(P (n)if ( n = n0)return adhoc(P (n);else divide P into smaller subinstancesP1,P2,.,Pk；for (i=1,i=k,i

10、+) yi=divide-and-conquer(Pi);return merge(y1,.,yk);zl 由劃分步、治理步、組合步3個步驟組 成。2.輸入：背包載重量M,存放n個物體的價值p、及重量w 信息的數(shù)組instance輸出：n個物體被裝入背包的份量劉,背包中物體的總價值float knapsack_greedy(float M,OBJECT instance,float x,int n)int i;float m,p = 0;for (i=0;in;i+) instancei.v = instancei.p / instancei.w;xi = 0;merge_sort(instance,n);m = M;for (i=0;in;i+) if (instancei.w=m) xi = 1; m -= instancei.w;p += instancei.p;elsexi = m / instancei.w;p += xi * insta