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

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

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

3、中，按照深度優(yōu)先搜索的策略，從根結(jié)點(diǎn)出發(fā)深度探索解空間樹(shù)。當(dāng)探索到某一結(jié)點(diǎn)時(shí)，要先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解，如果包含，就從該結(jié)點(diǎn)出發(fā)繼續(xù)探索下去，如果該結(jié)點(diǎn)不包含問(wèn)題的解，則逐層向其祖先結(jié)點(diǎn)回溯。若用回溯法求問(wèn)題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有可行的子樹(shù)都要已被搜索遍才結(jié)束。 而若使用回溯法求任一個(gè)解時(shí)，只要搜索到問(wèn)題的一個(gè)解就可以結(jié)束。搜索子集樹(shù)的一般模式： void search(int m) if(m>n) /遞歸結(jié)束條件 output(); /相應(yīng)的處理(輸出結(jié)果) else am=0; /設(shè)置狀態(tài)：0表示不要該物品 search(m+1); /遞歸搜索：繼續(xù)確定下一個(gè)物

4、品 am=1; /設(shè)置狀態(tài)：1表示要該物品 search(m+1); /遞歸搜索：繼續(xù)確定下一個(gè)物品 搜索排列樹(shù)的一般模式： void search(int m) if(m>n) /遞歸結(jié)束條件 output(); /相應(yīng)的處理(輸出結(jié)果) else for(i=m;i<=n;i+) swap(m,i); /交換am和ai if() if(canplace(m) /如果m處可放置 search(m+1); /搜索下一層 swap(m,i); /交換am和ai(換回來(lái))5. 動(dòng)態(tài)規(guī)劃的基本思想、基本步驟、基本要素是什么基本思想：將待求解問(wèn)題分解成若干子問(wèn)題，先求解子問(wèn)題，然后從這些子

5、問(wèn)題的解得到原問(wèn)題的解?；静襟E：找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征； 遞歸地定義最優(yōu)值； 以自底向上的方式計(jì)算出最優(yōu)值； 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。 基本要素：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問(wèn)題重疊問(wèn)題6. 什么是最優(yōu)子結(jié)構(gòu)性質(zhì)和子問(wèn)題重疊性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)：如果問(wèn)題的最優(yōu)解所包含的子問(wèn)題的解也是最優(yōu)的，則稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（即滿足最優(yōu)化原理）。最優(yōu)子結(jié)構(gòu)性質(zhì)為動(dòng)態(tài)規(guī)劃算法解決問(wèn)題提供了重要線索。 子問(wèn)題重疊性質(zhì)：指在用遞歸演算法自頂向下對(duì)問(wèn)題進(jìn)行求解時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題會(huì)被重復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是利用了這種子問(wèn)題的重疊性質(zhì)，對(duì)每一個(gè)子問(wèn)題

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

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

8、區(qū)別：在于它們對(duì)當(dāng)前擴(kuò)展節(jié)點(diǎn)所采用的擴(kuò)展方式不同。分支限界法：每個(gè)節(jié)點(diǎn)只有一次成為活結(jié)點(diǎn)的機(jī)會(huì)回溯法：活結(jié)點(diǎn)的所有可行子節(jié)點(diǎn)被遍歷后才被從棧中彈出11. 搜索算法的一般模式搜索算法關(guān)鍵要解決好狀態(tài)判重的問(wèn)題：void search()open表初始化為空;起點(diǎn)加入到open表;while( open表非空 )取open表中的一個(gè)結(jié)點(diǎn)u;從open表中刪除u;for( 對(duì)擴(kuò)展結(jié)點(diǎn)u得到的每個(gè)新結(jié)點(diǎn)vi )if(vi是目標(biāo)結(jié)點(diǎn))輸出結(jié)果并返回;If(notused(vi)vi進(jìn)入open表;12.貪心算法的基本思想、基本步驟及基本要素基本思想：貪心算法總是做出在當(dāng)前看來(lái)是最好的選擇，即貪心算法并不

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

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

11、。這種方法對(duì)于有n個(gè)元素的線性表在最壞的情況下需要n次比較。一般來(lái)說(shuō)，若沒(méi)有其他的附加信息，在有n個(gè)元素的線性表中查找一個(gè)元素在最壞情況都需要n次比較?？紤]最簡(jiǎn)單的情況，該線性表為有序表，設(shè)其按照主鍵的遞增順序從小到大排列。核心偽代碼：function BinarySearch(L,a,b,x) begin if a>b then return -1else beginm=(a+b)div 2;if x=Lm then return (m)else if x>Lmthen return BinarySearch(L,m+1,b,x); else return BinarySearc

