太原理工大学算法实验报告

1、本科实验报告课程名称： 算法设计与分析 实验项目： 算法设计与分析实验 实验地点： 致远楼403 专业班级： 学号： 学生姓名： 指导教师： 2017年 3 月 28日实验一 分治法合并排序一、实验目的 1.掌握合并排序的基本思想 2.掌握合并排序的实现方法 3.学会分析算法的时间复杂度 4.学会用分治法解决实际问题 二、实验内容随机产生一个整型数组，然后用合并排序将该数组做升序排列，要求输出排序前和排序后的数组。 三、实验环境程序设计语言：c+编程工具：microsoft visual studio 2013 四、程序代码#include stdafx.h#include#include#i

2、ncludeSortTestHelper.husing namespace std;templatevoid mergeSort(T arr,int n)_mergeSort(arr,0,n-1);templatevoid _mergeSort(T arr,int l,int r)if(l=r)return;int mid=(l+r)/2;_mergeSort(arr,l,mid);_mergeSort(arr,mid+1,r);if(arrmidarrmid+1)_merge(arr,l,mid,r);templatevoid _merge(T arr,int l,int mid,int r

3、)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;kmid)arrk=auxj-l;j+;else if(jr)arrk=auxi-l;i+;else if(auxi-lauxj-l)arrk=auxi-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

4、(int j=0;j10;j+) coutarrj ;coutendl;mergeSort(arr,10);cout经过排序的数组为：;for(int i=0;i9;i+)coutarri ;coutendl;#includestdafx.h#include#include#includeusing namespace std;namespace SortTestHelperint *generateRandomArray(int n,int randL,int randR)assert(randL=randR);int *arr=new intn;for(int i=0;in;i+)arri

5、=rand()%(randR-randL+1)+randL;return arr;五、实验结果截图六、实验总结一定要先找到递归函数式后，设计递归程序实验二 贪心法多机调度一、 实验目的 1. 掌握贪心算法的基本思想 2.掌握贪心算法的典型问题求解 3.进一步多机调度的基本思想和算法设计方法 4.学会用贪心法分析和解决实际问题二、 实验内容设计贪心算法实现作业调度，要求按作业调度顺序输出作业序列。如已知n=8，效益p=(35,30,25,20,15,10,5,1)，时间期限d=(4,2,4,5,6,4,5,7)，求该条件下的最大效益。三、 实验环境程序设计语言：c+编程工具：microsoft

6、visual studio 2013四、 方法描述和程序代码#include stdafx.h#includeiostreamusing namespace std;int _tmain(int argc, _TCHAR* argv)double work99,time99,t,w;double temp99,usetemp99,a,s=0;int A99;cout作业数为(x99):w;cout作业收益为:endl;for(int i=0;iworki;cout作业收益：endl;for(int i=0;iw;i+)cout worki ;coutendl;cout每个作业的时限为:endl

7、;for(int i=0;itimei;cout作业时限：endl;for(int i=0;iw;i+)cout timei ;coutendl;cout总作业时限为:t;/初始化录入数据for(int i=0;iw;i+)tempi=worki/timei;usetempi=tempi;/平均时间盈利cout作业平均时间盈利排序为：endl;for(int m=0;mw;m+)a=temp0,Am=0; for(int i=0;iw;i+) if(atempi) Am=i;a=tempi; tempAm=0;cout Am ; /作业平均时间盈利排序coutendl;cout可进行的作业有：

8、endl;for(int i=0;iw;i+)double x=s+timeAi;if(xt)s=s+timeAi;cout Ai2个不相交的子集Vi，1i=k，其中V1和Vk分别只有一个顶点s（源）和一个顶点t（汇）。图中所有边的始点和终点都在相邻的两个子集Vi和Vi+1中。求一条s到t的最短路线。参考讲义p136图5-24中的多段图，试选择使用向前递推算法或向后递推算法求解多段图问题。三、 实验环境程序设计语言：c+编程工具：microsoft visual studio 2013 四、 算法描述和程序代码#include stdafx.h#includeusing namespace s

9、td;#define INFTY 1000struct 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 最短路径权值： c en

10、dl;cout 最短路径： endl;for (int i = 0; i k - 1; i+)cout pi pi + 1 = 0; j-)int min = INFTY;for (T *r = aj-nextArc; r;r=r-nextArc)int v = r-adjVex;if (r-w + costv 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;voi

11、d Graph:GetT(int *m)T *x,*p,*q;for (int i = 0; i n; i+)p = q = ai;for (int j = 0; j 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 int12;cout 图的各点见的权值为： endl;for (int i = 0; i 12;

12、i+)for (int j = 0; j mij;q.GetT(m);int k;cout k;q.print(k);for (int i = 0; i 12; i+)delete mi;delete m;return 0;五、 实验结果截图六、 实验总结动态规划法应用于子问题重叠的情况，与分治法类似。实验四 回溯法求n皇后问题一、 实验目的掌握回溯算法的基本思想通过n皇后问题求解熟悉回溯法使用蒙特卡洛方法分析算法的复杂度二、 实验内容要求在一个8*8的棋盘上放置8个皇后，使得它们彼此不受“攻击”。两个皇后位于棋盘上的同一行、同一列或同一对角线上，则称它们在互相攻击。现在要找出使得棋盘上8个皇

13、后互不攻击的布局。三、 实验环境程序设计语言：c+编程工具：microsoft visual studio 2013四、 算法描述和程序代码 #include stdafx.h#include #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; i = N; i+) columni = 1; for(i = 1; i = 2*N; i+) rupi = lupi = 1; backtrack(1); return 0;/ 递回求解void showAnswer() int x, y; printf(n解答 %dn, +num); for(y = 1; y = N; y+) for(x = 1; x N) showAnswer