西工大算法復(fù)習(xí)資料的總結(jié)

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

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

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

5、畫其結(jié)構(gòu)特征； 遞歸地定義最優(yōu)值； 以自底向上的方式計(jì)算出最優(yōu)值； 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。基本要素：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊問題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ì)為動(dòng)態(tài)規(guī)劃算法解決問題提供了重 要線索。子問題重疊性質(zhì)：指在用遞歸演算法自頂向下對問題進(jìn)行求解時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題會被重復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是利用了這種子問題的重疊 性質(zhì)，對每一個(gè)子問題只計(jì)算一次， 然后將其計(jì)算結(jié)果保存在一個(gè)表格中，當(dāng)再次需要計(jì)算已經(jīng)計(jì)算

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

7、界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解空間樹。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會成為擴(kuò)展節(jié)點(diǎn)?；罱Y(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ò)展過程，這個(gè)過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。10. 分支限界法與回溯法的區(qū)別1.搜索方式不同：分支限界法使用廣度優(yōu)先或最小消耗優(yōu)先搜索，而回溯法使用深度優(yōu)先搜索。2主要區(qū)別：在于它們對當(dāng)前擴(kuò)展節(jié)點(diǎn)所采用的擴(kuò)展方式不同。分支限界法：每個(gè)節(jié)點(diǎn)只有一次成為活結(jié)點(diǎn)

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

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

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

11、， 在有n個(gè)元素的線性表中查找一個(gè)元素在最壞情況都需要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); en d;en d;2請采用快速排序算法為下列

