1、本科實驗報告課程名稱： 算法設計與分析 實驗項目：分治法合并排序 貪心法作業調度 動態規劃法求多段圖問題 回溯法求n皇后問題 實驗地點： 專業班級： 學號： 學生姓名： 指導教師： 實驗1 分治法合并排序一、實驗目的1. 掌握合并排序的基本思想2. 掌握合并排序的實現方法3. 學會分析算法的時間復雜度4. 學會用分治法解決實際問題二、實驗內容隨機產生一個整型數組，然后用合并排序將該數組做升序排列，要求輸出排序前和排序后的數組。三、實驗環境window10;惠普筆記本；dev cpp4、 算法描述和程序代碼#include<stdlib.h>#include<iostream&

2、gt;#include<stdio.h>#include<time.h>using namespace std;#define random(x)(rand()%x);int a10;/合并排序函數。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)

3、tk+ = ai+;while (j <= right)tk+ = aj+;for (i = 0, k = left; k <= right;)ak+ = ti+;/分劃函數，并且調用合并函數。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); /調用合并函數。int main() int i;cout <<

4、 "排序前的數組為："for (i = 0; i < 10; i+) ai = random(100); /調用random函數，產生10個0-100的隨機數。cout << ai << " "cout << endl;mergesort(0, 9);cout << "排序后的數組為："for (i = 0; i < 10; i+) cout << ai << " "getchar();return 0;五、實驗結果截圖六、實驗總結

5、通過編寫這個程序，我進一步了解了分株算法的思想，在實際運用過程當中，尤其是在算法編寫方面相對來說比較簡單，實現起來較為容易。實驗2 貪心法作業調度一、實驗目的1. 掌握貪心算法的基本思想2. 掌握貪心算法的典型問題求解3. 進一步多級調度的基本思想和算法設計方法4. 學會用貪心法分析和解決實際問題二、實驗內容設計貪心算法實現作業調度，要求按作業調度順序輸出作業序列。如已知n=8，效益p=(35, 30, 25, 20, 15, 10, 5, 1)，時間期限 d=(4, 2, 4, 5,

6、 6, 4, 5, 7)，求該條件下的最大效益。三、實驗環境window10;惠普筆記本；dev cpp四、算法描述和程序代碼#include <iostream>using namespace std;const int work8 = 45,30,28,25,23,15,10,1 ;/所有作業按收益從大到小排序const int maxtime8 = 4,7,3,2,4,6,7,5 ;class homework private:int res8;bool flag8;int maxreap;public:void dealwith()

7、/遍歷所有作業:int i;for (i = 0; i<8; i+) int time = maxtimei - 1;if (!flagtime) /如果最大期限那一天還未安排作業,則將當前作業安排在所允許的最大期限那天restime = worki;flagtime = true;else /如果當前作業所允許的最大期限那一天已經安排的其他作業,就向前搜索空位,將該作業安排進去for (int j = time - 1; j >= 0; j-)if (!flagj) resj = worki;flagj = true;break;cout << "作業完成順

8、序為:" ;for (i = 0; i<7; i+) cout << resi << "t"cout << endl;cout << endl << "最佳效益為:"int j;for (j = 0; j<7; j+)maxreap += resj;cout << maxreap << endl;homework()int i;for(i = 0;i<8;i+)flagi = false;maxreap = 0;int main() homew

9、ork a = homework();a.dealwith();getchar();return 0;五、實驗結果截圖六、實驗總結通過這個實驗讓我知道了閆新算法在實際當中的運用，也讓我了解到了貪心算法的便捷以及貪心算法的實用性實驗3 動態規劃法求多段圖問題一、實驗目的1. 掌握動態規劃算法的基本思想2. 掌握多段圖的動態規劃算法3. 選擇鄰接表或鄰接矩陣方式來存儲圖4. 分析算法求解的復雜度二、實驗內容設g=(v,e)是一個帶權有向圖，其頂點的集合v被劃分成k>2個不相交的子集vi，1<i<=k，其中v1和vk分別只有一個頂點s（源）和一個頂點t（匯）。圖中所有邊的始點和終點

10、都在相鄰的兩個子集vi和vi+1中。求一條s到t的最短路線。參考課本p124圖7-1中的多段圖，試選擇使用向前遞推算法或向后遞推算法求解多段圖問題。三、實驗環境window10;惠普筆記本；dev cpp四、算法描述和程序代碼#include<stdio.h>int v5050;int a50,b20;int static k,n,m;void creategraph() int i,j,t,s; printf("請輸入結點數："); scanf("%d",&n); for(i=0; i<=n; i+) for(j=0; j&l

11、t;=n; j+) vij=0;/初始化vij=0,表示兩結點沒有邊相連 printf("輸入圖的層數："); scanf("%d",&k); printf("請輸入每層的結點數的最大編號："); a0=0; for(i=1; i<=k; i+) scanf("%d",&ai); printf("請輸入邊數："); scanf("%d",&m); printf("請輸入結點之間的關系(如：結點i和結點j的距離為s，則輸入i,j,s)n&

12、quot;); 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+) /把第二層每個結點i與第一層結點s的邊距賦值給vii vii=v1i; for(r=2; r<k; r+) /向后逐層求解 for(i=ar-1+1; i<=ar; i+) /遍歷第r層的每個結點i與第(r+1)層結點j之間的邊距,選擇此刻最優解 for(j=ar+1; j<=ar+1; j

13、+) if(vij!=0&&vjj=0)/第一次把此刻路徑長度賦給vjj vjj=vii+vij; else if(vij!=0&&vjj!=0) if(vii+vij)<vjj) vjj=vii+vij; j=-1; b4=0; for(r=k-1; r>=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 forward()/向前求解法 int i,j,

14、t,r; for(i=ak-2+1; i<=ak-1; i+) /把第二層每個結點i與第一層結點s的邊距賦值給vii vii=viak; for(r=k-1; r>1; r-) /向前逐層求解 for(j=ar-1+1; j<=ar; j+)/遍歷第r層的每個結點i與第(r-1)層結點j之間的邊距,選擇此刻最優解 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)<v

15、ii) 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<=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("最短路徑為："); print

16、f("%d",b1); for(i=2; i<=k; i+) printf("->%d",bi); return 0;五、實驗結果截圖6、 實驗總結這個實驗讓我從中懂得了動態規劃算法的核心，更加收斂的運用動態規劃算法秋節各類問題，但動態規劃算法最重要的還是方程的選擇，這個在實際運用中相當重要。實驗4回溯法求n皇后問題一、實驗目的1. 掌握回溯算法的基本思想2. 通過n皇后問題求解熟悉回溯法3. 使用蒙特卡洛方法分析算法的復雜度二、實驗內容要求在一個8*8的棋盤上放置8個皇后，使得它們彼此不受“攻擊”。兩個皇后位于棋盤上的同一行、同一列或同一對

17、角線上，則稱它們在互相攻擊。現在要找出使得棋盤上8個皇后互不攻擊的布局。三、實驗環境window10;惠普筆記本；dev cpp四、算法描述和程序代碼#include<iostream>#include<math.h> using namespace std;#define n 8int res1008;int countres = 0;bool place(int k,int i,int *x) for(int j = 0;j<k;j+) if(xj = i | abs(xj-i) = abs(j-k) return false; return true;voi

18、d nqueen(int k,int n,int *x) for(int i = 0;i<n;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;i<n;i+) *(x+i) = -10;