數(shù)據(jù)結構與算法C語言——分治法.doc

學號： 1501010024 姓名：高梁上機XX 實驗名稱：分治法一、逆序對數(shù)問題1、 算法思想可以使用分治法-歸并排序解決上述問題。具體如下：將n個元素分成個數(shù)大致相同的兩半，且左邊的各個元素和右邊的各個元素各自有序：（1）如果左邊的元素a0右邊的元素an/2，則逆序對數(shù)加1，接著a0繼續(xù)與an/2+1比較，直到碰見a0an/2+t（tn/2）為止或直到與an-1比較完結束。（2）接著比較a1、a2、an/2-1與右邊的元素，與上述過程相同。2、 實現(xiàn)代碼及運行結果程序源代碼如下：#include #include#include#define LEN 10/*歸并排序*/該函數(shù)實現(xiàn)，將array的左右兩半排好序的數(shù)組，歸并為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+; for(i=start; i=end; i+) arrayi = tmpi; /遞歸的調用此函數(shù)，實現(xiàn)折半劃分，只完成劃分，不實現(xiàn)排序，最終返回array數(shù)組有序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, tmp, start, midIndex, end, t); /*mian函數(shù)*/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(逆序對數(shù)為：%dn,t);return 0;實驗結果：(1) 當數(shù)組aLEN=4,1,9,8,5,6,7,3,10,2時，程序運行結果見下圖，達到預期結果。(2) 當查找元素aLEN=4,1,9,8,5,6,7時，程序運行結果見下圖，達到預期結果。3、 復雜度分析及算法改進(1)時間復雜度算法中，每一次查找將搜索范圍縮小為原來的一般，即將一個規(guī)模為n的問題變成一個規(guī)模為n/2的問題，每次歸并需要移動n次，即時間復雜度為O（n）。因此，該算法的時間復雜度T（n）可表示如下： T（n）= T（n/2）+O（n）可得T(n)=O(nlogn)。(2)空間復雜度 算法中使用bLEN個臨時空間（用于存儲數(shù)組aLEN的排序數(shù)），因此空間復雜度S（n）=O(n)。(3) 算法改進可以考慮使用三分查找（或K分查找），不知道效率是否會更好。二、大整數(shù)乘法問題4、 算法思想A和B的乘積AxB。如果把A分解成A=a*10n/2+b，把B分解成B=c*10n/2+d，那么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 。實現(xiàn)代碼及運行結果程序源代碼如下：#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?len1: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 % 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); /