1、太原理工大学算法设计与分析实验报告资料课程名称：本科实验报告分算法设计与分析实验项目：分治法合并排序贪心法作业调度动态规划法求多段图问题 回溯法求 n 皇后问题实验地点：行勉楼 B209专业班级：软件 14*班学生姓名：指导教师：学号：201400*2016 年 4 月 10 日1一、实验目的1.2.3.4.掌握合并排序的基本思想 掌握合并排序的实现方法 学会分析算法的时间复杂度 学会用分治法解决实际问题4、算法描述和程序代码 #include#include#includeusing namespace std;#define random(x)(rand()%x);int a10;/合并排
2、序函数。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) i
3、f (left right) int mid = (left + right) / 2); MergeSort(left, mid);2MergeSort(mid + 1, right);Merge(left, mid, right); /调用合并函数。void 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;
4、i+) cout ai ;getchar();3一、实验目的1.2.3.4.掌握贪心算法的基本思想掌握贪心算法的典型问题求解进一步多级调度的基本思想和算法设计方法 学会用贪心法分析和解决实际问题四、算法描述和程序代码#include using namespace std;const int 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 de
5、alWith() /遍历所有作业:int i;for (i = 0; i= 0; j-)4if (!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;i8;i+)flagi = false;maxReap = 0;void main() HomeWor
6、k a = HomeWork();a.dealWith();getchar();5一、实验目的1.2.3.4.掌握动态规划算法的基本思想 掌握多段图的动态规划算法选择邻接表或邻接矩阵方式来存储图 分析算法求解的复杂度四、算法描述和程序代码#includeusing namespace std;structint r50;int length;SqList, L;void MSort(int SR, int TR1, int s, int t);6void Merge(int sR, int TR, int i, int mid, int n);void main()cout L.length;
7、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, 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;el
8、se /若序列的长度超过 1，则划分为两个子序列mid = (s + t) / 2; /将待排序的序列一分为二MSort(SR, TR2, s, mid); /对左子序列排序MSort(SR, TR2, mid + 1, 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 = S
9、Rj)TRk = SRi+;elseTRk = SRj+;if (i = mid) /如果左子序列还有元素未输出，则将左子序列剩余元素依次输出7int k1 = k;for (int i1 = i; i1 = mid; i1+)TRk1 = SRi1;k1+;if (j = n) /如果右子序列还有元素未输出，则将右子序列剩余元素依次输出 int k2 = k;for (int j2 = j; j2 = n; j2+)TRk2 = SRj2;k2+;8四、算法描述和程序代码 #includeusing namespace std;#define N 8int res1008;int count
10、Res = 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;elseNQueen(k+1,n,x);9void NQu
11、een(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;elsecout*t;coutendl;return 0;1011
