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

学号：1501010024姓名：高梁上机XX实验名称：分治法一、逆序对数问题1、算法思想可以使用分治法-归并排序解决上述问题。具体如下：将n个元素分成个数大致相同的两半，且左边的各个元素和右边的各个元素各自有序：（1）如果左边的元素a[0]右边的元素a[n/2]，则逆序对数加1，接着a[0]继续与a[n/2+1]比较，直到碰见a[0]a[n/2+t]（tn/2）为止或直到与a[n-1]比较完结束。（2）接着比较a[1]、a[2]、……、a[n/2-1]与右边的元素，与上述过程相同。2、实现代码及运行结果程序源代码如下：#includestdio.h#includestdlib.h#includemath.h#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[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(startend){midIndex=(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;iLEN;i++)printf(%4d,a[i]);printf(\n);MergeSort(a,b,0,LEN-1,&t);printf(逆序对数为：%d\n,t);return0;}实验结果：(1)当数组a[LEN]={4,1,9,8,5,6,7,3,10,2}时，程序运行结果见下图，达到预期结果。(2)当查找元素a[LEN]={4,1,9,8,5,6,7}时，程序运行结果见下图，达到预期结果。3、复杂度分析及算法改进(1)时间复杂度算法中，每一次查找将搜索范围缩小为原来的一般，即将一个规模为n的问题变成一个规模为n/2的问题，每次归并需要移动n次，即时间复杂度为O（n）。因此，该算法的时间复杂度T（n）可表示如下：T（n）=T（n/2）+O（n）可得T(n)=O(nlogn)。(2)空间复杂度算法中使用b[LEN]个临时空间（用于存储数组a[LEN]的排序数），因此空间复杂度S（n）=O(n)。(3)算法改进可以考虑使用三分查找（或K分查找），不知道效率是否会更好。二、大整数乘法问题4、算法思想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。实现代码及运行结果程序源代码如下：#includestdio.h#includestring.hchar*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=len1len2?len1:len2;if(len1len2){for(i=len1-1;i=(len1-len2);i--)str2[i]=str2[i-(len1-len2)];for(i;i=0;i--)str2[i]='0';str2[len1]='\0';}elseif(len1len2){for(i=len2-1;i=(len2-len1);i--)str1[i]=str1[i-(len2-len1)];for(i;i=0;i--)str1[i]='0';str1[len2]='\0';}for(i=0;iMaxlen;i++){a[i]=str1[i]-'0';b[i]=str2[i]-'0';}i--;for(i;i=0;i--)c[i]=a[i]+b[i];intd[1001];for(i=Maxlen-1;i=1;i--){d[i+1]=c[i]%10;c[i-1]=c[i-1]+c[i]/10;}d[1]=c[0]%10;d[0]=c[0]/10;intk;k=0;for(i=0;i=Maxlen;i++){if(d[i]==0&&i==0)i++;str3[k]=d[i]+'0';k++;}str3[k]='\0';str=str3;returnstr;}char*Mul1(char*A,intx)//x是个位数{inta[1000],b[1000],c[1000],carry[1000],d[1000];inti,j,n;n=strlen(A);chars[1000],*str;for(i=n-1;i=0;i--){a[i]=A[i]-'0';}for(i=n;i=1;i--){b[i]=a[i-1]*x;}carry[n]=0;for(i=n;i=1;i--){c[i]=b[i]+carry[i];d[i]=c[i]%10;carry[i-1]=c[i]/10;}d[i]=carry[i];if(x==0){for(i=0;in;i++)s[i]='0';s[i]='\0';str=s;returnstr;}else{i=0;j=0;while(d[i]==0)i++;for(i;i=n;i++){s[j]=d[i]+'0';j++;}s[j]='\0';str=s;returnstr;}}char*Mul(char*A,char*B)//两个字符串的乘积//voidMul(char*A,char*B){inta[1000],b[1000],c[2000],carry[1000],d[2000];inti,j,n;n=strlen(B);chars[2000],s1[2000]=0,s2[2000],*str;for(i=n-1;i=0;i--){strcpy(s2,s1);//s2=s1;s1为新的..strcpy(s1,Mul1(A,B[i]-'0'));//s1为字符串..//printf(%s\n,s1);for(j=n-i-1;j=1;j--)strcat(s1,0);//printf(%s\n,s1);strcpy(s1,Add(s1,s2));//printf(%s\n,s1);}str=s1;returnstr;/*for(i;i=n;i++){s[j]=d[i]+'0';j++;}s[j]='\0';str=s;returnstr;}*/}intmain(){chara[1000],b[1000],c[2000];gets(a);gets(b);//intx;scanf(%d,&x);//strcpy(c,Mul1(a,x));strcpy(c,Mul(a,b));printf(%s\n,c);//Mul(a,b);return0;}实验结果：当数组X=123456789123456789,Y=123456789123456789时，程序运行结果见下图，达到预期结果。5、复杂度分析及算法改进(1)时间复杂度在运算中，共进行3次n/2位整数的乘法，6次加减法和2次移位，即该算法的时间复杂度T（n）可表示如下：T（n）=3T（n/2）+O（n）n1T（1）=1可得T(n)=O(n^1.59)。(2)空间复杂度空间复杂度S（n）=O(1)。