第3章分治法3.2

求解排序問(wèn)題3.1

分治法概述3.3

求解查找問(wèn)題3.4

求解組合問(wèn)題3.5

求解大整數(shù)乘法和矩陣乘法問(wèn)題3.6并行計(jì)算簡(jiǎn)介

對(duì)于一個(gè)規(guī)模為n的問(wèn)題：若該問(wèn)題可以容易地解決（比如說(shuō)規(guī)模n較小）則直接解決，否則將其分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題形式相同，遞歸地解這些子問(wèn)題，然后將各子問(wèn)題的解合并得到原問(wèn)題的解。這種算法設(shè)計(jì)策略叫做分治法。3.1

分治法概述3.1.1分治法的設(shè)計(jì)思想分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：

（1）該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決。

（2）該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題。

（3）利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解。

（4）該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。3.1.2分治法的求解過(guò)程分治法通常采用遞歸算法設(shè)計(jì)技術(shù)，在每一層遞歸上都有3個(gè)步驟：

①分解：將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題。

②求解子問(wèn)題：若子問(wèn)題規(guī)模較小而容易被解決則直接求解，否則遞歸地求解各個(gè)子問(wèn)題。

③合并：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解。分治法的一般的算法設(shè)計(jì)框架如下：divide-and-conquer(P){if|P|≤n0returnadhoc(P);

將P分解為較小的子問(wèn)題P1，P2，…，Pk;for(i=1;i<=k;i++) //循環(huán)處理k次

yi=divide-and-conquer(Pi); //遞歸解決Pi

returnmerge(y1，y2，…，yk); //合并子問(wèn)題}

根據(jù)分治法的分割原則，原問(wèn)題應(yīng)該分為多少個(gè)子問(wèn)題才較適宜？各個(gè)子問(wèn)題的規(guī)模應(yīng)該怎樣才為適當(dāng)？這些問(wèn)題很難予以肯定的回答。但人們從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計(jì)算法時(shí)，最好使子問(wèn)題的規(guī)模大致相同。換句話說(shuō)，將一個(gè)問(wèn)題分成大小相等的k個(gè)子問(wèn)題的處理方法是行之有效的。當(dāng)k=1時(shí)稱為減治法。

許多問(wèn)題可以取k=2，稱為二分法，如圖4.1所示，這種使子問(wèn)題規(guī)模大致相等的做法是出自一種平衡子問(wèn)題的思想，它幾乎總是比子問(wèn)題規(guī)模不等的做法要好。P(n)P(n/2)P(n/4)P(n/4)……P(n/2)P(n/4)P(n/4)……3.2.1快速排序

基本思想：在待排序的n個(gè)元素中任取一個(gè)元素（通常取第一個(gè)元素）作為基準(zhǔn)，把該元素放入最終位置后，整個(gè)數(shù)據(jù)序列被基準(zhǔn)分割成兩個(gè)子序列，所有小于基準(zhǔn)的元素放置在前子序列中，所有大于基準(zhǔn)的元素放置在后子序列中，并把基準(zhǔn)排在這兩個(gè)子序列的中間，這個(gè)過(guò)程稱作劃分。

然后對(duì)兩個(gè)子序列分別重復(fù)上述過(guò)程，直至每個(gè)子序列內(nèi)只有一個(gè)記錄或空為止。3.2

求解排序問(wèn)題a[s]

a[s+1]………a[t]無(wú)序區(qū)a[s]…a[i-1]a[s]a[i+1]…a[t]無(wú)序區(qū)1無(wú)序區(qū)2劃分f(a,s,t)≡

不做任何事情

當(dāng)a[s..t]中長(zhǎng)度小于2f(a,s,t)≡

i=Partition(a,s,t); 其他情況f(a,s,i-1);

f(a,i+1,t);分治策略：

①分解：將原序列a[s..t]分解成兩個(gè)子序列a[s..i-1]和a[i+1..t]，其中i為劃分的基準(zhǔn)位置。

②求解子問(wèn)題：若子序列的長(zhǎng)度為0或?yàn)?，則它是有序的，直接返回；否則遞歸地求解各個(gè)子問(wèn)題。

③合并：由于整個(gè)序列存放在數(shù)組中a中，排序過(guò)程是就地進(jìn)行的，合并步驟不需要執(zhí)行任何操作。例如，對(duì)于{2，5，1，7，10，6，9，4，3，8}序列，其快速排序過(guò)程如下圖所示（沒(méi)有畫(huà)出空的子序列）。2,5,1,7,10,6,9,4,3,8125,7,10,6,9,4,3,83,456,9,10,7,8439,10,7,867,891078快速排序算法：intPartition(inta[]，ints，intt) //劃分算法{inti=s，j=t;

inttmp=a[s]; //用序列的第1個(gè)記錄作為基準(zhǔn)

while(i!=j) //從序列兩端交替向中間掃描，直至i=j為止{while(j>i&&a[j]>=tmp)

j--;

//從右向左掃描，找第1個(gè)關(guān)鍵字小于tmp的a[j]

a[i]=a[j]; //將a[j]前移到a[i]的位置

while(i<j&&a[i]<=tmp)

i++;