12、數(shù)字排序，并寫出最終結(jié)果(21 25 49 25* 16 08)快速排序的基本思想：選定一個(gè)基準(zhǔn)值元素，對帶排序的序列進(jìn)行分割，分割之后的序 列一部分小于基準(zhǔn)值元素，另一部分大于基準(zhǔn)值元素，再對這兩個(gè)分割好的子序列進(jìn)行上述 的過程。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;采用子序列的第一個(gè)元素作為基準(zhǔn)元素while (low < high)/從后往前在后半部分中尋找第一個(gè)小于基準(zhǔn)元素的元素while (low

13、 < 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(i nt a,i nt low,i nt high)if (low <high )

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

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

16、rri;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=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;sea

17、rch(m+1);weight-=wmsearch(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();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=v

18、alue;6循環(huán)賽日程表(遞歸與分治)設(shè)計(jì)思想：按分治策略，可以將所有選手對分為兩半，n個(gè)選手的比賽日程表就可以通過為n/2個(gè)選手設(shè)計(jì)的比賽日程表來決定。遞歸地用這種一分為二的策略對選手進(jìn)行分割， 直至只剩下兩個(gè)選手時(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 = 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, in

20、t 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+)f

21、or(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用備忘錄算法實(shí)現(xiàn)計(jì)算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);設(shè)計(jì)一個(gè)的

23、高效算法實(shí)現(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. retu

24、rn 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)實(shí)現(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. 活動(dòng)安排問題問題關(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 actio nint begi n;int en d;

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

27、ak=temp;11. 最優(yōu)服務(wù)次序問題思路是最短服務(wù)時(shí)間優(yōu)先，先將服務(wù)時(shí)間排序，然后注意后面的等待服務(wù)時(shí)間既包括等 待部分，也包括服務(wù)部分。貪心策略：對服務(wù)時(shí)間最短的顧客先服務(wù)的貪心選擇策略。首先對需要服務(wù)時(shí)間最短的顧客進(jìn)行服務(wù)，即做完第一次選擇后，原問題T變成了需對n-1個(gè)顧客服務(wù)的新問題T'。新問題和原問題相同，只是問題規(guī)模由n減小為n-1?；诖朔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)+.+

28、t( 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.vectorv int >su(s+1,0);5.int n=x.size();6.sort(x.begi n( ),x.e n

29、d();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(x

30、,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算法是解單源最短路徑問題的貪心算法。其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地

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

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

33、值為：disti=cvi, vi 屬于V.(2) 選擇vu,使得distu=Mindisti | vi 屬于V-S,vj就是長度最短的最短路徑的終點(diǎn)。 令 S=S U u.(3) 修改從v到集合V-S上任一頂點(diǎn)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. void Dijkstra( int n, int v,Type dist, int prev

34、,Type cN+1);5. void Traceback( int v,int i,int prev); / 輸出最短路徑 v 源點(diǎn)，i 終點(diǎn)6. int main()7. 8. int v = 1; / 源點(diǎn)為 19. int distN+1,prevN+1,cN+1N+1;10.10. cout<<"有向圖權(quán)的矩陣為："<<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<<cij

35、<<""17. 18. cout<<e ndl;19. 20. Dijkstra(N,v,dist,prev,c);21. for (int i=2; i<=N; i+)23.24.cout<< "源點(diǎn)1到點(diǎn)"<<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表示當(dāng)前從源到頂點(diǎn)i的最短特殊路徑長度38.si = false ;39.if (disti = M)40.41.previ = 0;/記錄從源到頂點(diǎn)i的最短路徑i的前一個(gè)頂點(diǎn)42.43.else2.6

37、6.精彩文檔previ = v;distv = 0;sv = true ;for (int i=1; i<n; i+)int temp = M;int u = v; / 上一頂點(diǎn)/取出V-S中具有最短特殊路徑長度的頂點(diǎn)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+)9.80.

38、7.88.精彩文檔if (!s j) && (cuj<M)Type n ewdist = distu + cuj;if (n ewdist < distj)dist j = n ewdist;prevj = u;/輸出最短路徑v源點(diǎn)，i終點(diǎn)void Traceback( int v,int i,int prev)if (v = i)cout<<i;return ;Traceback(v,previ,prev);cout<<"->" <<i;89. 13. 霍夫曼編碼問

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

40、義:1. template < class 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 &

41、gt; HuffmanTree(Type f,int n)3. 4. /生成單節(jié)點(diǎn)樹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)先隊(duì)列MinH eap<Huffma n

42、< Type>> Q(n);for (int i=1; i<=n; i+) Q.lnsert(wi);/反復(fù)合并最小頻率樹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、桌子問題關(guān)鍵思想：把課桌按起點(diǎn)從小到大排序，每次都是搬離當(dāng)前位置最近的課桌。算法代碼：#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;

44、while( num<n)temp=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ù)組稍微開大點(diǎn)4 #define le 9/ 每種狀態(tài)有9個(gè)數(shù)據(jù)，也可看為每種狀態(tài)下又有5 type

45、def int statele;/狀態(tài)：表示九個(gè)格子6 state stlen,goal;/st為狀態(tài)數(shù)組 goal為目標(biāo)數(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;

46、 i+)4 1 for (cnt=O,j=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)和

47、目標(biāo)狀態(tài)進(jìn)行比較2 return fron t;4 for (i=0; i<le; i+)/找到為0的元素，即空的那個(gè)格子，這里選取空2的那個(gè)格子是應(yīng)為相對于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;/記錄空的格子的行標(biāo)，列表，和所在位置，這里的位置按照從左到右2從上到下依次遞增8 for (i=0; i<4; i+)/按照上，下，左，右四個(gè)方向進(jìn)行搜索2 93 nx=x+deriO;0n y=y+deri1;3 nz=nx*3+ny;1 if (nx>=0&&a

48、mp;n x<3&&n y>=0&&n y<3)3 2 state & t=strear;3 memcpy (&t,&s, sizeof (s);/記錄此時(shí)的狀態(tài)即九個(gè)格子的數(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

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

50、法，不斷的為每一個(gè)節(jié)點(diǎn)著色，在前面n-1個(gè)節(jié)點(diǎn)都合法的著色之后，開始對第n個(gè)節(jié)點(diǎn)進(jìn)行著色，這時(shí)候枚舉可用的m個(gè)顏色，通過和第n個(gè)節(jié)點(diǎn)相鄰的節(jié)點(diǎn)的顏色，來判斷這個(gè)顏色是否合法，如果找到那么一種顏色使得第n個(gè)節(jié)點(diǎn)能夠著色，那么說明m種顏色的方案是可行的。用m種顏色為無向圖 G=(V,E)著色，其中，V的頂點(diǎn)個(gè)數(shù)為n,可以用一個(gè)n元組 x=(x1,x2,xn)來描述圖的一種可能著色，其中， xi 1,2,m , (1 <i <n)表示賦予頂點(diǎn) i的顏色。例如，5元組(1,2, 2, 3, 1)表示對具有5個(gè)頂點(diǎn)的無向圖(a)的一種著色，頂點(diǎn) A著顏色1，頂點(diǎn)B著顏色2，頂點(diǎn)C著顏色2，如

51、此等等。如果在n元組X中，所有相鄰 頂點(diǎn)都不會著相同顏色，就稱此 n元組為可行解，否則為無效解。容易看出，每個(gè)頂點(diǎn)可 著顏色有m種選擇，n個(gè)頂點(diǎn)就有mn種不同的著色方案，問題的解空間是一棵高度為n的完全m叉樹，這里樹高度的定義為從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑的長度。每個(gè)分支結(jié)點(diǎn)， 都有m個(gè)兒子結(jié)點(diǎn)。最底層有mn個(gè)葉子結(jié)點(diǎn)。例如，表示用3種顏色為3個(gè)頂點(diǎn)的圖著色的狀態(tài)空間樹。如圖所示，對第i (i>=1 )層上的每個(gè)頂點(diǎn)，從其父節(jié)點(diǎn)到該節(jié)點(diǎn)的邊上的標(biāo)號表示頂點(diǎn)i著色的顏色編號。1. #i nclude "stdafx.h"2. #i nclude <iostream>3