西工大算法復(fù)習(xí)資料總結(jié)(最終修訂版)

1、筆試部分一簡答題(40分)1. 算法的基本概念、性質(zhì)及其與程序的聯(lián)系與區(qū)別算法：是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令。算法性質(zhì)：輸入-有零個或者多個外部量作為算法的輸入；輸出-算法產(chǎn)生至少一個量最為輸出；確定性：組成算法的每條指令是清晰的、無歧義的；有限性：算法中指令的執(zhí)行次數(shù)有限和執(zhí)行的時間有限。程序：是算法用某種設(shè)計語言的具體實現(xiàn)，程序可以不滿足算法的有限性。2. 大O表示法的含義和漸進時間復(fù)雜度(要會計算復(fù)雜度)大O表示法：稱一個函數(shù)g(n)是O(f(n)，當(dāng)且僅當(dāng)存在常數(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)稱為這一算法的"時間復(fù)雜度"。當(dāng)輸入量n逐漸加大時，時間復(fù)雜度的極限情形稱為算法的“漸近時間復(fù)雜度”。3. 分治法的基本思想是什么分治法的基本思想是：將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問 題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。4. 回溯算法的基本思想及其一般模式(子集樹+排列樹)基本思想：在包含問題的所有解的解空間

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

4、m)遞歸結(jié)束條件 相應(yīng)的處理(輸出結(jié)果)設(shè)置狀態(tài)：0表示不要該物品遞歸搜索：繼續(xù)確定下一個物品設(shè)置狀態(tài)：1表示要該物品遞歸搜索：繼續(xù)確定下一個物品5.動態(tài)規(guī)劃的基本思想、基本步驟、基本要素是什么基本思想： 到原問題的解?；静襟E：將待求解問題分解成若干子問題，先求解子問題，然后從這些子問題的解得 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征； 遞歸地定義最優(yōu)值； 以自底向上的方式計算出最優(yōu)值； 根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解?；疽兀鹤顑?yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊問題if(m> n)/output。；/else遞歸結(jié)束條件 相應(yīng)的處理（輸出結(jié)果）for(i=m;i<=n ;i+)swa

5、p(m,i); /if()if(ca nplace(m) /search(m+1); /swap(m,i); /交換am和ai如果m處可放置搜索下一層交換am和ai（換回來）6什么是最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，則稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（即滿足最優(yōu)化原理）。最優(yōu)子結(jié)構(gòu)性質(zhì)為動態(tài)規(guī)劃算法解決問題提供了重 要線索。子問題重疊性質(zhì)：指在用遞歸演算法自頂向下對問題進行求解時，每次產(chǎn)生的子問題并不總是新問題，有些子問題會被重復(fù)計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊 性質(zhì)，對每一個子問題只計算一次， 然后將其計算結(jié)果保存在一個表格

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

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

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

9、在某種意義上的局部最優(yōu)選擇，即貪心選擇?；静襟E：從問題的某個初始解出發(fā)； 采用循環(huán)語句，當(dāng)可以向求解目標前進一步時，就根據(jù)局部最優(yōu)策略，得到一個局部最優(yōu)解縮小問題的規(guī)模； 將所有局部最優(yōu)解綜合起來，得到原問題的解。基本要素：貪心選擇性質(zhì)：指所求問題的整體最優(yōu)解可以通過一系列的局部最優(yōu)的選擇，即貪心選擇來達到。貪心選擇策略必須具備無后效性，即某個狀態(tài)以前的過程不會影響以后的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。最優(yōu)子結(jié)構(gòu)性質(zhì)：一個問題的最優(yōu)解包含其子問題的最優(yōu)解。13. 貪心算法與動態(tài)規(guī)劃算法聯(lián)系與區(qū)別聯(lián)系：都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，即一個問題的最優(yōu)解包含其子問題的最優(yōu)解。區(qū)別：在動態(tài)規(guī)劃算法中， 每步

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

11、壞的情況下需要n次比較。一般來說，若沒有其他的附加信息，在有n個元素的線性表中查找一個元素在最壞情況都需要n次比較?？紤]最簡單的情況，該線性表為有序表，設(shè)其按照主鍵的遞增順序從小到大排列。核心偽代碼：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

