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

本科实验报告课程名称： 算法设计与分析 实验项目：分治法合并排序 贪心法作业调度 动态规划法求多段图问题 回溯法求n皇后问题 实验地点： 致远楼B503 专业班级： 学号： 学生姓名： 指导教师： 2017年 3月18日实验1 分治法合并排序一、实验目的1. 掌握合并排序的基本思想2. 掌握合并排序的实现方法3. 学会分析算法的时间复杂度4. 学会用分治法解决实际问题二、实验内容随机产生一个整型数组，然后用合并排序将该数组做升序排列，要求输出排序前和排序后的数组。三、实验环境Window10;惠普笔记本；Dev cpp4、 算法描述和程序代码#include#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+;elsetk+ = aj+;while (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); /调用合并函数。int main() int i;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();return 0;五、实验结果截图六、实验总结通过编写这个程序，我进一步了解了分株算法的思想，在实际运用过程当中，尤其是在算法编写方面相对来说比较简单，实现起来较为容易。实验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)，求该条件下的最大效益。三、实验环境Window10;惠普笔记本；Dev cpp四、算法描述和程序代码#include using namespace std;const int Work8 = 45,30,28,25,23,15,10,1 ;/所有作业按收益从大到小排序const int maxTime8 = 4,7,3,2,4,6,7,5 ;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;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中的多段图，试选择使用向前递推算法或向后递推算法求解多段图问题。三、实验环境Window10;惠普笔记本；Dev cpp四、算法描述和程序代码#includeint V5050;int a50,b20;int static k,n,m;void createGraph() int i,j,t,s; printf(请输入结点数：); scanf(%d,&n); for(i=0; i=n; i+) for(j=0; j=n; j+) Vij=0;/初始化Vij=0,表示两结点没有边相连 printf(输入图的层数：); scanf(%d,&k); printf(请输入每层的结点数的最大编号：); a0=0; for(i=1; i=k; i+) scanf(%d,&ai); printf(请输入边数：); scanf(%d,&m); printf(请输入结点之间的关系(如：结点i和结点j的距离为s，则输入i,j,s)n); for(t=1; t=m; t+) scanf(%d%d%d,&i,&j,&s); Vij=s; int Backward()/向后求解法 int i,j,t,r; for(i=a1+1; i=a2; i+) /把第二层每个结点i与第一层结点s的边距赋值给Vii Vii=V1i; for(r=2; rk; r+) /向后逐层求解 for(i=ar-1+1; i=ar; i+) /遍历第r层的每个结点i与第(r+1)层结点j之间的边距,选择此刻最优解 for(j=ar+1; j=ar+1; j+) if(Vij!=0&Vjj=0)/第一次把此刻路径长度赋给Vjj Vjj=Vii+Vij; else if(Vij!=0&Vjj!=0) if(Vii+Vij)=2; r-) for(i=ar+1; i=ar+1; i+) if(br=j) break; for(j=ar-1+1; j=ar; j+) if(Vii-Vji)=Vjj) br=j; break; return Vnn;int Forward()/向前求解法 int i,j,t,r; for(i=ak-2+1; i1; r-) /向前逐层求解 for(j=ar-1+1; j=ar; j+)/遍历第r层的每个结点i与第(r-1)层结点j之间的边距,选择此刻最优解 for(i=ar-2+1; i=ar-1; i+) if(Vij!=0&Vii=0)/第一次把此刻路径长度赋给Vjj Vii=Vjj+Vij; else if(Vij!=0&Vii!=0) if(Vjj+Vij)Vii) Vii=Vjj+Vij; for(r=2; r=k-1; r+) for(i=ar-2+1; i=ar-1; i+) for(j=ar-1+1; j=ar; j+) if(Vii-Vij)=Vjj) br=j; break; i=j; r+; return V11;int main() int i,j,r,sp; createGraph(); b1=1; bk=n; /sp=Forward(); sp=Backward(); printf(最短路径长度为：%dn,sp); printf(最短路径为：); printf(%d,b1); for(i=2; i%d,bi); return 0;五、实验结果截图6、 实验总结这个实验让我从中懂得了动态规划算法的核心，更加收敛的运用动态规划算法秋节各类问题，但动态规划算法最重要的还是方程的选择，这个在实际运用中相当重要。实验4回溯法求n皇后问题一、实验目的1. 掌握回溯算法的基本思想2. 通过n皇后问题求解熟悉回溯法3. 使用蒙特卡洛方法分析算法的复杂度二、实验内容要求在一个8*8的棋盘上放置8个皇后，使得它们彼此不受“攻击”。两个皇后位于棋盘上的同一行、同一列或同一对角线上，则称它们在互相攻击。现在要找出使得棋盘上8个皇后互不攻击的布局。三、实验环境Window10;惠普笔记本；Dev cpp四、算法描述和程序代码#include#include using namespace std;#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; 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;iN;i+) *(x+i) = -10; NQueen(N,x); coutendl共countRes种解endl; char show; cout是否显示图示?(Y/N)show; if(show = Y | show = y) for(int