太原理工算法实验.doc

本科实验报告 课程名称： 算法设计与分析B 实验项目： 分治法合并排序问题、贪心 作业调度问题动态规划法多段 图问题、回溯N皇后问题 行知楼 C124 专业班级：软件工程 学号： 学生姓名： 戴 超 指导教师： 王幸 2015年 04月 11 日 实验一 分治法合并排序 一 实验目的 掌握合并排序的基本思想 掌握合并排序的实现方法 学会分析算法的时间复杂度 学会用分治法解决实际问题 二 实验内容 随机产生一个整型数组，然后用合并排序将该数组做升序排列，要求输出排序前和排序后的数组。 三 实验环境 程序设计语言：C++ 编程工具：Microsoft Visual Studio 2013 四 算法描述及程序代码 #include stdafx.h #include iostream using namespace std; const int n=10; //数组大小 const int max = 100; //定义一个值设为无穷大 int Arr1[n / 2 + 1], Arr2[n / 2 + 1]; void MergeSort(int *Ap, int p, int r); int _tmain(int argc, _TCHAR* argv[]) { int Arr[n]; cout 请输入 10个 任意数字（100）： endl; for (int i = 0; i n; i++) cin Arr[i]; //调用归并排序函数 cout 归并排序前的数组为： endl; for (int i = 0; i n; i++) cout Arr[i] ; MergeSort(Arr, 0, n - 1); cout \n归并排序后的结果为： endl; for (int i = 0; i n; i++) cout Arr[i] ; cout \n; return 0; } void Merge(int *Ap, int p, int q, int r){ int i=0, j=0; int n1 = q - p + 1; int n2 = r - q; for (int i = 0; i n1; i++) Arr1[i] = Ap[p + i]; for (int i = 0; i n1; i++) Arr2[i] = Ap[q + i+1]; Arr1[n1] = max; //设立一个标签 值为无穷大 Arr2[n2] = max; while(p=r){ //合并两个小的有序数列 if ((Arr1[i] Arr2[j])Arr1[i]100) Ap[p++] = Arr1[i++]; else if (Arr2[j]100) Ap[p++] = Arr2[j++]; } } void MergeSort(int *Ap,int p,int r){ //归并函数 int q; if (p r){ //递归调用本身 q = (p + r) / 2; MergeSort(Ap, p, q); MergeSort(Ap,q+1,r); Merge(Ap,p,q,r); } } 五 实验结果截图 六 实验总结 我通过对归并排序算法的编写，加深了与认识在C++实现这一算法（）这个的关键利用其调用本身，实现递归算法验使我复习了C++的内容，还增强了自己的实际动手能力。学科。 实验二 贪心法作业调度 一 实验目的 掌握贪心算法的基本思想 掌握贪心算法的典型问题求解 进一步掌握多机调度的基本思想和算法设计方法 学会用贪心法分析和解决实际问题 二 实验内容 设计贪心算法实现作业调度，要求按作业调度顺序输出作业序列。如已知n=8，机器数m=(1,2,3,4)，作业处理时间?d=(4,?2,?4,?5,?6,?4,?5,?7)，求该条件下的作业调度方案。 三 实验环境 程序设计语言：C++ 编程工具：Microsoft Visual Studio 2013 四 方法描述和程序