太原理工大学算法实验报告材料.doc

word
word
1 / 12
word
本科实验报告
课程名称：算法设计与分析
实验项目：算法设计与分析实验
实验地点：致远楼403
专业班级：学号：
学生：
指导教师：
2017年 3 月 28日
word
word
2 / 12
word
实验一分治法合并排序
一、实验目的




二、实验容
随机产生一个整型数组，然后用合并排序将该数组做升序排列，要求输出排序前和排序后的数组。
三、实验环境
程序设计语言：c++
编程工具：microsoft visual studio 2013
四、程序代码
#include ""
#include<iostream>
#include<cassert>
#include""
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(arr,mid+1,r);
if(arr[mid]>arr[mid+1])
__merge(arr,l,mid,r);
}
template<typename T>
void __merge(T arr[],int l,int mid,int r)
{
T *aux=new T[r-l+1];
word
word
3 / 12
word
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(i>mid)
{
arr[k]=aux[j-l];
j++;
}
else if(j>r)
{
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;j<10;j++)
cout<<arr[j]<<" ";
cout<<endl;
mergeSort(arr,10);
cout<<"经过排序的数组为：";
for(int i=0;i<9;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
word
word
4 / 12
word
#include""
#include<iostream>
#include<ctime>
#include<cassert>
using namespace std;
namespace SortTestHelper{
int *generateRandomArray(int n,int randL,int randR)
{
assert(randL<=randR);
int *arr=new int[n];
for(int i=0;i<n;i++)
arr[i]=rand()%(randR-randL+1)+randL;
return arr;
}
}
五、实验结果截图
六、实验总结
一定要先找到递归函数式后，设计递归程序
word
word
5 / 12
word
实验二贪心法多机调度
实验目的
1. 掌握