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

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

2、de#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 =

3、right;)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ù)。void 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

4、 ;cout endl;MergeSort(0, 9);cout 排序后的數(shù)組為：;for (i = 0; i 10; i+) cout ai ;getchar();五、實(shí)驗(yàn)結(jié)果截圖六、實(shí)驗(yàn)總結(jié)分治算法是很有用的算法，分治法的設(shè)計(jì)一般是遞歸的。兩路合并排序是一個(gè)典型的分治算法，其基本運(yùn)算為元素比較，最壞情況下的時(shí)間為W(n)=O(nlogn)，在排序過程中需要使用與原序列相同長度的輔助數(shù)組temp，因此它所需的額外空間為O(n)。通過編寫代碼，我很好的掌握了分治法的步驟：劃分；求解子問題；合并。對“分治策略”有了更深的體會，它將原問題劃分為彼此獨(dú)立的、規(guī)模較小而結(jié)構(gòu)相同的子問題。實(shí)驗(yàn)2 貪心法

5、作業(yè)調(diào)度一、實(shí)驗(yàn)?zāi)康?. 掌握貪心算法的基本思想2. 掌握貪心算法的典型問題求解3. 進(jìn)一步多級調(diào)度的基本思想和算法設(shè)計(jì)方法4. 學(xué)會用貪心法分析和解決實(shí)際問題二、實(shí)驗(yàn)內(nèi)容設(shè)計(jì)貪心算法實(shí)現(xiàn)作業(yè)調(diào)度，要求按作業(yè)調(diào)度順序輸出作業(yè)序列。如已知n=8，效益p=(35,30,25,20,15,10,5,1)，時(shí)間期限d=(4,2,4,5,6,4,5,7)，求該條件下的最大效益。三、實(shí)驗(yàn)環(huán)境Window7;惠普筆記本；VC+6.0.四、算法描述和程序代碼#include using namespace std;const int Work8 = 35,30,25,20,15,10,5,1 ;/所有作業(yè)按收

6、益從大到小排序const int maxTime8 = 4,2,4,5,6,4,5,7 ;class HomeWork private:int res8;bool flag8;int maxReap;public:void dealWith() /遍歷所有作業(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+

7、)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è)子集Vi和Vi+1中。求一條s到t的最短路線。參考課本P124圖7-1中的多段圖，試選擇使用向前遞推算法或向后遞推算法求解多段圖問題。三、實(shí)驗(yàn)環(huán)境Window7;惠普筆記本；VC+6.0.四、算法描述和程序代碼#includeusing namespace std;structint r50;int length;SqList, L;void MS

8、ort(int SR, int TR1, int s, int t);void Merge(int sR, int TR, int i, int mid, int n);void main()cout L.length;cout 請輸入待排序的數(shù):;for (int c = 0; c L.rc;cout 合并排序前的數(shù)組為:;for (int d = 0; dL.length; d+)cout L.rd ;cout endl;MSort(L.r, L.r, 0, L.length - 1);cout 合并排序后的數(shù)組為:;for (int i3 = 0; i3L.length; i3+)cou

9、t L.ri3 ;cout endl;void MSort(int SR, int TR1, int s, int t) /兩路合并排序int mid;int TR2100;if (s = t)TR1s = SRs;else /若序列的長度超過1，則劃分為兩個(gè)子序列mid = (s + t) / 2; /將待排序的序列一分為二MSort(SR, TR2, s, mid); /對左子序列排序MSort(SR, TR2, mid + 1, t); /對右子序列排序Merge(TR2, TR1, s, mid, t); /將兩個(gè)有序子序列合并成一個(gè)有序序列void Merge(int SR, int

10、 TR, int i, int mid, int n) /將兩個(gè)有序序列合并成一個(gè)有序序列int j, k;for (j = mid + 1, k = i; i = mid&j = n; +k)if (SRi = SRj)TRk = SRi+;elseTRk = SRj+;if (i = mid) /如果左子序列還有元素未輸出，則將左子序列剩余元素依次輸出int k1 = k;for (int i1 = i; i1 = mid; i1+)TRk1 = SRi1;k1+;if (j = n) /如果右子序列還有元素未輸出，則將右子序列剩余元素依次輸出int k2 = k;for (int j2

11、= j; j2 = n; j2+)TRk2 = SRj2;k2+;五、實(shí)驗(yàn)結(jié)果截圖6、 實(shí)驗(yàn)總結(jié)通過這次實(shí)驗(yàn)使得我對應(yīng)用動態(tài)規(guī)劃法求解問題有了很大的提高。動態(tài)規(guī)劃算法將原問題歸約為規(guī)模較小、結(jié)構(gòu)相同的子問題，建立原問題與子問題優(yōu)化函數(shù)間的依賴關(guān)系，從規(guī)模較小的子問題開始，利用上述依賴關(guān)系求解規(guī)模更大的子問題，直到得到原始問題的解為止。采用逐步向前遞推的方式，由子問題的最優(yōu)解來計(jì)算原問題的最優(yōu)解。算法所用空間除鄰接矩陣和最優(yōu)解path以外，還需要長度為n的cost和d兩個(gè)局部以為數(shù)組。這一算法的時(shí)間分析與DFS和BFS相似，總的執(zhí)行時(shí)間為(n)實(shí)驗(yàn)4回溯法求n皇后問題一、實(shí)驗(yàn)?zāi)康?. 掌握回溯算

12、法的基本思想2. 通過n皇后問題求解熟悉回溯法3. 使用蒙特卡洛方法分析算法的復(fù)雜度二、實(shí)驗(yàn)內(nèi)容要求在一個(gè)8*8的棋盤上放置8個(gè)皇后，使得它們彼此不受“攻擊”。兩個(gè)皇后位于棋盤上的同一行、同一列或同一對角線上，則稱它們在互相攻擊?，F(xiàn)在要找出使得棋盤上8個(gè)皇后互不攻擊的布局。三、實(shí)驗(yàn)環(huán)境Window7;惠普筆記本；VC+6.0.四、算法描述和程序代碼#includeusing namespace std;#define N 8int res1008;int countRes = 0;bool Place(int k,int i,int *x) for(int j = 0;jk;j+) if(xj

13、 = 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;ncountRes;n+) cout第n+1個(gè)解:endl; for(int i = 0;iN;i+) for(int j = 0;jN;j+