分治算法
2019-09-29 本文已影响0人
董泽平
分治法
1.什么是分治算法？
将原问题划分成n个小规模的问题，并且这些小规模问题与原问题结构相似，递归去解决这些子问题，最后合并子问题的结果，就得到了原问题的解。
2.分治基本操作步骤？
- 分解：将原问题分解为一系列子问题
- 解决：递归解决子问题，当子问题足够小，直接求解
- 合并：将子问题的解合并原问题的解。
3.分治算法需要满足的条件?
- 原问题与分解的小问题具有相同的结构
- 原问题分解的子问题之间无联系(和动态规划的直接区别)
- 具有终止分解的条件，问题分解到一定规模，停止，并可以求解
- 子问题的解可以合并原问题。
4.快速排序和归并排序
前面排序章节二我已经细讲了两种排序算法实现思想，这里只是谈谈它如何用到了分治思想。没懂这两个算法的，可以去看看我前面的资料。
首先是快速排序，它将原问题划分成一个个小问题，每次递归分区操作，每次分区都会确定一个基准值，基准值左边都小于基准数，基准值右边都大于这个基准数。当递归到数组里只剩一个数据时，那数据肯定有序了，然后递归逐层返回有序的数据，这就是典型的分治。
接着是归并排序，这个更简单，每次将数组分成两半，前半部分和后半部分，逐层递归分解，直到数组只剩一个数据停止(1个数据肯定有序了)，然后递归带回，逐层的合并，就是归并数据，每层都有序了，最终数组就有序了，还是分治的思想。
5.用分治思想求数组最大值
分析：每次将数组递归分解成两半，前半部分和后半部分，只剩一个数据，这个数据就是最大的，然后数据合并同时，比较最大值，最后一层合并，就是整个数组的最大值
int findMax(int *arr,int low,int high)
{
int max,mid,max1,max2;
mid = (low+high)/2;
//数组只有一个数据，它就是最大的
if(low==high)
{
max = arr[low];
return max;
}
//数组数据大于等于2个，那个左半分区和右半分区最大值比较
else
{
max1 = findMax(arr,low,mid);
max2 = findMax(arr,mid+1,high);
return max1>max2? max1:max2;
}
}
上面我就用到了分治思想，首先将问题递归划分成小规模数据，直到规模变成1，此时它就是最大值，然后归并数据时，两两比较大小，最后一层返回的就是最大值。
6.用分治思想求折半查找
分析：普通版本的折半查找我们很清楚，那如何用分治去实现？和普通版一样，每次对比中间数据，中间数据比目标查找值大，递归去左边找，反之去右边，递归退出的条件是找到了或者数据不存在。
int findNum(int *arr,int num,int low,int high)
{
if(low>high)
{
return -1;
}
int mid;
mid = (low+high)/2;
if(arr[mid]==num)
{
return mid;
}else if(arr[mid]<num)
{
return findNum(arr,num,mid+1,high);
}else
{
return findNum(arr,num,low,mid);
}
}
获取完整代码
我分别用C，C++，JAVA三种主流语言编写了完整代码，请大家指导批正，一起学习。