//從左向右掃描，找第1個(gè)關(guān)鍵字大于tmp的a[i]

a[j]=a[i]; //將a[i]后移到a[j]的位置

}

a[i]=tmp;

returni;}快速排序算法：voidQuickSort(inta[]，ints，intt) //對(duì)a[s..t]元素序列進(jìn)行遞增排序{if(s<t)

//序列內(nèi)至少存在2個(gè)元素的情況

{inti=Partition(a，s，t);

QuickSort(a，s，i-1); //對(duì)左子序列遞歸排序

QuickSort(a，i+1，t); //對(duì)右子序列遞歸排序

}}

【算法分析】快速排序的時(shí)間主要耗費(fèi)在劃分操作上，對(duì)長(zhǎng)度為n的區(qū)間進(jìn)行劃分，共需n-1次關(guān)鍵字的比較，時(shí)間復(fù)雜度為O(n)。對(duì)n個(gè)記錄進(jìn)行快速排序的過(guò)程構(gòu)成一棵遞歸樹(shù)，在這樣的遞歸樹(shù)中，每一層至多對(duì)n個(gè)記錄進(jìn)行劃分，所花時(shí)間為O(n)。當(dāng)初始排序數(shù)據(jù)正序或反序時(shí)，此時(shí)的遞歸樹(shù)高度為n，快速排序呈現(xiàn)最壞情況，即最壞情況下的時(shí)間復(fù)雜度為O(n2)；

當(dāng)初始排序數(shù)據(jù)隨機(jī)分布，使每次分成的兩個(gè)子區(qū)間中的記錄個(gè)數(shù)大致相等，此時(shí)的遞歸樹(shù)高度為log2n，快速排序呈現(xiàn)最好情況，即最好情況下的時(shí)間復(fù)雜度為O(nlog2n)。快速排序算法的平均時(shí)間復(fù)雜度也是O(nlog2n)。2.2.2歸并排序

歸并排序的基本思想是：首先將a[0..n-1]看成是n個(gè)長(zhǎng)度為1的有序表，將相鄰的k（k≥2）個(gè)有序子表成對(duì)歸并，得到n/k個(gè)長(zhǎng)度為k的有序子表；然后再將這些有序子表繼續(xù)歸并，得到n/k2個(gè)長(zhǎng)度為k2的有序子表，如此反復(fù)進(jìn)行下去，最后得到一個(gè)長(zhǎng)度為n的有序表。若k=2，即歸并在相鄰的兩個(gè)有序子表中進(jìn)行的，稱為二路歸并排序。若k>2，即歸并操作在相鄰的多個(gè)有序子表中進(jìn)行，則叫多路歸并排序。

1.自底向上的二路歸并排序算法例如，對(duì)于{2，5，1，7，10，6，9，4，3，8}序列，其排序過(guò)程如下圖所示，圖中方括號(hào)內(nèi)是一個(gè)有序子序列。底頂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二路歸并排序的分治策略如下：循環(huán)

log2n

次，length依次取1、2、…、log2n。每次執(zhí)行以下步驟：

①分解：將原序列分解成length長(zhǎng)度的若干子序列。

②求解子問(wèn)題：將相鄰的兩個(gè)子序列調(diào)用Merge算法合并成一個(gè)有序子序列。

③合并：由于整個(gè)序列存放在數(shù)組中a中，排序過(guò)程是就地進(jìn)行的，合并步驟不需要執(zhí)行任何操作。voidMerge(inta[]，intlow，intmid，inthigh)//a[low..mid]和a[mid+1..high]→a[low..high]{int*tmpa;

inti=low，j=mid+1，k=0;

tmpa=(int*)malloc((high-low+1)*sizeof(int));

while(i<=mid&&j<=high)if(a[i]<=a[j])

//將第1子表中的元素放入tmpa中

{tmpa[k]=a[i];i++;k++;}

else

//將第2子表中的元素放入tmpa中

{tmpa[k]=a[j];

j++;k++;}

while(i<=mid) //將第1子表余下部分復(fù)制到tmpa

{

tmpa[k]=a[i];i++;k++;}

while(j<=high)

//將第2子表余下部分復(fù)制到tmpa

{tmpa[k]=a[j];j++;k++;}

for(k=0，i=low;i<=high;k++，i++)

//將tmpa復(fù)制回a中

a[i]=tmpa[k];

free(tmpa);

//釋放tmpa所占內(nèi)存空間}voidMergePass(inta[]，intlength，intn)//一趟二路歸并排序{inti;

for(i=0;i+2*length-1<n;i=i+2*length)//歸并length長(zhǎng)的兩相鄰子表

Merge(a，i，i+length-1，i+2*length-1);

if(i+length-1<n)

//余下兩個(gè)子表，后者長(zhǎng)度小于length

Merge(a，i，i+length-1，n-1);

//歸并這兩個(gè)子表}voidMergeSort(inta[]，intn) //二路歸并算法{

intlength;

for(length=1;length<n;length=2*length)

MergePass(a，length，n);}

【算法分析】對(duì)于上述二路歸并排序算法，當(dāng)有n個(gè)元素時(shí)，需要

log2n

