汉诺塔问题递归算法分治分：递归解决较小的问题治：然后从子问题(2)

可使用分治法求解的一些经典问题

（1）二分搜索

（2）大整数乘法

（3）Strassen矩阵乘法

（4）棋盘覆盖

（5）合并排序

（6）快速排序

（7）线性时间选择

（8）最接近点对问题

（9）循环赛日程表

（10）汉诺塔

依据分治法设计程序时的思维过程

实际上就是类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。

1、一定是先找到最小问题规模时的求解方法

2、然后考虑随着问题规模增大时的求解方法

3、找到求解的递归函数式后（各种规模或因子），设计递归程序即可。

典型示例

1、求x的n次幂问题

int power(int x, int n)
{
	if (n == 0)
		return 1;
	if (n == 1)
		return x;
	if (n % 2 == 0)
		return power(x*x, n / 2);
	else
		return power(x*x, n / 2)*x;
}

int bin_search(int a[], int n, int x)
{
	int low, high, mid;
	low = 0;
	high = n - 1;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (x < a[mid])
			high = mid - 1;
		else if (x > a[mid])
			low = mid + 1;
		else
			return mid;
	}
	return -1;
}

int MaxSubSeqSum(const int *A, int left, int right)
{
	int MaxLeftSum, MaxRightSum, MaxSum;
	int MaxLeftBorderSum, MaxRightBorderSum;
	int LeftBorderSum, RightBorderSum;
	int center;
	int i;
	if (left == right)
	{
		if (A[left] > 0)
			return A[left];
		else
			return 0;
	}
	center = (left + right) / 2;
	MaxLeftSum = MaxSubSeqSum2(A, left, center);
	MaxRightSum = MaxSubSeqSum2(A, center + 1, right);
	MaxLeftBorderSum = 0;
	LeftBorderSum = 0;
	for (i = center; i >= left; i--)
	{
		LeftBorderSum += A[i];
		if (LeftBorderSum > MaxLeftBorderSum)
			MaxLeftBorderSum = LeftBorderSum;
	}
	MaxRightBorderSum = 0;
	RightBorderSum = 0;
	for (i = center + 1; i <= right; i++)
	{
		RightBorderSum += A[i];
		if (RightBorderSum > MaxRightBorderSum)
			MaxRightBorderSum = RightBorderSum;
	}
	MaxSum = Max_3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);
	return MaxSum;
}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-87683-2.html