《算法分析與設(shè)計(jì)》實(shí)驗(yàn)教學(xué)大綱new

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

一、實(shí)驗(yàn)學(xué)時(shí)總學(xué)時(shí)：48

總學(xué)分：3

實(shí)驗(yàn)學(xué)時(shí)：10

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

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

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

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

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

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