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

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 =