《算法設(shè)計(jì)與》實(shí)驗(yàn)指導(dǎo)書(shū)200609版

1、湖北汽車(chē)工業(yè)學(xué)院算法設(shè)計(jì)與分析-實(shí)驗(yàn)指導(dǎo)書(shū)電氣工程系軟件教研室 王文燕 編二六年目 錄實(shí)驗(yàn)一：分治與遞歸2實(shí)驗(yàn)二：貪心算法3實(shí)驗(yàn)三：動(dòng)態(tài)規(guī)劃法4實(shí)驗(yàn)四（1）：回溯法6實(shí)驗(yàn)四（2）：分枝限界法7參考書(shū)目8實(shí)驗(yàn)一：分治與遞歸【實(shí)驗(yàn)?zāi)康摹繉W(xué)會(huì)應(yīng)用分治算法思想完成汽車(chē)牌照的快速查找?！緦?shí)驗(yàn)要求】利用基數(shù)排序的思想對(duì)一批具有結(jié)構(gòu)特征的汽車(chē)牌照進(jìn)行排序，并且利用二分查找的思想對(duì)排好序的汽車(chē)牌照記錄實(shí)現(xiàn)查詢。對(duì)于車(chē)牌號(hào)為關(guān)鍵字的記錄集合，可以人工錄入數(shù)據(jù)，也可以按自動(dòng)方式隨機(jī)生成。按分治與遞歸的算法思想策略完成的程序，輸入要求的一批數(shù)據(jù)記錄后，屏幕輸出排好序的車(chē)牌號(hào)碼及相關(guān)信息。查詢時(shí)，程序查找到匹配的數(shù)據(jù)

2、，輸出該關(guān)鍵字的其他數(shù)據(jù)項(xiàng)。要求完成：算法描述寫(xiě)出程序代碼完成調(diào)試進(jìn)行過(guò)程與結(jié)果分析?！緦?shí)驗(yàn)性質(zhì)】驗(yàn)證型實(shí)驗(yàn)?！緦?shí)驗(yàn)內(nèi)容】應(yīng)用分治策略，進(jìn)行二分查找。將一個(gè)較大的問(wèn)題劃分為若干較小的問(wèn)題進(jìn)行求解，降低求解難度，從而獲得原問(wèn)題的解。進(jìn)行算法設(shè)計(jì)，并寫(xiě)出相應(yīng)程序，進(jìn)行調(diào)試測(cè)試。測(cè)試數(shù)據(jù)的每個(gè)記錄包括五項(xiàng)，分別為牌照號(hào)碼、汽車(chē)商標(biāo)、顏色、注冊(cè)日期和車(chē)主的姓名，其中牌照號(hào)碼一項(xiàng)的輸入形式如下：k0k1k2k3k4k5k601B7328其中k0-k1輸入值為0131（代表地區(qū)），k2輸入值為A-Z（代表車(chē)的使用類型），后4位為00009999（代表車(chē)號(hào)），例如：01B7328。這種牌照號(hào)碼具有多關(guān)鍵字的

