综述

递归是一种思想，分治是一种算法。分治算法的思想是将一个较大的问题分解为若干个与原问题相似的小问题进行求解。分治算法可以用递归或者迭代的思想实现。分治法的一般步骤如下：

  • 划分, 把问题分解为若干子问题
  • 求解，递归求解子问题
  • 合并，把子问题的解合并为原问题的解

经典问题

可以采用分治法的问题有：

  • 棋盘覆盖问题
  • 在一个已排序数组中找到对应的元素
  • 最大最小值问题
  • 实现归并排序
  • 快速幂
  • 逆序对问题（可以借鉴归并排序求解）

分析

1. 棋盘覆盖问题

  • 划分 : 将 2n*2n 的棋盘划分为4个 2 n-12 n-1的小正方形；
  • 求解 : 其中一个小正方形里面有一个黑格子，可以进行递归求解，另外三个小正方形没有黑格子，我们可以构造黑格子，令其令其和第一个小正方形一样，然后再进行递归求解；
  • 合并 : 当n=2的时候进行解的合并，如果子问题有解则原问题也有解。

2. 在一个已排序数组中找到对应的元素

该问题也叫二分查找问题。即每次将数组的中间元素 a[mid] 和对应元素 k 比较，分三种情况：1. 若 a[mid] == k，则返回mid；否则如果 a[mid] > k，则 k 在数组前半段；如果 a[mid] < k，则k在数组后半段，然后进行递归求解。

3. 最大最小值问题

暂略

4. 归并排序

归并排序是一种自底向上的分治算法。归并排序通过分治（递归）思想接触到子问题，然后在对子问题的合并中进行求解。归并排序的分治也是对数组进行不断二分的。到达最小的子问题（只有一个元素的时候）进行合并。合并结果先保存在一个临时数组中，然后再赋值到原数组。

5. 快速幂

对于 ak，分为两个子问题：

  1. 当 k 为偶数的时候（k & 1 = 0），可以写成 ak-1*ak-1
  2. 当 k 为奇数的时候，可以写成 a* ak-1*ak-1

6. 逆序对问题

只需考虑在归并排序的合并过程中，如果 a[leftLow] > b[rightLow]，则说明 b[rightLow] 和 a[leftLow]… a[leftHigh] 构成逆序对，所以执行 count= leftHigh - leftLow + 1 ;

代码实现

1.在一个已排序数组中找到对应的元素

递归实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
//定义-1为没有找到指定元素，-2为异常
//a为已排序数组，left和right为数组上下界，k为待查找元素
int find(int* a, int left,int right,int k)
{
	if(a==NULL || left<0)
		return -2;
	if(left>right)
		return -1;
	int middle=left+((right-left)>>1);
	if(a[middle]==k)
		return middle;
	else if(a[middle]>k)
		return find(a,left,middle-1,k);
	else if(a[middle<k])
		return find(a,middle+1,right,k);
};

int main()
{
	int a[10]={-1,2,3,4,5,6,7,8,9,15};
	printf("%d\n", find(a,0,9,8));
	return 0;
}

迭代实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
//定义-1为没有找到指定元素，-2为异常
//a为已排序数组，n为数组元素个数，k为待查找元素
int find(int* a,int n,int k)
{
	if(a!=NULL && n>0)
	{
		int low=0,high=n-1,middle;
		while(low<=high)
		{
			middle=low+((high-low)>>1);   //避免溢出
		
			if(a[middle]==k)
				return middle;
			else if(a[middle]>k)
				high=middle-1;
			else if(a[middle]<k)
				low=middle+1;
		}
		return -1;
	}else
	{
		return -2;
	}
};

int main()
{
	int a[10]={-1,2,3,4,5,6,7,8,9,15};
	int* b=NULL;
	printf("%d\n", find(a,sizeof(a)/sizeof(a[0]),11));
	printf("%d %d\n", find(a,0,11),find(b,sizeof(b)/sizeof(b[0]),11));
	return 0;
}

在用递归实现分治算法时，要注意段错误和栈溢出的问题。有的时候栈溢出不一定是递归调用太多，也可能是局部变量太大，所以建议较大的数组放在main函数外。

2. 归并排序也是采用了分治的思想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>
#include <stdlib.h>
void merge(int a[],int left,int middle,int right)
{
	int* temp=(int*)malloc((right-left)*sizeof(int));
	int leftLow=left,leftHigh=middle,rightLow=middle+1,rightHigh=right;
	int i=0;
	while(leftLow <=leftHigh && rightLow<= rightHigh)
	{
		if(a[leftLow]<= a[rightLow])
			temp[i++]=a[leftLow++];
		else
			temp[i++]=a[rightLow++];
	}
	if(rightLow<=rightHigh)
	{
		while(rightLow<=rightHigh)
			temp[i++]=a[rightLow++];
	}
	else
	{
		while(leftLow<= leftHigh)
			temp[i++]=a[leftLow++];
	}
	i=0;
	for(;i<right-left+1; i++)
		a[left+i]=temp[i];
	free(temp);
	return;
};

void mergeSort(int* a,int left,int right)
{
	if(left<right)   //不能left<=right，考虑临界条件
	{
		int middle=left+((right-left)>>1);
		mergeSort(a,left,middle);
		mergeSort(a,middle+1,right);
		merge(a,left,middle,right);
	}
	return;
};

int main()
{
	int a[]={1,4,3,6,8,7,3,9,0};
	mergeSort(a,0,8);
	int i=0;
	for(;i<9;++i)
		printf("%d\n", a[i]);
	return 0;
}

3. 快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>

int power(int a,int k)
{
	if(k==0)
		return 1;
	if(k & 1)
	{
		int m=power(a,(k-1)>>1);
		return m * m * a;
	}
	else
	{
		int m=power(a,(k>>1));
		return m * m;
	}
}
int main()
{
	printf("%d\n", power(2,5));
	return 0;
}