太原理工大學(xué)算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告

1、.本科實(shí)驗(yàn)報(bào)告課程名稱(chēng)： 算法設(shè)計(jì)與分析 實(shí)驗(yàn)項(xiàng)目：分治法合并排序 貪心法作業(yè)調(diào)度 動(dòng)態(tài)規(guī)劃法求多段圖問(wèn)題 回溯法求n皇后問(wèn)題 實(shí)驗(yàn)地點(diǎn)： 致遠(yuǎn)樓B503 專(zhuān)業(yè)班級(jí)： 學(xué)號(hào)： 學(xué)生姓名： 指導(dǎo)教師： 2017年 3月18日實(shí)驗(yàn)1 分治法合并排序一、實(shí)驗(yàn)?zāi)康?. 掌握合并排序的基本思想2. 掌握合并排序的實(shí)現(xiàn)方法3. 學(xué)會(huì)分析算法的時(shí)間復(fù)雜度4. 學(xué)會(huì)用分治法解決實(shí)際問(wèn)題二、實(shí)驗(yàn)內(nèi)容隨機(jī)產(chǎn)生一個(gè)整型數(shù)組，然后用合并排序?qū)⒃摂?shù)組做升序排列，要求輸出排序前和排序后的數(shù)組。三、實(shí)驗(yàn)環(huán)境Window10;惠普筆記本；Dev cpp4、 算法描述和程序代碼#include#include#include#

2、includeusing namespace std;#define random(x)(rand()%x);int a10;/合并排序函數(shù)。void Merge(int left, int mid, int right) int t11;int i = left, j = mid + 1, k = 0;while (i = mid) & (j = right) if (ai = aj)tk+ = ai+;elsetk+ = aj+;while (i = mid)tk+ = ai+;while (j = right)tk+ = aj+;for (i = 0, k = left; k = rig

3、ht;)ak+ = ti+;/分劃函數(shù)，并且調(diào)用合并函數(shù)。void MergeSort(int left, int right) if (left right) int mid = (left + right) / 2);MergeSort(left, mid);MergeSort(mid + 1, right);Merge(left, mid, right); /調(diào)用合并函數(shù)。int main() int i;cout 排序前的數(shù)組為：;for (i = 0; i 10; i+) ai = random(100); /調(diào)用random函數(shù)，產(chǎn)生10個(gè)0-100的隨機(jī)數(shù)。cout ai ;co

4、ut endl;MergeSort(0, 9);cout 排序后的數(shù)組為：;for (i = 0; i 10; i+) cout ai ;getchar();return 0;五、實(shí)驗(yàn)結(jié)果截圖六、實(shí)驗(yàn)總結(jié)通過(guò)編寫(xiě)這個(gè)程序，我進(jìn)一步了解了分株算法的思想，在實(shí)際運(yùn)用過(guò)程當(dāng)中，尤其是在算法編寫(xiě)方面相對(duì)來(lái)說(shuō)比較簡(jiǎn)單，實(shí)現(xiàn)起來(lái)較為容易。實(shí)驗(yàn)2 貪心法作業(yè)調(diào)度一、實(shí)驗(yàn)?zāi)康?. 掌握貪心算法的基本思想2. 掌握貪心算法的典型問(wèn)題求解3. 進(jìn)一步多級(jí)調(diào)度的基本思想和算法設(shè)計(jì)方法4. 學(xué)會(huì)用貪心法分析和解決實(shí)際問(wèn)題二、實(shí)驗(yàn)內(nèi)容設(shè)計(jì)貪心算法實(shí)現(xiàn)作業(yè)調(diào)度，要求按作業(yè)調(diào)度順序輸出作業(yè)序列。如已知n=8，效益p=(35

5、,30,25,20,15,10,5,1)，時(shí)間期限d=(4,2,4,5,6,4,5,7)，求該條件下的最大效益。三、實(shí)驗(yàn)環(huán)境Window10;惠普筆記本；Dev cpp四、算法描述和程序代碼#include using namespace std;const int Work8 = 45,30,28,25,23,15,10,1 ;/所有作業(yè)按收益從大到小排序const int maxTime8 = 4,7,3,2,4,6,7,5 ;class HomeWork private:int res8;bool flag8;int maxReap;public:void dealWith() /遍歷所