12、);en d;en d;2. 請采用快速排序算法為下列數(shù)字排序，并寫出最終結(jié)果(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)/從后往前在后半

13、部分中尋找第一個小于基準元素的元素while (low < 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

14、nt high)if (low <high )int 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;

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

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

17、weight+=wm<=c1)weight+=wm; search(m+1);weight-=wm search(m+1);5.01-背包問題(回溯法)關(guān)鍵代碼：int n,c; int w1000,v1000; int a1000,max=0;void search(i nt m) if(m>=n) checkmax();else am=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

18、+=vi; if(weight<=c) if(value>max) max=value;6. 循環(huán)賽日程表(遞歸與分治)設(shè)計思想：按分治策略，可以將所有選手對分為兩半，n個選手的比賽日程表就可以通過為n/2個選手設(shè)計的比賽日程表來決定。遞歸地用這種一分為二的策略對選手進行分割， 直至只剩下兩個選手時，比賽日程表的指定就很簡單了。核心代碼：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 =

19、 2 * n + 1 -arrayN * i + 2 * n - 1 - j;void Down 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 (int i = n; i < 2 * n; i+)for (int j = 0; j < n ;j+)arrayN * i + j =

20、 arrayN * (i - n) + j + n;void turn (i nt n, int 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=0;

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

22、;=n_ d;i+)int j=i+d;aij=0+ai+1j+pi-1*pi*pj;for(i nt k=i+1;k<j;k+) temp=aik+ak+1j+pi-1*pk*pj; if(temp<aij)aij=temp;9. 用備忘錄算法實現(xiàn)計算 Fibonacci數(shù)列核心代碼：int Fib(i nt n)int resultn=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=

23、result n-2; result n=f1+f2; return (f1+f2);設(shè)計一個的高效算法實現(xiàn)Fibo nacci數(shù)列Version 1（效率最差）1.2.long Fibonacci( int n)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

24、.return 0;5.else if (n = 1)6.return 1;7.else if (n >1)8.9.10.if (tempResultn!= 0)11.return tempResultn;12.else13.14.tempResultn = Fibonacci2 (n1) + Fibonacci2 (n - 2);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.temp0 = 0;

25、6.7.if (n > 0)8.temp1 = 1;9.10.for (int i = 2; i <= n; +i)11.12.tempi = tempi - 1 + tempi - 2;13.14.15.long result = tempn;16.17.delete temp;18.19.return result;20.10. 活動安排問題問題關(guān)鍵在于：理解什么是相容性活動！ 若區(qū)間s1,f1）與區(qū)間s2,f2）不相交，則稱活 動1與活動2是相容的，即s1>=f2或s2>=f1時，活動1與活動2相容。（區(qū)間表示的是活 動的起始時間s和結(jié)束時間f ）核心代碼：str

26、uct actio nint begi n; int en d;a1000;int n;/n表示活動的總數(shù)int sum=0;/sum表示能參加的活動的數(shù)量void search。sum=1;int temp=aO.e nd;/temp表示第一個活動結(jié)束的時間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(aj.e nd<ak.e nd)k=

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

