2011-2012(1)《算法分析與設計》上機指導書

PAGEPAGE8《算法分析與設計》實驗指導書（適用于計算機科學與技術、軟件工程專業(yè)）計算機科學與技術學院軟件教研室2011-8目錄TOC\o"2-2"\u實驗一算法分析 3實驗二分治策略 4實驗三堆排序 5實驗四動態(tài)規(guī)劃 6實驗五貪心算法 8實驗六圖算法1-基本圖算法 10實驗七 圖算法2-最小生成樹和單源頂點最短路徑 12實驗八圖算法3-所有點對最短路徑 14附錄一實驗規(guī)范 15實驗一算法分析一、實驗目的及任務1、使學生通過插入排序和合并排序的算法實現，理解算法的概念并且通過運行時間比較其時間復雜度。2、體會合并排序的分治方法的三個步驟：分解、遞歸求解和合并。3、了解漸近記號的意義和初步分析算法復雜性。二、實驗環(huán)境c++或java或Turboc三、問題描述Input:Asequenceofnnumbers<a1,a2,...,an>.Output:Apermutation(reordering)<a1’,a2’,...,an’>oftheinputsequencesuchthata1’a2’四、編程任務給定長度為n的一個序列，對其進行插入排序和合并排序五、數據輸入隨機產生10000以上的數據，放入輸入文件input.txt，用來進行排序六、結果輸出排序后的結果和兩種排序算法的運行時間輸出到文件output.txt七、實驗報告內容見《算法分析與設計》實驗規(guī)范。實驗二分治策略一、實驗目的及任務1、掌握遞歸和分治策略的概念和基本思想，分析并掌握“快速排序”問題的分治算法；2、分治算法思想解決median問題。二、實驗環(huán)境c++或java或Turboc三、問題描述(1)Input:Asequenceofnnumbers<a1,a2,...,an>.Output:Apermutation(reordering)<a1’,a2’,...,an’>oftheinputsequencesuchthata1’a2’(2)Input:AsetAofn(distinct)numbersandanumberi,with1≤i≤n.Output:Theelementx∈Athatislargerthanexactlyi-1otherelementsofA.四、編程任務給定長度為n的一個序列，對其進行快速排序和求第i小數五、數據輸入A=<13,19,9,5,12,8,7,4,11,2,6,21>六、結果輸出將排序結果輸出到文件output.txt。如果不存在所要求的第i小數，則輸出-1。七、實驗報告內容見《算法分析與設計》實驗規(guī)范。實驗三堆排序一、實驗目的及任務1、了解堆的性質；2利用堆構成一個優(yōu)先隊列，并實現相關的函數功能；3為圖算法做好準備。二、實驗環(huán)境c++或java或Turboc三、問題描述ApriorityqueueisadatastructureformaintainingasetSofelements,eachwithanassociatedvaluecalledakey.Amax-priorityqueuesupportsthefollowingoperations..INSERT(S,x)insertstheelementxintothesetS.ThisoperationcouldbewrittenasS←S∪{x}..MAXIMUM(S)returnstheelementofSwiththelargestkey..EXTRACT-MAX(S)removesandreturnstheelementofSwiththelargestkey..INCREASE-KEY(S,x,k)increasesthevalueofelementx'skeytothenewvaluek,whichisassumedtobeatleastaslargeasx'scurrentkeyvalue.四、編程任務編程建立最大堆，構造優(yōu)先隊列并實現以上的相關操作。五、數據輸入A=<15，13，9，5，12，8，7，4，0，6，2，1>六、結果輸出執(zhí)行INSERT(A,10)，EXTRACT-MAX(A)，將結果輸出到文件output.txt。七、實驗報告內容見《算法分析與設計》實驗規(guī)范。實驗四動態(tài)規(guī)劃一、實驗目的及任務掌握動態(tài)規(guī)劃算法的基本步驟：找出最優(yōu)解的性質，并刻畫其結構特征；遞歸地定義最優(yōu)值；以自底向上的方式計算出最優(yōu)值；根據計算最優(yōu)值時得到的信息，構造最優(yōu)解。熟悉最長公共子序列問題的算法，設計一個算法解決編輯距離問題。二、實驗環(huán)境c++或java或Turboc三、問題描述