趟歸并，每一趟歸并，其元素比較次數(shù)不超過(guò)n-1，元素移動(dòng)次數(shù)都是n，因此歸并排序的時(shí)間復(fù)雜度為O(nlog2n)。2.自頂向下的二路歸并排序算法例如，對(duì)于{2，5，1，7，10，6，9，4，3，8}序列，說(shuō)明其自頂向下的二路歸并排序的過(guò)程。2，5，1，7，10，6，9，4，3，82，51,2，57，101，2，5,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分解合并底頂設(shè)歸并排序的當(dāng)前區(qū)間是a[low..high]，則遞歸歸并的兩個(gè)步驟如下：

①分解：將序列a[low..high]一分為二，即求mid=(low+high)/2；遞歸地對(duì)兩個(gè)子序列a[low..mid]和a[mid+1..high]進(jìn)行繼續(xù)分解。其終結(jié)條件是子序列長(zhǎng)度為1（因?yàn)橐粋€(gè)元素的子表一定是有序表）。

②求解子問(wèn)題：排序兩個(gè)子序列a[low..mid]和a[mid+1..high]。

③

合并：與分解過(guò)程相反，將已排序的兩個(gè)子序列a[low..mid]和a[mid+1..high]歸并為一個(gè)有序序列a[low..high]。對(duì)應(yīng)的二路歸并排序算法如下：voidMergeSort(inta[]，intlow，inthigh)//二路歸并算法{intmid;

if(low<high) //子序列有兩個(gè)或以上元素

{ mid=(low+high)/2;

//取中間位置

MergeSort(a，low，mid); //對(duì)a[low..mid]子序列排序

MergeSort(a，mid+1，high); //對(duì)a[mid+1..high]子序列排序

Merge(a，low，mid，high); //將兩子序列合并，見(jiàn)前面的算法

}}遞歸出口為序列長(zhǎng)度為1或者0！

算法分析：設(shè)MergeSort(a，0，n-1)算法的執(zhí)行時(shí)間為T(n)，顯然Merge(a，0，n/2，n-1)的執(zhí)行時(shí)間為O(n)，所以得到以下遞推式：T(n)=1 當(dāng)n=1T(n)=2T(n/2)+O(n) 當(dāng)n>1容易推出，T(n)=O(nlog2n)。#defineMAXN55#defineMAXM105/*****求字符串a(chǎn)的逆序數(shù)ans***************/intans; //全局變量,累計(jì)逆序數(shù)voidMerge(chara[],intlow,intmid,inthigh)//兩個(gè)相鄰有序段歸并{inti=low;intj=mid+1;intk=0;char*tmp=(char*)malloc((high-low+1)*sizeof(int));while(i<=mid&&j<=high) //二路歸并{if(a[i]>a[j]){tmp[k++]=a[j++];

ans+=mid-i+1;}elsetmp[k++]=a[i++];}while(i<=mid)tmp[k++]=a[i++];while(j<=high)tmp[k++]=a[j++];for(intk1=0;k1<k;k1++) //tmp[0..k-1]=>a[low..high]a[low+k1]=tmp[k1];free(tmp);}a[low]…a[i]…a[mid]a[low..mid]a[mid+1]…a[j]…a[high]a[mid+1..high]若a[i]>a[j]

ans+=mid-i+1a[i..mid]>a[j]逆序數(shù)ans=0voidMerge_sort(chara[],intlow,inthigh)//遞歸二路歸并排序{if(low<high){ intmid=(low+high)/2; Merge_sort(a,low,mid); Merge_sort(a,mid+1,high); Merge(a,low,mid,high);}}intInversion(chara[],intn) //二路歸并法求字符串a(chǎn)的逆序數(shù){ans=0;Merge_sort(a,0,n-1);returnans;}/*************************************/typedefstruct{intv; //存放str[i]的逆序數(shù)inti; //存放字符串的下標(biāo)i}ElemType; //聲明數(shù)組b的元素類型structCmp //定義排序關(guān)系函數(shù){booloperator()(constElemType&s,constElemType&t)const{ returns.v<t.v;} //指定按逆序數(shù)遞增排序};intmain(){inti,n,m;charstr[MAXM][MAXN];ElemTypeb[MAXM];memset(b,0,sizeof(b));chartmp[MAXN];scanf("%d%d",&n,&m); //輸入n和mfor(i=0;i<m;i++) //輸入m個(gè)字符串scanf("%s",str[i]);for(i=0;i<m;i++) //求所有字符串的逆序數(shù){strcpy(tmp,str[i]); //由于保存原序列不變,臨時(shí)復(fù)制到tmp中b[i].v=Inversion(tmp,n); //求tmp的逆序?qū)€(gè)數(shù)b[i].i=i; //記錄原來(lái)的下標(biāo)}stable_sort(b,b+m,Cmp()); //采用穩(wěn)定的排序算法for(i=0;i<m;i++) //輸出結(jié)果printf("%s\n",str[b[i].i]);return0;}3.3.1查找最大和次大元素

【問(wèn)題描述】對(duì)于給定的含有n元素的無(wú)序序列，求這個(gè)序列中最大和次大的兩個(gè)不同的元素。

例如：（2,5,1,4,6,3），最大元素為6，次大元素為5。3.3

