西工大算法復習資料總結材料

1、筆試部分一簡答題(40分)1算法的基本概念、性質(zhì)及其與程序的聯(lián)系與區(qū)別算法：是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令。算法性質(zhì)：輸入-有零個或者多個外部量作為算法的輸入；輸出-算法產(chǎn)生至少一個量最為輸出；確定性：組成算法的每條指令是清晰的、無歧義的；有限性：算法中指令的執(zhí)行次數(shù)有限和執(zhí)行的時間有限。程序：是算法用某種設計語言的具體實現(xiàn)，程序可以不滿足算法的有限性。2大O表示法的含義和漸進時間復雜度(要會計算復雜度)大O表示法：稱一個函數(shù) g(n)是O(f(n)，當且僅當存在常數(shù) c>0和n0>=1 ，對一切 n>n0 均有|g(n)|<=c|f(n)|

2、成立，也稱函數(shù)g(n)以f(n)為界或者稱 g(n)囿于f(n)。記作g(n)=O(f(n)。定義：如果一個問題的規(guī)模是n ,解這一問題的某一算法所需要的時間為T(n),它是n的某一函數(shù)。T(n)稱為這一算法的"時間復雜度"。當輸入量n逐漸加大時，時間復雜度的極限情形稱為算法的“漸近時間復雜度”。3分治法的基本思想是什么分治法的基本思想是：將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各子問題的解合并得到原問題 的解。4回溯算法的基本思想及其一般模式（子集樹+排列樹）基本思想：在包含問題的所有解的解空間樹中，按照

3、深度優(yōu)先搜索的策略，從根結點出發(fā)深度探索解空間樹。當探索到某一結點時，要先判斷該結點是否包含問題的解，如果包含，就從該結點出發(fā)繼續(xù)探索下去，如果該結點不包含問題的解，則逐層向其祖先結點回溯。若用回溯法求問題的所有解時，要回溯到根，且根結點的所有可行的子樹都要已被搜索遍才結 束。而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結束。搜索子集樹的一般模式：void search（i nt m）if(m>n)output。；elseam=0;search(m+1);am=1;search(m+1);搜索排列樹的一般模式：void search(i nt m)/遞歸結束條件/相應的處理（

4、輸出結果）/設置狀態(tài)：0表示不要該物品/遞歸搜索：繼續(xù)確定下一個物品/設置狀態(tài)：1表示要該物品/遞歸搜索：繼續(xù)確定下一個物品if(m>n)/遞歸結束條件output。；/相應的處理(輸出結果)elsefor(i=m;i<=n ;i+)swap(m,i);/ 交換 am和 aiif()if(canplace(m)/如果m處可放置search(m+1); / 搜索下一層swap(m,i);/ 交換 am和 ai(換回來)5動態(tài)規(guī)劃的基本思想、基本步驟、基本要素是什么基本思想：將待求解問題分解成若干子問題，先求解子問題，然后從這些子問題的解得到原問題的解?；静襟E：找出最優(yōu)解的性質(zhì)，并刻

5、畫其結構特征； 遞歸地定義最優(yōu)值； 以自底向上的方式計算出最優(yōu)值； 根據(jù)計算最優(yōu)值時得到的信息，構造最優(yōu)解?；疽兀鹤顑?yōu)子結構性質(zhì)和子問題重疊問題6什么是最優(yōu)子結構性質(zhì)和子問題重疊性質(zhì)最優(yōu)子結構性質(zhì)：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，則稱該問題具有最優(yōu)子結構性質(zhì)（即滿足最優(yōu)化原理）。最優(yōu)子結構性質(zhì)為動態(tài)規(guī)劃算法解決問題提供了重 要線索。子問題重疊性質(zhì)：指在用遞歸演算法自頂向下對問題進行求解時，每次產(chǎn)生的子問題并不總是新問題，有些子問題會被重復計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊 性質(zhì)，對每一個子問題只計算一次， 然后將其計算結果保存在一個表格中，當再次需要計算已經(jīng)計算

6、過的子問題時，只是在表格中簡單地查看一下結果，從而獲得較高的效率。7分治法與動態(tài)規(guī)劃的聯(lián)系與區(qū)別聯(lián)系：基本思想相同，即將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。區(qū)別：適用于動態(tài)規(guī)劃法求解的問題， 經(jīng)分解得到的子問題往往不是相互獨立的。 分治 法子問題被重復計算多次，而動態(tài)規(guī)劃子問題可用一個表來記錄已解決子問題的答案，避免了子問題重復計算的問題。8動態(tài)規(guī)劃的變形（備忘錄方法）與動態(tài)規(guī)劃的聯(lián)系與區(qū)別聯(lián)系：都用表格保存已解決的子問題的答案區(qū)別：備忘錄方法的遞歸方式是自頂向下的，而動態(tài)規(guī)劃的遞歸方式是自底向上的。9分支限界法（廣度優(yōu)先搜索）的基本思想是什么分支限

7、界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。在分支限界法中，每一個活結點只有一次機會成為擴展節(jié)點?；罱Y點一旦成為擴展節(jié)點，就一次性產(chǎn)生所有兒子節(jié)點。在這些兒子節(jié)點中，導致不可行解或?qū)е路亲顑?yōu)解的兒子節(jié)點被舍棄，其余兒子節(jié)點被加入活結點表中。此后，從活結點表中取下一節(jié)點成為當前擴展節(jié)點，并重復上述節(jié)點擴展過程，這個過程一直持續(xù)到找到所需的解或活結點表為空時為止。10. 分支限界法與回溯法的區(qū)別1.搜索方式不同：分支限界法使用廣度優(yōu)先或最小消耗優(yōu)先搜索，而回溯法使用深度優(yōu)先搜索。2主要區(qū)別：在于它們對當前擴展節(jié)點所采用的擴展方式不同。分支限界法：每個節(jié)點只有一次成為活結點