1若給定序列X={x1,x2,…,xm}，則另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一個嚴格遞增下標序列{i1,i2,…,ik}使得對于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相應的遞增下標序列為{2，3，5，7}。給定2個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。給定2個序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長公共子序列。2設A和B是2個字符串。要用最少的字符操作將字符串A轉換為字符串B。這里所說的字符操作包括：山出一個字符、插入一個字符、將一個字符改為另一個字符。將字符串A變換為字符串B所用的最少字符操作稱為字符串A到字符串B的編輯距離，記為d(A,B)。試設計一個有效算法，對任意給定的兩個字符串，計算出它們的編輯距離d(A,B)。四、編程任務1求X和Y的最長公共子序列長度以及最長公共子序列2對于給定的字符串A和字符串B，編程計算其編輯距離d(A,B)。五、數據輸入由文件input.txt提供輸入數據，X={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A}。由文件input.txt提供輸入數據。文件的第1行是字符串A，文件的第2行是字符串B。A:fxpimuB:xwrs六、結果輸出1程序運行結束時，將編程計算出的最長公共子序列長度以及最長公共子序列輸出到文件output.txt中。2程序運行結束時，將編輯距離d(A,B)輸出到文件output.txt的第1行中。七、實驗報告內容見《算法分析與設計》實驗規(guī)范。實驗五貪心算法一、實驗目的及任務1、掌握貪心算法的基本性質。2貪心算法與動態(tài)規(guī)劃的區(qū)別。3貪心算法解決活動安排問題和背包問題。二、實驗環(huán)境c++或java或Turboc三、問題描述