求解查找問(wèn)題

【問(wèn)題求解】對(duì)于無(wú)序序列a[low.high]中，采用分治法求最大元素max1和次大元素max2的過(guò)程如下：

（1）a[low.high]中只有一個(gè)元素：則max1=a[low]，max2=-INF（-∞）（要求它們是不同的元素）。

（2）a[low.high]中只有兩個(gè)元素：則max1=MAX{a[low]，a[high]}，max2=MIN{a[low]，a[high]}。

（3）a[low.high]中有兩個(gè)以上元素：按中間位置mid=(low+high)/2劃分為a[low..mid]和a[mid+1..high]左右兩個(gè)區(qū)間（注意左區(qū)間包含a[mid]元素）。

求出左區(qū)間最大元素lmax1和次大元素lmax2，求出右區(qū)間最大元素rmax1和次大元素rmax2。

合并：若lmax1>rmax1，則max1=lmax1，max2=MAX{lmax2，rmax1}；否則max1=rmax1，max2=MAX{lmax1，rmax2}。voidsolve(inta[],intlow,inthigh,int&max1,int&max2){if(low==high) //區(qū)間只有一個(gè)元素{ max1=a[low]; max2=-INF;}elseif(low==high-1) //區(qū)間只有兩個(gè)元素{ max1=max(a[low],a[high]);max2=min(a[low],a[high]);}else //區(qū)間有兩個(gè)以上元素{ intmid=(low+high)/2; intlmax1,lmax2;

solve(a,low,mid,lmax1,lmax2); //左區(qū)間求lmax1和lmax2 intrmax1,rmax2;

solve(a,mid+1,high,rmax1,rmax2);//右區(qū)間求lmax1和lmax2 if(lmax1>rmax1) {max1=lmax1; max2=max(lmax2,rmax1); //lmax2,rmax1中求次大元素 } else {max1=rmax1; max2=max(lmax1,rmax2); //lmax1,rmax2中求次大元素 }}}

【算法分析】對(duì)于solve(a，0，n-1，max1，max2)調(diào)用，其比較次數(shù)的遞推式為：T(1)=T(2)=1T(n)=2T(n/2)+1//合并的時(shí)間為O(1)可以推導(dǎo)出T(n)=O(n)。3.3.2折半查找

基本思路：設(shè)a[low..high]是當(dāng)前的查找區(qū)間，首先確定該區(qū)間的中點(diǎn)位置mid=

(low+high)/2

；然后將待查的k值與a[mid].key比較：（1）若k==a[mid]，則查找成功并返回該元素的物理下標(biāo)；（2）若k<a[mid]，則由表的有序性可知a[mid..high]均大于k，因此若表中存在關(guān)鍵字等于k的元素，則該元素必定位于左子表a[low..mid-1]中，故新的查找區(qū)間是左子表a[low..mid-1]；（3）若k>a[mid]，則要查找的k必在位于右子表a[mid+1..high]中，即新的查找區(qū)間是右子表a[mid+1..high]。下一次查找是針對(duì)新的查找區(qū)間進(jìn)行的。intBinSearch(inta[]，intlow，inthigh，intk)//拆半查找算法{intmid;

if(low<=high) //當(dāng)前區(qū)間存在元素時(shí)

{ mid=(low+high)/2; //求查找區(qū)間的中間位置

if(a[mid]==k)

//找到后返回其物理下標(biāo)mid

returnmid;

if(a[mid]>k)

//當(dāng)a[mid]>k時(shí)

returnBinSearch(a，low，mid-1，k);

else //當(dāng)a[mid]<k時(shí)

returnBinSearch(a，mid+1，high，k);

}

elsereturn-1;

//若當(dāng)前查找區(qū)間沒(méi)有元素時(shí)返回-1}算法實(shí)現(xiàn)：

算法分析：折半查找算法的主要時(shí)間花費(fèi)在元素比較上，對(duì)于含有n個(gè)元素的有序表，采用折半查找時(shí)最壞情況下的元素比較次數(shù)為C(n)，則有：C(n)=1 當(dāng)n=1C(n)≤1+C(

n/2

) 當(dāng)n≥2由此得到：C(n)≤

log2n

+1折半查找的主要時(shí)間花在元素比較上，所以算法的時(shí)間復(fù)雜度為O(log2n)。3.3.3尋找一個(gè)序列中第k小元素

【問(wèn)題描述】對(duì)于給定的含有n元素的無(wú)序序列，求這個(gè)序列中第k（1≤k≤n）小的元素。

【問(wèn)題求解】假設(shè)無(wú)序序列存放在a[0..n-1]中，若將a遞增排序，則第k小的元素為a[k-1]。采用類似于快速排序的思想。對(duì)于序列a[s..t]，在其中查找第k小元素的過(guò)程如下：

將a[s]作為基準(zhǔn)劃分，其對(duì)應(yīng)下標(biāo)為i。3種情況：該元素的下標(biāo)為k-1若k-1=i，a[i]即為所求，返回a[i]。若k-1<i，第k小的元素應(yīng)在a[s..i-1]子序列中，遞歸在該子序列中求解并返回其結(jié)果。若k-1>i，第k小的元素應(yīng)在a[i+1..t]子序列中，遞歸在該子序列中求解并返回其結(jié)果。算法實(shí)現(xiàn)：intQuickSelect(inta[]，ints，intt，intk)//在a[s..t]序列中找第k小的元素{inti=s，j=t,tmp;

if(s<t)

{tmp=a[s];

while(i!=j)

//從區(qū)間兩端交替向中間掃描，直至i=j為止

{while(j>i&&a[j]>=tmp)j--;

a[i]=a[j];

//將a[j]前移到a[i]的位置

while(i<j&&a[i]<=tmp)i++;

a[j]=a[i];

//將a[i]后移到a[j]的位置

}

a[i]=tmp;

if(k-1==i)returna[i];

elseif(k-1<i)returnQuickSelect(a，s，i-1，k);

//在左區(qū)間中遞歸查找

elsereturnQuickSelect(a，i+1，t，k);

//在右區(qū)間中遞歸查找

}

elseif(s==t&&s==k-1) //區(qū)間內(nèi)只有一個(gè)元素且為a[k-1]

returna[k-1];}

