第3章分治法PPT课件

1、3.2 求解排序问题求解排序问题3.1 分治法概述分治法概述3.3 求解查找问题求解查找问题3.4 求解组合问题求解组合问题3.5 求解大整数乘法和矩阵乘法问题求解大整数乘法和矩阵乘法问题3.6 并行计算简介并行计算简介对于一个规模为对于一个规模为n的问的问题：题：若若该问题可以容易地解决该问题可以容易地解决（比如说规模（比如说规模n较小）则直接解较小）则直接解决，否决，否则将其分解为则将其分解为k个规个规模较小的子问模较小的子问题，这题，这些子问题互相独立且与原问题形式相些子问题互相独立且与原问题形式相同，递同，递归地解这些子问归地解这些子问题，然题，然后将各子问题的解合并得到后将各子问题的

2、解合并得到原问题的解原问题的解。这种算法设计策略叫做这种算法设计策略叫做分治法。3.1 分治法概述分治法概述分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：（1）该问题的规模缩小到一定的程度就可以容易地解决。）该问题的规模缩小到一定的程度就可以容易地解决。（2）该问题可以分解为若干个规模较小的相同问题。）该问题可以分解为若干个规模较小的相同问题。（3）利用该问题分解出的子问题的解可以合并为该问题的）利用该问题分解出的子问题的解可以合并为该问题的解。解。（4）该问题所分解出的各个子问题是相互独立）该问题所分解出的各个子问题是相互独立的，即的，即子问子问题之间不

3、包含公共的子问题。题之间不包含公共的子问题。分分治法通常采用递归算法设计技治法通常采用递归算法设计技术，在术，在每一层递归上都有每一层递归上都有3个步骤：个步骤： 分解：分解：将原问题分解为若干个规模较将原问题分解为若干个规模较小，相小，相互独互独立，与立，与原问题形式相同的子问题。原问题形式相同的子问题。 求解子问题：求解子问题：若子问题规模较小而容易被解决则直若子问题规模较小而容易被解决则直接求接求解，否解，否则递归地求解各个子问题。则递归地求解各个子问题。 合并：合并：将各个子问题的解合并为原问题的解。将各个子问题的解合并为原问题的解。 分治法的一般的算法分治法的一般的算法设计框架如下设

4、计框架如下：divide-and-conquer(P) if |P|n0 return adhoc(P); 将将P分解为较小的子问题分解为较小的子问题 P1，P2，Pk; for(i=1;ii & aj=tmp) j-; /从右向左扫从右向左扫描，找描，找第第1个关键字小于个关键字小于tmp的的aj ai=aj;/将将aj前移到前移到ai的位置的位置 while (ij & ai=tmp) i+; /从左向右扫从左向右扫描，找描，找第第1个关键字大于个关键字大于tmp的的ai aj=ai;/将将ai后移到后移到aj的位置的位置ai=tmp;return i;测试用例：测试用例：

5、5，2，1，7，10，6，9，4，3，8快速排序算法：快速排序算法：void QuickSort(int a，int s，int t)/对对as.t元素序列进行递增排序元素序列进行递增排序 if (st) /序列内至少存在序列内至少存在2个元素的情况个元素的情况 int i=Partition(a，s，t); QuickSort(a，s，i-1);/对左子序列递归排序对左子序列递归排序 QuickSort(a，i+1，t);/对右子序列递归排序对右子序列递归排序 【算法分析】快速快速排序的时间主要耗费在划分操作排序的时间主要耗费在划分操作上，对上，对长度为长度为n的区间进行划的区间进行划分，共

6、分，共需需n-1次关键字的比次关键字的比较，时较，时间复杂间复杂度为度为O(n)。对对n个记录进行快速排序的过程构成一棵递归个记录进行快速排序的过程构成一棵递归树，在树，在这样这样的递归树的递归树中，每中，每一层至多对一层至多对n个记录进行划个记录进行划分，所分，所花时间为花时间为O(n)。当初始排序数据正序或反序当初始排序数据正序或反序时，此时，此时的递归树高度为时的递归树高度为n，快快速排序呈现最坏情速排序呈现最坏情况，即况，即最坏情况下最坏情况下的时间复杂度为的时间复杂度为O(n2)；当初始排序数据当初始排序数据随机分随机分布布，使，使每次分成的两个子区间中的每次分成的两个子区间中的记录

7、个数记录个数大致相大致相等等，此，此时的时的递归树高度为递归树高度为log2n，快，快速排序呈速排序呈现最好情现最好情况，即况，即最好情况下最好情况下的时间复杂度为的时间复杂度为O(nlog2n)。快速。快速排序算法的排序算法的平均时间复杂度平均时间复杂度也是也是O(nlog2n)。 已知由已知由n（n2）个）个正整数正整数构成的集合构成的集合A=ak（0kn），将其划分为两个不相交的子集），将其划分为两个不相交的子集A1和和A2，元素，元素个数分别是个数分别是n1和和n2， A1和和A2中元素之和分别为中元素之和分别为S1和和S2。设。设计一个尽可能计一个尽可能高效高效的划分算法，满足的划分