1有n個活動的集合E={1,2,…,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi,且si<fi。如果選擇了活動i，則它在半開時間區(qū)間[si,fi]內占用資源。若區(qū)間[si,fi]與區(qū)間[sj,fj]不相交，則稱活動i與活動j是相容的。也就是說，當si≥fj或sj≥fi時，活動i與活動j相容?；顒影才艈栴}就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。20-1背包問題：給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?背包問題：與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。四、編程任務1在所給的活動集合中選出最大的相容活動子集合。2計算背包問題/0-1背包問題背包的價值五、數據輸入1i1234567891011si130535688212fi45678910111213142W={10,100,120}V={10,20,30}C=50六、結果輸出1、將編程計算出的最長最大活動安排結果輸出到文件output1.txt。2、將編程計算出的背包價值輸出到文件output2.txt。七、實驗報告內容見《算法分析與設計》實驗規(guī)范。實驗六圖算法1-基本圖算法一、實驗目的及任務1、掌握圖鄰接表的存儲方法；2、掌握深度優(yōu)先遍歷算法(DFS)；3、利用深度優(yōu)先遍歷的timestamps進行拓撲排序或計算有向圖的強連通分支；二、實驗環(huán)境c++或java或Turboc三、問題描述GivenG=(V,E)InDFS,edgesareexploredoutthemostrecentlydiscoveredvertexvthatstillhasunexplorededgesleavingit.Whenv'sedgeshavebeenexplored,thesearch"backtracks"toexploreedgesleavingthevertexfromwhichvwasdiscovered.Besidescreatingadepth-firstforest,DFSalsotimestampseachvertex.Eachvertexvhastwotimestamps:thefirsttimestampd[v]recordswhenvisfirstdiscovered,andthesecondonef[v]recordswhenthesearchfinishesexaminingv'sadjacencylist.Atopologicalsortofadirectedacyclicgraph(DAG)G=(V;E)isalinearorderingofallitsverticessuchthatifGcontainsanedge(u;v),thenuappearsbeforevintheordering(ifthegraphiscyclic,thennolinearorderingispossible).Astronglyconnectedcomponent(SCC)ofadirectedgraphG=(V;E)isamaximalsubsetofverticesCVsuchthatu,vC,wehaveu→vandv→u.四、編程任務1、深度優(yōu)先遍歷；2、利用深度優(yōu)先遍歷的timestamps進行拓撲排序；3、利用深度優(yōu)先遍歷的timestamps進行有向圖的強連通分支；五、數據輸入六、結果輸出1、將編程計算出深度優(yōu)先遍歷結果輸出到文件output1.txt；2、將編程進行拓撲排序結果輸出到文件output2.txt；3、將編程進行有向圖的強連通分支的結果輸出到文件output3.txt。七、實驗報告內容見《算法分析與設計》實驗規(guī)范。實驗七圖算法2-最小生成樹和單源頂點最短路徑一、實驗目的及任務1、應用優(yōu)先隊列求最小生成樹的Prim算法，了解其中的貪心算法的設計思想；2、應用優(yōu)先隊列求單源頂點的最短路徑Dijkstra算法，了解貪心算法的設計思想，并掌握松弛技巧。二、實驗環(huán)境c++或java或Turboc三、問題描述1、Givenaconnected,undirectedgraphG=(V,E),where(u,v)∈Ehasaweightw(u,v).WeintendtofindanacyclicsubsetTEthatconnectsalltheverticesandwhosetotalweightw(T)=isminimized.SinceTisacyclicandconnectsallvertices,itmustbeatree,calledspanningtree.TheproblemtofindsuchTiscalledminimumspanningtree(MST)problem.2、Dijkstra'salgorithmsolvesthesingle-sourceshortest-pathsproblemonaweighted,directedgraphG=(V,E)forthecaseinwhichalledgeweightsarenonnegative.Dijkstra'salgorithmmaintainsasetSofverticeswhosefinalshortest-pathweightsfromthesourceshavealreadybeendetermined.Thealgorithmrepeatedlyselectsthevertexu∈V–Swiththeminimumshortest-pathestimate,addsutoS,andrelaxesalledgesleavingu.四、編程任務對于給定的賦權圖G，編程計算圖的最大邊權最小生成樹。2、對于給定的賦權圖G，編程計算圖的單源頂點最短路徑。五、數據輸入1由文件input.txt給出輸入數據。第1行有2個正整數n和m，表示給定的圖G有n個頂點和m條邊，頂點編號為1，2，…，n。接下來的m行中，每行有3個正整數u,v,w，表示圖G的一條邊(u,v)及其邊權w。2六、結果輸出1將編程計算出的最大邊權最小生成樹的最大邊權輸出到文件output1.txt。如果不存在所要求的最大邊權最小生成樹，則輸出-1。輸入文件示例input.txt79122816102714231665257524741834125422輸出文件示例output.txt252將編程計算出單源頂點最短路徑結果輸出到output2.txt。七、實驗報告內容見《算法分析與設計》實驗規(guī)范實驗八圖算法3-所有點對最短路徑一、實驗目的及任務1、掌握Matrixmultiplication和Floyd-Warshallalgorithm的實現；2、了解這兩種算法的不同；3、進一步了解所有點對最短路徑問題中的動態(tài)規(guī)劃設計思想。二、實驗環(huán)境c++或java或Turboc三、問題描述Givenaweighted,directedgraphG=(V,E),foranyu,v∈V,findashortestpathfromutov.四、編程任務對于給定的賦權有向圖G，編程計算圖的所有點對的最短路徑。五、數據輸入六、結果輸出將編程計算出的所有點對的最短路徑輸出到文件output.txt。七、實驗報告內容見《算法分析與設計》實驗規(guī)范《算法分析與設計》實驗規(guī)范一、實驗課的意義

