太原理工算法實驗

1、本科實驗報告課程名稱： 算法設(shè)計與分析B 實驗項目： 分治法合并排序問題、貪心法作業(yè)調(diào)度問題、動態(tài)規(guī)劃法多段圖問題、回溯法求N皇后問題 實驗地點： 行知樓 C124 專業(yè)班級：軟件工程 學(xué)號： 學(xué)生姓名： 戴 超 指導(dǎo)教師： 王幸民 2015年 04月 11 日實驗一 分治法合并排序一 實驗?zāi)康?. 掌握合并排序的基本思想2. 掌握合并排序的實現(xiàn)方法3. 學(xué)會分析算法的時間復(fù)雜度4. 學(xué)會用分治法解決實際問題二 實驗內(nèi)容隨機產(chǎn)生一個整型數(shù)組，然后用合并排序?qū)⒃摂?shù)組做升序排列，要求輸出排序前和排序后的數(shù)組。三 實驗環(huán)境程序設(shè)計語言：C+編程工具：Microsoft Visual Studio 2

2、013四 算法描述及程序代碼#include "stdafx.h"#include <iostream>using namespace std;const int n=10; /數(shù)組大小const int max = 100; /定義一個值設(shè)為無窮大int Arr1n / 2 + 1, Arr2n / 2 + 1; void MergeSort(int *Ap, int p, int r);int _tmain(int argc, _TCHAR* argv)int Arrn;cout << "請輸入 10個 任意數(shù)字（<100）：&q

3、uot; << endl;for (int i = 0; i < n; i+)cin >> Arri; /調(diào)用歸并排序函數(shù)cout << "歸并排序前的數(shù)組為：" << endl;for (int i = 0; i < n; i+)cout << Arri << " "MergeSort(Arr, 0, n - 1);cout << "n歸并排序后的結(jié)果為：" << endl;for (int i = 0; i < n;

4、i+)cout<< Arri<<" "cout << "n"return 0;void Merge(int *Ap, int p, int q, int r)int i=0, j=0;int n1 = q - p + 1;int n2 = r - q;for (int i = 0; i < n1; i+)Arr1i = App + i;for (int i = 0; i < n1; i+)Arr2i = Apq + i+1;Arr1n1 = max; /設(shè)立一個標簽 值為無窮大Arr2n2 = max;wh

5、ile(p<=r) /合并兩個小的有序數(shù)列if (Arr1i < Arr2j)&&Arr1i<100)App+ = Arr1i+;else if (Arr2j<100) App+ = Arr2j+;void MergeSort(int *Ap,int p,int r) /歸并函數(shù) int q;if (p < r) /遞歸調(diào)用本身q = (p + r) / 2;MergeSort(Ap, p, q);MergeSort(Ap,q+1,r);Merge(Ap,p,q,r);五 實驗結(jié)果截圖六 實驗總結(jié)我通過對歸并排序算法的編寫，加深了分治法的理解與認識

6、。在用C+實現(xiàn)這一算法時，Merge（）函數(shù)是這個程序的關(guān)鍵，利用其調(diào)用本身，實現(xiàn)遞歸算法。通過實驗，使我復(fù)習(xí)了C+的內(nèi)容，還增強了自己的實際動手能力。讓我更加熱愛這門學(xué)科。實驗二 貪心法作業(yè)調(diào)度一 實驗?zāi)康? 掌握貪心算法的基本思想2 掌握貪心算法的典型問題求解3 進一步掌握多機調(diào)度的基本思想和算法設(shè)計方法4 學(xué)會用貪心法分析和解決實際問題二 實驗內(nèi)容設(shè)計貪心算法實現(xiàn)作業(yè)調(diào)度，要求按作業(yè)調(diào)度順序輸出作業(yè)序列。如已知n=8，機器數(shù)m=(1,2,3,4)，作業(yè)處理時間 d=(4, 2, 4, 5, 6, 4, 5, 

7、7)，求該條件下的作業(yè)調(diào)度方案。三 實驗環(huán)境程序設(shè)計語言：C+編程工具：Microsoft Visual Studio 2013四 方法描述和程序代碼#include "stdafx.h"#include <iostream>using namespace std;const int n = 8;const int m = 4;void Sort(int *t, int *p);void min_d(int *d, int &j);void JobSche(int(*s)m, int *p, int *d, int *t, int j, int i);i

