分治
分治法
在求解一个输入规模为n，而n的取值又很大的问题时，直接求解往往非常困难。这时，可以先分析问题本身所具有的某些特性，然后从这些特性出发，选择某些适当的设计策略来求解。这种方法，就是所谓的分治法。
分治法的适用条件
采用分治法解决的问题一般具有的特征如下：
1. 问题的规模缩小到一定的规模就可以较容易地解决。
2. 问题可以分解为若干个规模较小的模式相同的子问题，即该问题具有最优子结构性质。
3. 合并问题分解出的子问题的解可以得到问题的解。
4. 问题所分解出的各个子问题之间是独立的，即子问题之间不存在公共的子问题。
分治法的设计步骤
1. 划分步：把输入的问题划分为k个子问题，并尽量使这k个子问题的规模大致相同。
2. 治理步：当问题的规模大于某个预定的阈值n0时，治理步由k个递归调用组成。
3. 组合步：组合步把各个子问题的解组合起来，它对分治算法的实际性能至关重要，算法的有效性很大地依赖于组合步的实现。
分治法的关键是算法的组合步。究竟应该怎样合并，目前没有统一的模式，因此需要对具体问题进行具体分析，以得出比较好的合并算法。
分治法实例
1. 快速排序
#include "stdio.h"
#define N 10
int partition(int num[],int left,int right)
{
int pivot;
pivot=num[left]; /*提取支点数值，释放一个位置*/
while(left<right)
{
/*从右到左扫描*/
while(num[right]>=pivot&&left<right) right--; /*跳过大于或等于的数值*/
if(right!=left)
{
num[left]=num[right]; left++;
}
while(num[left]<=pivot&&left<right) left++; /*跳过小于或等于的数值*/
if(right!=left)
{
num[right]=num[left]; right--;
}
}
num[left]=pivot; /*移动支点数值到正确的位置*/
return left; /*返回支点的下标*/
}
void quicksort(int num[],int lower,int upper)
{
int pivot;
pivot=partition(num,lower,upper);
if(lower if(upper>pivot) quicksort(num,pivot+1,upper);
}
int main()
{
int num[N],i;
printf("Please input %d numbers:
",N);
for(i=0;i<N;i++) scanf("%d",&num);
quicksort(num,0,N-1);
printf("The sorted list, in ascending order, is:
");
for(i=0;i<N;i++) printf("%5d",num);
printf("
");
return 0;
}
2. 合并排序
#include "stdio.h"
#include "stdlib.h"
#define N 10
void merge(int A[],int p,int q,int r,int t)
{
int *temp;
temp=(int *)malloc(t*sizeof(int));
int i,j,k;
i=p;j=q+1;k=0;
while(i<=q&&j<=r)
{
if(A<=A[j]) temp[k++]=A[i++];
else temp[k++]=A[j++];
}
if(i==q+1)
{
for(;j<=r;j++,k++) temp[k]=A[j];
}
else
{
for(;i<=q;i++,k++) temp[k]=A;
}
k=0;
for(i=p;i<=r;i++,k++)
A=temp[k];
free((void *)temp);
}
void mergesort(int A[],int n)
{
int i,s,t=1;
while(t<n)
{
s=t;t=2*s;i=0; /*t:合并后的数组段长度;s:子数组段长度;i:起点元素下标.*/
while(i+t<n)
{
merge(A,i,i+s-1,i+t-1,t);
/*i+s-1:前子数组段的终点元素下标;i+t-1:后子数组段的终点元素下标.*/
i=i+t; /*将数组段按t为单位向前推进*/
}
if(i+s<n) /*处理尾部数据*/
merge(A,i,i+s-1,n-1,n-i);
}
}
int main()
{
int num[N],i;
printf("Please input %d numbers:
",N);
for(i=0;i<N;i++) scanf("%d",&num);
mergesort(num,N);
printf("The sorted list, in ascending order, is:
");
for(i=0;i<N;i++) printf("%5d",num);
printf("
");
return 0;
}
3. 大整数乘法
通常，在分析一个算法的计算复杂性时，一般将加法和乘法运算当作是基本运算来处理，即将执行一次加法或乘法运算所需的计算时间，看作一个仅仅取决于计算机硬件处理速度的常数。
然而，在有些情况下，需要处理数值很大的整数，这些数值无法在计算机硬件能直接表示的范围内进行处理。如果要精确地表示大整数的数值并在计算结果中要求精确地得到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算，即用分治法实现大整数的运算。另外，分治法实现大整数运算，可以大大提高运算效率。
设两个n（na，nb）位d进制数A、B相乘：
当位数n为偶数时，将数拆分为两段等长的数段，高位段为H，地位段为L，则有
A=Ha*dn/2+La B=Hb*dn/2+Lb
当位数n为奇数时，可在数的首位前添0，使数的位数为偶数，然后将数拆分为两段等长的数段。
例如，计算2进制数1010与1110的乘积。步骤如下：
（1）：1010=10*22+10 1110=11*22+10
（2）：1010*1110=（10*22+10）*（11*22+10）=10*11*24+10*11*22+10*10*22+10*10
（3）：1010*1110=（1*21+0）*（1*21+1）*24+（1*21+0）*（1*21+1）*22+（1*21+0）*（1*21+0）*22+（1*21+0）*（1*21+0）=2*3*16+2*3*4+2*2*4+2*2=140