分治算法

课程名称：算法设计与分析课程设计

实验编号 及实验名称 姓 名 实验地点 指导教师 许夏梦 实验二 分治算法 系 别 应用数学系 学 号 实验日期 同组其他成员 071612117 班 级 实验时数 成 绩 0716121 新电605 2009-9-23 4 骆世广 一、 实验目的及要求 1、了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1kn，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那么，对于这类问题分治法是十分有效的； 2、掌握分治法的一般控制流程； DanC(p,q) Global n, A[1:n];integer m,p,q;// 1pqn if Small(p,q) then return G(p,q); else m=Divide(p,q);//pmq return Combine(DanC(p,m),DanC(m+1,q)); endif end DanC 3、实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。 二、 实验环境及相关情况（包含使用软件、实验设备、主要仪器及材料等） 使用软件：C++软件； 使用实验设备：计算机：Intel(R);Pentium(R) 4 CPU 2.80GHz;2.79 GHz,0.99 GB 的内存； 使用系统：Microsoft Windows XP;Professional;版本 2002；Service Pack 2. 第 1 页 共 8 页

三、 实验内容及步骤（包含简要的实验步骤流程） 实验内容： 1、 编程实现归并排序算法和快速排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数； 2、 输入10组相同的数据，验证排序结果和完成排序的比较次数； 3、 与复杂性函数所计算的比较次数比较； 4、 用表格列出比较结果； 5、 给出文字分析。 实验步骤： 1、归并排序算法： void Merge(SeqList R，int low，int m，int high) {//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的 //子文件R[low..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) //两子文件非空时取其小者输出到R1[p]上 R1[p++]=(R[i].key<=R[j].key)?R[i++]：R[j++]； while(i<=m) //若第1个子文件非空，则复制剩余记录到R1中 R1[p++]=R[i++]； while(j<=high) //若第2个子文件非空，则复制剩余记录到R1中 R1[p++]=R[j++]； for(p=0，i=low；i<=high；p++，i++) R[i]=R1[p]；//归并完成后将结果复制回R[low..high] } //Merge 2、快速排序算法： void qsort(int s[], int l, int r) { int i, j, x; if (l < r) { i = l; j = r; x = s[i]; while (i < j) { while(i < j && s[j] > x) j--; /* 从右向左找第一个小于x的数 */ if(i < j) s[i++] = s[j]; while(i < j && s[i] < x) i++; /* 从左向右找第一个大于x的数 */ if(i < j) s[j--] = s[i]; } s[i] = x; qsort(s, l, i-1); /* 递归调用 */ qsort(s, i+1, r); } } 第 2 页 共 8 页

四、 实验结果（包括程序或图表、结论陈述、数据记录及分析等，可附页） 1、 归并排序算法实验结果（程序见附四-1）： 2、 快速排序算法实验结果（程序见附四-2）： 第 3 页 共 8 页

五、 实验总结（包括心得体会、问题回答及实验改进意见，可附页） 通过在计算机实现归并排序算法和快速排序算法，对分治算法有了较好的理解。由于在之前的C语言、数据结构有学过快速排序算法，所以，用程序实现起来较简单。但归并算法我们从未接触过，所以会遇到较多的困难，通过调试一步步的修改错误，最终编程求出结果，在提高算法设计水平的同时我更清楚什么是分治算法了。 六、 教师评语

第 4 页 共 8 页

附四-1

1、 归并排序算法的程序代码： #include #include #include #define N 10

void 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 b[100]; i=a2_start; j=a3_start;

while(i<=a2_end&&j<=a3_end) {

if(a2[i]<=a3[j]) {

b[k++]=a2[i++]; } else {

b[k++]=a3[j++]; } }

while(i<=a2_end) {

b[k++]=a2[i++]; }

while(j<=a3_end) {

b[k++]=a3[j++]; }

for(h=0;ha1[a1_start+h]=b[h]; } }

void prnt(int *a,int n) { int i;

for(i=0;i第 5 页 共 8 页

printf(\"%3d\ }

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(lefthalf=(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\prnt(a,n); } }

/*main 函数*/ int main()

{int i,n,a[100]={0};

printf(\" 归并排序\");

printf(\"\\n============================================\\n\"); printf(\" 请输入待排序数组个数,以回车结束：\\n\"); scanf(\"%d\

printf(\"\\n 请输入待排序数组,以回车结束：\\n\"); for(i=0;iscanf(\"%d\

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)

第 6 页 共 8 页

{ int c=0; c= a; a=b; b=c; }

void disp(int a[],int n) { for(int i=0;iint partion(int a[],int L,int r) { int i=L-1,j=r; int v=a[r]; while(1) {

while(a[++i]=j) break;

Swap(a[i],a[j]); }

Swap(a[i],a[r]); 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+1,r); }

int main()

{ int i,n,a[100];

printf(\" 请输入待排序数组个数,以回车结束：\\n\"); scanf(\"%d\

printf(\"\\n 请输入待排序数组,以回车结束：\\n\"); for(i=0;iscanf(\"%d\ quicksort(a,0,n-1); disp(a,n); getchar(); }

第 7 页 共 8 页

第 8 页 共 8 页