【算法分析】對(duì)于QuickSelect(a，s，t，k)算法，設(shè)序列a中含有n個(gè)元素，其比較次數(shù)的遞推式為：

T(n)=T(n/2)+O(n)可以推導(dǎo)出T(n)=O(n)，這是最好的情況，即每次劃分的基準(zhǔn)恰好是中位數(shù)，將一個(gè)序列劃分為長(zhǎng)度大致相等的兩個(gè)子序列。在最壞情況下，每次劃分的基準(zhǔn)恰好是序列中的最大值或最小值，則處理區(qū)間只比上一次減少1個(gè)元素，此時(shí)比較次數(shù)為O(n2)。在平均情況下該算法的時(shí)間復(fù)雜度為O(n)。3.3.4尋找兩個(gè)等長(zhǎng)有序序列的中位數(shù)

【問(wèn)題描述】對(duì)于一個(gè)長(zhǎng)度為n的有序序列（假設(shè)均為升序序列）a[0..n-1]，處于中間位置的元素稱為a的中位數(shù)。設(shè)計(jì)一個(gè)算法求給定的兩個(gè)有序序列的中位數(shù)。

例如，若序列a=(11，13，15，17，19)，其中位數(shù)是15，若b=(2，4，6，8，20)，其中位數(shù)為6。兩個(gè)等長(zhǎng)有序序列的中位數(shù)是含它們所有元素的有序序列的中位數(shù)，例如a、b兩個(gè)有序序列的中位數(shù)為11。a=(11，13，15，17，19)b=(2，4，6，8，20)c=(2，4，6，8，11，12，15，17，19，20)

【問(wèn)題求解】對(duì)于含有n個(gè)元素的有序序列a[s..t]，當(dāng)n為奇數(shù)時(shí)，中位數(shù)是出現(xiàn)在m=

(s+t)/2

處；當(dāng)n為偶數(shù)時(shí)，中位數(shù)下標(biāo)有m=

(s+t)/2

（下中位）和m=

(s+t)/2

+1（上中位）兩個(gè)。為了簡(jiǎn)單，僅考慮中位數(shù)為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，13，15，17，19，20)0

1

2

3

456

7

89m=

(s+t)/2=4m=

(s+t)/2=2m=

(s+t)/2=2采用二分法求含有n個(gè)有序元素的序列a、b的中位數(shù)的過(guò)程如下：855若n=1，較小者為中位數(shù)。其他又分為3種情況。分別求出a、b的中位數(shù)a[m1]和b[m2]：①若a[m1]=b[m2]，則a[m1]或b[m2]即為所求中位數(shù)，算法結(jié)束。1，3，5，6，92，3，5，8，105②若a[m1]<b[m2]，則舍棄序列a中前半部分（較小的一半），同時(shí)舍棄序列b中后半部分（較大的一半）要求舍棄的長(zhǎng)度相等。1，3，4，6，92，3，5，8，104，6，92，3，54繼續(xù)求③若a[m1]>b[m2]，則舍棄序列a中后半部分（較大的一半），同時(shí)舍棄序列b中前半部分（較小的一半），要求舍棄的長(zhǎng)度相等。舍棄一半即

n/2

個(gè)元素。1，3，5，6，92，3，4，8，104，8，104繼續(xù)求1，3，5intmidnum(inta[]，ints1，intt1，intb[]，ints2，intt2){//求兩個(gè)有序序列a[s1..t1]和b[s2..t2]的中位數(shù)

intm1，m2;

if(s1==t1&&s2==t2)//兩序列只有一個(gè)元素時(shí)返回較小者

returna[s1]<b[s2]?a[s1]:b[s2];

else

{m1=(s1+t1)/2; //求a的中位數(shù)

m2=(s2+t2)/2; //求b的中位數(shù)

if(a[m1]==b[m2]) //兩中位數(shù)相等時(shí)返回該中位數(shù)

returna[m1];

if(a[m1]<b[m2]) //當(dāng)a[m1]<b[m2]時(shí)

{postpart(s1，t1); //a取后半部分

prepart(s2，t2); //b取前半部分

returnmidnum(a，s1，t1，b，s2，t2);

}

else

//當(dāng)a[m1]>b[m2]時(shí)

{prepart(s1，t1); //a取前半部分

postpart(s2，t2); //b取后半部分

returnmidnum(a，s1，t1，b，s2，t2);

}

}}