28、)=t(1)+t(2);T(n )=t(1)+t(2)+.+t (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是服務(wù)數(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.intn=x.siz

29、e();6.sort(x.begi n( ),x.e nd();7.int i=0,j=0;8.while (i<n)9.stj+=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.intx10000;2.intmain ()3.4.int n;5.cin >> n;6.int temp;7.for (int j = 0; j< n;j+)8.9.scan f("%d&

30、quot;, &xj);10.11.sort(x,x+ n);12.for (inti = 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 << setprecision(2)<< t << endl;20.system("pause");21.return 0;22.12.最短路徑問題Dijkstra算法是解單源最短路徑問題的貪心算法

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

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

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

34、ack( int v, int i, intprev); 輸出最短路徑v 源點，i終點6. int mai n()7. 8.int v =;1;/源點為19.int distN+1,prevN+1,cN+1N+1;10.11.cout<<"有向圖權(quán)的矩陣為："<<e ndl;12.for (inti=1;i<=N;i+)13.14.for(int j=1;j<=N;j+)15.16.fin >>cij;17.cout<<cij<<"II.518.19.cout<<e ndl;20.

35、21.Dijkstra(N,v,dist,prev,c);22.for (int i=2;i<=N;i+)23.24.cout<<"源點1到點"<<i<<"的最短路徑長度為："<<disti<<",其路徑為25.JTraceback(1,i,prev);26.cout<<e ndl;27.28.29.return 0;30.31.template <class Type>32.void Dijkstra( int n, int v,Type dist, i

36、nt prev,Type cN+1)33.34.bool sN+1;35.for (int i=1;i<=n;i+)36.37.disti- cvi;/disti表示當(dāng)前從源到頂點i的最短特殊路徑長度38.si - false ;39.if (disti- M)40.41.previ - 0;/記錄從源到頂點i的最短路徑i的前一個頂點42.43.else44.45.previ - v;46.47.48.distv- 0;49.sv - true ;50.for (int i-1; i<n; i+)51.52.int temp - M;53.int u - v;/ 上一頂點54./取

37、出V-S中具有最短特殊路徑長度的頂點u55.for (int j-1;j<-n;j+)56.57.if (!sj)&& (distj<temp)58.59.u - j;60.temp=distj;61.62.63.su=true ;64./根據(jù)作出的貪心選擇更新Dist 值65.for (intj=1;j<=n; j+)66.67.if(!sj)&& (cuj<M)68.69.Typen ewdist=distu+ cuj;70.if (newdist<distj)71.72.distj=n ewdist;73.prevj=u;74

38、.8.79./輸出最短路徑v源點，i終點80.voidTraceback(int v, inti, intprev)81.82.if(v = i)83.84.cout<<i;85.return586.87.Traceback(v,previ,prev);88.cout<<"->"<<i;89.13.霍夫曼編碼問題(要求畫出霍夫曼樹)哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。其構(gòu)造步驟如下：(1) 哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹T。(2) 算法以|C|個葉結(jié)點開始，

39、執(zhí)行|C| 1次的“合并”運算后產(chǎn)生最終所要求的 樹To(3) 假設(shè)編碼字符集中每一字符c的頻率是f(c) o以f為鍵值的優(yōu)先隊列 Q用在貪心選擇時有效地確定算法當(dāng)前要合并的2棵具有最小頻率的樹。一旦2棵具有最小頻率的樹合并后，產(chǎn)生一棵新的樹，其頻率為合并的2棵樹的頻率之和，并將新樹插入優(yōu)先隊列Q。經(jīng)過n 1次的合并后，優(yōu)先隊列中只剩下一棵樹，即所要求的樹To構(gòu)造過程如圖所示:|f訂卜釘呼呼|卩1 |11 錨EHE2算法中用到的類定義:1.template <class Type>2.class Huffma n3.4.friendBinaryTree< int > H

40、uffmanTree(Type, int );5.public :6.operator Type() const7.8.return weight;9.10./private:11.BinaryTree< int > tree;12.Type weight;13.;算法HuffmanTree描述如下：11. template <class Type>2. BinaryTree< int > HuffmanTree(Type f, int n)3. 4. /生成單節(jié)點樹5. Huffman<Type> *w = new Huffman<Typ

41、e>n+1;6. BinaryTree< int > z,zero;8.for (int i=1; i<=n;i+)9.10.乙M akeTree(i,zero,zero);11.wi.weight=fi;12.wi.tree=z;13.14./建優(yōu)先隊列15.MinHeap<Huffman<Type>> Q(n);16.for (int i=1;i<=n;i+) Q.lnsert(wi);17./反復(fù)合并最小頻率樹18.Huffman<Type> x,y;19.for (int i=1; i<n; i+)20.21.x

42、= Q.RemoveMi n();22.y = Q.RemoveMi n();23.z.M akeTree(0,x.tree,y.tree);24.x.weight += y.weight;25.x.tree = z;26.Q.ln sert(x);27.28.x = Q.RemoveMi n();29.delete w;30.return x.tree;31. 32.14.用貪心算法解決搬桌子問題關(guān)鍵思想：把課桌按起點從小到大排序，每次都是搬離當(dāng)前位置最近的課桌。 算法代碼：#in clude<stdio.h>int mai n()structint start;int end;

43、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=O;while( num<n)temp=0;for(i=0;i <n ;i+)if(usedi=0&&ai.start>=temp)temp=ai.e nd; usedi=

44、1; nu m+;mi n+;prin tf("%d",mi n);15.八數(shù)碼難題核心代碼：1#in clude <stdio.h>2#in clude<memory.h>3#defi ne len 3628884#define le 95態(tài)6typedef int statele;7state stle n,goal;/狀態(tài)共有362880種，數(shù)組稍微開大點/每種狀態(tài)有9個數(shù)據(jù)，也可看為每種狀態(tài)下又有/狀態(tài)：表示九個格子/st為狀態(tài)數(shù)組goal為目標數(shù)組9種狀8int dislen,factle,headlen,vislen,der42=上，下,

45、9-1,0,1,0,0,-1,0,1;/dis為每種狀態(tài)的已走的步驟der為方向10左，右11 void encode()/ 編碼1213 int i;14 for (i=fact0=1; i<le; i+)15 facti=facti-1*i;1617int decode( int s)/ 解碼1819 inti,j,code,cnt;20 for(i=code=0; i<le; i+)21 22 for (cnt=0,j=i+1; j<le;j+)23 if (stsi>stsj)24 cnt+;25 code+=cnt*fact8-i;26 27 if (visc

46、ode)28 return0;29 else30 return viscode=1;3132int bfs()3334int front=1,rear=2,i,x,y,z,nx,ny,nz;35en code();36while (front<rear)3738state & s=stfro nt;39if (memcm(s,goal, sizeof (s)=0)/對front狀態(tài)和目標狀態(tài)進行比40較41return front;42for (i=0; i<le; i+)/找到為0的兀素，即空的那個格43子，這里選取空的那個格子是應(yīng)為相對于1,2,3,8這樣的數(shù)據(jù)，0作為

47、判斷依據(jù)簡單44于用數(shù)據(jù)作為判斷依據(jù)45 if (si=O) break ;46 x=i/3;47 y=i%3;48 z=i;/記錄空的格子的行標，列表，和所在位置，這里的位置按49照從左到右從上到下依次遞增50for(i=0; i<4; i+)51行搜索525354nx=x+deri0;55n y=y+deri1;56nz=n x*3+ny;57if (nx>=0&&nx<3&&ny>=0&&ny<3)5859state & t=strear;60memcpy&t，&s, sizeof (s

48、);61數(shù)值62tz=s nz;63t nz=sz;64disrear=disfr on t+1;65if (decode(rear)66已經(jīng)出現(xiàn)過67rear+;6869fron t+;/按照上，下，左，右四個方向進/記錄此時的狀態(tài)即九個格子的/判斷strear這種狀態(tài)是否return 0;int main( void )int i,oj;for (i=0; i<le; i+)seanf(”d",&st1i);/按從左到右從上到下的順序存儲數(shù)據(jù)for (i=0; i<le; i+)sea nf ("%d", &goali);oj=bf

49、s();if (oj)printf("%dn",disoj);elseputs ("Impossible");return 0;16.圖的M著色問題考慮所有的圖，討論在至多使用 m種顏色的情況下，可對一給定的圖著色的所有不同方 法。通過回溯的方法，不斷的為每一個節(jié)點著色，在前面n-1個節(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元組為可行解，否則為無效解。 容易看出，每個