A算法分析实验指导提纲

1、算法分析实验指导提纲余波 实验一、归并排序及各种排序算法性能比较一. 上机实验的问题和要求：了解各种排序算法，并能独立在计算机上实现，同时并能够计算它们的时间复杂度，并用计算机来验证.二程序设计的基本思想，原理和算法描述： (1)选择排序法：每次选择一个当前最小的并和当前的相对的第一个元素交换，直到最后只有一个元素时结束； (2)插入排序法：从第二个元素开始，每次插入一个到当前有序序列中，使得有序，当所有的元素插入完毕时，就排好序了； (3)快速排序法：每次选择一个中间元素，并进行交换，使得中间元素的左边比它小，右边比它大，然后对左右两边进行递归；(4)堆排序：采用插入的模式产生堆，然后把根交

2、换到最后，在形成一个堆，在吧根与当前最后一个交换，如此，直到最后只剩下一个元素；(5)归并排序：将序列每次分成两组，在进行合并，直到递归完成；三、源程序及注释：(1)选择排序：/算法的精髓：每趟比较选择一个最小的并交换void fun(int *a,int n)int temp, min;int i,j;for(i = 0 ; i n-1 ; i+)min = i;for( j = i+1 ; j n ; j+)if(aj amin)min = j; /min指示每趟最小值的下标temp = amin;amin = ai;ai = temp;(2)插入排序：/算法的精髓：将ai依次插入到前面已

3、经排序的数组中void fun(int *a,int n)int I,j,val;for(i = 1 ; i n ; i+)val = ai; /将ai依次插入j = i-1;while(val = 0)aj+1 = aj; /每次后移一次j-;aj+1 = val;(3)快速排序：/快速排序void quicksort(int *a,int i,int j)if(i j)int p = partion(a,i,j); /得到合适位置quicksort(a,i,p-1); /左边进行排序quicksort(a,p+1,j); /右边进行排序/分区 把al放在正确的位置int partion(i

4、nt *a,int l,int r)int i = l;int j = r+1;int temp;int v = al;for(;)while(a+iv) /从右边找到第一个比v小的if(j = l)break;if(i = j)break;temp = ai; /交换ai = aj;aj = temp;temp = aj; /al 与正确位置的数交换aj = al;al = temp;return j; /j为正确位置(4)堆排序：/参数：数组和个数 插入法的思想/功能：数组的a0.an-2是堆，当进行操作以后a0.an-1是堆void heapfy(int *a,int n)int tem

5、p;int h = n-1;while(h 0) /h = 0 时说明其已经是根节点，结束if(ah a(h-1)/2) /当前结点大于其父节点temp = ah;ah = a(h-1)/2;a(h-1)/2 = temp;h = (h-1)/2;elsebreak;/输入：数组，和元素个数，a0的两个子树为堆/功能：使a0.an-1为堆void shiftdown(int *a,int n)int h = 0;int temp;while(2*h+2 a2*h+1) & (ah a2*h+2) /ah为父节点break;else if(a2*h+1 a2*h+2) /a2*h+1最大，交换使

6、其为父节点temp = ah;ah = a2*h+1;a2*h+1 = temp;h = 2*h+1;else /a2*h+2最大，交换使其为父节点temp = ah;ah = a2*h+2;a2*h+2 = temp;h = 2*h+2;/输入：数组，以及数组元素的个数/堆排序void heapsort(int *a,int n)int i;int temp;for(i = 1 ; i 1 ; i-) temp = a0; /把当前最大的换到后面a0 = ai;ai =temp;shiftdown(a,i); /通过操作，又变成一个堆(4)归并排序/输入：al =.=ap(有序) 且 ap+

7、1 = ap+2 = ar(有序)void merge(int *a,int l,int r,int p) /l = p = rint bN; /保存数据int i = l;int j = p+1;int k = i;int t;while(i = p) & (j = r)if(ai = aj)bk = ai;i+;k+;elsebk = aj;j+;k+;if(i=p)for(t = i ; t = p ; t+)bk = at;k+;elsefor(t = j ; t = r ; t+)bk = at;k+;for(i = l ; i = r ; i+)ai = bi;/归并排序，递归到最