實驗是對學生的一種全面綜合訓練。是與課堂聽講、自學和練習相輔相成的必不可少的一個教學環(huán)節(jié)。通常，實驗題中的問題比平時的習題復雜得多，也更接近實際。實驗著眼于原理與應用的結合點，使學生學會如何把書上學到的知識用于解決實際問題，培養(yǎng)軟件工作所需要的動手能力；另一方面，能使書上的知識變"活"，起到深化理解和靈活掌握教學內容的目的。平時的練習較偏重于如何編寫功能單一的"小"算法，而實驗題是軟件設計的綜合訓練，包括問題分析、總體結構設計、用戶界面設計、程序設計基本技能和技巧，多人合作，以至一整套軟件工作規(guī)范的訓練和科學作風的培養(yǎng)。二、實驗步驟

常用的軟件開發(fā)方法，是將軟件開發(fā)過程劃分為分析、設計、實現和維護四個階段。雖然算法分析與設計課程中的實驗題目的遠不如從實際問題中的復雜程度高，但為了培養(yǎng)一個軟件工作者所應具備的科學工作的方法和作風，也應遵循以下五個步驟來完成實驗題目：1．問題分析和任務定義在進行設計之前，首先應該充分地分析和理解問題，明確問題要求做什么?限制條件是什么。本步驟強調的是做什么?而不是怎么做。對問題的描述應避開算法和所涉及的數據類型，而是對所需完成的任務作出明確的回答。例如：輸入數據的類型、值的范圍以及輸入的形式；輸出數據的類型、值的范圍及輸出的形式；若是會話式的輸入，則結束標志是什么?是否接受非法的輸入?對非法輸入的回答方式是什么等。還應該為調試程序準備好測試數據，包括合法的輸入數據和非法形式的輸入數據。2．邏輯設計和詳細設計在設計這一步驟中需分邏輯設計和詳細設計兩步實現。邏輯設計指的是，對問題描述中涉及的操作對象定義相應的數據類型，并按照以數據結構為中心的原則劃分模塊，定義主程序模塊和各抽象數據類型；詳細設計則為定義相應的存儲結構并寫出各函數的偽碼算法。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結構清晰、合理、簡單和易于調試，抽象數據類型的實現盡可能做到數據封裝，基本操作的規(guī)格說明盡可能明確具體。作為邏輯設計的結果，應寫出每個抽象數據類型的定義(包括數據結構的描述和每個基本操作的功能說明)，各個主要模塊的算法，并畫出模塊之間的調用關系圖。詳細設計的結果是對數據結構和基本操作作出進一步的求精，寫出數據存儲結構的類型定義，寫出函數形式的算法框架。在求精的過程中，應盡量避免陷入語言細節(jié)，不必過早表述輔助數據結構和局部變量。3．編碼實現和靜態(tài)檢查編碼是把詳細設計的結果進一步求精為程序設計語言程序。如果基于詳細設計的偽碼算法就能直接在鍵盤上輸入程序的話，則可以不必用筆在紙上寫出編碼，而將這一步的工作放在上機準備之后進行，即在上機調試之前直接用鍵盤輸入。然而，不管你是否寫出編碼的程序，在上機之前，認真的靜態(tài)檢查是必不可少的。靜態(tài)檢查主要有兩種方法，一是用一組測試數據手工執(zhí)行程序(通常應先分模塊檢查)；二是通過對程序深入全面地理解程序邏輯，在這個過程中再加入一些注解和斷言。如果程序中邏輯概念清楚，后者將比前者有效。4．上機準備和上機調試上機準備包括以下幾個方面：

(1)注意同一高級語言文本之間的差別。

(2)熟悉機器的操作系統(tǒng)和語言集成環(huán)境的用戶手冊，尤其是最常用的命令操作，以便順利進行上機的基本活動。(3)掌握調試工具，考慮調試方案，設計測試數據