8、nt _tmain(int argc, _TCHAR* argv)int i, j, max;int Tn = 4, 2, 4, 5, 6, 4, 5, 7 ; /作業(yè)處理時間int Pn = 1, 2, 3, 4, 5, 6, 7, 8 ; /作業(yè)序號int Smm = 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ;int Dm = 0, 0, 0, 0 ;cout << "作業(yè)序號極其所需處理時間如下：" << "n序號： "for (int i = 0; i < 8;

9、i+)cout << Pi << " "cout << "n時間： "for (int i = 0; i < 8; i+)cout << Ti << " "cout << "n"Sort(T, P); /時間排序for (int i = 0; i < m; i+)Di = Ti;Si0 = Pi;if (m < n) /當(dāng)機器數(shù)小于作業(yè)數(shù)for (i = m; i < n; i+)min_d(D, j);JobSche(

10、S, P, D, T, j, i);max = D0;for (i = 0; i < m; i+)if (max < Di)max = Di;cout << "將所有作業(yè)處理完的最短用時為： " << max << endl;cout << "依次輸出每個機器按時間順序處理的作業(yè)號：" << endl;for (i = 1; i <= 4; i+)cout << "機器 " << i << " :"fo

11、r (j = 0; Si - 1j > 0; j+)cout <<" "<<Si - 1j;if (Si - 1j + 1 > 0)cout << " -> "cout << "n"return 0;void Sort(int *t,int *p) /時間排序函數(shù)int temp;for (int i = 7; i > 0; i-)for (int j = 7; j > (7-i); j-)if (tj-1 < tj)temp = tj-1;tj-1

12、= tj;tj = temp;temp = pj-1; /排序的同時作業(yè)號跟著移動pj-1 = pj;pj = temp;void min_d(int *d, int &j) /求此時最先空余機器函數(shù)int i; int min = d0; for (i = 0, j = 0; i < m&&j<m; i+)if (min>di)min = di;j = i;void JobSche(int (*s)m,int *p,int *d,int *t,int j,int i)int k; /貪心算法安排作業(yè)dj = dj+ti;for (k = 0; sjk

13、 != 0; k+);sjk = pi;五 實驗結(jié)果截圖六 實驗總結(jié)我通過對多機調(diào)度算法的編寫，加深了貪心算法的理解與認識，也更清楚的了解并掌握了多機調(diào)度問題。在用C+實現(xiàn)這一算法時，JobSche（）函數(shù)和min_d（）函數(shù)是這個算法的關(guān)鍵，利用min_d（）函數(shù)求出每次的最先空余機器，利用JobSche（）函數(shù)實現(xiàn)貪新算法作業(yè)調(diào)度。通過實驗，使我復(fù)習(xí)了C+的內(nèi)容，還增強了自己的實際動手能力。讓我更加熱愛這門學(xué)科。實驗三 動態(tài)規(guī)劃法求多段圖問題一 實驗?zāi)康?掌握動態(tài)規(guī)劃算法的基本思想2 掌握多段圖的動態(tài)規(guī)劃算法3 選擇鄰接表或鄰接矩陣方式來存儲圖4 分析算法求解的復(fù)雜度。二 實驗內(nèi)容設(shè)G=(

14、V,E)是一個帶權(quán)有向圖，其頂點的集合V被劃分成k>2個不相交的子集Vi，1<i<=k，其中V1和Vk分別只有一個頂點s（源）和一個頂點t（匯）。圖中所有邊的始點和終點都在相鄰的兩個子集Vi和Vi+1中。求一條s到t的最短路線。參考講義p136圖5-24中的多段圖，試選擇使用向前遞推算法或向后遞推算法求解多段圖問題。三 實驗環(huán)境程序設(shè)計語言：C+編程工具：Microsoft Visual Studio 2013四 算法描述和程序代碼#include "stdafx.h"#include <iostream>using namespace std

