《算法分析與設計》實驗教學大綱課程編號：10000284課程名稱：算法分析與設計英文名稱：AlgorithmAnalysisandDesign適應專業：軟件工程執筆人：劉淑英實驗教材（指導書）：王曉東，計算機算法設計與分析，電子工業出版社，2007主要參考書目：①張銘、劉曉丹譯電子工業出版社出版的《數據結構與算法分析》②徐士良主編清華大學出版社出版的《計算機常用算法》第二版③盧開澄主編清華大學出版社出版的《計算機指導引論－設計與分析》

一、實驗學時總學時：48

總學分：3

實驗學時：10

二、實驗課的任務、性質與目的《算法設計與分析》是計算機專業的專業核心課程，其先修課程有數據結構和至少一門高級語言。算法設計與分析課程將覆蓋計算機軟件實現中的大部分算法，并具有一定的深度和廣度，使學生對計算機常用算法有一個全盤的了解；通過此課的學習，學生應該具有針對所給的問題設計和實現高效算法的能力。通過上機實驗，將使學生熟悉、掌握課堂教學中所學的大部分算法。同時，上機實習是對學生在軟件設計方面的綜合訓練，包括問題分析，總體結構設計，用戶界面設計，程序設計基本技能和技巧等，以培養良好的編程風格和科學作風。通過理論聯系實際，以最終提高學生動手操作的能力以及分析問題的能力。本課程的主要目的是研究計算機領域及其它有關領域中的主要算法設計方法及一些常用算法，使學生掌握算法設計的常用方法，以便運用這些方法來設計解決一些常用的或較為復雜的實際問題的算法，并力爭做到快捷、有效，從而提高程序設計的質量。同時，還要使學生學會分析算法、估計算法的復雜性，以便理解并科學評估有一個算法的好壞。它屬于技術基礎課，是進行軟件設計的核心內容，是一門實踐性很強的課程。學生應具有C或C++、數據結構的基礎知識。三、實驗內容（1）分治策略算法（4學時）實驗內容：用分治法實現快速排序、歸并分類算法；編寫程序實現循環賽日程表。設有n=2k個運動員要進行網球循環賽。現要設計一個滿足以下要求的比賽日程表：（1）每個選手必須與其它n-1個選手各賽一次（2）每個選手一天只能賽一場（3）循環賽進行n-1天。實驗要求：掌握遞歸算法實現的過程；了解快速排序算法的思想，掌握用算法設計思想解題的思路。（2）貪心算法（2學時）實驗內容：編寫一個簡單的程序，實現單源最短路徑問題；編寫一段程序，實現找零；編寫程序實現多機調度問題。實驗要求：掌握貪心算法的基本設計思路，并用其解決實際問題。（3）動態規劃算法（2學時）實驗內容：編寫一個簡單的程序，解決0-1背包問題；編程解決合唱隊形安排。實驗要求：掌握動態規劃算法設計的基本策略。（4）回溯算法（2學時）實驗內容：用回溯法解8皇后問題；批處理作業調度。實驗要求：掌握回溯法的算法框架和算法的基本思想。

四、實驗要求（1）學生在完成預習報告、熟悉實驗內容后才能進入實驗室進行上機實驗。實驗1人一組，由學生獨立操作完成實驗。（2）學生分析問題，熟悉解決問題的算法描述。要求記錄上機實驗過程，且得到指導教師認可后，學生方可離開實驗室。（3）實驗完成后提交實驗報告。（4）實驗過程由指導老師監督，聽從老師安排和督導。

五、實驗項目的設置與內容提要

本課程主要通過綜合設計性實驗，完成一個問題的算法分析設計過程，培養學生解決設計問題的能力，提高學生綜合設計能力。要求學生通過查閱文獻、小組討論完成實驗任務。

序號實驗項目名稱實驗學時實驗類型實驗要求內容提要1分治策略算法4綜合設計性必做用分治策略解決排序等問題。2貪心算法2綜合設計性必做掌握貪心算法的基本設計思路，并用其解決實際問題。3動態規劃算法2綜合設計性必做掌握動態規劃算法設計的基本策略。4回溯算法2綜合設計性必做掌握回溯算法的基本思想。

