《算法分析與設(shè)計》實驗教學大綱new

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

一、實驗學時總學時：48

總學分：3

實驗學時：10

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

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

五、實驗項目的設(shè)置與內(nèi)容提要

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

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

六、考核方式（1）每次任務(wù)完成后由指導(dǎo)老師逐個的檢查實驗內(nèi)容、結(jié)果并評分，占實驗成績60%。（2）上機考勤評分，占實驗成績10%。（3）實驗報告占實驗成績30%。實驗一排序問題求解實驗?zāi)康?）以排序（分類）問題為例，掌握分治法的基本設(shè)計策略。2）熟練掌握一般插入排序算法的實現(xiàn)；3）熟練掌握快速排序算法的實現(xiàn)；4)理解常見的算法經(jīng)驗分析方法；實驗環(huán)境計算機、C語言程序設(shè)計環(huán)境實驗學時4學時，必做實驗。實驗內(nèi)容與步驟生成實驗數(shù)據(jù).要求：編寫一個函數(shù)datagenetare，生成2000個在區(qū)間[1,10000]上的隨機整數(shù)，并將這些數(shù)輸出到外部文件data.txt中。這些數(shù)作為后面算法的實驗數(shù)據(jù)。實現(xiàn)直接插入排序算法.要求：實現(xiàn)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的函數(shù)：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要求：實現(xiàn)QuickSort算法。算法的輸入是data.txt；輸出記錄為文件：resultsQS.txt；同時記錄運行時間為TimeQS?？焖倥判蛩惴ㄋ枷耄篜rocedureQuickSort（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實驗報告：實驗報告應(yīng)包括以下內(nèi)容：（1）題目；（2）2個算法的基本思想描述；（3）算法理論分析（參考教材）；（4）程序流程圖；（5）給出data.txt、resultsIS.txt、resultsQS.txt三個文件任選其一的清單；TimeIS、TimeQS的記錄結(jié)果；（6）實驗分析；以表或者圖的形式給出這2個算法的經(jīng)驗對比分析結(jié)果；并和理論分析結(jié)論進行對比。（7）說明本次調(diào)試實驗的心得體會、經(jīng)驗等。如果程序未通過，應(yīng)分析其原因。實驗二背包問題求解實驗?zāi)康?）以背包問題為例，掌握貪心法的基本設(shè)計策略。2）熟練掌握各種貪心策略情況下的背包問題的算法并實現(xiàn)；其中：量度標準分別取：效益增量P、物品重量w、P/w比值；3)分析實驗結(jié)果來驗證理解貪心法中目標函數(shù)設(shè)計的重要性。實驗環(huán)境計算機、C語言程序設(shè)計環(huán)境實驗學時2學時，必做實驗。實驗內(nèi)容與步驟理解需要求解背包問題.（1）背包問題的描述：已知有n種物品和一個可容納M重量的背包，每種物品i的重量為。假定將物品i的一部分放入背包就會得到的效益，這里，,。顯然，由于背包容量是M，因此，要求所有選中要裝入背包的物品總重量不得超過M.。如果這n件物品的總重量不超過M，則把所有物品裝入背包自然獲得最大效益?，F(xiàn)需解決的問題是，在這些物品重量的和大于M的情況下，該如何裝包，使得得到更大的效益值。由以上敘述，可將這個問題形式表述如下：極大化目標函數(shù)約束條件（2）用貪心策略求解背包問題首先需確定最優(yōu)的量度標準。這里考慮三種策略：策略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、目標函數(shù)的值fp1（即最后裝好包后背包的效益值）、背包的重量fw1；以策略2作為量度標準求解要求問題，記錄解向量為X21、目標函數(shù)的值fp2（即最后裝好包后背包的效益值）、背包的重量fw2；以策略3作為量度標準求解要求問題，記錄解向量為X3、目標函數(shù)的值fp3即最后裝好包后背包的效益值）、背包的重量fw3；實驗報告：實驗報告應(yīng)包括以下內(nèi)容：（1）題目；（2）算法的基本思想描述；（3）程序流程圖；（4）給出3個程序任意之一的程序清單；（5）實驗分析；通過實驗結(jié)果對比分析說明哪種策略好。（6）說明本次調(diào)試實驗的心得體會、經(jīng)驗等。如果程序未通過，應(yīng)分析其原因。Tips：1.解向量的表示。需要注意：因為算法中涉及到排序，如何保證各種物品的原始命名（如果以第幾種，即序號，來命名物品）關(guān)系需要考慮。#defineMAX200typedefstructSolution//定義的解向量{ intx[MAX];表示該號物品放了多少在背包里，這里intorder[MAX];表示物品的序號，相當于其名字}Solution;SolutionX;所以，初始化時，為：for(i=0;i<n;i++){ X.order[i]=i; X.x[i]=0;}2.主要函數(shù)：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]; } }實驗三最短路徑問題求解實驗?zāi)康模?）以最短路徑問題為例，掌握動態(tài)規(guī)劃的基本設(shè)計策略；2）掌握dijkstra貪心法求解最短路徑問題并實現(xiàn)；3）掌握動態(tài)規(guī)劃方法Floyd算法求解最短路徑問題并實現(xiàn)；3）分析實驗結(jié)果。實驗環(huán)境計算機、C語言程序設(shè)計環(huán)境實驗學時2學時，必做實驗。實驗內(nèi)容與步驟546315463122.然后改寫你的程序，求得所有各點之間的最短距離;輸出保存到文件dijkstra－output2.txt.3.以上圖作為輸入，利用Floyd算法求得所有各點直接的最短距離;輸出保存到文件floyd－output1.txt.實驗報告實驗報告應(yīng)包括以下內(nèi)容：（1）題目；（2）寫出算法設(shè)計思想；（3）程序清單；（4）運行的結(jié)果；（5）對運行情況所作的分析以及本次調(diào)試程序所取的經(jīng)驗。如果程序未通過，應(yīng)分析其原因。Tips:主要函數(shù)voiddijkstra::algorithm()//算法函數(shù){ 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++)//每次找到最優(yōu)的路徑代替原來的路徑for(j=0;j<n;j++)if(graph[i][j]>graph[i][k]+graph[k][j])//狀態(tài)轉(zhuǎn)換條件 {graph[i][j]=graph[i][k]+graph[k][j];//狀態(tài)轉(zhuǎn)換方程}}實驗四：N-皇后問題求解實驗?zāi)康模?1）以Q-皇后問題為例，掌握回溯法的基本設(shè)計策略。 2）掌握回溯法解決Q-皇后問題的算法并實現(xiàn)； 3）分析實驗結(jié)果。實驗環(huán)境 計算機、C語言程序設(shè)計環(huán)境實驗學時 2學時，必做實驗。實驗內(nèi)容與步驟用回溯法求解N-Queen，參考教材算法思想，并實現(xiàn)你的算法。要求：用鍵盤輸入N；輸出此時解的個數(shù)，并統(tǒng)計運算時間。給出N=4,5,6時，N-Queen解的個數(shù)。嘗試增大N，觀察運行情況；并理解該算法的時間復(fù)雜度。實驗報告實驗報告應(yīng)包括以下內(nèi)容：（1）題目；（2）寫出算法設(shè)計思想；（3）運行的結(jié)果；（4）對運行情況所作的分析以及本次調(diào)試程序所取的經(jīng)驗。（5）如果程序未通過，應(yīng)分析其原因。Tips:主要函數(shù)等 while(k>0)//對所有行執(zhí)行以下語句 { 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;}//轉(zhuǎn)向下一行 } 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關(guān)于文件的操作以背包問題為例：例如外部文件為knapsack-input.txt：2,讀入文件的操作：FILE*fp;/*Openforread(willfailiffile"knapsack-input.txt"doesnotexist)*/if((fp=fopen("knapsack-input.t