15、;int const M = 100; /標記值int const N = 9;int cost(int i, int p, int(*Side)9, int(*Cos)9, int(*D)9);int _tmain(int argc, _TCHAR* argv)int i = 0,j=0,k;int Arc54; /頂點序號int SideNN; /邊長int CosNN; /各邊成本函數(shù)int DNN; /最小路徑上后繼頂點cout << "多段圖問題n(每次輸入數(shù)據(jù)以100結(jié)束)"<<endl;for (int i = 0; i < 5;

16、 i+) /輸入頂點序號cout << "請輸入第 " << i + 1 << "層頂點序號："for (int j = 0; j < 4; j+)cin >> Arcij;if (Arcij = 100) j = 4;cout << "輸入各點間距離：n(如：1 2 3 表示1與2之間距離為3)n"for (int i = 0; i < N;i+) /對邊長進行賦值 for (int j = 0; j < N; j+)Sideij = M;while (i

17、!=100)cin >> i >> j >> k;if (i!=100)Sideij = k;cost(0, 0, Side, Cos, D); /調(diào)用動態(tài)規(guī)劃函數(shù)cout << "S到T的最短路徑長度為： " << Cos00<< "nS到T依次經(jīng)過的節(jié)點為： 0" ;i = 0, j = 0;while (Dij!=M) /輸出路徑cout <<" -> "<< Dij;j = Dij;i+;cout << "

18、;n"return 0;int cost(int i, int p, int (*Side)9, int (*Cos)9, int (*D)9)int min,h,j=0,k=0;if (i = 4&&p=(N-1) /當(dāng)?shù)阶詈笠粚訒r 給定最小值0min = 0;Cos4p = 0;D48 = M;return min;else if(i<4)for (j = 0; Sidepj = M; j+)h = Sidepj; /找到與下一層有連接的節(jié)點min = h +cost(i + 1, j, Side, Cos, D);k = j; for (;j<N;

19、j+) if (Sidepj != M) /選出cost值最小的節(jié)點if (min>(Sidepj + cost(i + 1, j, Side, Cos, D)min = Sidepj + cost(i + 1, j, Side, Cos, D);k = j; /標記符合條件節(jié)點Cosip = min;Dip = k;return min;五 實驗結(jié)果截圖六 實驗總結(jié)這個實驗是目前最難做的一個了，難點是對于數(shù)據(jù)的表示和數(shù)據(jù)間關(guān)系的構(gòu)造，以至于我平時沒事就會用手寫一寫，終于有一天有了思路對這個程序一氣呵成。我通過對多段圖求最短路徑的編寫，加深了動態(tài)規(guī)劃思想的理解與認識，也更清楚的了解并掌握

20、了多機調(diào)度問題。在用C+實現(xiàn)這一算法時，cost（）函數(shù)就是這個程序的靈魂，我通過遞歸的方法來實現(xiàn)動態(tài)規(guī)劃的思想，整個程序很簡練，這是我最滿意的一個實驗。通過實驗，使我復(fù)習(xí)了C+的內(nèi)容，還增強了自己的實際動手能力。實驗四 回溯法求n皇后問題一 實驗?zāi)康? 掌握回溯算法的基本思想2 通過n皇后問題求解熟悉回溯法3 使用蒙特卡洛方法分析算法的復(fù)雜度二 實驗內(nèi)容要求在一個8*8的棋盤上放置8個皇后，使得它們彼此不受“攻擊”。兩個皇后位于棋盤上的同一行、同一列或同一對角線上，則稱它們在互相攻擊?，F(xiàn)在要找出使得棋盤上8個皇后互不攻擊的布局。三 實驗環(huán)境程序設(shè)計語言：C+編程工具：Microsoft Vi

21、sual Studio 2013四 算法描述和程序代碼#include "stdafx.h"#include <iostream>using namespace std;int const N = 8;void Nqueens(int *X);int _tmain(int argc, _TCHAR* argv)int XN+1;cout << "八皇后問題n" << "依次輸出每行皇后所在的位置" << endl;Nqueens(X); /調(diào)用求解函數(shù)return 0;bool place(int k,int *X) int i=1;