数据结构与算法C语言——分治法.doc

《数据结构与算法C语言——分治法.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、学号：姓名：高梁上机XX实验名称：分治法一、逆序对数问题1、算法思想可以使用分治法-归并排序解决上述问题。具体如下：将n个元素分成个数大致相同的两半，且左边的各个元素和右边的各个元素各自有序：（1）如果左边的元素a[0]>右边的元素a[n/2]，则逆序对数加1，接着a[0]继续与a[n/2+1]比较，直到碰见a[0]#include#i

2、nclude#defineLEN10/*********************************归并排序************************************///该函数实现，将array[]的左右两半排好序的数组，归并为tmp[]，并排序voidMerge(intarray[],inttmp[],intstart,intmid,intend,int*t){inti=start,j=mid+1,k=start;while(i!=mid+1&&j!=end+1){if(array[i]>=array[j]){tmp[k++]=array[

3、j++];*t=*t+mid-i+1;}elsetmp[k++]=array[i++];}while(i!=mid+1)tmp[k++]=array[i++];while(j!=end+1)tmp[k++]=array[j++];for(i=start;i<=end;i++)array[i]=tmp[i];}//递归的调用此函数，实现折半划分，只完成划分，不实现排序，最终返回array[]数组有序voidMergeSort(intarray[],inttmp[],intstart,intend,int*t){intmidIndex;if(start

4、(start+end)/2;MergeSort(array,tmp,start,midIndex,t);MergeSort(array,tmp,midIndex+1,end,t);Merge(array,tmp,start,midIndex,end,t);}}/****************************mian函数*************************************/intmain(){inta[LEN]={4,1,9,8,5,6,7,3,10,2},b[LEN],t=0;for(inti=0;i

5、[i]);printf("");MergeSort(a,b,0,LEN-1,&t);printf("逆序对数为：%d",t);return0;}实验结果：(1)当数组a[LEN]={4,1,9,8,5,6,7,3,10,2}时，程序运行结果见下图，达到预期结果。(1)当查找元素a[LEN]={4,1,9,8,5,6,7}时，程序运行结果见下图，达到预期结果。1、复杂度分析及算法改进(1)时间复杂度算法中，每一次查找将搜索范围缩小为原来的一般，即将一个规模为n的问题变成一个规模为n/2的问题，每次归并需要移动n次，即时间复杂度为O（n）。因此，该算法的时间复杂度T（n）可

6、表示如下：T（n）=T（n/2）+O（n）可得T(n)=O(nlogn)。(2)空间复杂度算法中使用b[LEN]个临时空间（用于存储数组a[LEN]的排序数），因此空间复杂度S（n）=O(n)。(1)算法改进可以考虑使用三分查找（或K分查找），不知道效率是否会更好。二、大整数乘法问题1、算法思想A和B的乘积AxB。如果把A分解成A=a*10^n/2+b，把B分解成B=c*10^n/2+d，那么AxB=(a*10^n/2+b)x(c*10^n/2+d)=ac*10^n+(ad+bc)*10^n/2+bd=ac*10^n+((a+b)(c+d)-ac-bd)*10^n/2+bd。实

7、现代码及运行结果程序源代码如下：#include#includechar*Add(char*str1,char*str2){inta[1000],b[1000],c[1001],carry[1001];c[0]=0;inti,Maxlen;intlen1,len2;charstr3[1001],*str;len1=strlen(str1);len2=strlen(str2);Maxlen=len1>len2?len1:len2;if(len1>len2)