8、算法，满足|n1-n2|最小且最小且|S1-S2|最大。要求：最大。要求：（1）给出算法的基本设计思想。）给出算法的基本设计思想。（2）根据设计思想，采用）根据设计思想，采用C、C+描述算法，关键之描述算法，关键之处给出注释。处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。）说明你所设计算法的时间复杂度和空间复杂度。2016年全国计算机学科专业考研题示例22/121查找第查找第n/2小的元素小的元素递归快速排序 思路：将：将A递增排序，前递增排序，前 n/2 个元素放在个元素放在A1中，其他放中，其他放在在A2中中将最小的将最小的 n/2 个元素放在个元素放在A1中，其他放在中，其

9、他放在A2中中23/121int Partition(int a,int low,int high) /以以alow为为基准划分基准划分 int i=low,j=high; int povit=alow; while (ij) while (i=povit) j-; ai=aj; while (ij & aii)/在右区间查找在右区间查找 low=i+1; else high=i-1;/在左区间查找在左区间查找 int s1=0,s2=0; for (int i=0;in/2;i+) s1+=ai; for (int j=n/2;j2，即，即归并操作在相邻的多个有序子表中进归并操作在相

10、邻的多个有序子表中进行，则行，则叫多路归并排序。叫多路归并排序。 1. 自底向上的二路归并排序算法例例如，对如，对于于2，5，1，7，10，6，9，4，3，8序序列，列，其其排序过程排序过程如下图所示，图如下图所示，图中方括号内是一个有序子序列。中方括号内是一个有序子序列。底底顶顶2，5， 1，7，10，6， 9，4， 3，83，83，82，51，76，104，93，81，2，5，74，6，9，101，2，4，5，6，7，9，101，2，3，4，5，6，7,8，9，10二路归并排序的二路归并排序的分治策略分治策略如下：如下：循环循环 log2n 次，次，length依次取依次取1、2、log2

11、n。每次。每次执行以下步骤：执行以下步骤： 分解：分解：将原序列分解成将原序列分解成length长度的若干子序列。长度的若干子序列。 求解子问题：求解子问题：将相邻的两个子序列调用将相邻的两个子序列调用Merge算法算法合并成一个有序子序列。合并成一个有序子序列。 合并：合并：由于整个序列存放在数组中由于整个序列存放在数组中a中，排中，排序过程序过程是就地进行是就地进行的，合的，合并步骤不需要执行任何操作。并步骤不需要执行任何操作。 void Merge(int a，int low，int mid，int high)/有序表合并算法有序表合并算法alow.mid和和amid+1.highalo

12、w.high int *tmpa; int i=low，j=mid+1，k=0; tmpa=(int *)malloc(high-low+1)*sizeof(int); while (i=mid & j=high) if (ai=aj)/将第将第1子表中的元素放入子表中的元素放入tmpa中中 tmpak=ai; i+; k+; else/将第将第2子表中的元素放入子表中的元素放入tmpa中中 tmpak=aj;j+; k+; while (i=mid)/将第将第1子表余下部分复制到子表余下部分复制到tmpa tmpak=ai; i+; k+; while (j=high)/将第将第2子

13、表余下部分复制到子表余下部分复制到tmpa tmpak=aj; j+; k+; for (k=0，i=low;i=high;k+，i+) /将将tmpa复制回复制回a中中 ai=tmpak; free(tmpa);/释放释放tmpa所占内存空间所占内存空间void MergePass(int a，int length，int n)/一趟二路归并排序一趟二路归并排序 int i; for (i=0;i+2*length-1n;i=i+2*length) /归并归并length长的两相邻子表长的两相邻子表Merge(a，i，i+length-1，i+2*length-1); if (i+lengt

14、h-1n) /余下两个子余下两个子表，后表，后者长度小于者长度小于length Merge(a，i，i+length-1，n-1); /归并这两个子表归并这两个子表剩余剩余2个子个子表表归并归并的测试用例的测试用例：49 38 65 97 76 13 27 剩余剩余1个子表归并的测试用例个子表归并的测试用例：18,2,20,34,12,32,6,16,1,52，5，1，7，10，6，9，4，3，8void MergeSort(int a，int n)/二路归并算法二路归并算法 int length; for (length=1;lengthn;length=2*length)MergePass

15、(a，length，n);【算法分析】对于对于上述二路归并排序算上述二路归并排序算法，当法，当有有n个元素个元素时，需时，需要要 log2n 趟归趟归并，每并，每一趟归一趟归并，其并，其元素比较次数不超元素比较次数不超过过n-1，元，元素移动次数都是素移动次数都是n，因，因此归并排序的时间复杂度为此归并排序的时间复杂度为O(nlog2n)。2. 自顶向下的二路归并排序算法例例如，对如，对于于2，5，1，7，10，6，9，4，3，8序序列，说明其自顶向下的二路归并排序的过程。列，说明其自顶向下的二路归并排序的过程。2，5，1，7，10， 6，9，4，3，82，51, 2，57，101，2，5,

16、7, 10252，512，5，17，102，5，1，7，106，9，4，3，83，86，94, 6，93，4，6, 8, 91，2，3, 4, 5, 6, 7, 8, 9, 106，9，43，86，946971038分解分解合并合并底底顶顶设设归并排序的当前区间是归并排序的当前区间是alow.high，则，则递归归并的两递归归并的两个步骤如下：个步骤如下： 分解：分解：将序列将序列alow.high一分为一分为二，即二，即求求mid=(low+high)/2；递归地对两个子序列；递归地对两个子序列alow.mid和和amid+1.high进行继续分解。其终结条件是子序列长度为进行继续分解。其终

17、结条件是子序列长度为1（因为一个元素的子表一定是有序（因为一个元素的子表一定是有序表）。表）。 求解子问题：求解子问题：排序两个子序列排序两个子序列alow.mid和和amid+1.high。 合合并：并：与分解过程相与分解过程相反，将反，将已排序的两个子序列已排序的两个子序列alow.mid和和amid+1.high归并为一个有序序列归并为一个有序序列alow.high。对应的二路归并排序算法如下：对应的二路归并排序算法如下：void MergeSort(int a，int low，int high)/二路归并算法二路归并算法 int mid;if (low1容易推容易推出，出，T(n)=O

18、(nlog2n)。 【ACM、面试题】求解按求解按“最多排序最多排序”到到“最小排序最小排序”的的顺序排列问题。一个序列中的顺序排列问题。一个序列中的“未排序未排序”的度量是相对于彼此顺的度量是相对于彼此顺序不一致的条目对的数量，例如，在字母序列序不一致的条目对的数量，例如，在字母序列“DAABEC”中，该中，该度量为度量为5，因为，因为D大于右边是大于右边是4个字母，个字母，E大于其右边的大于其右边的1个字母。个字母。该度量称为该序列的该度量称为该序列的逆序数逆序数。序列。序列“AACEDGG”只有一个逆序对只有一个逆序对（E和和D），它几乎被排序好了，而序列），它几乎被排序好了，而序列“Z

19、WQM”有有6个逆序对，个逆序对，它是未排序的，恰好是反序。它是未排序的，恰好是反序。 你需要对若干个你需要对若干个DNA序列（仅包含序列（仅包含4个字母个字母A、C、G和和T的字的字符串）分类，注意是分类而不是按字母顺序排序，而是按照符串）分类，注意是分类而不是按字母顺序排序，而是按照“最最多排序多排序”到到“最小排序最小排序”的顺序排列，所有的顺序排列，所有DNA序列的长度都相序列的长度都相同。同。输入：输入：第一行包含两个整数：第一行包含两个整数：n（0n50）表示字符串长度，）表示字符串长度，m（0m100）表示字符串个数。后面是表示字符串个数。后面是m行，每行包含一个长度为行，每行包

20、含一个长度为n的字符串。的字符串。输出：输出：按按“最多排序最多排序”到到“最小排序最小排序”的顺序输出所有字符串。若两个字的顺序输出所有字符串。若两个字符串的逆序对个数相同，按原始顺序输出它们。符串的逆序对个数相同，按原始顺序输出它们。输入样例：输入样例：10 6 AACATGAAGGTTTTGGCCAATTTGGCCAAAGATCAGATTTCCCGGGGGGAATCGATGCAT样例输出：样例输出：CCCGGGGGGAAACATGAAGGGATCAGATTTATCGATGCATTTTTGGCCAATTTGGCCAAAAACATGAAGG AAAAACGGGT3 求求逆序数逆序数AACA例

21、：AACAA AC AAAAC1AAAC#define MAXN 55#define MAXM 105/*求字符串求字符串a的逆序数的逆序数ans*/int ans; /全局变量全局变量,累计逆序数累计逆序数void Merge(char a,int low,int mid,int high) /两个相邻有序段归并两个相邻有序段归并 int i=low; int j=mid+1; int k=0; char *tmp=(char *)malloc(high-low+1)*sizeof(int); while(i=mid & jaj) tmpk+=aj+; ans+=mid-i+1; e

22、lse tmpk+=ai+; while(i=mid) tmpk+=ai+; while(j=high) tmpk+=aj+; for(int k1=0;k1alow.high alow+k1=tmpk1; free(tmp);alow ai amid alow.midamid+1 aj ahigh amid+1.high若若aiaj ans+=mid-i+1ai.midaj逆序数逆序数ans=0void Merge_sort(char a,int low,int high) /递归二路归并排序递归二路归并排序 if(lowhigh) int mid=(low+high)/2;Merge_so

23、rt(a,low,mid);Merge_sort(a,mid+1,high);Merge(a,low,mid,high); int Inversion(char a,int n) /二路归并法求字符串二路归并法求字符串a的逆序数的逆序数 ans=0; Merge_sort(a,0,n-1); return ans;/*/typedef struct int v;/存放存放stri的逆序数的逆序数 int i;/存放字符串的下标存放字符串的下标i ElemType;/声明数组声明数组b的元素类型的元素类型struct Cmp/定义排序关系函数定义排序关系函数 bool operator()(co

24、nst ElemType &s,const ElemType &t) const return s.vt.v; /指定按逆序数递增排序指定按逆序数递增排序;int main() int i,n,m; char strMAXMMAXN; ElemType bMAXM; memset(b,0,sizeof(b); char tmpMAXN; scanf(%d%d,&n,&m);/输入输入n和和m for (i=0;im;i+)/输入输入m个字符串个字符串 scanf(%s,stri); for (i=0;im;i+)/求所有字符串的逆序数求所有字符串的逆序数 str

25、cpy(tmp,stri);/由于保存原序列不变由于保存原序列不变,临时复制到临时复制到tmp中中 bi.v=Inversion(tmp,n);/求求tmp的逆序对个数的逆序对个数 bi.i=i;/记录原来的下标记录原来的下标 stable_sort(b,b+m,Cmp();/采用稳定的排序算法采用稳定的排序算法 for (i=0;irmax1，则，则max1=lmax1，max2=MAXlmax2，rmax1；例如：例如：（ 4, 6, 3, 2, 5, 1 ）否则否则max1=rmax1，max2=MAXlmax1，rmax2。例如（例如（2, 5, 1, 4, 6, 3）void sol

26、ve(int a,int low,int high,int &max1,int &max2) if (low=high)/区间只有一个元素区间只有一个元素 max1=alow;max2=-INF; else if (low=high-1)/区间只有两个元素区间只有两个元素 max1=max(alow,ahigh); max2=min(alow,ahigh); else/区间有两个以上元素区间有两个以上元素 int mid=(low+high)/2;int lmax1,lmax2;solve(a,low,mid,lmax1,lmax2); /左区间求左区间求lmax1和和lmax

27、2int rmax1,rmax2;solve(a,mid+1,high,rmax1,rmax2); /右区间求右区间求lmax1和和lmax2if (lmax1rmax1) max1=lmax1; max2=max(lmax2,rmax1);/lmax2,rmax1中求次大元素中求次大元素else max1=rmax1; max2=max(lmax1,rmax2);/lmax1,rmax2中求次大元素中求次大元素 【算法分析】对于对于solve(a，0，n-1，max1，max2)调用，其比较次数的递推式为：调用，其比较次数的递推式为： T(1)=T(2)=1 T(n)=2T(n/2)+1 /

28、合并的时间为合并的时间为O(1)可以推导出可以推导出T(n)=O(n)。基本思路：设设alow.high是当前的查找区是当前的查找区间，首间，首先确定先确定该区间的中点位置该区间的中点位置mid= (low+high)/2 ；然后将待查的；然后将待查的k值与值与amid.key比较：比较： （1）若）若k=amid，则，则查找成功并返回该元素的物理下标；查找成功并返回该元素的物理下标； （2）若）若kamid，则，则要查找的要查找的k必在位于右子表必在位于右子表amid+1.high中，即中，即新的查找区间是右子表新的查找区间是右子表amid+1.high。下一次查找是针对新的查找区间进行的。

29、下一次查找是针对新的查找区间进行的。int BinSearch(int a，int low，int high，int k) int mid; if (lowk)/当当amidk时时return BinSearch(a，low，mid-1，k);else/当当amidk时时 return BinSearch(a，mid+1，high，k); else return -1;/若当前查找区间没有元素时返回若当前查找区间没有元素时返回-1拆半查找拆半查找算法算法实现实现：算法分析：折半查找算法的主要时间花费在元素比较折半查找算法的主要时间花费在元素比较上，上，对对于含有于含有n个元素的有序个元素的有序

30、表，采表，采用折半查找时最坏情况下的用折半查找时最坏情况下的元素比较次数为元素比较次数为C(n)，则，则有：有：C(n)=1当当n=1C(n)1+C( n/2 ) 当当n2由此得到由此得到：C(n) log2n +1折半查找的主要时间花在元素比较折半查找的主要时间花在元素比较上，所上，所以算法的时间以算法的时间复杂度为复杂度为O(log2n)。 时间复杂度推导及折半查找的时间复杂度推导及折半查找的非递归算法非递归算法见教材见教材P93-94折半查找你真的会了吗？据说据说90%的程序员编写的折半查找程序都有的程序员编写的折半查找程序都有bug!当有序数组中存在相同元素当有序数组中存在相同元素x时

31、，如何查找最左边的时，如何查找最左边的x ？当有序数组中存在相同元素当有序数组中存在相同元素x时，如何查找最右边的时，如何查找最右边的x ？当有序数组中存在相同元素当有序数组中存在相同元素x时，如何求时，如何求x的个数的个数 ？【问题描述】对于对于给定的含有给定的含有n元素的无序序元素的无序序列，求列，求这这个序列中第个序列中第k（1kn）小的元素。）小的元素。【问题求解】假设假设无序序列存放在无序序列存放在a0.n-1中，若中，若将将a递增排递增排序，则序，则第第k小的元素为小的元素为ak-1。采用类似于采用类似于快速排序快速排序的思想。的思想。对于序列对于序列as.t，在，在其中查找第其中

32、查找第k小元素小元素的过程如下：的过程如下：将将as作为基准划分，其对应下标为作为基准划分，其对应下标为i。3种情况种情况：该元素的下标为k-1若若k-1=i，ai即为所求，返回即为所求，返回ai。若若k-1i，第，第k小的元素应在小的元素应在ai+1.t子序列中，子序列中，递归在该子序列中求解并返回其结果。递归在该子序列中求解并返回其结果。算法实现：算法实现：int QuickSelect(int a，int s，int t，int k)/在在as.t序列中找第序列中找第k小的元素小的元素 int i=s，j=t,tmp; if (si & aj=tmp) j-;ai=aj; /将将

33、aj前移到前移到ai的位置的位置while (ij & ai=tmp) i+;aj=ai; /将将ai后移到后移到aj的位置的位置 ai=tmp; if (k-1=i) return ai; else if (k-1i) return QuickSelect(a，s，i-1，k); /在左区间中递归查找在左区间中递归查找 else return QuickSelect(a，i+1，t，k); /在右区间中递归查找在右区间中递归查找 else if (s=t & s=k-1)/区间内只有一个元素且为区间内只有一个元素且为ak-1 return ak-1;测试用例：测试用例： 2，

34、5，1，7，10，6，9，4，3，8【算法分析】对于对于QuickSelect(a，s，t，k)算算法法，设设序列序列a中含有中含有n个元个元素素，其其比较次数的递推式为：比较次数的递推式为：T(n)=T(n/2)+O(n)可以推导出可以推导出T(n)=O(n)，这，这是是最好的情最好的情况况，即，即每次划分每次划分的基准恰好是中位的基准恰好是中位数，将数，将一个序列划分为长度大致相等的两一个序列划分为长度大致相等的两个子序列。个子序列。在在最坏情况最坏情况下，每下，每次划分的基准恰好是序列中的最大值次划分的基准恰好是序列中的最大值或最小或最小值，则值，则处理区间只比上一次减少处理区间只比上一

35、次减少1个元个元素，此素，此时比较时比较次数为次数为O(n2)。在在平均情况平均情况下该算法的时间复杂度为下该算法的时间复杂度为O(n)。【问题描述】对于对于一个长度为一个长度为n的有序序列（假设均的有序序列（假设均为升序序列）为升序序列）a0.n-1，处，处于于中间位置的元素称为中间位置的元素称为a的的中位数中位数。 设计一个算法求给定的两个有序序列的中位数。设计一个算法求给定的两个有序序列的中位数。 例例如，若如，若序列序列a=(11，13，15，17，19)，其，其中位数中位数是是15，若，若b=(2，4，6，8，20)，其，其中位数为中位数为6。两个等长。两个等长有序序列的中位数是含它

36、们所有元素的有序序列的中位有序序列的中位数是含它们所有元素的有序序列的中位数，数，例例如如a、b两个有序序列的中位数为两个有序序列的中位数为11。a=(11，13，15，17，19) b=(2，4，6，8，20)c=(2，4，6，8，11，12，15，17，19，20)【问题求解】对于对于含有含有n个元素的有序序列个元素的有序序列as.t，当，当n为奇为奇数数时，中时，中位数是出现在位数是出现在m= (s+t)/2 处；当处；当n为偶为偶数数时，中时，中位数下标有位数下标有m= (s+t)/2 （下中位）和（下中位）和m= (s+t)/2 +1（上中位）两个。为了（上中位）两个。为了简简单，单

37、，仅仅考虑中位数为考虑中位数为m= (s+t)/2 处。处。a=(11，13，15，17，19)b=(2， 4， 6， 8，20)0 1 2 3 40 1 2 3 4c=(2， 4， 6， 8， 11，12，15，17，19，20)0 1 2 3 4 5 6 7 8 9m= (s+t)/2 =4m= (s+t)/2 =2m= (s+t)/2 =2采采用用二分法二分法求含有求含有n个有序元素的序列个有序元素的序列a、b的中位数的过程如下：的中位数的过程如下：855若若n=1，较小者为中位数。，较小者为中位数。其他又分为其他又分为3种情况。种情况。分别求出分别求出a、b的中位数的中位数am1和和b

38、m2： 若若am1=bm2，则，则am1或或bm2即为所求中即为所求中位位数，算数，算法结束法结束。 1，3，5，6，92，3，5，8，105 若若am1bm2，则，则舍弃序列舍弃序列a中后半部分（较大的中后半部分（较大的一一半半），同），同时舍弃序列时舍弃序列b中前半部分（较小的中前半部分（较小的一一半半），要），要求舍弃的长度求舍弃的长度相相等。舍弃一等。舍弃一半即半即 n/2 个元素。个元素。1，3，5，6，92，3，4，8，105，6，94，8，104继续求int (int a，int s1，int t1，int b，int s2，int t2) /求两个有序序列求两个有序序列as1.

39、t1和和bs2.t2的中位数的中位数int m1，m2;if (s1=t1 & s2=t2) /两序列只有一个元素时返回较小者两序列只有一个元素时返回较小者return as1bs2?as1:bs2;else m1=(s1+t1)/2;/求求a的中位数的中位数 m2=(s2+t2)/2;/求求b的中位数的中位数 if (am1=bm2)/两中位数相等时返回该中位数两中位数相等时返回该中位数return am1; if (am1bm2)/当当am1bm2时时 prepart(s1，t1);/a取前半部分取前半部分 postpart(s2，t2);/b取后半部分取后半部分 return (

40、a，s1，t1，b，s2，t2); 【算法分析】对于对于含有含有n个元素的有序序列个元素的有序序列a和和b，设，设调调用用midnum(a，0，n-1，b，0，n-1)求求中位数的执行时间为中位数的执行时间为T(n)，显，显然然有以下递归式：有以下递归式：T(n)=1当当n=1T(n)=T(n/2)+1当当n1容易推容易推出，出，T(n)=O(log2n)。3.4 求解组合问题求解组合问题 【问题描述】给定一个有给定一个有n（n1）个整数的序列，要求求出其中最）个整数的序列，要求求出其中最大连续子序列的和。大连续子序列的和。 例如例如： 序列（序列（-2，11，-4，13，-5，-2）的最大子

41、序列和为）的最大子序列和为20 序列（序列（-6，2，4，-7，5，3，2，-1，6，-9，10，-2）的最大子）的最大子序列和为序列和为16。 规定一个序列最大连续子序列和至少是规定一个序列最大连续子序列和至少是0（长度为（长度为0的子序列）的子序列），如果小于如果小于0，其结果为，其结果为0。 【问题求解】对于含有对于含有n个整数的序列个整数的序列a0.n-1，若，若n=1，表示该序，表示该序列仅含一个元素，如果该元素大于列仅含一个元素，如果该元素大于0，则返回该元素；否则返回，则返回该元素；否则返回0。 若若n1，采用分治法求解最大连续子序列时，取其中间位置，采用分治法求解最大连续子序列

42、时，取其中间位置mid= (n-1)/2 ，该子序列只可能出现，该子序列只可能出现3个地方。个地方。 （1）该子序列完全落在左半部即）该子序列完全落在左半部即a0.mid中。采用递归求出其最大中。采用递归求出其最大连续子序列和连续子序列和maxLeftSum。a0 a1 ai amidmaxLeftSum （2）该子序列完全落在右半部即）该子序列完全落在右半部即amid+1.n-1中。采用递归求出中。采用递归求出其最大连续子序列和其最大连续子序列和maxRightSum。amid+1 amid+2 aj an-1maxRightSum（3）该）该子序列跨越序列子序列跨越序列a的中部而占据左右两

43、部的中部而占据左右两部分分。1 -2 3 5 2 -1 5 -3n=8，mid=(0+7)/2=386 max(8,6)=8? 1 -2 3 5 2 -1 5 -386跨越序列跨越序列a的中部：的中部：amid左、右左、右最大连续子序列最大连续子序列和的和的+ 8+6=14max3(8,6,14)=14ai ai+1 amidamid+1 aj maxLeftSummaxRightSum结果：max3( maxLeftSum, maxRightSum, maxLeftBorderSum+maxRightBorderSum )maxLeftBorderSummaxRightBorderSum考虑

44、该子序列跨越序列考虑该子序列跨越序列amid元素的情况元素的情况long (int a，int left，int right)/求求aleft.high序列中最大连续子序列和序列中最大连续子序列和 int i，j; long maxLeftSum，maxRightSum; long maxLeftBorderSum，leftBorderSum; long maxRightBorderSum，rightBorderSum; if (left=right)/子序列只有一个元素时子序列只有一个元素时 if (aleft0) /该元素大于该元素大于0时返回它时返回它return aleft;else/

45、该元素小于或等于该元素小于或等于0时返回时返回0return 0; int mid=(left+right)/2;/求中间位置求中间位置maxLeftSum=(a，left，mid);/求左边求左边maxRightSum=(a，mid+1，right); /求右边求右边maxLeftBorderSum=0，leftBorderSum=0;for (i=mid;i=left;i-)/求出以左边加上求出以左边加上amid元素元素 leftBorderSum+=ai;/构成的序列的最大和构成的序列的最大和 if (leftBorderSummaxLeftBorderSum)maxLeftBorder

46、Sum=leftBorderSum;maxRightBorderSum=0，rightBorderSum=0;for (j=mid+1;jmaxRightBorderSum)maxRightBorderSum=rightBorderSum;return max3(maxLeftSum，maxRightSum， maxLeftBorderSum+maxRightBorderSum); 【算法分析】设设求解序列求解序列a0.n-1最大连续子序列和的执行时间最大连续子序列和的执行时间为为T(n)，第（，第（1）、（）、（2）两）两种情况的执行时间为种情况的执行时间为T(n/2)，第（，第（3）种）种

47、情情况的执行时间为况的执行时间为O(n)，所，所以得到以下递推式：以得到以下递推式：T(n)=1当当n=1T(n)=2T(n/2)+n当当n1容易推容易推出，出，T(n)=O(nlog2n)。 【问题描述】有一个有一个2k2k（k0）的棋盘，恰好有一个方格）的棋盘，恰好有一个方格与其他方格不同，称之为特殊方格。现在要用如与其他方格不同，称之为特殊方格。现在要用如下下的的L型骨牌覆盖型骨牌覆盖除了特殊方格外的其他全部方格，骨牌可以任意旋转，并且任何两除了特殊方格外的其他全部方格，骨牌可以任意旋转，并且任何两个骨牌不能重叠。请给出一种覆盖方法。个骨牌不能重叠。请给出一种覆盖方法。 【问题求解】棋盘

48、中的方格数棋盘中的方格数=2k2k=4k，覆盖使用的，覆盖使用的L型骨牌个数型骨牌个数=(4k-1)/3。 采用的方法是：将棋盘划分为采用的方法是：将棋盘划分为4个大小相同个大小相同4个象限，根据特殊方格的个象限，根据特殊方格的位置位置（dr，dc），在中间位置放置一个合适的，在中间位置放置一个合适的L型骨牌。型骨牌。 例如，如例如，如下下图所示，特殊方格在左上角象限中，在中间放置一个覆盖图所示，特殊方格在左上角象限中，在中间放置一个覆盖其他其他3个象限中各一个方格的个象限中各一个方格的L型骨牌。型骨牌。其他情况类似！其他情况类似！特殊方格在左上角象限特殊方格在左上角象限（dr，dc）放置一个

49、放置一个L型骨牌型骨牌中间位置中间位置k=3，n=23=8333444888999222777555666101010111111111131313141414181818191919121212171717151515161616202020212121左上角左上角象限象限右上角右上角象限象限右下角右下角象限象限左下角左下角象限象限 用用（tr，tc）表示一个象限左上角方格的坐标，表示一个象限左上角方格的坐标，（dr，dc）是特殊是特殊方格所在的坐标，方格所在的坐标，size是棋盘的行数和列数。是棋盘的行数和列数。 用二维数组用二维数组board存放覆盖方案，用存放覆盖方案，用tile全局变

50、量表示全局变量表示L型骨牌的编型骨牌的编号（从整数号（从整数1开始），开始），board中中3个相同的整数表示一个个相同的整数表示一个L型骨牌。型骨牌。(tr,tc)(dr,dc)ss左上角（行左上角（行, ,列）列）#include#define MAX 1025/问题表示问题表示int k;/棋盘大小棋盘大小int x,y;/特殊方格的位置特殊方格的位置/求解问题表示求解问题表示int boardMAXMAX;int tile=1;void ChessBoard(int tr,int tc,int dr,int dc,int size) if(size=1) return;/递归出口递归出

51、口 int t=tile+;/取一个取一个L型骨，其牌号为型骨，其牌号为tile int s=size/2;/分割棋盘分割棋盘 /考虑左上角象限考虑左上角象限 if(drtr+s & dctc+s)/特殊方格在此象限中特殊方格在此象限中ChessBoard(tr,tc,dr,dc,s); else/此象限中无特殊方格此象限中无特殊方格 boardtr+s-1tc+s-1=t;/用用t号号L型骨牌覆盖右下角型骨牌覆盖右下角ChessBoard(tr,tc,tr+s-1,tc+s-1,s);/将右下角作为特殊方格继续处理该象限将右下角作为特殊方格继续处理该象限 s(tr,tc)(dr,dc

52、)s(tr,tc)(tr+s-1,tc+s-1)ss(tr,tc) /考虑右上角象限考虑右上角象限 if(dr=tc+s) ChessBoard(tr,tc+s,dr,dc,s);/特殊方格在此象限中特殊方格在此象限中 else/此象限中无特殊方格此象限中无特殊方格 boardtr+s-1tc+s=t;/用用t号号L型骨牌覆盖左下角型骨牌覆盖左下角ChessBoard(tr,tc+s,tr+s-1,tc+s,s); /将左下角作为特殊方格继续处理该象限将左下角作为特殊方格继续处理该象限 (tr,tc)s(tr,tc+s)(dr,dc)s(tr,tc+s)(tr+s-1,tc+s)ss /处理左

53、下角象限处理左下角象限 if(dr=tr+s & dc=tr+s & dc=tc+s)/特殊方格在此象限中特殊方格在此象限中 ChessBoard(tr+s,tc+s,dr,dc,s); else/此象限中无特殊方格此象限中无特殊方格 boardtr+stc+s=t; /用用t号号L型骨牌覆盖左上角型骨牌覆盖左上角ChessBoard(tr+s,tc+s,tr+s,tc+s,s); /将左上角作为特殊方格继续处理该象限将左上角作为特殊方格继续处理该象限 (tr,tc)k=3，n=23=83344889932048779522610107115566110111113131411

54、1819191312141418181719151212162017172115151616202021213.4.3 求解循环日程安排问题 【问题描述】设有设有n=2k个选手要进行网球循环赛，要求设计个选手要进行网球循环赛，要求设计一个满足以下要求的比赛日程表：一个满足以下要求的比赛日程表： （1）每个选手必须与其他）每个选手必须与其他n-1个选手各赛一次。个选手各赛一次。 （2）每个选手一天只能赛一次。）每个选手一天只能赛一次。 （3）循环赛在）循环赛在n-1天之内结束。天之内结束。 【问题求解】按问题要求可将比赛日程表设计成一个按问题要求可将比赛日程表设计成一个n行行n-1列列的二维表，

55、其中第的二维表，其中第i行、第行、第j列表示和第列表示和第i个选手在第个选手在第j天比赛的选手。天比赛的选手。 假设假设n位选手被顺序编号为位选手被顺序编号为1、2、n（2k）。）。2211k=1k=222114433左上角左上角左左下下角角右上右上角角右下右下角角44332211人为添加的人为添加的表示表示选手选手1与与选手选手2比赛比赛加加2k-1=2由由k=1创建创建k=2的过程的过程k=2左上角左上角左左下下角角右上右上角角右下右下角角2211443344332211由由k=2创建创建k=3的过程的过程22114433443322116655887788776655k=3加加2k-1=

56、422114433443322116655887788776655 将将n=2k问题划分为问题划分为4部分：部分： （1）左上角左上角：左上角为：左上角为2k-1个选手在前半程的比赛日程（个选手在前半程的比赛日程（k=1时直接给时直接给出，否则，上一轮求出的就是出，否则，上一轮求出的就是2k-1个选手的比赛日程）。个选手的比赛日程）。 （2）左下角左下角：左下角为另：左下角为另2k-1个选手在前半程的比赛日程，由左上角加个选手在前半程的比赛日程，由左上角加2k-1得到，例如得到，例如22个选手比赛，左下角由左上角直接加个选手比赛，左下角由左上角直接加2（2k-1）得到，）得到，23个个选手比赛

57、，左下角由左上角直接加选手比赛，左下角由左上角直接加4（2k-1）得到。）得到。 （3）右上角右上角：将左下角直接复制到右上角得到另：将左下角直接复制到右上角得到另2k-1个选手在后半程的个选手在后半程的比赛日程。比赛日程。 （4）右下角右下角：将左上角直接复制到右下角得到：将左上角直接复制到右下角得到2k-1个选手在后半程的比个选手在后半程的比赛日程。赛日程。#include #define MAX 101/问题表示问题表示int k;/求解结果表示求解结果表示int aMAXMAX;/存放比赛日程表（行列下标为存放比赛日程表（行列下标为0的元素不用）的元素不用）void Plan(int

58、k) int i,j,n,t,temp; n=2;/n从从21=2开始开始 a11=1; a12=2; /求解求解2个选手比赛日程个选手比赛日程,得到得到左上角左上角元素元素 a21=2; a22=1; for (t=1;tk;t+)/迭代处理迭代处理22(t=1),2k(t=k-1)个选手个选手 temp=n;/temp=2tn=n*2; /n=2(t+1)for (i=temp+1;i=n;i+ )/填填左下角左下角元素元素 for (j=1; j=temp; j+)aij=ai-tempj+temp; /产生产生左下角元素左下角元素for (i=1; i=temp; i+)/填填右上角右

59、上角元素元素 for (j=temp+1; j=n; j+)aij=ai+temp(j+temp)% n;for (i=temp+1; i=n; i+)/填填右下角右下角元素元素 for (j=temp+1; j1由此可得由此可得T(n)=O(n2)。采用分治法，采用分治法，把把X*Y写成另一种形式：写成另一种形式： X*Y=A*C*2n+(A-B)*(D-C)+A*C+B*D*2n/2+B*D虽然该式看起来比前式复杂些，但它仅需做虽然该式看起来比前式复杂些，但它仅需做3次次n/2位整数的位整数的乘法（乘法（A*C、B*D和和(A-B)*(D-C)），），6次加、减法和次加、减法和2次移位。次

60、移位。由此可以推出由此可以推出： T(n) = O(n1.59) （log23=1.59）【问题描述】对于对于两个两个nn的矩阵的矩阵A和和B，计计算算C=AB。【问题求解】常用常用的计算公式是的计算公式是Cij = ，对对应算法应算法的时间复杂度为的时间复杂度为O(n3)。是否存在更有效的算法呢？假设是否存在更有效的算法呢？假设n=2k，考考虑采用分治法思虑采用分治法思路路，当当n2时时，将将A、B分成分成4个个n/2n/2的矩阵：的矩阵：nkkjikBA1222112112221121122211211CCCC，CBBBB，BAAAAA利用块矩阵的乘利用块矩阵的乘法法，矩矩阵阵C可表示为可表示为22221221212211212212121121121111BABABABABABABABAC2222122121221