3、特征，可以將其分為三段來(lái)考慮，即：數(shù)字、字母和數(shù)字。其余四項(xiàng)輸入內(nèi)容因?yàn)椴簧婕氨境绦虻暮诵乃枷?，故只要求一般字符串類型即可。查詢時(shí)要求輸入合法的汽車(chē)牌照號(hào)碼。測(cè)試數(shù)據(jù)要求用30個(gè)左右的數(shù)據(jù)項(xiàng)進(jìn)行測(cè)試，頭兩位暫限定0104，第3位也暫限定為A-E，以便可使牌照號(hào)碼相對(duì)集中。【注意事項(xiàng)】用C語(yǔ)言或C+實(shí)現(xiàn)算法。選擇合適的數(shù)據(jù)結(jié)構(gòu)?！菊{(diào)試分析和心得體會(huì)】對(duì)整個(gè)算法實(shí)現(xiàn)的時(shí)間復(fù)雜度進(jìn)行討論分析?！具x做題一】完成矩陣乘積的Strassen算法描述、實(shí)現(xiàn)及其復(fù)雜度分析?！具x做題二】設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽?，F(xiàn)要設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：每個(gè)選手必須與其他n-1個(gè)選手各賽一次；每個(gè)選手一

4、天只能賽一次；循環(huán)賽一共進(jìn)行n-1天。按此要求可將比賽日程表設(shè)計(jì)成有n行和n-l列的一個(gè)表。在表中第i行和第j列處填入第i個(gè)選手在第j天所遇到的選手。用分治法編寫(xiě)為該循環(huán)賽設(shè)計(jì)一張比賽日程表的算法并運(yùn)行實(shí)現(xiàn)、對(duì)復(fù)雜度進(jìn)行分析。實(shí)驗(yàn)二：貪心算法【實(shí)驗(yàn)?zāi)康摹繎?yīng)用貪心算法求解管道鋪設(shè)施工的最佳方案?！緦?shí)驗(yàn)要求】需要在某個(gè)城市的n個(gè)居民區(qū)之間鋪設(shè)煤氣管道，則在這n個(gè)居民區(qū)之間只要鋪設(shè)n-1條管道即可。假設(shè)任意兩個(gè)居民區(qū)之間都可以架設(shè)管道，但由于地理環(huán)境的不同，所需經(jīng)費(fèi)不同。選擇最優(yōu)的施工方案能使總投資盡可能少，這個(gè)問(wèn)題即為求網(wǎng)的“最小生成樹(shù)”問(wèn)題。參照以下居民區(qū)示意圖，使得求解算法為：在可能架設(shè)的m條

5、管道中選取n-1條，既能連通n-1個(gè)居民區(qū)，有使總投資達(dá)到“最小”。網(wǎng)可采用鄰接矩陣為存儲(chǔ)結(jié)構(gòu)，以定點(diǎn)對(duì)（i,j）的形式輸出最小生成樹(shù)的邊。要求完成：算法描述寫(xiě)出程序代碼完成調(diào)試進(jìn)行過(guò)程與結(jié)果分析。18.218.2IA1218.738.252.5446HB5645.979210.5GC41.123.123.1E856673FD98.7居民區(qū)示意圖【實(shí)驗(yàn)性質(zhì)】驗(yàn)證型實(shí)驗(yàn)?！緦?shí)驗(yàn)內(nèi)容】應(yīng)用貪心算法策略，具體可采用Kruskal算法或Prim算法來(lái)求解居民區(qū)示意圖的最小生成樹(shù)，使得對(duì)每一條邊的選擇都是當(dāng)前狀態(tài)下最優(yōu)的。但無(wú)論采用何種算法實(shí)現(xiàn)都要選好恰當(dāng)?shù)妮o助數(shù)據(jù)結(jié)構(gòu)，來(lái)存放邊或頂點(diǎn)的集合。根據(jù)所設(shè)計(jì)

6、的算法完成程序?qū)崿F(xiàn)?！咀⒁馐马?xiàng)】選上述居民區(qū)示意圖中的數(shù)據(jù)作為測(cè)試數(shù)據(jù)。用C語(yǔ)言或C+實(shí)現(xiàn)算法。選擇合適的數(shù)據(jù)結(jié)構(gòu)?！菊{(diào)試分析和心得體會(huì)】注意整個(gè)算法的時(shí)間復(fù)雜度，并對(duì)其進(jìn)行分析。【選做題一】就下列問(wèn)題描述應(yīng)用貪心策略完成其算法描述并實(shí)現(xiàn)該算法，之后對(duì)其復(fù)雜度進(jìn)行分析：有n個(gè)活動(dòng)的集合A=1,2,n，其中每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。已知：每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi,且si <fi 。如果選擇了活動(dòng)i，則它在半開(kāi)時(shí)間區(qū)間si, fi)內(nèi)占用資源。若區(qū)間si, fi)與區(qū)間sj, fj)不相交，則稱

