太原理工大學(xué)算法設(shè)計實驗報告

1、實驗1 分治法實驗?zāi)康模?1. 掌握合并排序的基本思想 2. 掌握合并排序的實現(xiàn)方法 3. 學(xué)會分析算法的時間復(fù)雜度 4. 學(xué)會用分治法解決實際問題實驗內(nèi)容：分治法求幾個大小不同整數(shù)的最大最小元。主要儀器設(shè)備：華碩筆記本、visual stdio2013上機(jī)調(diào)試修改源程序：#include<iostream>#include<time.h>#define N 5using namespace std;void getData(int a, int n)time_t t;srand(unsigned)time(&t);int i;for (i = 0; i <

2、; n; i+)ai = rand() % 100;void MaxMin(int i, int j, int l,int &max, int &min)int maxl, minl;if (i = j)max = min = lj;else if (i = j - 1)if (li < lj)max = lj;min = li;elsemax = li;min = lj;elseint m = (i + j) / 2;MaxMin(i, m, l, max, min);MaxMin(m + 1, j, l, maxl, minl);if (max < maxl)m

3、ax = maxl;if (min>minl)min = minl;void main()int lN, max, min;getData(l,N);for (int i = 0; i < N; i+)cout << li << " "cout << endl;MaxMin(0, 4, l, max, min);cout << "MAX=" << max << " " << "MIN=" << min <

4、;< endl;輸出結(jié)果：討論、心得（可選）:分治算法是很有用的算法效率很高，分治法的設(shè)計一般是遞歸的。兩路合并排序是一個典型的分治算法，其基本運算為元素比較，最壞情況下的時間為W(n)=O(nlogn)，在排序過程中需要使用與原序列相同長度的輔助數(shù)組temp，因此它所需的額外空間為O(n)。通過編寫代碼，我很好的掌握了分治法的步驟：劃分；求解子問題；合并。對“分治策略”有了更深的體會，它將原問題劃分為彼此獨立的、規(guī)模較小而結(jié)構(gòu)相同的子問題。實驗2貪心法實驗?zāi)康模?.掌握貪心算法的基本思想2.掌握貪心算法的典型問題求解3.進(jìn)一步多級調(diào)度的基本思想和算法設(shè)計方法4.學(xué)會用貪心法分析和解決實

5、際問題實驗內(nèi)容：利用貪心法來解決背包問題，使得具有有限空間的背包具有最大的價值。主要儀器設(shè)備：華碩筆記本、visual stdio2013上機(jī)調(diào)試修改源程序：#include<iostream>using namespace std;void DP(int c5050,int w50,int v50,int n,int C) for(int i=0;i<=C;i+) c0i=0; for(int t=1;t<=n;t+) ct0=0; for(int j=1;j<=C;j+) if(wt<=j) if(vt+ct-1j-wt>ct-1j)ctj=vt+

6、ct-1j-wt;else ctj=ct-1j; else ctj=ct-1j; void Output(int c5050,int x50,int w50,int n,int C) for(int k=n;k>=2;k-) if(ckC=ck-1C) xk=0; else xk=1;C=C-wk; x1=c1C?1:0;int main() int c5050; int w50,v50,x50,C,n; cout<<"輸入物品總個數(shù):" cin>>n; cout<<"輸入背包的總?cè)萘浚?quot; cin>>

7、C; cout<<"依次輸入物品的重量："<<endl; for(int i=1;i<=n;i+) cin>>wi; cout<<"依次輸入物品的價值："<<endl; for(int t=1;t<=n;t+) cin>>vt; DP(c,w,v,n,C); Output(c,x,w,n,C); cout<<"最優(yōu)解為："<<endl; for(int e=1;e<=n;e+) cout<<xe<<

8、" " cout<<endl<<"最大容量為："<<endl; cout<<cnC<<endl; return 0; 輸出結(jié)果：討論、心得（可選）:貪心法是一種求解組合優(yōu)化問題的算法設(shè)計技術(shù)它可用于求背包問題、帶時限的作業(yè)進(jìn)行排序問題等，其求解過程由一些列決策構(gòu)成。貪心算法的關(guān)鍵在于貪心策略，兩要素是：最優(yōu)子結(jié)構(gòu)和貪心策略，背包問題是一個典型的貪心算法。通過編寫貪心法處理背包問題，我對于貪心法的解決問題的思路更熟悉了。實驗3回溯法實驗?zāi)康模?.掌握回溯算法的基本思想2.通過n皇后問題求解熟悉回溯

