分治法
在求解一個輸入規模為n，而n的取值又很大的問題時，直接求解往往非常困難。這時，可以先分析問題本身所具有的某些特性，然後從這些特性出發，選擇某些適當的設計策略來求解。這種方法，就是所謂的分治法。適用條件
採用分治法解決的問題一般具有的特徵如下：1. 問題的規模縮小到一定的規模就可以較容易地解決。
2. 問題可以分解為若干個規模較小的模式相同的子問題，即該問題具有最優子結構性質。
3. 合併問題分解出的子問題的解可以得到問題的解。
4. 問題所分解出的各個子問題之間是獨立的，即子問題之間不存在公共的子問題。
設計步驟
1. 劃分步：把輸入的問題劃分為k個子問題，並儘量使這k個子問題的規模大致相同。2. 治理步：當問題的規模大於某個預定的閾值n0時，治理步由k個遞歸調用組成。
3. 組合步：組合步把各個子問題的解組合起來，它對分治算法的實際性能至關重要，算法的有效性很大地依賴於組合步的實現。
分治法的關鍵是算法的組合步。究竟應該怎樣合併，目前沒有統一的模式，因此需要對具體問題進行具體分析，以得出比較好的合併算法。
分治法實例
快速排序
#include "stdio.h"#define N 10
int partition(int num[],int left,int right)
{
int pivot;
pivot=num[left]; /*提取支點數值，釋放一個位置*/
while(left
{
/*從右到左掃描*/
while(num[right]>=pivot&≤ft
if(right!=left)
{
num[left]=num[right]; left++;
}
while(num[left]<=pivot&≤ft
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",N);
for(i=0;i
quicksort(num,0,N-1);
printf("The sorted list, in ascending order, is:\n");
for(i=0;i
printf("\n");
return 0;
}
合併排序
#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
{
s=t;t=2*s;i=0; /*t:合併後的 數組段長度;s:子數組段長度;i:起點元素下標.*/
while(i+t
{
merge(A,i,i+s-1,i+t-1,t);
/*i+s-1:前子數組段的終點元素下標;i+t-1:後子數組段的終點元素下標.*/
i=i+t; /*將數組段按t為單位向前推進*/
}
if(i+s
merge(A,i,i+s-1,n-1,n-i);
}
}
int main()
{
int num[N],i;
printf("Please input %d numbers:\n",N);
for(i=0;i
mergesort(num,N);
printf("The sorted list, in ascending order, is:\n");
for(i=0;i
printf("\n");
return 0;
}
大整數乘法
通常，在分析一個算法的計算複雜性時，一般將加法和乘法運算當作是基本運算來處理，即將執行一次加法或乘法運算所需的計算時間，看作一個僅僅取決於計算機硬體處理速度的常數。然而，在有些情況下，需要處理數值很大的整數，這些數值無法在計算機硬體能直接表示的範圍內進行處理。如果要精確地表示大整數的數值並在計算結果中要求精確地得到所有位數上的數字，就必須用軟體的方法來實現大整數的算術運算，即用分治法實現大整數的運算。另外，分治法實現大整數運算，可以大大提高運算效率。
設兩個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