12、h(L,a,m-1,x); end; end;2. 請(qǐng)采用快速排序算法為下列數(shù)字排序，并寫(xiě)出最終結(jié)果（21 25 49 25* 16 08）快速排序的基本思想:選定一個(gè)基準(zhǔn)值元素，對(duì)帶排序的序列進(jìn)行分割，分割之后的序列一部分小于基準(zhǔn)值元素，另一部分大于基準(zhǔn)值元素，再對(duì)這兩個(gè)分割好的子序列進(jìn)行上述的過(guò)程。void swap(int a,int b)int t;t =a ;a =b ;b =t ; int Partition(int arr,int low,int high) int pivot=arrlow;/采用子序列的第一個(gè)元素作為基準(zhǔn)元素 while (low < high) /從后

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

14、t a,int low,int high) if (low <high ) int n=Partition (a ,low ,high ); QuickSort (a ,low ,n ); QuickSort (a ,n+1,high ); 3. 寫(xiě)出對(duì)下面的序列進(jìn)行歸并排序的過(guò)程（從小到大）（63 14 9 98 23 48 15 70）核心代碼:void MergeSort(int low,int high) if(low>=high)/每個(gè)子列表中剩下一個(gè)元素時(shí)停止return; /將列表劃分成相等的兩個(gè)子列表,若有奇數(shù)個(gè)元素，則在左邊子列表大于右邊子列表else int m

15、id=(low+high)/2; MergeSort(low,mid);/遞歸劃分子列表MergeSort(mid+1,high);/遞歸劃分子列表/新建一個(gè)數(shù)組b用于存放歸并的元素int b=new inthigh-low+1;/兩個(gè)子列表進(jìn)行排序歸并，直到兩個(gè)子列表中的一個(gè)結(jié)束for(int 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+)/如果第二個(gè)子列表中仍然有元素，則追加到新列表bk=arrj;f

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

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

18、ght+=wi;value+=vi;if(weight<=c) if(value>max) max=value; 6. 循環(huán)賽日程表(遞歸與分治)設(shè)計(jì)思想：按分治策略，可以將所有選手對(duì)分為兩半，n個(gè)選手的比賽日程表就可以通過(guò)為n/2個(gè)選手設(shè)計(jì)的比賽日程表來(lái)決定。遞歸地用這種一分為二的策略對(duì)選手進(jìn)行分割，直至只剩下兩個(gè)選手時(shí)，比賽日程表的指定就很簡(jiǎn)單了。核心代碼：int N = 1; void UpRightCopy(int n, int array) for(int i = 0; i < n; i+) for(int j = n; j < 2 * n;j+) array

19、N * i + j = 2 * n + 1 -arrayN * i + 2 * n - 1 - j; void DownRightCopy(int n, int array) for(int i = n; i < 2 * n; i+) for (int j = n; j < 2 * n;j+) arrayN * i + j = arrayN * (i - n) + j - n; void LeftDownCopy(int n, int array) for (int i = n; i < 2 * n; i+) for (int j = 0; j < n;j+) arra

20、yN * i + j = arrayN * (i - n) + j + n; void turn(int n, int array) if(n = 1) array0 = 1; else turn(n / 2, array); DownRightCopy(n / 2, array); UpRightCopy(n / 2, array); LeftDownCopy(n / 2, array); 7. 最長(zhǎng)公共子序列核心代碼： char a201,b201; int n1,n2; void search() int List201201;for(int i=0;i<=n1;i+) Listi

21、0=0;for(int j=0;j<=n2;j+) List0j=0;for(int i=1;i<=n1;i+)for(int j=1;j<=n2;j+)if(ai-1=bj-1)Listij=Listi-1j-1+1; else if(Listi-1j>Listij-1) Listij=Listi-1j; else Listij=Listij-1; 8. 矩陣連乘問(wèn)題核心代碼：int n;int p11;void search()int a1111,temp;for(int i=1;i<=n;i+)aii=0; for(int d=1;d<=n-1;d+)

