太原理工大學算法設(shè)計與分析實驗報告

1、.本科實驗報告課程名稱： 算法設(shè)計與分析 實驗項目：分治法合并排序 貪心法作業(yè)調(diào)度 動態(tài)規(guī)劃法求多段圖問題 回溯法求n皇后問題 實驗地點： 致遠樓B503 專業(yè)班級： 學號： 學生姓名： 指導教師： 2017年 3月18日實驗1 分治法合并排序一、實驗目的1. 掌握合并排序的基本思想2. 掌握合并排序的實現(xiàn)方法3. 學會分析算法的時間復雜度4. 學會用分治法解決實際問題二、實驗內(nèi)容隨機產(chǎn)生一個整型數(shù)組，然后用合并排序?qū)⒃摂?shù)組做升序排列，要求輸出排序前和排序后的數(shù)組。三、實驗環(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個0-100的隨機數(shù)。cout ai ;co

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

5、,30,25,20,15,10,5,1)，時間期限d=(4,2,4,5,6,4,5,7)，求該條件下的最大效益。三、實驗環(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è)完成順序為: ;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個不相交的子集Vi，1i=k，其中V1和Vk分別只有一個頂點s（源）和一個頂點t（匯）。圖中所有邊的始點和終點都在相鄰的兩個子集

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

8、%d,&k); printf(請輸入每層的結(jié)點數(shù)的最大編號：); a0=0; for(i=1; i=k; i+) scanf(%d,&ai); printf(請輸入邊數(shù)：); scanf(%d,&m); printf(請輸入結(jié)點之間的關(guān)系(如：結(jié)點i和結(jié)點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+) /把第二層每個結(jié)點i與第一層結(jié)點s的邊距賦值給Vii Vii=V1i; for(r=2; rk

9、; r+) /向后逐層求解 for(i=ar-1+1; i=ar; i+) /遍歷第r層的每個結(jié)點i與第(r+1)層結(jié)點j之間的邊距,選擇此刻最優(yōu)解 for(j=ar+1; j=ar+1; j+) if(Vij!=0&Vjj=0)/第一次把此刻路徑長度賦給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層的每個結(jié)點i與第(r-1)層結(jié)點j之間的邊距,選擇此刻最優(yōu)解 for(i=ar-2+1; i=ar-1; i+) if(Vij!=0&Vii=0)/第一次把此刻路徑長度賦給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(最短路徑長度為：%dn,sp); printf(最短路徑為：); printf(%d,b1); for(i=2; i%d,bi); return 0;五、實驗結(jié)果截圖6、 實驗總結(jié)這個實驗讓我從中懂得了動態(tài)規(guī)劃算法的核心，更加收斂的運用動態(tài)規(guī)劃算法秋節(jié)各類問題，但動態(tài)規(guī)劃算法最重要的還是方程的選擇，這個

12、在實際運用中相當重要。實驗4回溯法求n皇后問題一、實驗目的1. 掌握回溯算法的基本思想2. 通過n皇后問題求解熟悉回溯法3. 使用蒙特卡洛方法分析算法的復雜度二、實驗內(nèi)容要求在一個8*8的棋盤上放置8個皇后，使得它們彼此不受“攻擊”。兩個皇后位于棋盤上的同一行、同一列或同一對角線上，則稱它們在互相攻擊?，F(xiàn)在要找出使得棋盤上8個皇后互不攻擊的布局。三、實驗環(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