算法设计与分析——分治算法

任何能用计算机求解的问题所需要的计算时间都与其规模你有关，问题规模越少，越容易直接求解，解题所需的计算时间也越少。

分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，各个解决，分而治之。如果原问题可以分割成k个子问题，且子问题都可以解决，并可利用这些子问题的解求出原问题的解，那么分治法就是可行的，有分治法产生子问题往往是原问题的较小模式，这就为使用递归技术提供了方便,递归这些子问题再将其合并。

分治一般来说在每一层递归上都有三个步骤：
1.分解：将原问题分解成若干子问题，这些子问题相互独立，形式相同；
2.解决：若子问题规模较小，直接解决，否则再次递归；
3.合并：将各个子问题的解合并成为原问题的解。

分支法能解决的问题所具备的特征：
1、该问题的规模缩小到一定程度就可以容易的解决；
2、该问题可以分解成若干个规模较小的相同问题，即该问题具有最优子结构的性质；
3、利用该问题分解出的子问题的解可以合并为该问题的解；
4、该问题所分解出的子问题是相互独立的，即子问题之间不包含公共的子子问题。

例题一：

在a[left:right]中选第k小的元素

int select(int left,int right,int k)//在a[left:right]中选第k小的元素
{
if(left>=right)
return a[left];
int i=left;
int j=right+1;
int p=a[left];
while(true)
{
do
{
i+=1;
}while(a[i]<p);
if(i>=j)
break;
swap(a[i],a[j]);
}
ia(j-left+1==k)
return p;
a[left]=a[j];
a[j]=p;
if(j-left+1<k)
return select(j+1,right,k-j+left-1);
else
return select(left,j-1,k);
}

例题二
输油管道问题：

算法一：
对数组A排序，取中间元素
int n;
int x;
int a[1000];
cin>>n;
for(int k=0;k<=n;k++)
cin>>x>>a[k];
sort(a,a+n);
int min=0;
for(int i=0;i<n;++i)
min+=(int)fabs(a[i]-a[n/2]);
cout<<min<<endl;

算法二：
采用分治算法求中位数
int main()
{
int n;
int x;
int a[1000];
cin>>n;
for(int k=0;k<=n;k++)
cin>>x>>a[k];
int y=select(0,n-1,n/2);
int min=0;
for(int i=0;i<n;++i)
min+=(int)fabs(a[i]-y);
cout<<min<<endl;
}
int select(int left,int right,int k)//在a[left:right]中选第k小的元素
{
if(left>=right)
return a[left];
int i=left;
int j=right+1;
int p=a[left];
while(true)
{
do
{
i+=1;
}while(a[i]<p);
if(i>=j)
break;
swap(a[i],a[j]);
}
ia(j-left+1==k)
return p;
a[left]=a[j];
a[j]=p;
if(j-left+1<k)
return select(j+1,right,k-j+left-1);
else
return select(left,j-1,k);
}

例题三：
最大子段和问题：

int sum(int a[],int left,int right)
{
sum=0;
if(left==right)
{
if(a[left]>0)
sum=a[left];
else
sum=0
}
else
{
int center;
center=(left+right)/2
leftsum=sum(a,left,center);
rightsum=sum(a,center+1,right);
s1=0;
lefts=0;
for(i=center;i>=left;i–)
{
lefts+=a[i];
if(lefts>s1)
s1=lefts;
}
s2=0;
rights=0;
for(j=center+1;j<=right;++j)
{
rights+=a[j];
if(rights>s2)
s2=rights;
}
sum=s1+s2;
if(sum<leftsum)
sum=leftsum;
if(sum<rightsum)
sum=rightsum;
}
return sum;
}