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

本科实验报告课程名称：算法设计与分析实验项目：算法设计与分析实验实验地点：致远楼403 专业班级：学号：学生姓名：指导教师：2017年 3 月 28日实验一分治法合并排序一、实验目的 1.掌握合并排序的基本思想 2.掌握合并排序的实现方法 3.学会分析算法的时间复杂度 4.学会用分治法解决实际问题二、实验内容随机产生一个整型数组，然后用合并排序将该数组做升序排列，要求输出排序前和排序后的数组。三、实验环境程序设计语言：c++编程工具：microsoft visual studio 2013四、程序代码#include stdafx.h#includeiostream#includecassert#includeSortTestHelper.husing namespace std;templatetypename Tvoid mergeSort(T arr[],int n){_mergeSort(arr,0,n-1);}templatetypename Tvoid __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(arr[mid]arr[mid+1])__merge(arr,l,mid,r);}templatetypename Tvoid __merge(T arr[],int l,int mid,int r){T *aux=new T[r-l+1];for(int i=l;i=r;i++)aux[i-l]=arr[i];int i=l,j=mid+1;for(int k=l;k=r;k++){if(imid){arr[k]=aux[j-l];j++;}else if(jr){arr[k]=aux[i-l];i++;}else if(aux[i-l]aux[j-l]){arr[k]=aux[i-l];i++;}else{arr[k]=aux[j-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;j10;j++) coutarr[j] ;coutendl;mergeSort(arr,10);cout经过排序的数组为：;for(int i=0;i9;i++)coutarr[i] ;coutendl;}#includestdafx.h#includeiostream#includectime#includecassertusing namespace std;namespace SortTestHelper{int *generateRandomArray(int n,int randL,int randR){assert(randL=randR);int *arr=new int[n];for(int i=0;in;i++)arr[i]=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 visual studio 2013方法描述和程序代码#includestdafx.h#includeiostreamusingnamespace std;int _tmain(int argc, _TCHAR* argv[]){double work[99],time[99],t,w;double temp[99],usetemp[99],a,s=0;int A[99];cout作业数为(x99):endl;cinw;cout作业收益为:endl;for(int i=0;iw;i++){cinwork[i];}cout作业收益：endl;for(int i=0;iw;i++){cout work[i] ;}coutendl;cout每个作业