六、考核方式（1）每次任務完成后由指導老師逐個的檢查實驗內容、結果并評分，占實驗成績60%。（2）上機考勤評分，占實驗成績10%。（3）實驗報告占實驗成績30%。實驗一排序問題求解實驗目的1）以排序（分類）問題為例，掌握分治法的基本設計策略。2）熟練掌握一般插入排序算法的實現；3）熟練掌握快速排序算法的實現；4)理解常見的算法經驗分析方法；實驗環境計算機、C語言程序設計環境實驗學時4學時，必做實驗。實驗內容與步驟生成實驗數據.要求：編寫一個函數datagenetare，生成2000個在區間[1,10000]上的隨機整數，并將這些數輸出到外部文件data.txt中。這些數作為后面算法的實驗數據。實現直接插入排序算法.要求：實現insertionsort算法。算法的輸入是data.txt；輸出記錄為文件：resultsIS.txt；同時記錄運行時間為TimeIS。直接插入算法思想：Procedureinsertionsort(A,n) A(0)=-￥ forj=2tondo item=A(j);i=j-1 whileitem<A(i)do A(i+1)=A(i);i=i-1 repeat A(i+1)=item repeatEndinsertionsort用A(m)用A(m)劃分集合A的函數：Procedurepartition(m,p) integerm,p,I;globalA(m:p-1) v=A(m);I=mLoop loopI=I+1untilA(I)>=vrepeat loopp=p-1untilA(p)<=vrepeat ifI<p thencallinterchange(A(i),A(p))ElseexitEndifRepeatA(m)=A(p);A(p)=vEndpartition要求：實現QuickSort算法。算法的輸入是data.txt；輸出記錄為文件：resultsQS.txt；同時記錄運行時間為TimeQS。快速排序算法思想：ProcedureQuickSort（p,q）integerp,q；globaln,A(1:n)ifp<qthen j←q+1 callPartition(p,j)callQuickSort(p,j-1) callQuickSort(j+1,q)endifendQuickSort實驗報告：實驗報告應包括以下內容：（1）題目；（2）2個算法的基本思想描述；（3）算法理論分析（參考教材）；（4）程序流程圖；（5）給出data.txt、resultsIS.txt、resultsQS.txt三個文件任選其一的清單；TimeIS、TimeQS的記錄結果；（6）實驗分析；以表或者圖的形式給出這2個算法的經驗對比分析結果；并和理論分析結論進行對比。（7）說明本次調試實驗的心得體會、經驗等。如果程序未通過，應分析其原因。實驗二背包問題求解實驗目的1）以背包問題為例，掌握貪心法的基本設計策略。2）熟練掌握各種貪心策略情況下的背包問題的算法并實現；其中：量度標準分別取：效益增量P、物品重量w、P/w比值；3)分析實驗結果來驗證理解貪心法中目標函數設計的重要性。實驗環境計算機、C語言程序設計環境實驗學時2學時，必做實驗。實驗內容與步驟理解需要求解背包問題.（1）背包問題的描述：已知有n種物品和一個可容納M重量的背包，每種物品i的重量為。假定將物品i的一部分放入背包就會得到的效益，這里，,。顯然，由于背包容量是M，因此，要求所有選中要裝入背包的物品總重量不得超過M.。如果這n件物品的總重量不超過M，則把所有物品裝入背包自然獲得最大效益。現需解決的問題是，在這些物品重量的和大于M的情況下，該如何裝包，使得得到更大的效益值。由以上敘述，可將這個問題形式表述如下：極大化目標函數約束條件（2）用貪心策略求解背包問題首先需確定最優的量度標準。這里考慮三種策略：策略1：按物品價值p降序裝包，策略2：按物品重w升序裝包策略3：按物品價值與重量比值p/w的降序裝包（3）分別以上面三種策略分別求以下情況背包問題的解：n=7，M=15，（）=（10，5，15，7，6，18，3）（）=（2，3，5，7，1，4，1）。以策略3為例的背包問題的貪心算法描述：procedureGREEDY-KNAPSACK(P,W,M,X,n)//P（1：n）和W（1：n）分別含有按P（i）/W（i）≥P（i+1）/W（i+1）排序的n件物品的效益值和重量。M是背包的容量，而X（1：n）是解向量。//realP(1：n)，W（1：n）,X（1：n），M，cu；integeri，n;X0//將解向量初始化為零cuM//cu是背包剩余容量fori1tondoifW(i)>cuthenexitendifX(i)1cucu-W(i)repeatifi≤nthenX(i)cu/W(i)endifendGREEDY-KNAPSACK以策略1作為量度標準求解要求問題，記錄解向量為X1、目標函數的值fp1（即最后裝好包后背包的效益值）、背包的重量fw1；以策略2作為量度標準求解要求問題，記錄解向量為X21、目標函數的值fp2（即最后裝好包后背包的效益值）、背包的重量fw2；以策略3作為量度標準求解要求問題，記錄解向量為X3、目標函數的值fp3即最后裝好包后背包的效益值）、背包的重量fw3；實驗報告：實驗報告應包括以下內容：（1）題目；（2）算法的基本思想描述；（3）程序流程圖；（4）給出3個程序任意之一的程序清單；（5）實驗分析；通過實驗結果對比分析說明哪種策略好。（6）說明本次調試實驗的心得體會、經驗等。如果程序未通過，應分析其原因。Tips：1.解向量的表示。需要注意：因為算法中涉及到排序，如何保證各種物品的原始命名（如果以第幾種，即序號，來命名物品）關系需要考慮。#defineMAX200typedefstructSolution//定義的解向量{ intx[MAX];表示該號物品放了多少在背包里，這里intorder[MAX];表示物品的序號，相當于其名字}Solution;SolutionX;所以，初始化時，為：for(i=0;i<n;i++){ X.order[i]=i; X.x[i]=0;}2.主要函數：voidGreedyKnapsack(floatprofit[],floatweight[],floatx[],intm,intn) { floatcu; inti; cu=float(m); for(i=0;i<n;i++) { x[i]=0; } for(i=0;i<n;i++) { if(weight[i]>cu) break; x[i]=1; cu=cu-weight[i]; } if(i<n) { x[i]=cu/weight[i]; } }實驗三最短路徑問題求解實驗目的：1）以最短路徑問題為例，掌握動態規劃的基本設計策略；2）掌握dijkstra貪心法求解最短路徑問題并實現；3）掌握動態規劃方法Floyd算法求解最短路徑問題并實現；3）分析實驗結果。實驗環境計算機、C語言程序設計環境實驗學時2學時，必做實驗。實驗內容與步驟546315463122.然后改寫你的程序，求得所有各點之間的最短距離;輸出保存到文件dijkstra－output2.txt.3.以上圖作為輸入，利用Floyd算法求得所有各點直接的最短距離;輸出保存到文件floyd－output1.txt.實驗報告實驗報告應包括以下內容：（1）題目；（2）寫出算法設計思想；（3）程序清單；（4）運行的結果；（5）對運行情況所作的分析以及本次調試程序所取的經驗。如果程序未通過，應分析其原因。Tips:主要函數voiddijkstra::algorithm()//算法函數{ initialize(); intcount=0; inti; intu; while(count<num_of_vertices) { u=minimum(); set[++count]=u; mark[u]=1; for(i=1;i<=num_of_vertices;i++) { if(graph[u][i]>0) { if(mark[i]!=1) { if(pathestimate[i]>pathestimate[u]+graph[u][i]) { pathestimate[i]=pathestimate[u]+graph[u][i]; predecessor[i]=u; } } }} }}//---------------------------------------------------------------------------floatgraph[maxsize][maxsize];//成本矩陣，鄰接矩陣//floydalgorithmfor(k=0;k<n;k++) {//graph[i][j]=min{graph[i][j]},graph[i][k]+graph[k][j]for(i=0;i<n;i++)//每次找到最優的路徑代替原來的路徑for(j=0;j<n;j++)if(graph[i][j]>graph[i][k]+graph[k][j])//狀態轉換條件 {graph[i][j]=graph[i][k]+graph[k][j];//狀態轉換方程}}實驗四：N-皇后問題求解實驗目的： 1）以Q-皇后問題為例，掌握回溯法的基本設計策略。 2）掌握回溯法解決Q-皇后問題的算法并實現； 3）分析實驗結果。實驗環境 計算機、C語言程序設計環境實驗學時 2學時，必做實驗。實驗內容與步驟用回溯法求解N-Queen，參考教材算法思想，并實現你的算法。要求：用鍵盤輸入N；輸出此時解的個數，并統計運算時間。給出N=4,5,6時，N-Queen解的個數。嘗試增大N，觀察運行情況；并理解該算法的時間復雜度。實驗報告實驗報告應包括以下內容：（1）題目；（2）寫出算法設計思想；（3）運行的結果；（4）對運行情況所作的分析以及本次調試程序所取的經驗。（5）如果程序未通過，應分析其原因。Tips:主要函數等 while(k>0)//對所有行執行以下語句 { X[k]=X[k]+1;//移到下一列 while(X[k]<=n&&!PLACE(k)) { X[k]=X[k]+1;//移到下一列，再判斷 } if(X[k]<=n)//找到一個位置 { if(k==n)//一個完整的解 { //print printf("thesoutionis:\n"); for(t=1;t<=n;t++) printf("%3d",X[t]); printf("\n"); count+=1; } else {k=k+1;X[k]=0;}//轉向下一行 } else k=k-1;//回溯 } printf("\nthenumberofthesolutionsis%d\n",count);boolPLACE(intk){ i=1; while(i<k) { if(X[i]==X[k]||abs(X[i]-X[k])==abs(i-k)) returnfalse; i=i+1; } returntrue;}附錄1關于文件的操作以背包問題為例：例如外部文件為knapsack-input.txt：2,讀入文件的操作：FILE*fp;/*Openforread(willfailiffile"knapsack-input.txt"doesnotexist)*/if((fp=fopen("knapsack-input.t