太原理工大学算法设计与分析实验报告

1、本科实验报告课程名称： 分算法设计与分析 实验项目：分治法合并排序 贪心法作业调度 动态规划法求多段图问题 回溯法求n皇后问题 实验地点： 行勉楼B209 专业班级：软件14*班 学号：201400*学生姓名： * 指导教师： * 2016年 4 月10日实验1 分治法合并排序一、实验目的1. 掌握合并排序的基本思想2. 掌握合并排序的实现方法3. 学会分析算法的时间复杂度4. 学会用分治法解决实际问题二、实验内容随机产生一个整型数组，然后用合并排序将该数组做升序排列，要求输出排序前和排序后的数组。三、实验环境Window7;惠普笔记本；VC+6.0.4、 算法描述和程序代码 #include

2、<iostream>#include<stdio.h>#include<time.h>using 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+;elsetk+ = aj+;while

3、(i <= mid)tk+ = ai+;while (j <= right)tk+ = aj+;for (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

4、;cout << "排序前的数组为："for (i = 0; i < 10; i+) ai = random(100); /调用random函数，产生10个0-100的随机数。cout << ai << " "cout << endl;MergeSort(0, 9);cout << "排序后的数组为："for (i = 0; i < 10; i+) cout << ai << " "getchar();五、实验结果截图六

5、、实验总结分治算法是很有用的算法，分治法的设计一般是递归的。两路合并排序是一个典型的分治算法，其基本运算为元素比较，最坏情况下的时间为W(n)=O(nlogn)，在排序过程中需要使用与原序列相同长度的辅助数组temp，因此它所需的额外空间为O(n)。通过编写代码，我很好的掌握了分治法的步骤：划分；求解子问题；合并。对“分治策略”有了更深的体会，它将原问题划分为彼此独立的、规模较小而结构相同的子问题。实验2 贪心法作业调度一、实验目的1. 掌握贪心算法的基本思想2. 掌握贪心算法的典型问题求解3. 进一步多级调度的基本思想和算法设计方法4. 学会用贪心法分析和解决实际问题二、实验内容设计贪心算法

6、实现作业调度，要求按作业调度顺序输出作业序列。如已知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 <iostream>using namespace std;const int Work8 = 35,30,25,20,15,1

7、0,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<8; i+) int Time = maxTimei - 1;if (!flagTime) /如果最大期限那一天还未安排作业,则将当前作业安排在所允许的最大期限那天resTime = Worki;flagTime = true;else /如果当前作业所允许的最大

8、期限那一天已经安排的其他作业,就向前搜索空位,将该作业安排进去for (int j = Time - 1; j >= 0; j-)if (!flagj) resj = Worki;flagj = true;break;cout << "作业完成顺序为:" ;for (i = 0; i<7; i+) cout << resi << "t"cout << endl;cout << endl << "最佳效益为:"int j;for (j = 0; j<

9、;7; j+)maxReap += resj;cout << maxReap << endl;HomeWork()int i;for(i = 0;i<8;i+)flagi = false;maxReap = 0;void main() HomeWork a = HomeWork();a.dealWith();getchar();五、实验结果截图六、实验总结通过实验编写代码使得我对应用贪心法求解问题有了很大的提高。贪心法是一种求解组合优化问题的算法设计技术，其求解过程由一些列决策构成。贪心算法的关键在于贪心策略，两要素是：最优子结构和贪心策略，对带时限的作业进行排序

10、是一个典型的贪心算法，在本次实验中我使用了改进后的可行解判定方法来解决这个问题，使算法的时间从(n2)减少到接近O(n)。实验3 动态规划法求多段图问题一、实验目的1. 掌握动态规划算法的基本思想2. 掌握多段图的动态规划算法3. 选择邻接表或邻接矩阵方式来存储图4. 分析算法求解的复杂度二、实验内容设G=(V,E)是一个带权有向图，其顶点的集合V被划分成k>2个不相交的子集Vi，1<i<=k，其中V1和Vk分别只有一个顶点s（源）和一个顶点t（汇）。图中所有边的始点和终点都在相邻的两个子集Vi和Vi+1中。求一条s到t的最短路线。参考课本P124图7-1中的多段图，试选择使

11、用向前递推算法或向后递推算法求解多段图问题。三、实验环境Window7;惠普笔记本；VC+6.0.四、算法描述和程序代码#include<iostream>using namespace std;structint 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 << "请输入待排序的数目:"cin >> L.length;

12、cout << "请输入待排序的数:"for (int c = 0; c<L.length; c+)cin >> L.rc;cout << "合并排序前的数组为:"for (int d = 0; d<L.length; d+)cout << L.rd << " "cout << endl;MSort(L.r, L.r, 0, L.length - 1);cout << "合并排序后的数组为:"for (int i3 =

13、0; i3<L.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, t); /对右子序列排序Mer

14、ge(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+;elseTRk = SRj+;if (i <= mid) /如果左子序列还有元素未输出，则将左子序列剩余元素依次输出int k1 = k;for (int i1 = i; i1

15、<= mid; i1+)TRk1 = SRi1;k1+;if (j <= n) /如果右子序列还有元素未输出，则将右子序列剩余元素依次输出int k2 = k;for (int j2 = j; j2 <= n; j2+)TRk2 = SRj2;k2+;五、实验结果截图6、 实验总结通过这次实验使得我对应用动态规划法求解问题有了很大的提高。动态规划算法将原问题归约为规模较小、结构相同的子问题，建立原问题与子问题优化函数间的依赖关系，从规模较小的子问题开始，利用上述依赖关系求解规模更大的子问题，直到得到原始问题的解为止。采用逐步向前递推的方式，由子问题的最优解来计算原问题的最优解

16、。算法所用空间除邻接矩阵和最优解path以外，还需要长度为n的cost和d两个局部以为数组。这一算法的时间分析与DFS和BFS相似，总的执行时间为(n)实验4回溯法求n皇后问题一、实验目的1. 掌握回溯算法的基本思想2. 通过n皇后问题求解熟悉回溯法3. 使用蒙特卡洛方法分析算法的复杂度二、实验内容要求在一个8*8的棋盘上放置8个皇后，使得它们彼此不受“攻击”。两个皇后位于棋盘上的同一行、同一列或同一对角线上，则称它们在互相攻击。现在要找出使得棋盘上8个皇后互不攻击的布局。三、实验环境Window7;惠普笔记本；VC+6.0.四、算法描述和程序代码#include<iostream>

17、;using namespace std;#define N 8int res1008;int countRes = 0;bool Place(int k,int i,int *x) for(int j = 0;j<k;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;i<n;i+) if(Place(k,i,x) xk = i; if(k = n-1) for (i = 0; i < n; i+) resco

18、untResi = xi; cout << xi << "t" countRes+; 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;i<N;i+) *(x+i) = -10; NQueen(N,x); cout<<endl<<"共"<<countRes<<"种解"<<endl; char show; cout<<"是否显示图示?(Y/N)"<<endl; cin>>show; if(show = 'Y' | show = 'y') for(int n = 0;n<countRes;n+) cout<<"第"<<n+1<<"个解:"<<endl; for(int i = 0;i<N;i+) for(int j = 0;j<N;j+) if(resni