1、太原理工大学算法设计与分析实验报告本科实验报告课程名称： 分算法设计与分析 实验项目：分治法合并排序 贪心法作业调度 动态规划法求多段图问题 回溯法求n皇后问题 实验地点： 行勉楼B209 专业班级：软件14*班 学号：*学生姓名： * 指导教师： * 2016年 4 月10日实验1 分治法合并排序一、实验目的1. 掌握合并排序的基本思想2. 掌握合并排序的实现方法3. 学会分析算法的时间复杂度4. 学会用分治法解决实际问题二、实验内容随机产生一个整型数组，然后用合并排序将该数组做升序排列，要求输出排序前和排序后的数组。三、实验环境Window7;惠普笔记本；VC+6.0.四、算法描述和程序代
2、码 #include#include#includeusing namespace std;#define random(x)(rand()%x);int a10;/合并排序函数。void Merge(int left, int mid, int right) int t11;int i = left, j = mid + 1, k = 0; while (i = mid) & (j = right) if (ai = aj) tk+ = ai+; else tk+ = aj+; while (i = mid) tk+ = ai+; while (j = right) tk+ = aj+; f
3、or (i = 0, k = left; k = right;) ak+ = ti+;/分划函数，并且调用合并函数。void MergeSort(int left, int right) if (left right) int mid = (left + right) / 2); MergeSort(left, mid); MergeSort(mid + 1, right); Merge(left, mid, right); /调用合并函数。 void main() int i; cout 排序前的数组为：; for (i = 0; i 10; i+) ai = random(100); /调
4、用random函数，产生10个0-100的随机数。 cout ai ; cout endl; MergeSort(0, 9); cout 排序后的数组为：; for (i = 0; i 10; i+) cout ai ; getchar();五、实验结果截图六、实验总结分治算法是很有用的算法，分治法的设计一般是递归的。两路合并排序是一个典型的分治算法，其基本运算为元素比较，最坏情况下的时间为W(n)=O(nlogn)，在排序过程中需要使用与原序列相同长度的辅助数组temp，因此它所需的额外空间为O(n)。通过编写代码，我很好的掌握了分治法的步骤：划分；求解子问题；合并。对“分治策略”有了更深的
5、体会，它将原问题划分为彼此独立的、规模较小而结构相同的子问题。实验2 贪心法作业调度一、实验目的1. 掌握贪心算法的基本思想2. 掌握贪心算法的典型问题求解3. 进一步多级调度的基本思想和算法设计方法4. 学会用贪心法分析和解决实际问题二、实验内容设计贪心算法实现作业调度，要求按作业调度顺序输出作业序列。如已知n=8，效益p=(35,30,25,20,15,10,5,1)，时间期限d=(4,2,4,5,6,4,5,7)，求该条件下的最大效益。三、实验环境Window7;惠普笔记本；VC+6.0.四、算法描述和程序代码#include using namespace std;const int
6、Work8 = 35,30,25,20,15,10,5,1 ;/所有作业按收益从大到小排序 const int maxTime8 = 4,2,4,5,6,4,5,7 ;class HomeWork private: int res8; bool flag8; int maxReap;public: void dealWith() /遍历所有作业: int i; for (i = 0; i= 0; j-) if (!flagj) resj = Worki; flagj = true; break; cout 作业完成顺序为: ; for (i = 0; i7; i+) cout resi t;
7、cout endl; cout endl 最佳效益为:; int j; for (j = 0; j7; j+) maxReap += resj; cout maxReap endl; HomeWork() int i; for(i = 0;i2个不相交的子集Vi，1i=k，其中V1和Vk分别只有一个顶点s（源）和一个顶点t（汇）。图中所有边的始点和终点都在相邻的两个子集Vi和Vi+1中。求一条s到t的最短路线。参考课本P124图7-1中的多段图，试选择使用向前递推算法或向后递推算法求解多段图问题。三、实验环境Window7;惠普笔记本；VC+6.0.四、算法描述和程序代码#includeusi
8、ng namespace std;struct int r50; int length;SqList, L;void MSort(int SR, int TR1, int s, int t);void Merge(int sR, int TR, int i, int mid, int n);void main() cout L.length; cout 请输入待排序的数:; for (int c = 0; c L.rc; cout 合并排序前的数组为:; for (int d = 0; dL.length; d+) cout L.rd ; cout endl; MSort(L.r, L.r,
9、0, L.length - 1); cout 合并排序后的数组为:; for (int i3 = 0; i3L.length; i3+) cout L.ri3 ; cout endl;void MSort(int SR, int TR1, int s, int t) /两路合并排序 int mid; int TR2100; if (s = t) TR1s = SRs; else /若序列的长度超过1，则划分为两个子序列 mid = (s + t) / 2; /将待排序的序列一分为二 MSort(SR, TR2, s, mid); /对左子序列排序 MSort(SR, TR2, mid + 1,
10、 t); /对右子序列排序 Merge(TR2, TR1, s, mid, t); /将两个有序子序列合并成一个有序序列 void Merge(int SR, int TR, int i, int mid, int n) /将两个有序序列合并成一个有序序列 int j, k; for (j = mid + 1, k = i; i = mid&j = n; +k) if (SRi = SRj) TRk = SRi+; else TRk = SRj+; if (i = mid) /如果左子序列还有元素未输出，则将左子序列剩余元素依次输出 int k1 = k; for (int i1 = i; i
11、1 = mid; i1+) TRk1 = SRi1; k1+; if (j = n) /如果右子序列还有元素未输出，则将右子序列剩余元素依次输出 int k2 = k; for (int j2 = j; j2 = n; j2+) TRk2 = SRj2; k2+; 五、实验结果截图六、实验总结通过这次实验使得我对应用动态规划法求解问题有了很大的提高。动态规划算法将原问题归约为规模较小、结构相同的子问题，建立原问题与子问题优化函数间的依赖关系，从规模较小的子问题开始，利用上述依赖关系求解规模更大的子问题，直到得到原始问题的解为止。采用逐步向前递推的方式，由子问题的最优解来计算原问题的最优解。算法
12、所用空间除邻接矩阵和最优解path以外，还需要长度为n的cost和d两个局部以为数组。这一算法的时间分析与DFS和BFS相似，总的执行时间为(n)实验4回溯法求n皇后问题一、实验目的1. 掌握回溯算法的基本思想2. 通过n皇后问题求解熟悉回溯法3. 使用蒙特卡洛方法分析算法的复杂度二、实验内容要求在一个8*8的棋盘上放置8个皇后，使得它们彼此不受“攻击”。两个皇后位于棋盘上的同一行、同一列或同一对角线上，则称它们在互相攻击。现在要找出使得棋盘上8个皇后互不攻击的布局。三、实验环境Window7;惠普笔记本；VC+6.0.四、算法描述和程序代码#includeusing namespace st
13、d;#define N 8int res1008;int countRes = 0;bool Place(int k,int i,int *x) for(int j = 0;jk;j+) if(xj = i | abs(xj-i) = abs(j-k) return false; return true;void NQueen(int k,int n,int *x) for(int i = 0;in;i+) if(Place(k,i,x) xk = i; if(k = n-1) for (i = 0; i n; i+) rescountResi = xi; cout xi t; countRe
14、s+; cout endl; else NQueen(k+1,n,x); void NQueen(int n,int *x) NQueen(0,n,x);int main() int xN; for(int i = 0;iN;i+) *(x+i) = -10; NQueen(N,x); coutendl共countRes种解endl; char show; cout是否显示图示?(Y/N)show; if(show = Y | show = y) for(int n = 0;ncountRes;n+) cout第n+1个解:endl; for(int i = 0;iN;i+) for(int j = 0;jN;j+) if(resni = j) coutQt; else cout*t; coutendl; return 0;五、实验结果截图六、实验总结通过这次试验我对皇后问题的知识点有了很大的了解，编写代码和调试代码的能力有所提高。在算法设计策略中，回溯法是比贪心法和动态规划法更一般的方法。n皇后问题以检查两皇后是否冲突作为基本运算，该算法的最坏情形复杂性为O(3n2nn)=O(nn+1)。n皇后问题有n!个叶子节点，遍历时间为（n！）。