8、简单的情况，再一步一步复杂化void mergesort(int *a,int l,int r) if(l r) /l=r时说明只有一个数据，不需要排序，本来就有序int p = (l+r)/2; /与树的后续遍历很相似mergesort(a,l,p); /排左边部分mergesort(a,p+1,r); /排右边部分merge(a,l,r,p); /两边合并实验二：快速排序一、实验内容利用分治算法解决排序问题，加深对分治策略的理解和运用的能力。二、算法思想分治算法思想：把规模为n的问题分成k个规模较小的子问题，且每个子问题相互独立且于原问题性质相同，递归的求解子问题，最后合并得到原问题的解。

9、快速排序算法思想：假定把对n个对象的排序看作是对1到n的n个整数的排序。快速排序算法的基本思想是从中取一适合的关键字k，以k为标准把需要排序的n个对象分成两部分，一部分比k小，另一部分比k大，即：(小于k的部分)k（大于k的部分）然后递归地对两部分分别进行快速排序，排序完毕后，简单的合并连接起来即可。三、实验过程int Partition( int L, int low, int high ) /对排序区间Llow.high进行一次分区，返回基准位置下标 pivotkey=Llow; i=low; j=high; L0=Llow; while( ii&L j .key=pivotkey) j-

10、; /i指向基准,j向右扫描 L i = L j ; / 比基准小的记录左移 while(ij&L i .key=pivotkey) i+; /j指向基准i向左扫描 L j = L i ; / 比基准大的记录右移 L i = L0; /基准到位 return i； /返回基准的位置下标 void QuickSort ( int L, int low, int high ) /对排序区间Llow.high进行快速排序 if( low high ) pivotloc=partition( L, low, high ); /进行分区，返回基准下标 QuickSort (L, low, pivotlo

11、c-1) ; / 对左半区进行快速排序 QuickSort (L, pivotloc+1, high) ; / 对右半区进行快速排序 int main() int n; coutn; cout用空格隔开，输入待排序的数字：endl; int data20; for(int i=1;idatai; QuickSort(data,1,n); cout经快速排序后的输出结果为：endl; for(int i=1;in;i+) coutdatai,; return (0);四、实验结论上述程序的一次输出结果：请输入待排序数字的个数：5用空格隔开，输入待排序的数字：12 5 4 23 1经快速排序后的输

12、出结果为：1,4,5,12,23,快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程中产生的两个区域分别包含n-1个元素和1个元素的时候。其算法的时间复杂度为O(n2),在最好的情况下每次划分的基准恰好为中值，可得其算法时间复杂度为O(nn)。实验三：0-1背包贪心法是一种改进了的分级处理方法。用贪心法设计算法的特点是一步一步地进行，根据某个优化测度（可能是目标函数，也可能不是目标函数），每一步上都要保证能获得局部最优解。每一步只考虑一个数据，它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加

13、为止。这种能够得到某种度量意义下的最优解的分级处理方法称为贪心法。 选择能产生问题最优解的最优度量标准是使用贪心法的核心问题。 假定有n个物体和一个背包，物体i 有质量wi，价值为pi，而背包的载荷能力为M。若将物体i的一部分xi（1=i=n,0=xi=1)装入背包中，则有价值pi*xi。在约束条件（w1*x1+w2*x2+wn*xn)=M下使目标(p1*x1+p2*x2+pn*xn)达到极大，此处0=xi0,1=i=n.这个问题称为背包问题（Knapsack problem）。 要想得到最优解，就要在效益增长和背包容量消耗两者之间寻找平衡。也就是说，总应该把那些单位效益最高的物体先放入背包。

14、 在实现算法的程序中，实现算法的核心程序倒没碰到很大的问题，然而实现寻找最优度量标准程序时麻烦不断！ 在寻找最优度量标准时，大致方向是用冒泡排序算法。也就是根据pi/wi的大小来对wi来排序。 在直接用此算法时，可以有如下的一段代码： /根据效益tempArrayi对重量wi排序，为进入贪心算法作准备 1 void sort(float tempArray, flaot w, int n) 2 3 int i = 0, j = 0; 4 int index = 0; 5 6 /用类似冒泡排序算法，根据效益pi/wi对wi排序 7 for (i = 0; i n; i+) 8 9 float s

15、wapMemory = 0; 10 float temp; 11 12 temp = tempArrayi; 13 index = i; 14 15 for (j = i + 1; j n; j+) 16 17 if (temp tempArrayj) 18 19 temp = tempArrayj; 20 index = j; 21 22 23 24 /对wi排序 25 swapMemory = windex; 26 windex = wi; 27 wi = swapMemory; 28 29 30 return; 31 然而仔细对算法分析后可以发现，“拿来主义”在这里用不上了！ 对算法的测

