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

1、学号： 1501010024 姓名：高梁上机XX 实验名称：分治法一、逆序对数问题1、 算法思想可以使用分治法-归并排序解决上述问题。具体如下：将n个元素分成个数大致相同的两半，且左边的各个元素和右边的各个元素各自有序：（1）如果左边的元素a0右边的元素an/2，则逆序对数加1，接着a0继续与an/2+1比较，直到碰见a0an/2+t（tn/2）为止或直到与an-1比较完结束。（2）接着比较a1、a2、an/2-1与右边的元素，与上述过程相同。2、 实现代码及运行结果程序源代码如下：#include #include#include#define LEN 10/*归并排序*/该函数实现，将ar

2、ray的左右两半排好序的数组，归并为tmp，并排序 void Merge(int array,int tmp, int start, int mid, int end,int *t) int i = start, j=mid+1, k = start; while(i!=mid+1 & j!=end+1) if(arrayi = arrayj) tmpk+ = arrayj+;*t =*t+mid-i+1; else tmpk+ = arrayi+; while(i != mid+1) tmpk+ = arrayi+; while(j != end+1) tmpk+ = arrayj+; fo

3、r(i=start; i=end; i+) arrayi = tmpi; /递归的调用此函数，实现折半划分，只完成划分，不实现排序，最终返回array数组有序void MergeSort(int array, int tmp, int start, int end,int *t) int midIndex; if(start end) midIndex = (start + end) / 2; MergeSort(array, tmp, start, midIndex, t); MergeSort(array, tmp, midIndex+1, end, t); Merge(array, tm

4、p, start, midIndex, end, t); /*mian函数*/int main()int aLEN=4,1,9,8,5,6,7,3,10,2,bLEN,t=0;for (int i=0;iLEN;i+)printf(%4d ,ai);printf(n);MergeSort(a, b, 0, LEN-1,&t);printf(逆序对数为：%dn,t);return 0;实验结果：(1) 当数组aLEN=4,1,9,8,5,6,7,3,10,2时，程序运行结果见下图，达到预期结果。(2) 当查找元素aLEN=4,1,9,8,5,6,7时，程序运行结果见下图，达到预期结果。3、 复杂

5、度分析及算法改进(1)时间复杂度算法中，每一次查找将搜索范围缩小为原来的一般，即将一个规模为n的问题变成一个规模为n/2的问题，每次归并需要移动n次，即时间复杂度为O（n）。因此，该算法的时间复杂度T（n）可表示如下： T（n）= T（n/2）+O（n）可得T(n)=O(nlogn)。(2)空间复杂度 算法中使用bLEN个临时空间（用于存储数组aLEN的排序数），因此空间复杂度S（n）=O(n)。(3) 算法改进可以考虑使用三分查找（或K分查找），不知道效率是否会更好。二、大整数乘法问题4、 算法思想A和B的乘积AxB。如果把A分解成A=a*10n/2+b，把B分解成B=c*10n/2+d，那

6、么AxB=( a*10n/2+b)x(c*10n/2+d)=ac*10n+(ad+bc)*10n/2+bd=ac*10n+(a+b)(c+d)-ac-bd)*10n/2+bd 。实现代码及运行结果程序源代码如下：#include #include char* Add(char* str1,char *str2)int a1000,b1000,c1001,carry1001; c0=0;int i,Maxlen; int len1,len2; char str31001,*str;len1=strlen(str1);len2=strlen(str2); Maxlen = len1len2?len

7、1:len2;if(len1len2) for(i=len1-1;i=(len1-len2);i-)str2i = str2i-(len1-len2);for(i;i=0;i-)str2i =0;str2len1=0;else if(len1=(len2-len1);i-)str1i = str1i-(len2-len1);for(i;i=0;i-)str1i =0;str1len2=0;for(i=0;i=0;i-)ci= ai + bi; int d1001;for(i=Maxlen-1;i=1;i-)di+1 = ci % 10; ci-1 = ci-1 + ci/10;d1 = c0

8、% 10 ;d0 = c0 /10;int k; k=0;for(i=0;i=0;i-)ai = Ai - 0;for(i=n;i=1;i-)bi = ai-1*x; carryn = 0;for(i=n;i=1;i-)ci = bi + carryi;di = ci%10;carryi-1 = ci /10;di =carryi;if(x=0)for(i=0;in;i+)si = 0;si = 0;str = s; return str;elsei=0; j=0;while(di =0)i+;for(i;i=0;i-)strcpy(s2,s1); /s2 =s1; s1为新的.strcpy(s1,Mul1(A,Bi-0); /s1为字符串./printf(%sn,s1);for(j=n-i-1;j=1;j-)strcat(s1,0); /