1、本科實驗報告課程名稱： 算法設計與分析 實驗項目： 算法設計與分析實驗 實驗地點： 致遠樓403 專業班級： 學號： 學生姓名： 指導教師： 2017年 3 月 28日實驗一 分治法合并排序一、實驗目的 1.掌握合并排序的基本思想 2.掌握合并排序的實現方法 3.學會分析算法的時間復雜度 4.學會用分治法解決實際問題 二、實驗內容隨機產生一個整型數組，然后用合并排序將該數組做升序排列，要求輸出排序前和排序后的數組。 三、實驗環境程序設計語言：c+編程工具：microsoft visual studio 2013 四、程序代碼#include "stdafx.h"#inclu

2、de<iostream>#include<cassert>#include"SortTestHelper.h"using namespace std;template<typename T>void mergeSort(T arr,int n)_mergeSort(arr,0,n-1);template<typename T>void _mergeSort(T arr,int l,int r)if(l>=r)return;int mid=(l+r)/2;_mergeSort(arr,l,mid);_mergeSort(a

3、rr,mid+1,r);if(arrmid>arrmid+1)_merge(arr,l,mid,r);template<typename T>void _merge(T arr,int l,int mid,int r)T *aux=new Tr-l+1;for(int i=l;i<=r;i+)auxi-l=arri;int i=l,j=mid+1;for(int k=l;k<=r;k+)if(i>mid)arrk=auxj-l;j+;else if(j>r)arrk=auxi-l;i+;else if(auxi-l<auxj-l)arrk=aux

4、i-l;i+;elsearrk=auxj-l;j+;delete aux;int _tmain(int argc, _TCHAR* argv)int n=10;int *arr=SortTestHelper:generateRandomArray(n,0,n);cout<<"未排序的數組為："for(int j=0;j<10;j+) cout<<arrj<<" "cout<<endl;mergeSort(arr,10);cout<<"經過排序的數組為："for(int

5、i=0;i<9;i+)cout<<arri<<" "cout<<endl;#include"stdafx.h"#include<iostream>#include<ctime>#include<cassert>using namespace std;namespace SortTestHelperint *generateRandomArray(int n,int randL,int randR)assert(randL<=randR);int *arr=new intn

6、;for(int i=0;i<n;i+)arri=rand()%(randR-randL+1)+randL;return arr;五、實驗結果截圖六、實驗總結一定要先找到遞歸函數式后，設計遞歸程序實驗二 貪心法多機調度一、 實驗目的 1. 掌握貪心算法的基本思想 2.掌握貪心算法的典型問題求解 3.進一步多機調度的基本思想和算法設計方法 4.學會用貪心法分析和解決實際問題二、 實驗內容設計貪心算法實現作業調度，要求按作業調度順序輸出作業序列。如已知n=8，效益p=(35, 30, 25, 20, 15, 10, 5, 

7、1)，時間期限 d=(4, 2, 4, 5, 6, 4, 5, 7)，求該條件下的最大效益。三、 實驗環境程序設計語言：c+編程工具：microsoft visual studio 2013四、 方法描述和程序代碼#include "stdafx.h"#include"iostream"using namespace std;int _tmain(int argc, _TCHAR* argv)double work99,time99,t,w;double temp99,use

8、temp99,a,s=0;int A99;cout<<"作業數為(x<99):"<<endl;cin>>w;cout<<"作業收益為:"<<endl;for(int i=0;i<w;i+)cin>>worki;cout<<"作業收益："<<endl;for(int i=0;i<w;i+)cout<<" "<<worki<<" "cout<&l

9、t;endl;cout<<"每個作業的時限為:"<<endl;for(int i=0;i<w;i+)cin>>timei;cout<<"作業時限："<<endl;for(int i=0;i<w;i+)cout<<" "<<timei<<" "cout<<endl;cout<<"總作業時限為:"<<endl;cin>>t;/初始化錄入數據for