7、活動(dòng)i與活動(dòng)j是相容的。也就是說(shuō)，當(dāng)sifj或sjfi時(shí)，活動(dòng)i與活動(dòng)j相容。求解：安排盡量多項(xiàng)活動(dòng)在該場(chǎng)地進(jìn)行，即求A的最大相容子集。設(shè)待安排的11個(gè)活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的升序排列如下：i1234567891011si130535688212fi4567891011121314將此表數(shù)據(jù)作為實(shí)現(xiàn)該算法的測(cè)試數(shù)據(jù)?！具x做題二】構(gòu)造以n=6, 相應(yīng)的頻率表為=45,13,12,16,9,5的字符集CS=A,B,C,D,E,F 為測(cè)試數(shù)據(jù)的Huffman樹(shù)。應(yīng)用貪心算法思想完成其算法描述，并編碼實(shí)現(xiàn)以及對(duì)其時(shí)間復(fù)雜度進(jìn)行分析。實(shí)驗(yàn)三：動(dòng)態(tài)規(guī)劃法【實(shí)驗(yàn)?zāi)康摹繎?yīng)用動(dòng)態(tài)規(guī)劃算法思想求解矩陣

8、連乘的順序問(wèn)題?！緦?shí)驗(yàn)要求】應(yīng)用動(dòng)態(tài)規(guī)劃算法的最優(yōu)子結(jié)構(gòu)性質(zhì)和子問(wèn)題重疊性質(zhì)求解此問(wèn)題。分析動(dòng)態(tài)規(guī)劃算法的基本思想，應(yīng)用動(dòng)態(tài)規(guī)劃策略寫(xiě)出算法及相應(yīng)的程序，求解此題。要讀懂讀透Ai,j，A1,n=A1,k ×Ak+1,n，mij，sij各式所表達(dá)的含義并正確加以應(yīng)用。mij的遞歸定義： 0 （ i=j ）mij= minmik mk+1j+ni-1nknj （ i<j）要求完成：算法描述寫(xiě)出程序代碼完成調(diào)試進(jìn)行過(guò)程與結(jié)果分析?！緦?shí)驗(yàn)性質(zhì)】驗(yàn)證型實(shí)驗(yàn)?！緦?shí)驗(yàn)內(nèi)容】對(duì)于下列所描述的問(wèn)題，給出相應(yīng)的算法描述，并完成程序?qū)崿F(xiàn)與時(shí)間復(fù)雜度的分析。該問(wèn)題描述為：一般地，考慮矩陣A1，A2，

9、，An的連乘積，它們的維數(shù)分別為d0,d1,dn,即Ai的維數(shù)為di-1×di (1in)。確定這n個(gè)矩陣的乘積結(jié)合次序，使所需的總乘法次數(shù)最少。對(duì)應(yīng)于乘法次數(shù)最少的乘積結(jié)合次序?yàn)檫@n個(gè)矩陣的最優(yōu)連乘積次序。按給定的一組測(cè)試數(shù)據(jù)對(duì)根據(jù)算法設(shè)計(jì)的程序進(jìn)行調(diào)試：6個(gè)矩陣連乘積A=A1×A2×A3×A4×A5×A6，各矩陣的維數(shù)分別為：A1：10×20，A2：20×25，A3：25×15，A4：15×5，A5：5×10，A6：10×25。完成測(cè)試。【注意事項(xiàng)】用C語(yǔ)言或C+實(shí)現(xiàn)算法