16、试用例是p3 = 25, 24, 15;w3 = 18, 15, 10。得到的结果如下： please input the total count of object: 3 Please input array of p : 25 24 15 Now please input array of w : 18 15 10 sortResulti is : 1 -.000000 1 1.600000 2 1.600000 after arithmetic data: xi 0.000000 0.333333 0.000000 可以看到其效益为x3 = 1.4, 1.6, 1.5，于是在M = 20

17、的情况下，其预想中的输出结果是0，1，0.5。然而事实上是不是就这样呢？ 当程序进入此函数经过必要的变量初始化后，进入了外围循环，也就是程序的第7行。第一轮循环中，temp = tempArray0 = 1.4,index = i = 0;程序运行到第15行，也就是进入了内层循环。 内层循环的主要任务是从第i + 1个元素之后找到一个最大的效益并保存此时的下标。到了第24行后，就开始对wi进行排序。 问题就在这里了！排序后的wi = 1.6, 1.6, 1.5，因此对wi排序后就既改变了wi的原有顺序，还改变了wi的原来值！ 据此，做出一些修改，得到了如下的一段代码： 1 void sort(

18、float tempArray, int sortResult, int n) 2 3 int i = 0, j = 0; 4 int index = 0, k = 0; 5 6 for (i = 0; i n; i+)/对映射数组赋初值0 7 8 sortResulti = 0; 9 10 11 for (i = 0; i n; i+) 12 13 float swapMemory = 0; 14 float temp; 15 16 temp = tempArrayi; 17 index = i; 18 19 for (j = i; j n; j+) 20 21 if (temp tempA

19、rrayj) & (sortResultj = 0) 22 23 temp = tempArrayj; 24 index = j; 25 26 27 28 if (sortResultindex = 0) 29 30 sortResultindex = +k; 31 32 33 34 for (i = 0; i n; i+) 35 36 if (sortResulti = 0) 37 38 sortResulti = +k; 39 40 41 42 return; 43 修改后最大的一个改变是没有继续沿用直接对wi排序，而是用wi的一个映射数组sortResulti。sortResulti中元

20、素值存放的是根据效益计算得wi的大小顺序！这样wi原有的值和位置都没有改变，从而使算法得以实现！ 至于有没有更好的实现版本，还在探索中！ #include #define MAXSIZE 100 /假设物体总数 #define M 20 /背包的载荷能力 /算法核心，贪心算法 void GREEDY(float w, float x, int sortResult, int n) float cu = M; int i = 0; int temp = 0; for (i = 0; i n; i+)/准备输出结果 xi = 0; for (i = 0; i cu) break; xtemp =

21、1;/若合适则取出 cu -= wtemp;/将容量相应的改变 if (i = n)/使背包充满 xtemp = cu / wtemp; return; void sort(float tempArray, int sortResult, int n) int i = 0, j = 0; int index = 0, k = 0; for (i = 0; i n; i+)/对映射数组赋初值0 sortResulti = 0; for (i = 0; i n; i+) float temp = tempArrayi; index = i; /找到最大的效益并保存此时的下标 for (j = 0;

22、 j n; j+) if (temp tempArrayj) & (sortResultj = 0) temp = tempArrayj; index = j; /对wi作标记排序 if (sortResultindex = 0) sortResultindex = +k; /修改效益最低的sortResulti标记 for (i = 0; i n; i+) if (sortResulti = 0) sortResulti = +k; return; /得到本算法的所有输入信息 void getData(float p, float w, int *n) int i = 0; printf(p

23、lease input the total count of object: ); scanf(%d, n); printf(Please input array of p :n); for (i = 0; i (*n); i+) scanf(%f, &pi); printf(Now please input array of w :n); for (i = 0; i (*n); i+) scanf(%f, &wi); return; void output(float x, int n) int i; printf(nnafter arithmetic data: advise method

24、n); for (i = 0; i n; i+) printf(x%dt, i); printf(n); for (i = 0; i n; i+) printf(%2.3ft, xi); return; void main() float pMAXSIZE, wMAXSIZE, xMAXSIZE; int i = 0, n = 0; int sortResultMAXSIZE; getData(p, w, &n); for (i = 0; i n; i+) xi = pi / wi; sort(x, sortResult, n); GREEDY(w, x, sortResult, n); ou