6、有作業(yè):int i;for (i = 0; i= 0; j-)if (!flagj) resj = Worki;flagj = true;break;cout 作業(yè)完成順序?yàn)? ;for (i = 0; i7; i+) cout resi t;cout endl;cout endl 最佳效益為:;int j;for (j = 0; j7; j+)maxReap += resj;cout maxReap endl;HomeWork()int i;for(i = 0;i2個(gè)不相交的子集Vi，1i=k，其中V1和Vk分別只有一個(gè)頂點(diǎn)s（源）和一個(gè)頂點(diǎn)t（匯）。圖中所有邊的始點(diǎn)和終點(diǎn)都在相鄰的兩個(gè)子集

7、Vi和Vi+1中。求一條s到t的最短路線。參考課本P124圖7-1中的多段圖，試選擇使用向前遞推算法或向后遞推算法求解多段圖問(wèn)題。三、實(shí)驗(yàn)環(huán)境Window10;惠普筆記本；Dev cpp四、算法描述和程序代碼#includeint V5050;int a50,b20;int static k,n,m;void createGraph() int i,j,t,s; printf(請(qǐng)輸入結(jié)點(diǎn)數(shù)：); scanf(%d,&n); for(i=0; i=n; i+) for(j=0; j=n; j+) Vij=0;/初始化Vij=0,表示兩結(jié)點(diǎn)沒(méi)有邊相連 printf(輸入圖的層數(shù)：); scanf(

8、%d,&k); printf(請(qǐng)輸入每層的結(jié)點(diǎn)數(shù)的最大編號(hào)：); a0=0; for(i=1; i=k; i+) scanf(%d,&ai); printf(請(qǐng)輸入邊數(shù)：); scanf(%d,&m); printf(請(qǐng)輸入結(jié)點(diǎn)之間的關(guān)系(如：結(jié)點(diǎn)i和結(jié)點(diǎn)j的距離為s，則輸入i,j,s)n); for(t=1; t=m; t+) scanf(%d%d%d,&i,&j,&s); Vij=s; int Backward()/向后求解法 int i,j,t,r; for(i=a1+1; i=a2; i+) /把第二層每個(gè)結(jié)點(diǎn)i與第一層結(jié)點(diǎn)s的邊距賦值給Vii Vii=V1i; for(r=2; rk

9、; r+) /向后逐層求解 for(i=ar-1+1; i=ar; i+) /遍歷第r層的每個(gè)結(jié)點(diǎn)i與第(r+1)層結(jié)點(diǎn)j之間的邊距,選擇此刻最優(yōu)解 for(j=ar+1; j=ar+1; j+) if(Vij!=0&Vjj=0)/第一次把此刻路徑長(zhǎng)度賦給Vjj Vjj=Vii+Vij; else if(Vij!=0&Vjj!=0) if(Vii+Vij)=2; r-) for(i=ar+1; i=ar+1; i+) if(br=j) break; for(j=ar-1+1; j=ar; j+) if(Vii-Vji)=Vjj) br=j; break; return Vnn;int Forw

10、ard()/向前求解法 int i,j,t,r; for(i=ak-2+1; i1; r-) /向前逐層求解 for(j=ar-1+1; j=ar; j+)/遍歷第r層的每個(gè)結(jié)點(diǎn)i與第(r-1)層結(jié)點(diǎn)j之間的邊距,選擇此刻最優(yōu)解 for(i=ar-2+1; i=ar-1; i+) if(Vij!=0&Vii=0)/第一次把此刻路徑長(zhǎng)度賦給Vjj Vii=Vjj+Vij; else if(Vij!=0&Vii!=0) if(Vjj+Vij)Vii) Vii=Vjj+Vij; for(r=2; r=k-1; r+) for(i=ar-2+1; i=ar-1; i+) for(j=ar-1+1; j

11、=ar; j+) if(Vii-Vij)=Vjj) br=j; break; i=j; r+; return V11;int main() int i,j,r,sp; createGraph(); b1=1; bk=n; /sp=Forward(); sp=Backward(); printf(最短路徑長(zhǎng)度為：%dn,sp); printf(最短路徑為：); printf(%d,b1); for(i=2; i%d,bi); return 0;五、實(shí)驗(yàn)結(jié)果截圖6、 實(shí)驗(yàn)總結(jié)這個(gè)實(shí)驗(yàn)讓我從中懂得了動(dòng)態(tài)規(guī)劃算法的核心，更加收斂的運(yùn)用動(dòng)態(tài)規(guī)劃算法秋節(jié)各類(lèi)問(wèn)題，但動(dòng)態(tài)規(guī)劃算法最重要的還是方程的選擇，這個(gè)

12、在實(shí)際運(yùn)用中相當(dāng)重要。實(shí)驗(yàn)4回溯法求n皇后問(wèn)題一、實(shí)驗(yàn)?zāi)康?. 掌握回溯算法的基本思想2. 通過(guò)n皇后問(wèn)題求解熟悉回溯法3. 使用蒙特卡洛方法分析算法的復(fù)雜度二、實(shí)驗(yàn)內(nèi)容要求在一個(gè)8*8的棋盤(pán)上放置8個(gè)皇后，使得它們彼此不受“攻擊”。兩個(gè)皇后位于棋盤(pán)上的同一行、同一列或同一對(duì)角線上，則稱(chēng)它們?cè)诨ハ喙簟，F(xiàn)在要找出使得棋盤(pán)上8個(gè)皇后互不攻擊的布局。三、實(shí)驗(yàn)環(huán)境Window10;惠普筆記本；Dev cpp四、算法描述和程序代碼#include#include using namespace std;#define N 8int res1008;int countRes = 0;bool Place

13、(int k,int i,int *x) for(int j = 0;jk;j+) if(xj = i | abs(xj-i) = abs(j-k) return false; return true;void NQueen(int k,int n,int *x) for(int i = 0;in;i+) if(Place(k,i,x) xk = i; if(k = n-1) for (i = 0; i n; i+) rescountResi = xi; cout xi t; countRes+; cout endl; else NQueen(k+1,n,x); void NQueen(int n,int *x) NQueen(0,n,x);int main() int xN; for(int i = 0;iN;i+) *(x+i) = -10; NQueen(N,x); coutendl共countRes種解endl; char show; cout是否顯示圖示?(Y/N)show; if(show = Y | show = y) for(int n = 0;n