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

2、amespace std;#define random(*)(rand()%*);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)tk+ = ai+;while (j = right)tk+ = aj+;for (i = 0, k = left; k = right;)ak+ = ti+;

3、/分劃函數，并且調用合并函數。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 排序前的數組為：;for (i = 0; i 10; i+) ai = random(100); /調用random函數，產生10個0-100的隨機數。cout ai ;cout endl;MergeS

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

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

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

7、短路線。參考課本P124圖7-1中的多段圖，試選擇使用向前遞推算法或向后遞推算法求解多段圖問題。三、實驗環境Window10;惠普筆記本；Dev cpp四、算法描述和程序代碼#includeint 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=n; j+) Vij=0;/初始化Vij=0,表示兩結點沒有邊相連 printf(輸入圖的層數：); scanf(%d,&k); printf(請輸

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

9、(i=ar-1+1; i=ar; i+) /遍歷第r層的每個結點i與第(r+1)層結點j之間的邊距,選擇此刻最優解 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 Forward()/向前求解法 int i

10、,j,t,r; for(i=ak-2+1; i1; 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)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=ar; j+) if(Vii-V

11、ij)=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;五、實驗結果截圖實驗總結這個實驗讓我從中懂得了動態規劃算法的核心，更加收斂的運用動態規劃算法秋節各類問題，但動態規劃算法最重要的還是方程的選擇，這個在實際運用中相當重要。實驗4回溯法求n皇

12、后問題一、實驗目的1. 掌握回溯算法的基本思想2. 通過n皇后問題求解熟悉回溯法3. 使用蒙特卡洛方法分析算法的復雜度二、實驗容要求在一個8*8的棋盤上放置8個皇后，使得它們彼此不受攻擊”。兩個皇后位于棋盤上的同一行、同一列或同一對角線上，則稱它們在互相攻擊。現在要找出使得棋盤上8個皇后互不攻擊的布局。三、實驗環境Window10;惠普筆記本；Dev cpp四、算法描述和程序代碼#include#include using namespace std;#define N 8int res1008;int countRes = 0;bool Place(int k,int i,int *) fo

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