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

word实验1 分治法合并排序一、实验目的1.掌握合并排序的根本思想2. 掌握合并排序的实现方法3.学会分析算法的时间复杂度4.学会用分治法解决实际问题二、实验容随机产生一个整型数组，然后用合并排序将该数组做升序排列，要求输出排序前和排序后的数组。三、实验环境Window10;惠普笔记本；Dev cpp4、 算法描述和程序代码#include<stdlib.h>#include<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 (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 <iostream>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<8; i+) int Time = maxTimei - 1;if (!flagTime) /如果最大期限那一天还未安排作业,如此将当前作业安排在所允许的最大期限那天resTime = Worki;flagTime = true;else /如果当前作业所允许的最大期限那一天已经安排的其他作业,就向前搜索空位,将该作业安排进去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<7; j+)maxReap += resj;cout << maxReap << endl;HomeWork()int i;for(i = 0;i<8;i+)flagi = false;maxReap = 0;int main() HomeWork a = HomeWork();a.dealWith();getchar();return 0;五、实验结果截图六、实验总结通过这个实验让我知道了闫新算法在实际当中的运用，也让我了解到了贪心算法的便捷以与贪心算法的实用性实验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中的多段图，试选择使用向前递推算法或向后递推算法求解多段图问题。三、实验环境Window10;惠普笔记本；Dev cpp四、算法描述和程序代码#include<stdio.h>int 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; r<k; 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)<Vjj) Vjj=Vii+Vij; j=-1; b4=0; for(r=k-1; r>=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; i<=ak-1; i+) /把第二层每个结点i与第一层结点s的边距赋值给Vii Vii=Viak; for(r=k-1; r>1; 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<=k; i+) printf("->%d",bi); return 0;五、实验结果截图6、 实验总结这个实验让我从中懂得了动态规划算法的核心，更加收敛的运用动态规划算法秋节各类问题，但动态规划算法最重要的还是方程的选择，这个在实际运用中相当重要。实验4回溯法求n皇后问题一、实验目的1. 掌握回溯算法的根本思想2. 通过n皇后问题求解熟悉回溯法3. 使用蒙特卡洛方法分析算法的复杂度二、实验容要求在一个8*8的棋盘上放置8个皇后，使得它们彼此不受“攻击。两个皇后位于棋盘上的同一行、同一列或同一对角线上，如此称它们在互相攻击。现在要找出使得棋盘上8个皇后互不攻击的布局。三、实验环境Window10;惠普笔记本；Dev cpp四、算法描述和程序代码#include<iostream>#include<math.h> 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+) 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;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 = j) cout<<"Q"<<"t" else cout<<"*"<<"t" cout<<endl; return 0;五、实验结果截图六、实验总结在n皇后问题中可以看出回溯算法求出的是这个问题的所有解，而不是单纯地求出了这个问题所产生的最优解，这样对于我们在实际运用方面十分实用。11 / 11