【算法分析】對(duì)于含有n個(gè)元素的有序序列a和b，設(shè)調(diào)用midnum(a，0，n-1，b，0，n-1)求中位數(shù)的執(zhí)行時(shí)間為T(n)，顯然有以下遞歸式：T(n)=1 當(dāng)n=1T(n)=T(n/2)+1

當(dāng)n>1容易推出，T(n)=O(log2n)。3.4.1

求解最大連續(xù)子序列和問(wèn)題3.4

求解組合問(wèn)題

【問(wèn)題描述】給定一個(gè)有n（n≥1）個(gè)整數(shù)的序列，要求求出其中最大連續(xù)子序列的和。

例如：

序列（-2，11，-4，13，-5，-2）的最大子序列和為20

序列（-6，2，4，-7，5，3，2，-1，6，-9，10，-2）的最大子序列和為16。

規(guī)定一個(gè)序列最大連續(xù)子序列和至少是0（長(zhǎng)度為0的子序列），如果小于0，其結(jié)果為0。

【問(wèn)題求解】對(duì)于含有n個(gè)整數(shù)的序列a[0..n-1]，若n=1，表示該序列僅含一個(gè)元素，如果該元素大于0，則返回該元素；否則返回0。

若n>1，采用分治法求解最大連續(xù)子序列時(shí)，取其中間位置mid=

(n-1)/2

，該子序列只可能出現(xiàn)3個(gè)地方。

（1）該子序列完全落在左半部即a[0..mid]中。采用遞歸求出其最大連續(xù)子序列和maxLeftSum。a0

a1…ai…amidmaxLeftSum

（2）該子序列完全落在右半部即a[mid+1..n-1]中。采用遞歸求出其最大連續(xù)子序列和maxRightSum。amid+1

amid+2…aj…an-1maxRightSum（3）該子序列跨越序列a的中部而占據(jù)左右兩部分。1-2352-15-3n=8，mid=(0+7)/2=386

max(8,6)=8?×1-2352-15-386跨越序列a的中部：amid左、右最大連續(xù)子序列和的+

8+6=14max3(8,6,14)=14ai

ai+1……amidamid+1……aj

maxLeftSummaxRightSum結(jié)果：max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum)maxLeftBorderSummaxRightBorderSum考慮該子序列跨越序列amid元素的情況longmaxSubSum(inta[]，intleft，intright) //求a[left..high]序列中最大連續(xù)子序列和{inti，j;longmaxLeftSum，maxRightSum;

longmaxLeftBorderSum，leftBorderSum;

longmaxRightBorderSum，rightBorderSum;

if(left==right)

//子序列只有一個(gè)元素時(shí){

if(a[left]>0) //該元素大于0時(shí)返回它

returna[left];

else

//該元素小于或等于0時(shí)返回0

return0;}

intmid=(left+right)/2;

//求中間位置

maxLeftSum=maxSubSum(a，left，mid); //求左邊

maxRightSum=maxSubSum(a，mid+1，right); //求右邊

maxLeftBorderSum=0，leftBorderSum=0;

for(i=mid;i>=left;i--)

//求出以左邊加上a[mid]元素

{leftBorderSum+=a[i];

//構(gòu)成的序列的最大和

if(leftBorderSum>maxLeftBorderSum)

maxLeftBorderSum=leftBorderSum;

}

maxRightBorderSum=0，rightBorderSum=0;

for(j=mid+1;j<=right;j++)

//求出a[mid]右邊元素

{rightBorderSum+=a[j];

//構(gòu)成的序列的最大和

if(rightBorderSum>maxRightBorderSum)

maxRightBorderSum=rightBorderSum;

}

returnmax3(maxLeftSum，maxRightSum， maxLeftBorderSum+maxRightBorderSum);}

【算法分析】設(shè)求解序列a[0..n-1]最大連續(xù)子序列和的執(zhí)行時(shí)間為T(n)，第（1）、（2）兩種情況的執(zhí)行時(shí)間為T(n/2)，第（3）種情況的執(zhí)行時(shí)間為O(n)，所以得到以下遞推式：T(n)=1 當(dāng)n=1T(n)=2T(n/2)+n

當(dāng)n>1容易推出，T(n)=O(nlog2n)。3.4.2求解棋盤覆蓋問(wèn)題

【問(wèn)題描述】有一個(gè)2k×2k（k>0）的棋盤，恰好有一個(gè)方格與其他方格不同，稱之為特殊方格?，F(xiàn)在要用如下的L型骨牌覆蓋除了特殊方格外的其他全部方格，骨牌可以任意旋轉(zhuǎn)，并且任何兩個(gè)骨牌不能重疊。請(qǐng)給出一種覆蓋方法。

【問(wèn)題求解】棋盤中的方格數(shù)=2k×2k=4k，覆蓋使用的L型骨牌個(gè)數(shù)=(4k-1)/3。