22、 for(int i;i<=n-d;i+)int j=i+d;aij=0+ai+1j+pi-1*pi*pj;for(int k=i+1;k<j;k+)temp=aik+ak+1j+pi-1*pk*pj;if(temp<aij)aij=temp; 9. 用備忘錄算法實(shí)現(xiàn)計(jì)算Fibonacci數(shù)列核心代碼：int Fib(int n)int resultn=0,0,.,0;int f1,f2;if(n<2)return n; if(resultn-1=0)f1=Fib(n-1);elsef1=resultn-1;if(resultn-2=0)f2=Fib(n-2);else

23、f2=resultn-2;resultn=f1+f2;return (f1+f2);設(shè)計(jì)一個(gè)的高效算法實(shí)現(xiàn)Fibonacci數(shù)列Version 1(效率最差)1. long Fibonacci(int n)   2.    3.   if (n = 0)   4.       return 0;   5.   else

24、 if (n = 1)   6.       return 1;   7.   else if (n > 1)   8.        return Fibonacci (n - 1) + Fibonac

25、ci (n - 2);   9.   else   10.        return -1;   11.    Version2(效率其次)1. long Fibonacci2(int n)   2.    3.   if (n =

26、60;0)   4.      return 0;   5.   else if (n = 1)   6.     return 1;   7.   else if (n > 1)   8.   

27、;   9.   10.     if(tempResultn != 0)   11.       return tempResultn;   12.     else   13.        14.  &#

28、160;        tempResultn = Fibonacci2 (n - 1) + Fibonacci2 (n - 2);   15.           return tempResultn;   16.   

29、0;     17.       18.   Version 3(效率最高-放棄遞歸用循環(huán)實(shí)現(xiàn))1. long Fibonacci3(int n)   2.    3.   long * temp = new longn + 1;   4.   5.

30、   temp0 = 0;   6.   7.   if (n > 0)   8.      temp1 = 1;   9.   10.    for(int i = 2; i <= n; +i)&

31、#160;  11.      12.      tempi = tempi - 1 + tempi - 2;   13.      14.   15.   long result = tempn;   16. 

32、0; 17.   delete temp;   18.   19.   return result;   20.   10. 活動(dòng)安排問(wèn)題問(wèn)題關(guān)鍵在于：理解什么是相容性活動(dòng)！若區(qū)間s1,f1)與區(qū)間s2,f2)不相交，則稱活動(dòng)1與活動(dòng)2是相容的，即s1>=f2或s2>=f1時(shí)，活動(dòng)1與活動(dòng)2相容。（區(qū)間表示的是活動(dòng)的起始時(shí)間s和結(jié)束時(shí)間f）核心代碼：struct actionint begin;int end;a1

33、000;int n;/n表示活動(dòng)的總數(shù)int sum=0;/sum表示能參加的活動(dòng)的數(shù)量void search()sum=1;int temp=a0.end;/temp表示第一個(gè)活動(dòng)結(jié)束的時(shí)間for(int i=1;i<n;i+)if(ai.begin>=temp)sum+;temp=ai.end;void selection_sort()for(int i=0;i<n;i+)int k=i;for(int j=i+1;j<n;j+)if(aj.end<ak.end)k=j; struct action temp=ai; ai=ak; ak=temp;11. 最優(yōu)

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

35、n);總等待時(shí)間為：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個(gè)隊(duì)列上的某一個(gè)顧客的等待時(shí)間；su是求和數(shù)組，suj的值為第j個(gè)隊(duì)列上所有顧客的等待時(shí)間；第一種代碼：1. double greedy(vector<int>x,int s)   2. 3.     vector<int>st(s+1,0);  4.    