25、tput(x, n); getch(); 实验五 最短路的Dijkstra算法1、 实验目的：1.掌握最短路径的算法原理；2.掌握最短路径的算法实现。2、 实验内容：首先由教师讲解最短路径的算法，然后由学生验证其算法实现，对比手工计算与程序计算的结果异同并验证是否掌握算法的原理。3、 实验要求1.遵守实验室使用规范； 2.学习最短路径算法的原理；3.实现最短路径算法Dijkstra算法，对比手工计算与程序计算的结果异同；4.按时完成实验报告。4.实验步骤1.教师讲授实验内容及其基本要求2.教师指导进行编程实现Dijkstra算法5.参考伪码 void ShortestPath_DIJ(MGra

26、ph G，int v0，PathMatrix &P，ShortPathTable &D)/用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径Pv及其带权长度Dv。/若Pvw为TRUE，则w是从v0到v当前求得最短路径上的顶点。/finalv为TRUE当且仅当vS，即已经求得从v0到v的最短路径。 for(v=0； vG.vexnum； +v) finalv=FALSE； Dv=G.arcsv0v；for(w=0； wG.vexnum； +w) Pvw = FALSE；/设空路径 if (DvINFINITY) Pvv0=TRUE； Pvv=TRUE；/forDv0 = 0； fi