10、。選擇合適的數(shù)據(jù)結(jié)構(gòu)。注意：是求解完成矩陣連乘的乘法運(yùn)算次數(shù)最少的矩陣連乘次序，而不是求解矩陣連乘的結(jié)果?！菊{(diào)試分析和心得體會(huì)】運(yùn)行依算法寫(xiě)出的程序并分析算法實(shí)現(xiàn)的時(shí)間復(fù)雜度情況。【選做題一】就以圖中所示為測(cè)試數(shù)據(jù)，應(yīng)用動(dòng)態(tài)規(guī)劃策略完成下列問(wèn)題的算法描述并編碼實(shí)現(xiàn)以及對(duì)其復(fù)雜度進(jìn)行分析：圖G<V,E,w>,頂點(diǎn)集V可以劃分為k+1個(gè)兩兩不相交的子集Vi, i=0,1,2,k。其中V0=s,Vk=t。對(duì)G中任一邊<u,v>,存在Vi、Vi+1，使得u屬于Vi，v屬于Vi+1,其中0ik。在G中求s出發(fā)到t的最短路徑。G稱為k段圖。s12345678t42310967103

11、848965448【選做題二】以下列4個(gè)單詞及其出現(xiàn)的概率：cat(0.12)，come(0.08)，of(0.35)，the(0.45)為測(cè)試數(shù)據(jù)，運(yùn)用動(dòng)態(tài)規(guī)劃法構(gòu)造一棵最優(yōu)二分搜索樹(shù)。試完成其算法描述、編碼實(shí)現(xiàn)、復(fù)雜度分析。實(shí)驗(yàn)四（一）：回溯法【實(shí)驗(yàn)?zāi)康摹繎?yīng)用回溯法求解最佳任務(wù)分配方案【實(shí)驗(yàn)要求】待求解問(wèn)題描述為：有n個(gè)人和m項(xiàng)課題任務(wù)（nm），其中第i個(gè)人承擔(dān)了第j項(xiàng)課題任務(wù)的經(jīng)費(fèi)消耗記作COST(i,j)，總體經(jīng)費(fèi)消耗情況有m×n的COST矩陣給定。應(yīng)用回溯法策略求解此問(wèn)題，安排每項(xiàng)課題任務(wù)只能由一個(gè)人來(lái)承擔(dān)，且使完成這m項(xiàng)課題任務(wù)的總經(jīng)費(fèi)消耗為最小?？梢越柚鷨?wèn)題的解空間樹(shù)并

12、以深度優(yōu)先搜索的方式遍歷此樹(shù)，從而獲得問(wèn)題的解。要求完成：算法描述寫(xiě)出程序代碼完成調(diào)試過(guò)程與結(jié)果分析?！緦?shí)驗(yàn)性質(zhì)】綜合型實(shí)驗(yàn)?！緦?shí)驗(yàn)內(nèi)容】應(yīng)用回溯法思想進(jìn)行算法設(shè)計(jì)，并寫(xiě)出程序加以實(shí)現(xiàn)。具體的任務(wù)分配結(jié)果由序號(hào)形式輸出，如最佳方案中第i個(gè)人被分配承擔(dān)第j項(xiàng)課題任務(wù),則輸出(i,j)。當(dāng)最佳方案不止一個(gè)時(shí)（都擁有最小經(jīng)費(fèi)消耗，但人員組成情況不同），輸出所有符合要求的分配方案。考慮到某人不能承擔(dān)某項(xiàng)課題的實(shí)際情況（任務(wù)分配方案不能與人的能力相抵觸），在矩陣COST(i,j)中，當(dāng)?shù)趇個(gè)人不能勝任第j項(xiàng)工作時(shí)，COST(i,j)的值為0。【注意事項(xiàng)】用C語(yǔ)言或C+實(shí)現(xiàn)算法。選擇合適的數(shù)據(jù)結(jié)構(gòu)。取如下

13、測(cè)試數(shù)據(jù)進(jìn)行測(cè)試：10×7的COST矩陣數(shù)據(jù)如下：1234567133.16.215.435.824.510.30216.710.918.214.28.923.616.2317.821.734.68.57.6015.2414.56.86.912.122.77.99.85016.411.228.336.819.522.1614.4025.617.718.99.110.8726.525.819.717.231.532.516.68024.822.419.717.626.518.8916.419.57.68.921.717.88.81021.714.223.67.810.3022.8【調(diào)試