36、; vector<int>su(s+1,0);    5.     int n=x.size();    6.     sort(x.begin(),x.end();    7.     int i=0,j=0;    8.     wh

37、ile(i<n)  9.         stj+=xi;     10.         suj+=stj;     11.         i+;  12.     &#

38、160;   j+;     13.         if(j=s)j=0;   14.        15.     double t=0;  16.     for(i=0;i<s;i+)  

39、0;17.         t+=sui;   18.     t/=n;   19.     return t;  20. 第二種方法： 1. int x10000;   2. int main()  3.      

40、 4.     int n;  5.     cin >> n;  6.     int temp;  7.     for(int j = 0; j< n; j+)  8.     

41、0;  9.        scanf("%d",&xj);  10.         11.      sort(x,x+n);      12.     for(int i = 1; i&

42、#160;< n; i+)  13.         xi+=xi-1;            14.     double t = 0;  15.     for(int i = 0;

43、0;i < n; i+)  16.         t+=xi;          17.     t/=n;  18.     cout.setf(ios:fixed);     19.   

44、  cout << setprecision(2)  << t << endl;        20.     system("pause");  21.     return 0;  22. 12. 最短路徑問(wèn)題Dijkstra算法是解單源最

45、短路徑問(wèn)題的貪心算法。其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。初始時(shí)，S中僅含有源。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過(guò)S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。Dijkstra算法每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)數(shù)組dist作必要的修改。一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其他頂點(diǎn)之間的最短路徑長(zhǎng)度。Dijkstra算法可描述如下，其中輸入帶權(quán)有向圖是G=(V,E)，V=1,2,，n，頂點(diǎn)v是源。c是一

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

47、vi的當(dāng)前最短路徑長(zhǎng)度的初值為：disti=cvi, vi屬于V.   (2) 選擇vu, 使得distu=Mindisti | vi屬于V-S,vj就是長(zhǎng)度最短的最短路徑的終點(diǎn)。令S=S U u.   (3) 修改從v到集合V-S上任一頂點(diǎn)vi的當(dāng)前最短路徑長(zhǎng)度:如果 distu+cuj< distj 則修改 distj= distu+cuj.    (4) 重復(fù)操作(2),(3)共n-1次. 1. const int N = 5;  2. con

48、st int M = 1000;   3. template<class Type>  4. void Dijkstra(int n,int v,Type dist,int prev,Type cN+1);  5. void Traceback(int v,int i,int prev);/輸出最短路徑 v源點(diǎn)，i終點(diǎn)  6. int&

49、#160;main()  7.   8.     int v = 1;/源點(diǎn)為1  9.     int distN+1,prevN+1,cN+1N+1;  10.   11.     cout<<"有向圖權(quán)的矩陣為："<<endl;  12.   

50、60; for(int i=1; i<=N; i+)  13.       14.         for(int j=1; j<=N; j+)  15.           16.     

51、60;       fin>>cij;      17.             cout<<cij<<" "    18.           

52、;19.         cout<<endl;  20.       21.     Dijkstra(N,v,dist,prev,c);  22.     for(int i=2; i<=N; i+)  23.     

53、0; 24.         cout<<"源點(diǎn)1到點(diǎn)"<<i<<"的最短路徑長(zhǎng)度為:"<<disti<<"，其路徑為"  25.         Traceback(1,i,prev);  26.       

54、;  cout<<endl;  27.       28.   29.     return 0;  30.   31. template<class Type>  32. void Dijkstra(int n,int v,Type dist,int prev,Type c

55、N+1)  33.   34.     bool sN+1;  35.     for(int i=1; i<=n; i+)  36.       37.         disti = cvi;/disti表示當(dāng)前從源到頂點(diǎn)i的最短

56、特殊路徑長(zhǎng)度  38.         si = false;  39.         if(disti = M)  40.           41.        

57、     previ = 0;/記錄從源到頂點(diǎn)i的最短路徑i的前一個(gè)頂點(diǎn)  42.           43.         else  44.           45.    

58、;         previ = v;  46.           47.       48.     distv = 0;  49.     sv = true;&

59、#160; 50.     for(int i=1; i<n; i+)  51.       52.         int temp = M;  53.         int u = v;/

60、上一頂點(diǎn)  54.         /取出V-S中具有最短特殊路徑長(zhǎng)度的頂點(diǎn)u  55.         for(int j=1; j<=n; j+)  56.           57.     

61、60;       if(!sj) && (distj<temp)  58.               59.                 u =

62、60;j;  60.                 temp = distj;  61.               62.          &#

63、160;63.         su = true;  64.         /根據(jù)作出的貪心選擇更新Dist值  65.         for(int j=1; j<=n; j+)  66.     

64、;      67.             if(!sj) && (cuj<M)  68.               69.        &#

65、160;        Type newdist = distu + cuj;  70.                 if(newdist < distj)  71.       

66、            72.                     distj = newdist;  73.           &#

67、160;         prevj = u;  74.                   75.               76.  