27、nalv0 = TRUE； /初始化，v0顶点属于S集 /开始主循环，每次求得v0到某个v顶点的最短路径，并加v到s集。 for(i=1; iG.vexnum；+i) /其余G.vexnum-1个顶点min = INFINITY； /当前所知离v0顶点的最近距离for(w=0；wG.vexnum；+w)if(!finalw) /w顶点在V-S中if(Dwmin)v=w；min=Dw； /w顶点离v0顶点更近finalv=TRUE； /离v0顶点最近的v加入S集for(w=0；wG.vexnum；+w) /更新当前最短路径及距离if(!finalw&(min+G.arcsvwDw) /修改Dw和

28、PwDw=min+G.arcsvw；Pw=Pv； Pww=TRUE； /Pw=Pv+w/if/for/ShortestPath_DIJ实验六 构造网络的最小生成树实验六.1 采用普里姆(prim)算法构造网络的最小生成树4、 实验目的：深入理解最小生成树的概念，熟练掌握普里姆（prim）算法的工作过程，并通过定义合适的数据结构，采用C语言程序实现。5、 实验内容：根据模板程序编制普里姆算法的程序，在计算机中进行调试，同时寻找两个结点大于6的网络，利用文件读入其邻接矩阵，运行程序。记录运行结果，并把运行结果与手工生成的结果进行比较，验证程序的正解性。要求从文本文件中读入网络的邻接矩阵。3、实验原

29、理 prim算法的主要步骤 数据表示 算法实现细节4、实验步骤与实验结果 编写prim算法的C语言程序 输入计算机进行调试 准备两个顶点大于6的网络，把网络的邻接矩阵输入文本文件中，运行程序，记录程序的运行结果，根据结果画出最小生成树，并与手工生成的最小生成树进行比较。实验结果：画出网络图，写出相应的邻接矩阵记录程序的运行结果，根据结果画出最小生成树并写出最小生成树的权值。附录：程序模板#include /*定义一个结构体，用于记录一条边的始点与终点*/typedef struct ppint p,q; edge;int g100100,u100,v100,vexnum;edge p100;/

30、用于记录最小生成树的各条边void input()/读入图的邻接矩阵int i,j,temp;FILE *fp;fp=fopen(pp5.txt,r);fscanf(fp,%d,&vexnum);for (i=1;i=vexnum;i+)printf(n);for (j=1;j=vexnum;j+)fscanf(fp,%d,&temp);gij=temp;printf(%d ,temp);fclose(fp);main()int i,j,k,m,n,ma,s=0; input();/输入数据for (i=1;i=vexnum;i+)/集合V中包含了所有顶点vi=1;u1=1;v1=0;/第1个

31、节点加入至集合U中，并从集合V中去掉for (i=1;i=vexnum-1;i+)/最多需vexnum-1条边/以下找连接节点集U至节点集V的最小边ma=1000;/ma存放最小边的权值for (j=1;j=i;j+)/集合U中的第j个节点，其编号为uj,每次增加一个，共有i个for (k=1;k0表示有边*/if(vk!=0&magujk&gujk0)ma=gujk;/保存最小边值m=uj;/最小边的始点编号n=k;/最小边的终点编号 s=s+ma;/求和 ui+1=n;vn=0;/把找到最小边的终点编号从V中去掉，并加入至U中 pi.p=m;pi.q=n;/保存最小边的始点编号与终点编号p

32、rintf(n);for (i=1;i=vexnum-1;i+)printf(n%d %d %d,pi.p,pi.q,gpi.ppi.q);printf(nsum=%dnn,s);实验六.2 采用克鲁斯卡尔(kruskal)算法构造网络的最小生成树1、 实验目的：深入理解最小生成树的概念，熟练掌握克鲁斯卡尔（kruskal）算法的工作过程，并通过定义合适的数据结构，采用C语言程序实现。2、 实验内容：根据模板程序编制克鲁斯卡你算法的程序，在计算机中进行调试，同时寻找两个结点大于6的网络，利用文件读入其邻接矩阵，运行程序。记录运行结果，并把运行结果与手工生成的结果进行比较，验证程序的正解性。要求

33、从文本文件中读入网络的邻接矩阵。3、实验原理 克鲁斯卡你算法的主要步骤 数据表示 算法实现细节4、实验步骤与实验结果 编写kruskal算法的C语言程序 输入计算机进行调试 准备两个顶点大于6的网络，把网络的邻接矩阵输入文本文件中，运行程序，记录程序的运行结果，根据结果画出最小生成树，并与手工生成的最小生成树进行比较。实验结果：画出网络图，写出相应的邻接矩阵记录程序的运行结果，根据结果画出最小生成树并写出最小生成树的权值。附录：程序模板#include typedef struct pp/定义最小生成树连的结构int p,q,r;/顶点1，顶点2，权值 edge;int g100100,sor

34、t100,vexnum;/定义图的邻接矩阵，集合，顶点数edge p100,temp;void input()/读入图的邻接矩阵int i,j,temp;FILE *fp;fp=fopen(pp5.txt,r);fscanf(fp,%d,&vexnum);for (i=1;i=vexnum;i+)printf(n);for (j=1;j=vexnum;j+)fscanf(fp,%d,&temp);gij=temp;printf(%d ,temp);fclose(fp);main()int i,j,k,l,m,sum=0;l=0;input();/从文件读入邻接矩阵for (i=1;i=vexn

35、um;i+)/初始时，每一顶点属于一个集合sorti=i;for (i=1;i=vexnum-1;i+)/把边存入p数组for (j=i+1;j0) l+; pl.p=i;pl.q=j;pl.r=gij;for (i=1;il;i+)/对边按权值进行排序k=i;m=pk.r;for (j=i+1;jpj.r) m=pj.r;k=j;temp=pi;pi=pk;pk=temp;k=1;i=1;while(kvexnum)if(sortpi.p!=sortpi.q)/同一条边的两个节点分别属于两个集合l=sortpi.q;/另一节点的集合号printf(n%d %d %d,pi.p,pi.q,pi

36、.r);/选择这条边sum=sum+pi.r;for (j=1;jhalf)|(t*(t-1)/2-counthalf) return; if (tn) sum+; else for (int i=0;i2;i+) p1t=i; count+=i; for (int j=2;j=t;j+) pjt-j+1=pj-1t-j+1pj-1t-j+2; count+=pjt-j+1; Backtrack(t+1); for (int j=2;j=t;j+) count-=pjt-j+1; count-=i; 实验八 ：N皇后一、上机实验的问题和要求：1 实现N皇后问题 二程序设计的基本思想，原理和算法

37、描述： (1)N皇后问题：通过回溯法的思想，解决N皇后;三、源程序及注释：(1)N皇后：#include#include#include/算法思想:利用全排列的算法，做相关的改动#define N 15#define Cswap(a,b) int temp = a; a = b; b = temp;int dig2*N-1; /记录各个主对角线的皇后情况，初始化为0说明还没有放任何皇后int sec_dig2*N-1; /记录各个负对角线的皇后情况，初始化为0说明还没有放任何皇后int rowN; /记录每列皇后的放的情况，初始化为0,1,.,N-1;int count; /记录8皇后的个数i

38、nt ok;/输出void output()int i,j;for(i = 0 ; i N ; i+)for(j = 0 ; j = N)output();count+;ok = 1;return;if(ok = 1)return;for(int k = i ; k N ; k+)Cswap(rowk,rowi);/只有主对角线和副对角线上都没有皇后时才可以放下一个皇后if(digrowi-i+N-1 = 0 & sec_digi+rowi = 0)/占用主对角线和副对角线digrowi-i+N-1 = sec_digi+rowi = 1;/放置下一个皇后queen(i+1);/还原主对角线和副对角线dig