10、(int i=0;i<w;i+)tempi=worki/timei;usetempi=tempi;/平均時間盈利cout<<"作業平均時間盈利排序為："<<endl;for(int m=0;m<w;m+)a=temp0,Am=0; for(int i=0;i<w;i+) if(a<tempi) Am=i;a=tempi; tempAm=0;cout<<" "<<Am<<" " /作業平均時間盈利排序cout<<endl;cout<&l

11、t;"可進行的作業有："<<endl;for(int i=0;i<w;i+)double x=s+timeAi;if(x<t)s=s+timeAi;cout<<" "<<Ai<<" "五、實驗結果截圖六、實驗總結貪心算法設計的關鍵是貪心策略的選擇。實驗三 動態規劃法求多段圖問題一、 實驗目的 1.掌握動態規劃算法的基本思想 2.掌握多段圖的動態規劃算法 3.選擇鄰接表或鄰接矩陣方式來存儲圖 4.分析算法求解的復雜度。二、 實驗內容設G=(V,E)是一個帶權有向圖，其頂點的集合

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

13、00struct Tint adjVex;int w;struct T *nextArc;class Graphprivate:T *a;int *p;int n;public:Graph(int n) this->n = n; p = new intn; a = new T*n; for (int i = 0; i < n; i+)ai = new T; void GetT(int *m);int fp(int k);void print(int k);void Graph:print(int k)int c = fp(k);cout << "最短路徑權值：

14、" << c << endl;cout << "最短路徑：" << endl;for (int i = 0; i < k - 1; i+)cout << pi << "->" << pi + 1 << endl;int Graph:fp(int k)int c, *cost = new intn; int q, *d = new intn;costn - 1 = 0;dn - 1 = -1;for (int j = n - 2; j &g

15、t;= 0; j-)int min = INFTY;for (T *r = aj->nextArc; r;r=r->nextArc)int v = r->adjVex;if (r->w + costv < min)min = r->w + costv;q = v;costj = min;dj = q;p0 = 0; pk - 1 = n - 1; c = cost0;for (int j = 1; j <= k - 2; j+)pj = dpj - 1;deletecost;deleted;return c;void Graph:GetT(int *m

16、)T *x,*p,*q;for (int i = 0; i < n; i+)p = q = ai;for (int j = 0; j < n; j+)if (mij != 0)x = new T;x->adjVex = j;x->w = mij;p->nextArc = x;p = p->nextArc;p->nextArc = NULL;int _tmain(int argc, _TCHAR* argv)int *m;Graph q(12);m =new int* 12;for (int i = 0; i <12; i+)mi = new in

17、t12;cout << "圖的各點見的權值為：" << endl;for (int i = 0; i < 12;i+)for (int j = 0; j < 12; j+)cin >> mij;q.GetT(m);int k;cout << "到第幾個結點的最短路徑:"cin >> k;q.print(k);for (int i = 0; i < 12; i+)delete mi;delete m;return 0;五、 實驗結果截圖六、 實驗總結動態規劃法應用于子問題重疊的情

18、況，與分治法類似。實驗四 回溯法求n皇后問題一、 實驗目的掌握回溯算法的基本思想通過n皇后問題求解熟悉回溯法使用蒙特卡洛方法分析算法的復雜度二、 實驗內容要求在一個8*8的棋盤上放置8個皇后，使得它們彼此不受“攻擊”。兩個皇后位于棋盤上的同一行、同一列或同一對角線上，則稱它們在互相攻擊。現在要找出使得棋盤上8個皇后互不攻擊的布局。三、 實驗環境程序設計語言：c+編程工具：microsoft visual studio 2013四、 算法描述和程序代碼 #include "stdafx.h"#include <stdlib.h>#define N 4int columnN+1; int rup2*N+1; int lup2*N+1; int queenN+1 = 0;int num; / 解答編號確定 void backtrack(int); int _tmain(int argc, _TCHAR* argv) int i; num = 0; for(i = 1;