太原理工算法實(shí)驗(yàn)

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

2、013四 算法描述及程序代碼#include "stdafx.h"#include <iostream>using namespace std;const int n=10; /數(shù)組大小const int max = 100; /定義一個(gè)值設(shè)為無(wú)窮大int Arr1n / 2 + 1, Arr2n / 2 + 1; void MergeSort(int *Ap, int p, int r);int _tmain(int argc, _TCHAR* argv)int Arrn;cout << "請(qǐng)輸入 10個(gè) 任意數(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è)立一個(gè)標(biāo)簽 值為無(wú)窮大Arr2n2 = max;wh

5、ile(p<=r) /合并兩個(gè)小的有序數(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);五 實(shí)驗(yàn)結(jié)果截圖六 實(shí)驗(yàn)總結(jié)我通過(guò)對(duì)歸并排序算法的編寫(xiě)，加深了分治法的理解與認(rèn)識(shí)

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

7、7)，求該條件下的作業(yè)調(diào)度方案。三 實(shí)驗(yàn)環(huán)境程序設(shè)計(jì)語(yǔ)言：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è)處理時(shí)間int Pn = 1, 2, 3, 4, 5, 6, 7, 8 ; /作業(yè)序號(hào)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è)序號(hào)極其所需處理時(shí)間如下：" << "n序號(hào)： "for (int i = 0; i < 8;

9、i+)cout << Pi << " "cout << "n時(shí)間： "for (int i = 0; i < 8; i+)cout << Ti << " "cout << "n"Sort(T, P); /時(shí)間排序for (int i = 0; i < m; i+)Di = Ti;Si0 = Pi;if (m < n) /當(dāng)機(jī)器數(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è)處理完的最短用時(shí)為： " << max << endl;cout << "依次輸出每個(gè)機(jī)器按時(shí)間順序處理的作業(yè)號(hào)：" << endl;for (i = 1; i <= 4; i+)cout << "機(jī)器 " << 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í)間排序函數(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; /排序的同時(shí)作業(yè)號(hào)跟著移動(dòng)pj-1 = pj;pj = temp;void min_d(int *d, int &j) /求此時(shí)最先空余機(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;五 實(shí)驗(yàn)結(jié)果截圖六 實(shí)驗(yàn)總結(jié)我通過(guò)對(duì)多機(jī)調(diào)度算法的編寫(xiě)，加深了貪心算法的理解與認(rèn)識(shí)，也更清楚的了解并掌握了多機(jī)調(diào)度問(wèn)題。在用C+實(shí)現(xiàn)這一算法時(shí)，JobSche（）函數(shù)和min_d（）函數(shù)是這個(gè)算法的關(guān)鍵，利用min_d（）函數(shù)求出每次的最先空余機(jī)器，利用JobSche（）函數(shù)實(shí)現(xiàn)貪新算法作業(yè)調(diào)度。通過(guò)實(shí)驗(yàn)，使我復(fù)習(xí)了C+的內(nèi)容，還增強(qiáng)了自己的實(shí)際動(dòng)手能力。讓我更加熱愛(ài)這門(mén)學(xué)科。實(shí)驗(yàn)三 動(dòng)態(tài)規(guī)劃法求多段圖問(wèn)題一 實(shí)驗(yàn)?zāi)康?掌握動(dòng)態(tài)規(guī)劃算法的基本思想2 掌握多段圖的動(dòng)態(tài)規(guī)劃算法3 選擇鄰接表或鄰接矩陣方式來(lái)存儲(chǔ)圖4 分析算法求解的復(fù)雜度。二 實(shí)驗(yàn)內(nèi)容設(shè)G=(

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

15、;int const M = 100; /標(biāo)記值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; /頂點(diǎn)序號(hào)int SideNN; /邊長(zhǎng)int CosNN; /各邊成本函數(shù)int DNN; /最小路徑上后繼頂點(diǎn)cout << "多段圖問(wèn)題n(每次輸入數(shù)據(jù)以100結(jié)束)"<<endl;for (int i = 0; i < 5;

16、 i+) /輸入頂點(diǎn)序號(hào)cout << "請(qǐng)輸入第 " << i + 1 << "層頂點(diǎn)序號(hào)："for (int j = 0; j < 4; j+)cin >> Arcij;if (Arcij = 100) j = 4;cout << "輸入各點(diǎn)間距離：n(如：1 2 3 表示1與2之間距離為3)n"for (int i = 0; i < N;i+) /對(duì)邊長(zhǎng)進(jìn)行賦值 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)用動(dòng)態(tài)規(guī)劃函數(shù)cout << "S到T的最短路徑長(zhǎng)度為： " << Cos00<< "nS到T依次經(jīng)過(guò)的節(jié)點(diǎn)為： 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(shí) 給定最小值0min = 0;Cos4p = 0;D48 = M;return min;else if(i<4)for (j = 0; Sidepj = M; j+)h = Sidepj; /找到與下一層有連接的節(jié)點(diǎn)min = h +cost(i + 1, j, Side, Cos, D);k = j; for (;j<N;

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

20、了多機(jī)調(diào)度問(wèn)題。在用C+實(shí)現(xiàn)這一算法時(shí)，cost（）函數(shù)就是這個(gè)程序的靈魂，我通過(guò)遞歸的方法來(lái)實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃的思想，整個(gè)程序很簡(jiǎn)練，這是我最滿意的一個(gè)實(shí)驗(yàn)。通過(guò)實(shí)驗(yàn)，使我復(fù)習(xí)了C+的內(nèi)容，還增強(qiáng)了自己的實(shí)際動(dòng)手能力。實(shí)驗(yàn)四 回溯法求n皇后問(wèn)題一 實(shí)驗(yàn)?zāi)康? 掌握回溯算法的基本思想2 通過(guò)n皇后問(wèn)題求解熟悉回溯法3 使用蒙特卡洛方法分析算法的復(fù)雜度二 實(shí)驗(yàn)內(nèi)容要求在一個(gè)8*8的棋盤(pán)上放置8個(gè)皇后，使得它們彼此不受“攻擊”。兩個(gè)皇后位于棋盤(pán)上的同一行、同一列或同一對(duì)角線上，則稱它們?cè)诨ハ喙簟，F(xiàn)在要找出使得棋盤(pán)上8個(gè)皇后互不攻擊的布局。三 實(shí)驗(yàn)環(huán)境程序設(shè)計(jì)語(yǔ)言：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 << "八皇后問(wèn)題n" << "依次輸出每行皇后所在的位置" << endl;Nqueens(X); /調(diào)用求解函數(shù)return 0;bool place(int k,int *X) int i=1;