8、的機會回溯法：活結點的所有可行子節(jié)點被遍歷后才被從棧中彈出11. 搜索算法的一般模式搜索算法關鍵要解決好狀態(tài)判重的問題：void search。open表初始化為空；起點加入到 open表；while（ open 表非空）取open表中的一個結點 u;從open表中刪除u;for(對擴展結點u得到的每個新結點vi ）if（vi是目標結點）輸出結果并返回；lf(n otused(vi)vi進入open 表;12. 貪心算法的基本思想、基本步驟及基本要素基本思想：貪心算法總是做出在當前看來是最好的選擇，即貪心算法并不從整體最優(yōu)上加以考慮，所做的選擇只是在某種意義上的局部最優(yōu)選擇，即貪心選擇。基本步

9、驟：從問題的某個初始解出發(fā)； 采用循環(huán)語句，當可以向求解目標前進一步時，就根據(jù)局部最優(yōu)策略，得到一個局部最優(yōu)解縮小問題的規(guī)模； 將所有局部最優(yōu)解綜合起來，得到原問題的解?；疽兀贺澬倪x擇性質(zhì)：指所求問題的整體最優(yōu)解可以通過一系列的局部最優(yōu)的選擇，即貪心選擇來達到。貪心選擇策略必須具備無后效性,即某個狀態(tài)以前的過程不會影響以后的狀態(tài)，只與當前狀態(tài)有關。最優(yōu)子結構性質(zhì)：一個問題的最優(yōu)解包含其子問題的最優(yōu)解。13. 貪心算法與動態(tài)規(guī)劃算法聯(lián)系與區(qū)別聯(lián)系：都要求問題具有最優(yōu)子結構性質(zhì)，即一個問題的最優(yōu)解包含其子問題的最優(yōu)解。區(qū)別：在動態(tài)規(guī)劃算法中， 每步所做的選擇往往是依賴于相關子問題的解，因而只有

10、在解出相關子問題后，才能做出選擇。而在貪心算法中，僅在當前狀態(tài)下做出最好的選擇， 即局部最優(yōu)選擇，然后再去解做出這個選擇后產(chǎn)生的相應的子問題。動態(tài)規(guī)劃算法通常以自底向上方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式做出相機的貪心選擇以簡化問題規(guī)模。二設計題(60分-寫出核心代碼或偽代碼和相關的變量聲明)1用二分查找算法查找某一個元素在線性表中的位置。此問題的輸入是待查元素x和線性表L,輸出為x在L中的位置或者x不在L中的信息。最直接的做法就是一個一個地掃描L的所有元素，直到找到x為止。這種方法對于有n個元素的線性表在最壞的情況下需要n次比較。一般來說，若沒有其他的附加信息，

11、 在有n個元素的線性表中查找一個元素在最壞情況都需要n次比較?？紤]最簡單的情況，該線性表為有序表，設其按照主鍵的遞增順序從小到大排列。核心偽代碼：fun ctio n Bin arySearch(L,a,b,x)beginif a>b the n retur n -1else begi nm=(a+b)div 2;if x=Lm the n retur n (m)else if x>Lmthe n return Bin arySearch(L,m+1,b,x);elsereturn Bin arySearch(L,a,m-1,x); en d;en d;2請采用快速排序算法為下列數(shù)

12、字排序，并寫出最終結果(21 25 49 25* 16 08)快速排序的基本思想：選定一個基準值元素，對帶排序的序列進行分割，分割之后的序 列一部分小于基準值元素，另一部分大于基準值元素，再對這兩個分割好的子序列進行上述 的過程。void swap(i nt a,i nt b) int t;t =a ;a =b ;b =t ;int Partiti on (i nt arr,i nt low,i nt high)in t pivot=arrlow;采用子序列的第一個元素作為基準元素while (low < high)/從后往前在后半部分中尋找第一個小于基準元素的元素while (low

13、< high && arrhigh >= pivot)-high;/將這個比樞紐元素小的元素交換到前半部分swap(arrlow, arrhigh);/從前往后在前半部分中尋找第一個大于基準元素的元素while (low <high &&arr low <=pivot )+low ;/將這個基準元素大的元素交換到后半部分swap (arr low ,arr high );return low ;/ 返回基準元素所在的位置void QuickSort(i nt a,i nt low,i nt high)if (low <high )i

14、nt n=Partiti on (a ,low ,high );QuickSort (a ,low ,n );QuickSort (a ,n+1,high );3寫出對下面的序列進行歸并排序的過程(從小到大)(63 14 9 98 23 48 15 70)核心代碼：void MergeSort(i nt low,i nt high)if(low>=high)每個子列表中剩下一個元素時停止return;/將列表劃分成相等的兩個子列表，若有奇數(shù)個元素，則在左邊子列表大于右邊子列 表elseint mid=(low+high)/2;MergeSort(low,mid);遞歸劃分子列表Merge

15、Sort(mid+1,high);/遞歸劃分子列表/新建一個數(shù)組b用于存放歸并的元素in t b=new in thigh-low+1;/兩個子列表進行排序歸并，直到兩個子列表中的一個結束for(i nt i=low,j=mid+1,k=low;i<=mid&&j<=high;k+)if(arri<=arrj)bk=arri;elsebk=arrj;j+； for(;j<=high;j+,k+)/如果第二個子列表中仍然有元素，則追加到新列表bk=arrj; for(;i<=mid;i+,k+)/如果第一個子列表中仍然有元素，則追加到新列表bk=ar

16、ri;for(i nt z=0;z<high-low+1;z+)/將排序的數(shù)組b的所有元素復制到原始數(shù)組arr中arrz=bz;4裝載問題問題關鍵在于：首先將第一艘船盡可能裝滿且c1<最大值max，然后將剩余的部分裝上第二艘船c2，若:總重量-c1<c2則能裝入兩艘船。關鍵代碼：int c1,c2 ,n ,w10;int weight=O,max=O;void search(i nt m)if(m=n)if(weight<=c1) if(weight>max) max=weight;elseif(weight+=wm<=c1) weight+=wm;sear

17、ch(m+1);weight-=wmsearch(m+1);5.01-背包問題(回溯法)關鍵代碼：int n,c;int w1000,v1000;int a1000,max=0;void search(i nt m)if(m>=n)checkmax();elseam=0;search(m+1);am=1;search(m+1)void checkmax()int i;int weight=0,value=0;for(i=0;i <n ;i+)if(ai=1)weight+=wi; value+=vi; if(weight<=c) if(value>max) max=va

18、lue;6循環(huán)賽日程表(遞歸與分治)設計思想：按分治策略，可以將所有選手對分為兩半，n個選手的比賽日程表就可以通過為n/2個選手設計的比賽日程表來決定。遞歸地用這種一分為二的策略對選手進行分割， 直至只剩下兩個選手時，比賽日程表的指定就很簡單了。核心代碼：int N = 1;void UpRightCopy(i nt n, int array)for(i nt i = 0; i < n; i+)for(i nt j = n; j < 2 * n ;j+)arrayN * i + j = 2 * n + 1 -arrayN * i + 2 * n - 1 - j;void Down

19、RightCopy(i nt n, int array)for(i nt i = n; i < 2 * n; i+)for (int j = n; j < 2 * n ;j+)arrayN * i + j = arrayN * (i - n) + j - n;void LeftDow nCopy(i nt n, int array)for (i nt i = n; i < 2 * n; i+)for (int j = 0; j < n ;j+)arrayN * i + j = arrayN * (i - n) + j + n;void turn (i nt n, int

20、 array)if(n = 1)array0 = 1;elseturn(n / 2, array);Dow nRightCopy( n / 2, array);UpRightCopy(n / 2, array);LeftDow nCopy (n / 2, array);7最長公共子序列核心代碼：char a201,b201;int n1, n2;void search()int List201201;for(i nt i=0;i<=n 1;i+)ListiO=O;for(i nt j=O;j<=n 2;j+)ListOj=O;for(i nt i=1;i<=n 1;i+)fo

21、r(i nt j=1;j<=n 2;j+)if(ai-1=bj-1)Listi j=Listi-1j-1+1;elseif(Listi-1 j>Listij-1)Listi j=Listi-1j;elseListi j=Listi j-1;8矩陣連乘問題核心代碼：int n;in t p11;void a1111,temp;for(i nt i=1;i<=n ;i+)aii=O；for(i nt d=1;d<=n _1;d+)for(i nt i;i<=n_ d;i+)int j=i+d;aij=0+ai+1j+pi-1*pi*pj;for(

22、i nt k=i+1;k<j;k+)temp=aik+ak+1j+pi-1*pk*pj;if(temp<ai j)ai j=temp;9用備忘錄算法實現(xiàn)計算Fibo nacci數(shù)列核心代碼：int Fib(i nt n)int result n =0,0,.,0;int f1,f2;if(n <2)return n;if(result n-1=0)f1=Fib( n-1);elsef1=result n-1;if(result n-2=0)f2=Fib( n-2);elsef2=result n-2; result n=f1+f2; return (f1+f2);設計一個的高

23、效算法實現(xiàn)Fibo nacci數(shù)列Version 1(效率最差)1. long Fibonacci( int n)2. 3. if (n = 0)4. return 0;5. else if (n = 1)6. return 1;7. else if (n > 1)8. return Fibonacci (n -1) + Fibonacci (n -2);9. else10. return -1;11. Version2(效率其次)1. long Fibonacci2( int n)2. 3. if (n = 0)4. return 0;5. else if (n =1)6. retur

24、n 1;7. else if (n > 1)8. 9.9. if (tempResultn !=0)10. return tempResultn;11. else12. 13. tempResultn = Fibonacci2 (n -1) + Fibonacci2 (n -15.return tempResultn;16.17.18.Version 3（效率最高-放棄遞歸用循環(huán)實現(xiàn)）1.long Fibonacci3( int n)2.3.long * temp = new long n + 1;4.5.temp 0 = 0;6.7.if (n > 0)8.temp 1 = 1;

25、9.10.for (int i = 2; i <= n; +i)11.12.tempi = tempi -1 + tempi -2;13.14.15.long result = tempn;17. delete temp;18.18. return result;19. 10. 活動安排問題問題關鍵在于：理解什么是相容性活動！ 若區(qū)間s1,f1）與區(qū)間s2,f2）不相交，則稱活動 1與活動2是相容的，即s1>=f2或s2>=f1時，活動1與活動2相容。（區(qū)間表示的是活 動的起始時間s和結束時間f）核心代碼：struct actio nint begi n;int en d;a

26、1000;int n;/n表示活動的總數(shù)int sum=0;/sum表示能參加的活動的數(shù)量void search。sum=1;int temp=aO.e nd;/temp 表示第一個活動結束的時間 for(i nt i=1;i< n;i+)if(ai.begi n>=temp)sum+;temp=ai.e nd;void selecti on _sort()for(i nt i=0;i< n;i+)int k=i;for(i nt j=i+1;j <n ;j+)if(a j.end<ak.end)k=j;struct actio n temp=ai;ai=ak;a

27、k=temp;11. 最優(yōu)服務次序問題思路是最短服務時間優(yōu)先，先將服務時間排序，然后注意后面的等待服務時間既包括等 待部分，也包括服務部分。貪心策略：對服務時間最短的顧客先服務的貪心選擇策略。首先對需要服務時間最短的顧客進行服務，即做完第一次選擇后，原問題T變成了需對n-1個顧客服務的新問題T'。新問題和原問題相同，只是問題規(guī)模由n減小為n-1?；诖朔N選擇策略，對新問題T'，選擇n-1顧客中選擇服務時間最短的先進行服務，如此進行下去，直至所有服務都完成為 止。每個客戶需要的等待時間為：T(1)=t(1);T( 2)=t(1)+t(2);T(n )=t(1)+t (2)+.+t

28、( n);總等待時間為：T=n *t(1)+( n-1)*t (2)+( n-2)*t(3)+.+( n+1-i)*t(i)+.+2*t( n-1)+1*t (n)注：st是服務數(shù)組，Stj為第j個隊列上的某一個顧客的等待時間；su是求和數(shù)組,suj的值為第j個隊列上所有顧客的等待時間；第一種代碼：1. double greedy(vector< int >x, int s)2. 3. vector< int >st(s+1,0);4.vectorv int >su(s+1,0);5.int n=x.size();6.sort(x.begi n( ),x.e nd

29、();7.int i=0,j=0;8.while (i<n)9.st j+=xi;10.suj+=stj;11.i+;12.j+;13.if (j=s)j=0;14.15.double t=0;16.for (i=0;i<s;i+)17.t+=sui;18.t/=n;19.return t;20.第二種方法:1. int x10000;2. int main()4.int n;5.cin >> n;6.int temp;7.for (int j = 0; j< n; j+)8.9.scanf( "%d"，&xj);10.11.sort(

30、x,x+ n);12.for (int i = 1; i < n; i+)13.xi+=xi-1;14.double t = 0;15.for (int i = 0; i < n; i+)16.t+=xi;17.t/=n;18.cout.setf(ios:fixed);19.cout << setprecisi on(2) << t << en dl;20.system( "pause");21.return 0;22. 12. 最短路徑問題Dijkstra算法是解單源最短路徑問題的貪心算法。其基本思想是，設置頂點集合S并不斷

31、地作貪心選擇來擴充這個集合。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。初始時，S中僅含有源。設u是G的某一個頂點，把 從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當前每個頂點所對應的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數(shù)組 dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其他頂點之間的最短路徑長度。Dijkstra算法可描述如下，其中輸入帶權有向圖是 G=(V,E) , V=1,2,，n，頂點v是源。 c是一個二維數(shù)組，cij表示邊(i,j)的權。當(

32、i,j)不屬于E時，cij是一個大數(shù)。disti表 示當前從源到頂點i的最短特殊路徑長度。 在Dijkstra算法中做貪心選擇時， 實際上是考慮 當S添加u之后，可能出現(xiàn)一條到頂點的新的特殊路，如果這條新特殊路是先經(jīng)過老的S到達頂點u,然后從u經(jīng)過一條邊直接到達頂點 i,則這種路的最短長度是 distu+cui。 如果distu+cui<disti，則需要更新 disti的值。步驟如下：(1) 用帶權的鄰接矩陣 c來表示帶權有向圖，cij表示弧<vi,vj>上的權值。設S為已 知最短路徑的終點的集合，它的初始狀態(tài)為空集。從源點 v經(jīng)過S到圖上其余各點vi的當前 最短路徑長度的

33、初值為：disti=cvi, vi 屬于V.(2) 選擇vu,使得distu=Mindisti | vi 屬于V-S,vj就是長度最短的最短路徑的終點。 令 S=S U u.(3) 修改從v到集合V-S上任一頂點vi的當前最短路徑長度：如果distu+cuj< distj 則修改 distj= distu+cuj.(4) 重復操作(2),(3)共n-1次.1. con st int N = 5;2. const int M = 1000;3. template < class Type4. void Dijkstra( int n, int v,Type dist, int pre

34、v,Type cN+1);5. void Traceback( int v,int i,int prev); / 輸出最短路徑 v 源點，i 終點6. int main()7. 8. int v = 1; / 源點為 19. int distN+1,prevN+1,cN+1N+1;10.10. cout<<"有向圖權的矩陣為："<<e ndl;11. for (int i=1; i<=N; i+)12. 13. for (int j=1; j<=N; j+)14. 15. fin>>cij;16. cout<<ci

35、j<<""17. 18. cout<<e ndl;19. 20. Dijkstra(N,v,dist,prev,c);21. for (int i=2; i<=N; i+)23.24.cout<< "源點1到點"<<i<< "的最短路徑長度為："<<disti<<"，其路徑為”；25.Traceback(1,i,prev);26.cout<<e ndl;27.28.29.return 0;30.31.template <

36、; class Type>32.void Dijkstra( int n, int v,Type dist, int prev,Type cN+1)33.34.bool sN+1;35.for (int i=1; i<=n; i+)36.37.disti = cvi;disti表示當前從源到頂點i的最短特殊路徑長度38.si = false ;39.if (disti = M)40.41.previ = 0;/記錄從源到頂點i的最短路徑i的前一個頂點42.43.else44.標準實用0.61

37、.5.66.文案大全previ = v;distv = 0;sv = true ;for (int i=1; i<n; i+)int temp = M;int u = v; / 上一頂點/取出V-S中具有最短特殊路徑長度的頂點ufor (int j=1; j<=n; j+)if (!s j) && (dist j<temp)u = j;temp = distj;su = true ;/根據(jù)作出的貪心選擇更新Dist值for (int j=1; j<=n; j+)標準實用6.77.

38、7.88.文案大全Type n ewdist = distu + cuj;if (n ewdist < distj)dist j = n ewdist;prevj = u;/輸出最短路徑v源點，i終點void Traceback( int v,int i,int prev)if (v = i)cout<<i;return ;Traceback(v,previ,prev);cout<< "->" <<i;89. 13. 霍夫曼編碼問題(要求畫出霍夫曼樹)哈夫曼提出構造最優(yōu)前

39、綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。其構造步驟 如下:(1) 哈夫曼算法以自底向上的方式構造表示最優(yōu)前綴碼的二叉樹T。(2) 算法以|C|個葉結點開始，執(zhí)行|C| 1次的“合并”運算后產(chǎn)生最終所要求的樹T。(3) 假設編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊列 Q用在貪心選擇時有效地確定算法當前要合并的2棵具有最小頻率的樹。一旦2棵具有最小頻率的樹合并后，產(chǎn)生一棵新的樹，其頻率為合并的2棵樹的頻率之和，并將新樹插入優(yōu)先隊列Q。經(jīng)過n 1次的合并后，優(yōu)先隊列中只剩下一棵樹，即所要求的樹To構造過程如圖所示:算法中用到的類定義:1. template < cl

40、ass Type2. class Huffman3. 4. friendBinaryTree< int > HuffmanTree(Type,int );5. public :6. operator Type()const7. 8. return weight;9. 10. /private:11. BinaryTree<int > tree;12. Type weight;13. ;算法HuffmanTree 描述如下：1. template < class Type>2. BinaryTree< int > HuffmanTree(Type

41、f,int n)3. 4. /生成單節(jié)點樹5. Huffman<Type> *w = new Huffman<Type>n+1;6. BinaryTree< int > z,zero;8.29.for (int i=1; i<=n; i+)乙M akeTree(i,zero,zero);wi.weight = fi;wi.tree = z;/建優(yōu)先隊列MinH eap<Huffma n< Type>> Q(n

42、);for (int i=1; i<=n; i+) Q.lnsert(wi);/反復合并最小頻率樹Huffma n< Type> x,y;for (int i=1; i<n; i+)x = Q.RemoveMi n();y = Q.RemoveMi n();z.MakeTree(O,x.tree,y.tree);x.weight += y.weight;x.tree = z;Q.l nsert(x);x = Q.RemoveMi n();delete w;30. return x.tree;31. 32.14. 用貪心算法解決搬桌子問題關鍵思想：把課桌按起點從小到大排序

43、，每次都是搬離當前位置最近的課桌。算法代碼：#in clude<stdio.h>int mai n()structint start;int end;a100;int i,j;int n,m,min,nu m,temp,used100=0;scan f("%d%d",&m,&n);for(i=0;i< n;i+)scan f("%d%d",&ai.start,&ai.e nd);/ sort(a,n);/按start從小到大對數(shù)組 a排序mi n=0;num=0;while( num<n)temp=

44、O;for(i=0;i <n ;i+)if(usedi=O&&ai.start>=temp)temp=ai.e nd;usedi=1;nu m+;mi n+;prin tf("%d",mi n);15. 八數(shù)碼難題核心代碼：1 #in clude <stdio.h>2 #in clude<memory.h>9種狀態(tài)3 #define len 362888/狀態(tài)共有 362880 種，數(shù)組稍微開大點4 #define le 9/ 每種狀態(tài)有9個數(shù)據(jù)，也可看為每種狀態(tài)下又有5 typedef int statele;/狀態(tài)：表

45、示九個格子6 state stlen,goal;/st為狀態(tài)數(shù)組 goal為目標數(shù)組/dis為每7 int dislen,factle,headlen,vislen,der42= -1,0,1,0,0,-1,0,1;8種狀態(tài)的已走的步驟 /der為方向：上，下，左，右9 void encode()/ 編碼10int i;1 for (i=fact0=1; i<le; i+)1 facti=facti-1*i;12 int decode( int s)/ 解碼13 int i,j,code,cnt;1 for (i=code=0; i<le; i+)4 1 for (cnt=O,j=

46、i+1; j<le; j+)5 if (stsi>stsj)1 cn t+;6 code+=cnt*fact8-i;1 7 if (viscode)1 return 0;8 else1 retur n viscode=1;9 2int bfs()0 2 int front=1,rear=2,i,x,y,z,nx,ny,nz;1 en code();2 while (front<rear)2 2 state & s=stfro nt;3 if (memcmp (s,goal, sizeof (s)=0)/ 對 front 狀態(tài)和目標狀態(tài)進行比較2 return fron

47、 t;4 for (i=0; i<le; i+)/找到為0的元素，即空的那個格子，這里選取空2的那個格子是應為相對于1,2,3,8這樣的數(shù)據(jù)，0作為判斷依據(jù)簡單于用數(shù)據(jù)作為判斷5依據(jù)2 if (si=0) break ;6 x=i/3;2 y=i%3;7 z=i;/記錄空的格子的行標，列表，和所在位置，這里的位置按照從左到右2從上到下依次遞增8 for (i=0; i<4; i+)/按照上，下，左，右四個方向進行搜索2 93 nx=x+deriO;0n y=y+deri1;3 nz=nx*3+ny;1 if (nx>=0&&n x<3&&

48、n y>=0&&n y<3)3 2 state & t=strear;3 memcpy (&t,&s, sizeof (s);/記錄此時的狀態(tài)即九個格子的數(shù)值3 tz=s nz;3 tn z=sz;4 disrear=disfr on t+1;3 if (decode(rear)/判斷strear這種狀態(tài)是否已經(jīng)出現(xiàn)過5 rear+;3 6 3fron t+;7 3 return 0;8 3int main( void )4 int i,oj;0 for (i=0; i<le; i+)scanf (”d"，&st1i)

49、;/按從左到右從上到下的順序存儲數(shù)據(jù)for (i=0; i<le; i+)scanf ("%d"，&goali);oj=bfs();if (oj)printf ("%dn" ,disoj);elseputs ("Impossible" );4142434445464748495051return 0;52535455565758596061626364656667686916.圖的M著色問題考慮所有的圖，討論在至多使用m種顏色的情況下，可對一給定的圖著色的所有不同方法。通過回溯的方法，不斷的為每一個節(jié)點著色，在前面n-1

50、個節(jié)點都合法的著色之后，開始對第n個節(jié)點進行著色，這時候枚舉可用的m個顏色，通過和第n個節(jié)點相鄰的節(jié)點的顏色，來判斷這個顏色是否合法，如果找到那么一種顏色使得第n個節(jié)點能夠著色，那么說明m種顏色的方案是可行的。用m種顏色為無向圖 G=(V,E)著色，其中，V的頂點個數(shù)為n,可以用一個n元組 x=(x1,x2,xn)來描述圖的一種可能著色，其中， xi 1,2,m , (1 <i <n)表示賦予頂點 i的顏色。例如，5元組(1,2, 2, 3, 1)表示對具有5個頂點的無向圖(a)的一種著色，頂點 A著顏色1，頂點B著顏色2，頂點C著顏色2，如此等等。如果在n元組X中，所有相鄰 頂點都不會著相同顏色，就稱此 n元組為可行解，否則為無效解。容易看出，每個頂點可 著顏色有m種選擇，n個頂點就有mn種不同的著色方案，問題的解空間是一棵高度為n的完全m叉樹，這里樹高度的定義為從根節(jié)點到葉子節(jié)點的路徑的長度。每個分支結點， 都有m個兒子結點。最底層有mn個葉子結點。例如，表示用3種顏色為3個頂點的圖著色的狀態(tài)空間樹。如圖所示，對第i (i>=1 )層上的每個頂點，從其父節(jié)點到該節(jié)點的邊上的標號表示頂點i著色的顏色編號。1. #i nclude "stdafx.h"2. #i nclude <iostream>3.