分治法求解問題
一、尋找兩個等長有序序列的中位數
1.1 問題描述
對於一個長度為n的有序序列（假設均為升序序列），a[0...n-1]，處於中間位置的元素稱為a的中位數，現要求兩個等長有序序列合併的中位數。
1.2 求解思路
對於求兩個有序序列a[],b[]的中位數，首先考慮到二路歸併後求其中位數c[m]（m=(s+t)/2,s為序列左側編號，t為序列右側編號，對於偶數位中位數，只考慮下中位），但時間複雜度為O(n)，效率比較低，因此這裡考慮採用分治法。當兩個有序序列元素個數只有一個時，返回較小的那一個；當元素個數不止一個時，分為以下三種情況：
（1）a[m1]與b[m1]相等,a[m1]或b[m1]就是中位數，因為合併後a[m1]和b[m1]必定在中間位置。
（2）a[m1]>b[m1],此時考慮大的舍大的，小的舍小的。即元素大的序列捨棄後半子序列，保留前半子序列；元素小的序列捨棄前半子序列，保留厚板子序列（要求捨棄的長度相等）。
（3）a[m1]>b[m1],同（2）。
在求解過程中，保留前半子序列prepart可以直接t=m；但保留後半子序列postpart時，需要考慮到奇偶位數問題，當元素個數為奇數(s+t)%2==0個時，直接t=m（這樣捨棄的位數才相等），當元素個數為偶數(s+t)%2!=0個時，t=m+1（因為偶數個元素時，考慮的是下中位，因此為使捨棄的位數相等，下中位就不能要）。
1.3 詳細程式碼
#include<iostream>
using namespace std;
#define MAXV 51
void prepart(int& s,int& t){//求序列前半部分
int m=(s+t)/2;
t=m; //包括當前數
}
void postpart(int& s,int& t){
int m=(s+t)/2;
if((s+t)%2==0){//當前剩餘奇數位
s=m;
}
else{//當前剩餘偶數位。（若b保留後半部分，由於a保留的前半部分包含中間位，為保證捨棄長度相等，b需捨棄中間位）
s=m+1;
}
}
int Solve(int a[],int s1,int t1,int b[],int s2,int t2){//採用遞迴方法
int m1,m2;
if(s1==t1&&s2==t2){
return a[s1]<b[s2]?a[s1]:b[s2];
}
else{
m1=(s1+t1)/2;
m2=(s2+t2)/2;
if(a[m1]==b[m2]){
return a[m1];
}
else if(a[m1]<b[m2]){//a捨棄前半部分，保留後半部分，b捨棄後半部分，保留前半部分（小的捨棄小的，大的捨棄大的）
postpart(s1,t1);
prepart(s2,t2);
return Solve(a,s1,t1,b,s2,t2);
}
else { //a保留前半部分，b保留後半部分
prepart(s1,t1);
postpart(s2,t2);
return Solve(a,s1,t1,b,s2,t2);
}
}
}
int main(){
int n;//序列長度
int a[MAXV];//第一個序列
int b[MAXV];//第二個序列
cout<<"請輸入序列長度："<<endl;
cin>>n;
cout<<"請輸入第一個序列：";
for(int i=0;i<n;i++){
cin>>a[i];
}
cout<<"請輸入第二個序列：";
for(int i=0;i<n;i++){
cin>>b[i];
}
int result=Solve(a,0,n-1,b,0,n-1);
cout<<"中位數為："<<result<<endl;
return 0;
}
1.4 時間複雜度分析
對於此種演演算法，每次比較後序列減少一半，當n=1時，T(n)=1；當n>1時，T(n)=T(n/2)+1，因此時間複雜度為O(log₂n)。
二、求解最大連續子序列和問題
2.1 問題描述
給定一個包含 K個整數的序列 {N1,N2,…,NK}。連續子序列定義為 {Ni,Ni+1,…,Nj}，其中 1≤i≤j≤K。最大子序列是指序列內各元素之和最大的連續子序列。規定一個序列的最大連續子序列和至少為0，若小於0，則返回0。
2.2 求解思路
採用分治法的思想。對於一個序列，將其一分為二，中間元素對應編號mid，序列左側left，序列右側right，其最大連續子序列和只可能存在三種位置即mid左邊，mid右邊以及跨越了mid分佈於中間（當序列只有一個元素時，若這個元素大於0，返回這個元素，否則返回0）。因此只需要求左側最大連續子序列和maxLeftSum，右側最大連續子序列和maxRightSum以及中間最大連續子序列和maxMidSum，比較最大值返回即可。採用遞迴思想，每次將序列一分為二，直到遞迴出口：當前序列只有一個元素。求中間最大連續子序列和的過程可以看做順序遍歷（使用for迴圈），當加上當前這個元素後值小於當前所記錄的最大和時，所記錄的最大和不變，只有當加上當前元素值大於最大和時，最大和才變。
2.3 程式碼如下：
#include<iostream>
#include<algorithm>
using namespace std;
int Solve(int a[],int left,int right){
if(left==right){
if(a[left]>0){
return a[left];
}
else return 0;
}
int mid=(left+right)/2;
int maxLeftSum,maxRightSum;//左右序列中最大子序列
int leftBorderSum,maxLeftBorderSum;//跨過中間序列時，左邊已有序列以及最大連續子序列
int rightBorderSum,maxRightBorderSum;
maxLeftSum=Solve(a,left,mid);//求左邊序列最大連續子序列和
maxRightSum=Solve(a,mid+1,right);//求右邊序列最大連續子序列和
leftBorderSum=0;maxLeftBorderSum=0;
for(int i=mid;i>=left;i--){//跨越中間時求中間左邊最大連續子序列和
leftBorderSum+=a[i];
if(leftBorderSum>maxLeftBorderSum){
maxLeftBorderSum=leftBorderSum;
}
}
rightBorderSum=0;maxRightBorderSum=0;
for(int i=mid+1;i<=right;i++){//跨越中間時求中間右邊最大連續子序列和
rightBorderSum+=a[i];
if(rightBorderSum>maxRightBorderSum){
maxRightBorderSum=rightBorderSum;
}
}
int maxMidSum=maxLeftBorderSum+maxRightBorderSum;
return max(maxMidSum,max(maxLeftSum,maxRightSum));
}
int main(){
int a[]={-2,11,-4,13,-5,-2},n=6;
int b[]={-6,2,4,-7,5,3,2,-1,6,-9,10,-2},m=12;
cout<<"a序列的最大連續子序列和為："<<Solve(a,0,n-1)<<endl;
cout<<"b序列的最大連續子序列和為："<<Solve(b,0,m-1)<<endl;
return 0;
}
2.4 時間複雜度分析
使用遞迴方法，遞迴模型為：當n==1時，T(n)=1；當n>1時，T(n)=T(n/2)+n。由此可得時間複雜度為O(nlog₂n)。
2.5 窮舉法求最大連續子序列和（O(n)）
使用窮舉法求最大連續子序列和時，基本思路為：遍歷序列，用max記錄最大連續子序列和，now記錄當前連續子序列和，當加了一個元素後now>max，就設max=now；當加了一個元素後now<0，就設now=0，從當前元素的下一個元素重新開始記錄。程式碼如下：
int Solve(int a[],int n){
int max=-INF,now=0;
for(int i=0;i<n;i++){
now+=a[i];
if(now<0){//重新開始下一個子序列
now=0;
}
if(max<now){//比較求最大連續子序列和
max=now;
}
}
return max;
}
由於在演演算法中，只對序列遍歷了一遍，因此時間複雜度為O(n)。
2.6 演演算法題acwing-1479.最大子序列和
問題描述：此題與例題不同之處在於此題要求輸出最大連續子序列和最左邊元素和最右邊元素。求解此題時，採用窮舉法，設定變數temp儲存開始位置（初始時為0）。for迴圈遍歷，當加了一個元素後now>max，就設max=now，left=temp，right=i；當加了一個元素後now<0，就設now=0，從當前元素的下一個元素重新開始記錄即temp=i+1。程式碼如下：
void Solve(vector<int> v,int n){
int i,now=0,max=-INF;
int left=0,right=0;
int temp=0;
for(i=0;i<n;i++){
now+=v[i];
if(now<0){
now=0;
temp=i+1;
}
else{
if(now>max){
max=now;
left=temp;
right=i;
}
}
}
if(max<0){//此時表示沒有最大連續子序列
max=0;
left=0;
right=n-1;
}
cout<<max<<" "<<v[left]<<" "<<v[right];
}
三、求解大整數乘法問題
3.1 問題描述
設X和Y都是n（為了簡單，假設n為2的冪，且X，Y均為正數）位的二進位制整數，現在要計算它們的乘積X×Y。當位數n很大時可以用傳統方法來設計一個計算乘積X×Y的演演算法，但是這樣做計算步驟太多，顯得效率低，此時可以採用分治法設計一個更有效的大整數乘積演演算法。
3.2 求解思路
首先看演演算法求解過程和改進過程：
通過此過程可以看出，我們需要求四次乘法，分別是AC，AD，BC，BD，因此可以考慮使用分治法，每次將兩個數一分為二，採用遞迴演演算法，直到一分為二後只剩一位，此時為遞迴出口，由於是二進位制相乘，因此只需判斷0和1即可。最後遞迴出來可以求得最外層AC，AD，BC，BD，將其轉化為十進位制，帶入方程即可求得它們乘積的解，最後將其轉換為二進位制即為結果。
3.3 詳細程式碼
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 20
void left(int a[],int n,int b[]){//求高n/2位
for(int i=0;i<MAXN;i++){
b[i]=0;
}
for(int i=n/2;i<=n;i++){
b[i-n/2]=a[i];
}
}
void right(int a[],int n,int b[]){//求低n/2位
for(int i=0;i<MAXN;i++){
b[i]=0;
}
int i;
for(i=0;i<n/2;i++){
b[i]=a[i];
}
b[i]='\0';
}
long Trans2to10(int a[]){//將二進位制轉換為十進位制
int s=a[0],x=1;
for(int i=1;i<MAXN;i++){
x=2*x;
s+=a[i]*x;
}
return s;
}
void Trans10to2(int x,int a[]){//將十進位制轉換為二進位制
int i,j=0;
while(x>0){
a[j]=x%2;//求餘數
j++;
x=x/2;
}
for(i=j;i<MAXN;i++){
a[i]=0;
}
}
void MULT(int X[],int Y[],int Z[],int n){
long e1,e2,e3,e4,e;
int A[MAXN],B[MAXN],C[MAXN],D[MAXN];
int m1[MAXN],m2[MAXN],m3[MAXN],m4[MAXN];
for(int i=0;i<MAXN;i++){
Z[i]=0;
}
if(n==1){
if(X[0]==1&&Y[0]==1) Z[0]=1;
else Z[0]=0;
}
else{
left(X,n,A); //求X高n/2位
right(X,n,B); //求X低n/2位
left(Y,n,C); //求Y高n/2位
right(Y,n,D); //求Y低n/2位
MULT(A,C,m1,n/2); //m1=AC
MULT(A,D,m2,n/2); //m2=AD
MULT(B,C,m3,n/2); //m3=BC
MULT(B,D,m4,n/2); //m4=BD
e1=Trans2to10(m1); //將e1轉換為十進位制數
e2=Trans2to10(m2);
e3=Trans2to10(m3);
e4=Trans2to10(m4);
e=e1*(int)pow(2,n)+(e2+e3)*(int)pow(2,n/2)+e4;//求解
Trans10to2(e,Z); //將e轉換成二進位制數
}
}
void disp(int a[]){
for(int i=MAXN-1;i>=0;i--){
cout<<a[i];
}
cout<<endl;
}
void trans(char a[],int n,int X[]){//將字串轉化為陣列（注意：低位在前，高位在後）
for(int i=0;i<n;i++){
X[i]=(int)(a[n-i-1]-'0');
}
for(int i=n;i<MAXN;i++){
X[i]=0;
}
}
int main(){
long e;
char a[]="10101100";
char b[]="10010011";
int X[MAXN],Y[MAXN],Z[MAXN];
int n=8;
trans(a,n,X);//將字串X轉換為陣列
trans(b,n,Y);//將字串Y轉換為陣列
cout<<"X：";disp(X);
cout<<"Y：";disp(Y);
cout<<"Z=X*Y"<<endl;
MULT(X,Y,Z,n);//求得Z
cout<<"Z：";disp(Z);
e=Trans2to10(Z);
cout<<"Z對應的十進位制數："<<e<<endl;
cout<<"驗證正確性："<<endl;
long x,y;
x=Trans2to10(X);
y=Trans2to10(Y);
cout<<"X對應的十進位制數為："<<x<<endl;
cout<<"Y對應的十進位制數為："<<y<<endl;
cout<<"z=x*y"<<endl;
cout<<"求解結果："<<x*y<<endl;
return 0;
}
3.4 時間複雜度分析
根據遞迴模型可知，最後時間複雜度為O(n^2)；
3.5 執行結果
3.6 注意事項
在求解過程中注意二進位制寫法左邊是高位，右邊是低位；而陣列儲存時，從小到大是從低位到高位，分開儲存時要注意順序。程式碼中變數比較多，注意區分。十進位制轉二進位制，二進位制轉十進位制要熟練。