9、法 3. 使用蒙特卡洛方法分析算法的復(fù)雜度實驗內(nèi)容：要求在一個8*8的棋盤上放置8個皇后，使得它們彼此不受“攻擊”。兩個皇后位于棋盤上的同一行、同一列或同一對角線上，則稱它們在互相攻擊?，F(xiàn)在要找出使得棋盤上8個皇后互不攻擊的布局。主要儀器設(shè)備：華碩筆記本、visual stdio2013上機(jī)調(diào)試修改源程序：#include <iostream>#include<cmath>using namespace std;bool Place(int k, int i, int *x)for (int j = 0; j<k; j+)if (xj = i)

10、 | (abs(xj - i) = abs(j - k)return 0;return 1;void NQueen(int k, int n, int *x)int a100100 = ;for (int i = 0; i<n; i+)if (Place(k, i, x) = 1)xk = i;if (k = n - 1)for (int i = 0; i<n; i+)cout << xi << " "aixi = 1;cout << endl << "如下圖示" << endl;f

11、or (int i = 0; i<n; i+)for (int j = 0; j<n; j+)cout << aij << " "cout << endl;cout << endl;else NQueen(k + 1, n, x);void NQueen(int n, int *x)NQueen(0, n, x);int main()int n;cin >> n;int k100;NQueen(n, k);return 0;輸出:討論、心得（可選）:通過這次試驗我對皇后問題的知識點有了很大的了解，編寫代

12、碼和調(diào)試代碼的能力有所提高。對于回溯法的認(rèn)知也更深入了在算法設(shè)計策略中，回溯法是比貪心法和動態(tài)規(guī)劃法更一般的方法。n皇后問題以檢查兩皇后是否沖突作為基本運算，該算法的最壞情形復(fù)雜性為O(3n×2nn)=O(nn+1)。實驗4動態(tài)規(guī)劃法實驗?zāi)康模?.掌握動態(tài)規(guī)劃算法的基本思想2.掌握多段圖的動態(tài)規(guī)劃算法3.選擇鄰接表或鄰接矩陣方式來存儲圖4.分析算法求解的復(fù)雜度實驗內(nèi)容：設(shè)G=(V,E)是一個帶權(quán)有向圖，其頂點的集合V被劃分成k>2個不相交的子集Vi，1<i<=k，其中V1和Vk分別只有一個頂點s（源）和一個頂點t（匯）。圖中所有邊的始點和終點都在相鄰的兩個子集Vi和

13、Vi+1中。求一條s到t的最短路線。參考課本P124圖7-1中的多段圖，試選擇使用向前遞推算法或向后遞推算法求解多段圖問題。主要儀器設(shè)備：華碩筆記本、visual stdio2013上機(jī)調(diào)試修改源程序：#include <stdio.h>#include <stdlib.h>#include <conio.h>#include "iostream"#define MAX 100 #define n 12 #define k 5 using namespace std;int cnn;void init(int cost) int i, j

14、;for (i = 0; i<13; i+)for (j = 0; j<13; j+)cij = MAX;c12 = 9; c13 = 7; c14 = 3; c15 = 2; c26 = 4; c27 = 2; c28 = 1;c36 = 2; c37 = 7; c48 = 11; c57 = 11; c58 = 8; c69 = 6; c610 = 5;c79 = 4; c710 = 3; c810 = 5; c811 = 6; c912 = 4; c1012 = 2; c1112 = 5;void fgraph(int cost, int path, int d) int r

15、, j, temp, min;for (j = 0; j <= n; j+)costj = 0;for (j = n - 1; j >= 1; j-)temp = 0;min = cjtemp + costtemp; for (r = 0; r <= n; r+)if (cjr != MAX)if (cjr + costr)<min) min = cjr + costr;temp = r;costj = cjtemp + costtemp;dj = temp;path1 = 1;pathk = n;for (j = 2; j<k; j+)pathj = dpath

16、j - 1;int main()int cur = -1;int cost13,d12;int pathk;cout <<"多段圖問題" << endl;cout << "n"init(cost);fgraph(cost, path, d);cout << "向前遞推后的最短路徑:n"for (int i = 1; i <= 5; i+)cout << pathi << " "cout << "n"cout << endl &l