68、         77.       78.   79. /輸出最短路徑 v源點(diǎn)，i終點(diǎn)  80. void Traceback(int v,int i,int prev)  81.   82.     if(v = i)  83.

69、60;     84.         cout<<i;  85.         return;  86.       87.     Traceback(v,previ,prev);  88.  

70、0;  cout<<"->"<<i;  89.   13. 霍夫曼編碼問(wèn)題（要求畫(huà)出霍夫曼樹(shù)）哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。其構(gòu)造步驟如下：     (1)哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹(shù)T。     (2)算法以|C|個(gè)葉結(jié)點(diǎn)開(kāi)始，執(zhí)行|C|1次的“合并”運(yùn)算后產(chǎn)生最終所要求的樹(shù)T。     (3)假設(shè)編碼字符集中每一字符c的頻率是f(

71、c)。以f為鍵值的優(yōu)先隊(duì)列Q用在貪心選擇時(shí)有效地確定算法當(dāng)前要合并的2棵具有最小頻率的樹(shù)。一旦2棵具有最小頻率的樹(shù)合并后，產(chǎn)生一棵新的樹(shù)，其頻率為合并的2棵樹(shù)的頻率之和，并將新樹(shù)插入優(yōu)先隊(duì)列Q。經(jīng)過(guò)n1次的合并后，優(yōu)先隊(duì)列中只剩下一棵樹(shù)，即所要求的樹(shù)T。構(gòu)造過(guò)程如圖所示：算法中用到的類定義：1. template<class Type>   2. class Huffman  3.   4.     friend BinaryTree<i

72、nt> HuffmanTree(Type,int);  5.     public:  6.         operator Type() const   7.           8.        

73、     return weight;  9.           10.     /private:  11.         BinaryTree<int> tree;  12.     

74、60;   Type weight;  13. ;  算法HuffmanTree描述如下：1. template<class Type>  2. BinaryTree<int> HuffmanTree(Type f,int n)  3.   4.     /生成單節(jié)點(diǎn)樹(shù)  5.     Huff

75、man<Type> *w = new Huffman<Type>n+1;  6.     BinaryTree<int> z,zero;  7.   8.     for(int i=1; i<=n; i+)  9.       10.  

76、0;      z.MakeTree(i,zero,zero);  11.         wi.weight = fi;  12.         wi.tree = z;  13.       14.  &

77、#160;  /建優(yōu)先隊(duì)列  15.     MinHeap<Huffman<Type>> Q(n);  16.     for(int i=1; i<=n; i+) Q.Insert(wi);  17.     /反復(fù)合并最小頻率樹(shù)  18.     Huf

78、fman<Type> x,y;  19.     for(int i=1; i<n; i+)  20.       21.         x = Q.RemoveMin();  22.         

79、;y = Q.RemoveMin();  23.         z.MakeTree(0,x.tree,y.tree);  24.         x.weight += y.weight;  25.         x.tree = z

80、;  26.         Q.Insert(x);  27.       28.     x = Q.RemoveMin();  29.     delete w;  30.     return x.tree;&#

81、160; 31.  32.14. 用貪心算法解決搬桌子問(wèn)題關(guān)鍵思想：把課桌按起點(diǎn)從小到大排序，每次都是搬離當(dāng)前位置最近的課桌。算法代碼：#include<stdio.h>int main()structint start;int end;a100;int i,j;int n,m,min,num,temp,used100=0;scanf("%d%d",&m,&n);for(i=0;i<n;i+)scanf("%d%d",&ai.start,&ai.end);/sort(a,n); /按s

82、tart從小到大對(duì)數(shù)組a排序min=0;num=0;while(num<n)temp=0;for(i=0;i<n;i+)if(usedi=0&&ai.start>=temp)temp=ai.end;usedi=1;num+;min+;printf("%d",min);15. 八數(shù)碼難題核心代碼：12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667

83、6869#include <stdio.h>#include<memory.h>#define len          /狀態(tài)共有種，數(shù)組稍微開(kāi)大點(diǎn)#define le 9               /每種狀態(tài)有9個(gè)數(shù)據(jù),也可看為每種狀態(tài)下又有9種狀態(tài)typedef int statele;        /狀態(tài)：表示九個(gè)格子state stlen,goal;           /st為狀態(tài)數(shù)組