采用的方法是：將棋盤劃分為4個(gè)大小相同4個(gè)象限，根據(jù)特殊方格的位置（dr，dc），在中間位置放置一個(gè)合適的L型骨牌。

例如，如下圖所示，特殊方格在左上角象限中，在中間放置一個(gè)覆蓋其他3個(gè)象限中各一個(gè)方格的L型骨牌。其他情況類似！特殊方格在左上角象限（dr，dc）放置一個(gè)L型骨牌中間位置k=3，n=23=8333444888999222777555666101010111111111131313141414181818191919121212171717151515161616202020212121左上角象限右上角象限右下角象限左下角象限

用（tr，tc）表示一個(gè)象限左上角方格的坐標(biāo)，（dr，dc）是特殊方格所在的坐標(biāo)，size是棋盤的行數(shù)和列數(shù)。

用二維數(shù)組board存放覆蓋方案，用tile全局變量表示L型骨牌的編號(hào)（從整數(shù)1開(kāi)始），board中3個(gè)相同的整數(shù)表示一個(gè)L型骨牌。(tr,tc)(dr,dc)ss左上角（行,列）

#include<stdio.h>#defineMAX1025//問(wèn)題表示intk; //棋盤大小intx,y; //特殊方格的位置//求解問(wèn)題表示intboard[MAX][MAX];inttile=1; voidChessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return; //遞歸出口intt=tile++; //取一個(gè)L型骨，其牌號(hào)為tileints=size/2; //分割棋盤

//考慮左上角象限

if(dr<tr+s&&dc<tc+s) //特殊方格在此象限中

ChessBoard(tr,tc,dr,dc,s);else //此象限中無(wú)特殊方格{ board[tr+s-1][tc+s-1]=t; //用t號(hào)L型骨牌覆蓋右下角

ChessBoard(tr,tc,tr+s-1,tc+s-1,s);

//將右下角作為特殊方格繼續(xù)處理該象限}s(tr,tc)(dr,dc)s(tr,tc)(tr+s-1,tc+s-1)ss(tr,tc)//考慮右上角象限if(dr<tr+s&&dc>=tc+s)

ChessBoard(tr,tc+s,dr,dc,s); //特殊方格在此象限中else //此象限中無(wú)特殊方格{ board[tr+s-1][tc+s]=t; //用t號(hào)L型骨牌覆蓋左下角

ChessBoard(tr,tc+s,tr+s-1,tc+s,s);

//將左下角作為特殊方格繼續(xù)處理該象限}(tr,tc)s(tr,tc+s)(dr,dc)s(tr,tc+s)(tr+s-1,tc+s)ss//處理左下角象限if(dr>=tr+s&&dc<tc+s) //特殊方格在此象限中

ChessBoard(tr+s,tc,dr,dc,s);else //此象限中無(wú)特殊方格{board[tr+s][tc+s-1]=t; //用t號(hào)L型骨牌覆蓋右上角

ChessBoard(tr+s,tc,tr+s,tc+s-1,s);

//將右上角作為特殊方格繼續(xù)處理該象限}(tr,tc)//處理右下角象限if(dr>=tr+s&&dc>=tc+s) //特殊方格在此象限中

ChessBoard(tr+s,tc+s,dr,dc,s);else //此象限中無(wú)特殊方格{ board[tr+s][tc+s]=t; //用t號(hào)L型骨牌覆蓋左上角

ChessBoard(tr+s,tc+s,tr+s,tc+s,s);

//將左上角作為特殊方格繼續(xù)處理該象限}}(tr,tc)k=3，n=23=833448899320487795226101071155661101111131314111819191312141418181719151212162017172115151616202021213.4.3求解循環(huán)日程安排問(wèn)題

【問(wèn)題描述】設(shè)有n=2k個(gè)選手要進(jìn)行網(wǎng)球循環(huán)賽，要求設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：

（1）每個(gè)選手必須與其他n-1個(gè)選手各賽一次。

（2）每個(gè)選手一天只能賽一次。

（3）循環(huán)賽在n-1天之內(nèi)結(jié)束。

【問(wèn)題求解】按問(wèn)題要求可將比賽日程表設(shè)計(jì)成一個(gè)n行n-1列的二維表，其中第i行、第j列表示和第i個(gè)選手在第j天比賽的選手。

假設(shè)n位選手被順序編號(hào)為1、2、…、n（2k）。2211k=1k=222114433左上角左下角右上角右下角44332211人為添加的表示選手1與選手2比賽加2k-1=2由k=1創(chuàng)建k=2的過(guò)程k=2左上角左下角右上角右下角2211443344332211由k=2創(chuàng)建k=3的過(guò)程22114433443322116655887788776655k=3加2k-1=422114433443322116655887788776655

將n=2k問(wèn)題劃分為4部分：

（1）左上角：左上角為2k-1個(gè)選手在前半程的比賽日程（k=1時(shí)直接給出，否則，上一輪求出的就是2k-1個(gè)選手的比賽日程）。

（2）左下角：左下角為另2k-1個(gè)選手在前半程的比賽日程，由左上角加2k-1得到，例如22個(gè)選手比賽，左下角由左上角直接加2（2k-1）得到，23個(gè)選手比賽，左下角由左上角直接加4（2k-1）得到。

