《算法设计与分析实验.doc》由会员分享，可在线阅读，更多相关《算法设计与分析实验.doc（49页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date算法设计与分析实验算法设计与分析实验本科实验报告课程名称： 算法设计与分析 实验项目：分治法合并排序、 贪心法作业调度、动态规划法求多段图问题、回溯法求n皇后问题实验地点： 行知楼c122 专业班级： 软件1310 学号： 2013005990 学生姓名： 葛文卿 指导教师： 王幸民 2015年 03 月 28 日实验项目分治法合并排序一、 实验目的掌握合并排序的基本
2、思想掌握合并排序的实现方法学会分析算法的时间复杂度学会用分治法解决实际问题二、实验内容随机产生一个整型数组，然后用合并排序将该数组做升序排列，要求输出排序前和排序后的数组。三、实验环境程序设计语言：c+编程工具：microsoft visual studio 2010四、算法描述和程序代码#include using namespace std; void merge(int *data, int p, int q, int r) int n1, n2, i, j, k; int *left=NULL, *right=NULL; n1 = q-p+1; n2 = r-q; left = (in
3、t *)malloc(sizeof(int)*(n1); right = (int *)malloc(sizeof(int)*(n2); for(i=0; in1; i+) /对左数组赋值 lefti = datap+i; for(j=0; jn2; j+) /对右数组赋值 rightj = dataq+1+j; i = j = 0; k = p; while(in1 & jn2) /将数组元素值两两比较，并合并到data数组 if(lefti = rightj) datak+ = lefti+; else datak+ = rightj+; for(; in1; i+) /如果左数组有元素剩
4、余，则将剩余元素合并到data数组 datak+ = lefti; for(; jn2; j+) /如果右数组有元素剩余，则将剩余元素合并到data数组 datak+ = rightj; void mergeSort(int *data, int p, int r) int q; if(p r) /只有一个或无记录时不须排序 q = (int)(p+r)/2); /将data数组分成两半 mergeSort(data, p, q); /递归拆分左数组 mergeSort(data, q+1, r); /递归拆分右数组 merge(data, p, q, r); /合并数组 int main()
5、 int n,i; int* input = NULL; /输入数据 coutn; input = (int *)malloc(sizeof(int)*(n); cout请对数组赋值: ; for(i=0; iinputi; /处理数据 mergeSort(input,0,n-1); /输出结果 for(i=0; in; +i) coutinputi ; coutendl; return 0; for(; in1; i+) /如果左数组有元素剩余，则将剩余元素合并到data数组 datak+ = lefti; for(; jn2; j+) /如果右数组有元素剩余，则将剩余元素合并到data数组
6、 datak+ = rightj; void mergeSort(int *data, int p, int r) int q; if(p r) /只有一个或无记录时不须排序 q = (int)(p+r)/2); /将data数组分成两半 mergeSort(data, p, q); /递归拆分左数组 mergeSort(data, q+1, r); /递归拆分右数组 merge(data, p, q, r); /合并数组 int main() int n,i; int* input = NULL; /输入数据 coutn; input = (int *)malloc(sizeof(int)*
7、(n); cout请对数组赋值: ; for(i=0; iinputi; /处理数据 mergeSort(input,0,n-1); /输出结果 for(i=0; in; +i) coutinputi ; coutendl; return 0; 五、实验结果截图六、实验总结掌握了合并排序的基本思想，并实现了合并排序。实验项目贪心法作业调度一、实验目的掌握贪心算法的基本思想掌握贪心算法的典型问题求解进一步多级调度的基本思想和算法设计方法学会用贪心法分析和解决实际问题二、实验内容设计贪心算法实现作业调度，要求按作业调度顺序输出作业序列。如已知n=8，效益p=(35,30,25,20,15,10,5
8、,1)，时间期限d=(4,2,4,5,6,4,5,7)，求该条件下的最大效益。三、实验环境程序设计语言：c+编程工具：microsoft visual studio 2010四、算法描述和程序代码#includeusingnamespacestd;#defineN6/作业数#defineM3/机器数intt7,b,p7,s47,d4,c;voidzuoye(ints47,intd4,intp7,intt7)intf;intn=2;for(inti=1;i=M;i+)si1=pi;di=ti;for(intl=M+1;l=N;l+)if(d1d3)f=3;sfn=pl;n+;df=df+tl;f
9、or(intw=1;w=3;w+)for(intr=1;r=6;r+)if(swr!=0) coutswr;coutendl;voidmain()cout共有三台机器，请输入六个作业工作时间：;for(inti=1;iti;for(inte=1;e=6;e+)pe=e;for(intj=1;j=6;j+)for(intq=j+1;qtj)c=pq;pq=pj;pj=c;b=tq;tq=tj;tj=b;zuoye(s,d,p,t);五、实验结果截图六、实验总结掌了贪心算法的基本思想学会了用贪心算法求解典型问题实验项目动态规划法求多段图问题一、 实验目的掌握动态规划算法的基本思想掌握多段图的动态规
10、划算法选择邻接表或邻接矩阵方式来存储图分析算法求解的复杂度。二、实验内容设G=(V,E)是一个带权有向图，其顶点的集合V被划分成k2个不相交的子集Vi，1i=k，其中V1和Vk分别只有一个顶点s（源）和一个顶点t（汇）。图中所有边的始点和终点都在相邻的两个子集Vi和Vi+1中。求一条s到t的最短路线。参考讲义p136图5-24中的多段图，试选择使用向前递推算法或向后递推算法求解多段图问题。三、实验环境程序设计语言：c+编程工具：microsoft visual studio 2010四、算法描述和程序代码#include #include #define N 12 #define K 5 #d
11、efine MAX 23767int costNN; int pathK; typedef struct nodeint v;int w;struct node *next;node;node LN; void init(node *L) int i, j;node *p, *q; for (i = 0; i N; i+) for (j = 0; j N; j+) costij = MAX; cost01 = 9;cost02 = 7;cost03 = 3;cost04 = 2;cost15 = 4;cost16 = 2;cost17 = 1;cost25 = 2;cost26 = 7;cos
12、t37 = 11;cost46 = 11;cost47 = 8;cost58 = 6;cost59 = 5;cost68 = 4;cost69 = 3;cost79 = 5;cost710 = 6;cost811 = 4;cost911 = 2;cost1011 = 5;/*生成邻接表*/ for (i = 0; i N; i+)Li = (node *)malloc(sizeof(node);for (i = 0; i N; i+)q = Li;for (j = 0; j 0 & costij v = j;p-w = costij;q-next = p;q = p;q-next = NULL
13、;void Method1() /*使用邻接矩阵存储*/ int i, j, maxlen, temp, vN, dN; for (i = 0; i = 0; i-) for (maxlen = MAX, j = i + 1; j 0 & costij + vj maxlen) maxlen = costij + vj; temp = j; vi = maxlen; di = temp; path0 = 0; pathK-1 = N - 1;for (i = 1; i = K - 2; i+) pathi = dpathi-1;void Method2(node *L) /*使用邻接表存储*/
14、 int i, j, maxlen, temp, vN, dN;node *p;for (i = 0; i = 0; i-) p = Li-next;maxlen = MAX; while (p)if (p-w + vp-v w + vp-v; temp = p-v;p = p-next; vi = maxlen; di = temp; path0 = 0; pathK-1 = N - 1;for (i = 1; i = K - 2; i+) pathi = dpathi-1;void print() int i; for (i = 0; i K; i+) printf(%d , pathi
15、+ 1); printf(n);int main()init(&L); printf(最短路径:n ); Method1(); print(); printf(最短路径:n); Method2(&L); print(); system(pause); return 0;五、实验结果截图六、实验总结掌握了动态规划算法的基本思想掌握了多段图的动态规划算法实验项目回溯法求n皇后问题一、实验目的掌握回溯算法的基本思想通过n皇后问题求解熟悉回溯法使用蒙特卡洛方法分析算法的复杂度二、实验内容要求在一个8*8的棋盘上放置8个皇后，使得它们彼此不受“攻击”。两个皇后位于棋盘上的同一行、同一列或同一对角线上，则
16、称它们在互相攻击。现在要找出使得棋盘上8个皇后互不攻击的布局。三、实验环境程序设计语言：c+编程工具：microsoft visual studio 2010四、算法描述和程序代码#include#includeint x100;bool(int k) int i; for(i=1;ik;i+) if(xk=xi|abs(k-i)=abs(xk-xi) return 0; return 1;void queue(int n) int i,k; for(i=1;i=1) xk=xk+1; while(xk=n&!bool(k) xk=xk+1;/搜索下一列 if(xk=n&k=n)/得到一个输出 for(i=1;i=n;i+) printf(%d ,xi); printf(n); /return else if(xk=n&kn) k=k+1;/ else xk=0;/重置xk,回溯 k=k-1; void main() int n; printf(输入皇后个数n:n); scanf(%d,&n); queue(n);五、实验结果截图六、实验总结掌握了回溯算法的基本思想通过n皇后问题求解熟悉了回溯法-