1009040130-贺程-实验2.doc

算法分析与设计实验报告实验二 分治法算法设计姓名 贺程 学号 1009040130 班级 电子商务1002班时间 2013/3/12 地点 文波机房同 组 人 无指导教师 朱少林实验目的 a) 掌握分治法算法设计的一般思想和方法。b) 理解并掌握二分查找、归并分类、快速分类算法。c) 能熟练运用分治法求解问题。a) 实验中所准备的数据是有代表性的。实验内容 a) 写一个顺序查找算法，将其与二分查找算法一起转换成程序，上机验证。b) 选择不同规模的数据集运行上述二程序，统计它们的时间开销并比较。c) 归并分类、快速分类算法转换成程序并验证之。d) 选择不同规模的数据集运行上二程序，统计它们的时间开销并比较。相关内容（1）分治策略的抽象化控制Procedure DANDC(p, q)Global n, A(1:n); integer m,p,q /1pqn/If SMALL(p,q) Then return(G(p,q) Else mDIVIDE(p,q) /pmq/ Return(COMBINE(DANDC(p,m),DANDC(m+1,q)EndifendDANDC（2）二分检索算法Procedure BINSRCH(A,n,x,j)/给定一个按非降次序排列的元素数组A(1:n)，n1，判断x是否出现。/若是，置j，使得x=A(j)，若非，j=0/Integer low, high, mid, j, n ;low1;highnwhile lowhigh do midint(low+high)/2) case :xA(mid): lowmid+1 :else: jmid; return EndcaseRepeatj0endBINSRCH（3）归并分类算法Procedure MERGESORT(low, high)/A(low : high)是一个全程数组，它含有high-low+10个待分类的元素/Integer low, high;If low high thenmid int(low+high)/2) /求这个集合的分割点/call MERGESORT(low, mid) /将一个子集合分类/call MERGESORT(mid+1, high)/将另一个子集合分类/CALL MERGE(low,mid,high) /归并两个已分类的子集合/EndifendMERGESORTProcedure MERGE(low, mid, high)/A(low : high)是一个全程数组，它含有两个放在A（low : mid）和A（mid+1 : high）中的已分类的子集合。目标是将这两个已分类的集合归并成一个集合，并存放到A(low : high)中/使用一个辅助数组B(low : high)/Integer h, I, j, k, low, mid, high; /lowmidmid then for kj to high do /处理剩余的元素/ B(i) A(k);ii+1 repeat Else for kh to mid do B(i) A(k); ii+1 repeatendiffor k low to high do /将已归并的集合复制到A/A(k) B(k)repeatendMERGE（4）改进的归并分类算法Procedure MERGESORT1(low, high, p)/ 利用辅助数组LINK(low : high)将全程数组A(low : high)按降序分类。LINK中的值表示按分类次序给出A的下标的表，并把p置于指示这表的开始处/Global A(low : high), LINK(low : high)If high-low+1 16 Then call INSERTIONSORT(A, LONK, low, high, p) Elsemid int(low+high)/2) call MERGESORT(low, mid, q) /返回q表/call MERGESORT(mid+1, high, r)/返回r表/CALL MERGE(q, r, p) /将表q和r归并成表p/EndifendMERGESORT1Procedure MERGE1(low, mid, high)/q和r是全程数组LINK(1 : n)中两个表的指针，这两个表可用来获得全程数组A（1 : n）中已分类的子集合。此算法执行后构造出一个由p所指示的新表，利用此表可以得到按非降次序把A中元素分好类的元素表，同时q和r所指示的表随之消失。假定LINK（0）被定义，且假定表由0所结束。/使用一个辅助数组B(low : high)/Global n, A（1 : n）LINK（0 : n）Local integer i, j, ki q; jr; k0 /新表在LINK（0）处开始/while i0 and j0 do /当两表皆非空时/if A(h)A(j) /找较小的关键字/then LINK(k) i; ki; iLINK(i) /加一个新关键字到此表/ else LINK(k) j; kj; jLINK(j)endif ii+1repeatif i=0 then LINK(k) j /处理剩余的元素/ Else LINK(k) iendifpLINK(0)endMERGE1（5）快速分类算法Procedure QUICKSORT(p, q)/将全程数组A(1 : n)中元素A(p)，A(q)按递增的方式分类，认为A(n+1)已被定义，且大于或等于A(p : q)的所有元素，即A(n+1)=+/Integer p, q; global n, A(1 : n)If pqThen jq+1 call PARTITION(p,j) call QUICKSORT(p,j-1) /j是划分元素的位置/ call QUICKSORT(j+1,q)endifendQUICKSORTProcedure PARTITION(m , p)/在A（m），A（m+1），A（p-1）中的元素按如下方式重新排列：如果最初t= A（m），则在重新排列后，对于m和p-1之间的某个q，有A（q）=t，并使得对于mkq，有A（k）t，而对于qkp，有A（k）t。退出过程时，p带着划分元素所在的下标位置，即q的值返回。/Integer m, p, i; global A(m : p-1)vA(m);im; /A（m）是划分元素/looploop ii+1 until A(i)v repeat / i由左向右移/loop pp-1 until A(p)v repeat /p由右向左移/if ip then call INTERCHANGE(A(i), A(p) /A（i）和A（p）换位/else exitendifrepeatA(m)A(p);A(p)vendPARTITION实验步骤a) 准备一定规模的数据集用于实验。此数据集越大越有得于验证算法，可以考虑最终的数据个数超过10000个。b) 编写归并分类、快速分类程序，将上数据集中的数据分类。可以使用较少的数据调试程序时。c) 用规模从小到大的数据集运行上述程序，统计它们的运行时间，并作对比分析。d) 编写顺序查找、二分查找程序。e) 将查找程序与分类程序结合起来，用不同规模的数据集运行，统计程序运行时间。附加实验与思考（1）写一个自底向上的归并分类算法，并编程调试通过。用不同个数的数据运行该程序， 给出程序执行时间曲线。（2）设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表。 每个选手必须与其它n-1选手各赛一次； 每个选手一天只能赛一次。（3）任选一个可以用分治法求解的问题并用分治思想设计算法求解，将所设计算法转换成程序上机验证。实验步骤首先用种子生成器生成100000个整型数写到test.txt中，下面用到的测试数据均从text.txt中取，文件key.txt中只存放一个整型数800，用作查找的关键字，将排好序的数据写到文件sortResult.txt中。key.txt中的内容：800文件test.txt和sortResult.txt中包含有100000行数据，这里就不便显示。1 顺序查找#include#include#define N 100#define len 100000FILE *f1,*f2;int t1,t2;int search_seq(int key,int n)int i = 0;while(key != ni & i len)i+;if(key = ni)return i;elsereturn -1;void main()int key,i=0,j,data,nlen;f1 = fopen(key.txt,r);/读操作f2 = fopen(test.txt,r);fscanf(f1,%d, &key);while(i len)/这里用数组存放文件中的数据，占用了额外的存储空间，但是可以方便对不同算法进行时间复杂度分析fscanf(f2,%d, &data);ni+ = data;fclose(f1);fclose(f2);t1 = clock();for(j = 0;j N;j+)i = search_seq(key,n);t2 = clock();if(i = -1)printf(没有找到%dn,key);elseprintf(%d是第%d个数n,key,i+1);printf(程序运行时间：%fn,(double)t2-t1)/N);程序执行结果：800是56969个数程序运行时间是：0.160再从同样的文件中运用二分查找，查找相同的数据。2 二分查找 归并分类 快速分类在查找前先运用二路归并分类 或 快速分类 对待查找数据进行排序。#include#include#define N 1000#define len 100000FILE *f1,*f2,*f3;int search_bin(int key,int n)int high = len-1,low = 0,middle;while(low = high)middle = (low+high)/2;if(key nmiddle)low = middle+1;elsereturn middle;return 0;void Merge(int temp,int result,int size)/对序列r0一rn-1进行一次二路归并排序，每个有序子(文件)序列的长度为sizeint i,j,lb1,ub1,lb2,ub2,sp;lb1=0;/第一个子文件(序列)的起始位置sp =0;while(lb1+size=len-1)/测试是否存在两个可以合并的子文件lb2=lb1+size;/第二个子文件(序列)的起始位置ub1=lb2-1;/第一个子文件(序列)的结束位置if (lb2+size-1= len-1) /设置第二个子序列的结束位置ub2=lb2+size -1;elseub2=len-1;for(i=lb1,j=lb2; i=ub1 & j=ub2;)/合并两个子文件if(tempi=tempj)resultsp+=tempi+;elseresultsp+=tempj+;while(i=ub1) /序列2已归并完,将序列1中剩余的记录顺序存放到数组swap中resultsp+=tempi+;while(j=ub2)/序列1已归并完,将序列2中剩余的记录顺序存放到数组swap中resultsp+=tempj+;lb1=ub2+1;/whilefor (i=lb1; ilen;)/将原始序列中无法配对的子文件顺序存放到数组swap中(复制到结果文件)resultsp+=tempi+; void Merge_Sort(int n)/对数组n归并int size = 1,resultlen;/子文件的大小while (size len)Merge(n,result,size);/从a归并到bsize*=2;Merge (result,n,size);/从b归并到asize*=2;int Partition(int n,int low,int high)int pivotkey;n0 = nlow;pivotkey = nlow;while(low high)while(low = pivotkey)high-;nlow = nhigh;while(low high & nlow = pivotkey)low+;nhigh = nlow;nlow = n0;return low;void QSort(int n,int low,int high)int pivotloc;if(low high)pivotloc = Partition(n,low,high);/将nlow.high一分为二QSort(n,low,pivotloc-1);/对低子表递归排序，pivotloc是枢轴位置QSort(n,pivotloc+1,high);/对高子表递归排序void Quick_Sort(int n)QSort(n,0,len-1);void main()int key,i=0,j,data,nlen,t1,t2,t3,t4,t5,t6;f1 = fopen(key.txt,r);/读操作f2 = fopen(test.txt,r);fscanf(f1,%d, &key);while(i len)/这里用数组存放文件中的数据，占用了额外的存储空间，但是可以方便对不同算法进行时间复杂度分析fscanf(f2,%d, &data);ni+ = data;/归并排序 和 快速排序选择运行其一t1 = clock();Merge_Sort(n);t2 = clock();/*t3 = clock();Quick_Sort(n);t4 = clock();*/f3 = fopen( sortResult.txt , w ) ;/写操作,把排好序的数字写到文件sortResult.txt中for(j = 0;j le