分治算法.doc

广东金融学院实验报告课程名称：算法设计与分析课程设计实验编号及实验名称实验二 分治算法系 别应用数学系姓 名许夏梦学 号071612117班 级0716121实验地点新电605实验日期2009-9-23实验时数4指导教师骆世广同组其他成员成 绩一、 实验目的及要求1、了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1kn，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那么，对于这类问题分治法是十分有效的；2、掌握分治法的一般控制流程； DanC(p,q) Global n, A1:n;integer m,p,q;/ 1pqn if Small(p,q) then return G(p,q); else m=Divide(p,q);/pmq return Combine(DanC(p,m),DanC(m+1,q); endif end DanC3、实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。二、 实验环境及相关情况（包含使用软件、实验设备、主要仪器及材料等）使用软件：C+软件；使用实验设备：计算机：Intel(R);Pentium(R) 4 CPU 2.80GHz;2.79 GHz,0.99 GB 的内存；使用系统：Microsoft Windows XP;Professional;版本 2002；Service Pack 2.三、 实验内容及步骤（包含简要的实验步骤流程）实验内容：1、 编程实现归并排序算法和快速排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数；2、 输入10组相同的数据，验证排序结果和完成排序的比较次数；3、 与复杂性函数所计算的比较次数比较；4、 用表格列出比较结果；5、 给出文字分析。实验步骤：1、归并排序算法：void Merge(SeqList R，int low，int m，int high)/将两个有序的子文件Rlow.m)和Rm+1.high归并成一个有序的 /子文件Rlow.high int i=low，j=m+1，p=0； /置初始值 RecType *R1； /R1是局部向量，若p定义为此类型指针速度更快 R1=(ReeType *)malloc(high-low+1)*sizeof(RecType)； if(! R1) /申请空间失败 Error(Insufficient memory available!)； while(i=m&j=high) /两子文件非空时取其小者输出到R1p上 R1p+=(Ri.key=Rj.key)?Ri+：Rj+； while(i=m) /若第1个子文件非空，则复制剩余记录到R1中 R1p+=Ri+； while(j=high) /若第2个子文件非空，则复制剩余记录到R1中 R1p+=Rj+； for(p=0，i=low；i=high；p+，i+) Ri=R1p；/归并完成后将结果复制回Rlow.high /Merge 2、快速排序算法：void qsort(int s, int l, int r) int i, j, x; if (l r) i = l; j = r; x = si; while (i j) while(i x) j-; /* 从右向左找第一个小于x的数 */ if(i j) si+ = sj; while(i j & si x) i+; /* 从左向右找第一个大于x的数 */ if(i j) sj- = si; si = x; qsort(s, l, i-1); /* 递归调用 */ qsort(s, i+1, r); 四、 实验结果（包括程序或图表、结论陈述、数据记录及分析等，可附页）1、 归并排序算法实验结果（程序见附四-1）：2、 快速排序算法实验结果（程序见附四-2）：五、 实验总结（包括心得体会、问题回答及实验改进意见，可附页）通过在计算机实现归并排序算法和快速排序算法，对分治算法有了较好的理解。由于在之前的C语言、数据结构有学过快速排序算法，所以，用程序实现起来较简单。但归并算法我们从未接触过，所以会遇到较多的困难，通过调试一步步的修改错误，最终编程求出结果，在提高算法设计水平的同时我更清楚什么是分治算法了。六、 教师评语附四-11、 归并排序算法的程序代码：#include #include #include#define N 10void merge(int *a1,int a1_start,int *a2,int a2_start, int a2_end,int *a3,int a3_start,int a3_end); void merge_sort(int *a,int left,int right);/*函数功能：两个数组合并成一个数组； 函数原型：void merge(int *a1,int a1_start,int a1_end,int *a2,int a2_start,int a2_end,int *a3,int a3_start,int a3_end)函数参数：函数返回值：void */void merge(int *a1,int a1_start,int *a2,int a2_start,int a2_end,int *a3,int a3_start,int a3_end)int i,j,h,k=0;int b100; i=a2_start; j=a3_start;while(i=a2_end&j=a3_end) if(a2i=a3j) bk+=a2i+; else bk+=a3j+; while(i=a2_end) bk+=a2i+;while(j=a3_end) bk+=a3j+;for(h=0;hk;h+) a1a1_start+h=bh; void prnt(int *a,int n) int i; for(i=0;in;i+) printf(%3d,ai); printf(n);/*函数功能：使用归并排序法进行排序：从小到大；函数原型：void merge_sort(int *a,int left,int right) 函数参数：int *a:数组名,int left:排序数组的开始下标,int right:排序数组的结束下标 函数返回值：void */int s=1;void merge_sort(int *a,int left,int right,int n)int half;if(leftright)half=(int)(left+right)/2);merge_sort(a,left,half,n);merge_sort(a,half+1,right,n);merge(a,left,a,left,half,a,half+1,right);printf(n=第%d次排序=n,s+);prnt(a,n);/*main 函数*/int main()int i,n,a100=0; printf( 归并排序); printf(n=n); printf( 请输入待排序数组个数,以回车结束：n);scanf(%d,&n); printf(n 请输入待排序数组,以回车结束：n); for(i=0;in;i+) scanf(%d,&ai); printf(n=n); printf(n 初始数组：); prnt(a,n); merge_sort(a,0,n-1,n); printf(n=n); printf(n 排序结果：); prnt(a,n); getch();附四-2快速排序算法的程序代码： #include void Swap(int&a,int&b) int c=0; c= a; a=b; b=c; void disp(int a,int n) for(int i=0;in;i+) printf(%d ,ai); int partion(int a,int L,int r) int i=L-1,j=r; int v=ar; while(1) while(a+iv); while(v=j) break; Swap(ai,aj); Swap(ai,ar); return i; void quicksort(int a,int L,int r) if(L=r) return; int i; i=partion(a,L,r); quicksort(a,L,i-1); quicksort(a,i