14、分析和心得體會(huì)】討論并分析整個(gè)算法實(shí)現(xiàn)的搜索過(guò)程及時(shí)間復(fù)雜度?！具x做題一】圖的著色問(wèn)題：設(shè)G=(V,E)是一連通無(wú)向圖，有m種顏色，用這些顏色為G的各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色，且相鄰頂點(diǎn)顏色不同。試用回溯法設(shè)計(jì)一個(gè)算法，找出所有可能滿足上述條件的著色法，如果這個(gè)圖不能用m種顏色著色滿足相鄰頂點(diǎn)顏色互異的要求就給出否定的回答?！具x做題二】完成01背包問(wèn)題的回溯求解算法描述、編碼實(shí)現(xiàn)、復(fù)雜度分析。測(cè)試數(shù)據(jù)為n=8，M=10，W=(1,11,21,23,33,43,45,55)， P=(11,21,31,33,43,53,55,65)。實(shí)驗(yàn)四（二）：分枝限界法【實(shí)驗(yàn)?zāi)康摹繎?yīng)用分枝限界法的算法設(shè)計(jì)

15、思想求解旅行商問(wèn)題?！緦?shí)驗(yàn)要求】按照問(wèn)題的描述：旅行商從某城市出發(fā)，遍歷n個(gè)城市最后返回出發(fā)城市。設(shè)從城市i 到城市j的路徑為wij,應(yīng)用分枝限界法選擇旅行路線，使得推銷員的旅行代價(jià)最小。采用優(yōu)先隊(duì)列分枝限界法完成。要求完成：算法描述寫(xiě)出程序代碼完成調(diào)試進(jìn)行過(guò)程與結(jié)果分析?！緦?shí)驗(yàn)性質(zhì)】綜合型實(shí)驗(yàn)?！緦?shí)驗(yàn)內(nèi)容】設(shè)n5，從城市1出發(fā)，經(jīng)過(guò)每個(gè)城市且僅經(jīng)過(guò)一次，回到城市1，且使得總的代價(jià)最小。采用優(yōu)先隊(duì)列分枝限界法完成。下列數(shù)據(jù)，表示各城市之間路徑的矩陣： v1 v2 v3 v4 v5v1 14 1 16 2 v2 14 25 2 3v3 1 25 9 9v4 16 2 9 6 v5 2 3 9 6

16、 【注意事項(xiàng)】用C語(yǔ)言或C+實(shí)現(xiàn)算法。選擇合適的數(shù)據(jù)結(jié)構(gòu)，構(gòu)造適合的估值函數(shù)?！菊{(diào)試分析和心得體會(huì)】討論并分析整個(gè)算法實(shí)現(xiàn)的搜索過(guò)程及時(shí)間復(fù)雜度?！具x做題一】完成01背包問(wèn)題的分枝限界求解算法描述、編碼實(shí)現(xiàn)、復(fù)雜度分析。測(cè)試數(shù)據(jù)為n=8，M=10，W=(1,11,21,23,33,43,45,55)， P=(11,21,31,33,43,53,55,65)。【選做題二】給定n個(gè)作業(yè)的集合J=J1,J2,Jn。每一個(gè)作業(yè)Ji都有2項(xiàng)任務(wù)要分別在2臺(tái)機(jī)器上完成。每一個(gè)作業(yè)必須先由機(jī)器1處理，然后再由機(jī)器2處理。作業(yè)Ji需要機(jī)器j的處理時(shí)間為tji，i=1,2,n；j=1,2。對(duì)于一個(gè)確定的作業(yè)調(diào)度，設(shè)是Fji是作業(yè)i在機(jī)器j上完成處理的時(shí)間。則所有作業(yè)在機(jī)器2上完成處理的時(shí)間和稱為該作業(yè)調(diào)度的完成時(shí)間和。批處理作業(yè)調(diào)度問(wèn)題要求對(duì)于給定的n個(gè)作業(yè)，制定最佳作業(yè)調(diào)度方案，使其完成時(shí)間和達(dá)到最小。試采用分枝限界法完成其算法描述、編碼實(shí)現(xiàn)、復(fù)雜度分析。注意：完成實(shí)驗(yàn)四（一）、（二）之后，對(duì)回溯法與分枝限界法的算法思想及解題思路進(jìn)行對(duì)比分析。