（3）右上角：將左下角直接復(fù)制到右上角得到另2k-1個(gè)選手在后半程的比賽日程。

（4）右下角：將左上角直接復(fù)制到右下角得到2k-1個(gè)選手在后半程的比賽日程。#include<stdio.h>#defineMAX101//問(wèn)題表示intk; //求解結(jié)果表示inta[MAX][MAX]; //存放比賽日程表（行列下標(biāo)為0的元素不用）voidPlan(intk){inti,j,n,t,temp;n=2; //n從2^1=2開(kāi)始a[1][1]=1;a[1][2]=2; //求解2個(gè)選手比賽日程,得到左上角元素a[2][1]=2;a[2][2]=1;for(t=1;t<k;t++) //迭代處理2^2(t=1)…,2^k(t=k-1)個(gè)選手{ temp=n; //temp=2^t n=n*2; //n=2^(t+1) for(i=temp+1;i<=n;i++) //填左下角元素 for(j=1;j<=temp;j++) a[i][j]=a[i-temp][j]+temp; //產(chǎn)生左下角元素 for(i=1;i<=temp;i++) //填右上角元素 for(j=temp+1;j<=n;j++) a[i][j]=a[i+temp][(j+temp)%n]; for(i=temp+1;i<=n;i++) //填右下角元素 for(j=temp+1;j<=n;j++) a[i][j]=a[i-temp][j-temp];}}3.5

求解大整數(shù)乘法和矩陣乘法問(wèn)題3.5.1求解大整數(shù)乘法問(wèn)題

【問(wèn)題描述】設(shè)X和Y都是n（為了簡(jiǎn)單，假設(shè)n為2的冪，且X、Y均為正數(shù)）位的二進(jìn)制整數(shù)，現(xiàn)在要計(jì)算它們的乘積X*Y。當(dāng)位數(shù)n很大時(shí)，可以用傳統(tǒng)方法來(lái)設(shè)計(jì)一個(gè)計(jì)算乘積X*Y的算法，但是這樣做計(jì)算步驟太多，顯得效率較低?？梢圆捎梅种畏▉?lái)設(shè)計(jì)一個(gè)更有效的大整數(shù)乘積算法。

【問(wèn)題求解】先將n位的二進(jìn)制整數(shù)X和Y各分為兩段，每段的長(zhǎng)為n/2位，如下圖所示。由此，X=A*2n/2+B，Y=C*2n/2+D。這樣，X和Y的乘積為：X*Y=(A*2n/2+B)*(C*2n/2+D)=A*C*2n+(A*D+C*B)*2n/2+B*D如果這樣計(jì)算X*Y，則必須進(jìn)行4次n/2位整數(shù)的乘法（A*C、A*D、B*C和B*D），以及3次不超過(guò)n位的整數(shù)加法，此外還要做2次移位（分別對(duì)應(yīng)乘2n和乘2n/2）。所有這些加法和移位共用O(n)步運(yùn)算。設(shè)T(n)是兩個(gè)n位整數(shù)相乘所需的運(yùn)算總數(shù)，則有以下遞推式：T(n)=O(1)

當(dāng)n=1T(n)=4T(n/2)+O(n)

當(dāng)n>1由此可得T(n)=O(n2)。采用分治法，把X*Y寫(xiě)成另一種形式：

X*Y=A*C*2n+[(A-B)*(D-C)+A*C+B*D]*2n/2+B*D雖然該式看起來(lái)比前式復(fù)雜些，但它僅需做3次n/2位整數(shù)的乘法（A*C、B*D和(A-B)*(D-C)），6次加、減法和2次移位。由此可以推出：

T(n)=O(n1.59)3.5.2求解矩陣乘法問(wèn)題【問(wèn)題描述】對(duì)于兩個(gè)n×n的矩陣A和B，計(jì)算C=A×B。

【問(wèn)題求解】常用的計(jì)算公式是Cij=

，對(duì)應(yīng)算法的時(shí)間復(fù)雜度為O(n3)。是否存在更有效的算法呢？假設(shè)n=2k，考慮采用分治法思路，當(dāng)n≥2時(shí)，將A、B分成4個(gè)n/2×n/2的矩陣：利用塊矩陣的乘法，矩陣C可表示為因此，原問(wèn)題可以劃分成計(jì)算8個(gè)子問(wèn)題的乘積問(wèn)題，因此，兩個(gè)n×n矩陣乘積的計(jì)算量是2個(gè)n/2×n/2矩陣乘積計(jì)算量的8倍，再加上n/2×n/2階矩陣相加的4倍，后者最多需要O(n2)，因此有：T(n)=O(1) 當(dāng)n=1T(n)=8T(n/2)+O(n2) 當(dāng)n>1可以推導(dǎo)出T(n)=O(n3)。也就是說(shuō)，它跟前面介紹的兩個(gè)矩陣直接相乘的計(jì)算量沒(méi)有什么差別。是否可以算得更快呢？Strassen通過(guò)研究分析，提出了Strassen算法。要計(jì)算矩陣乘積：只需要計(jì)算其中：d1=