分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
分治算法应用的场景很多,比如快速排序算法,还有汉诺塔问题,应该说很多搜索算法和排序算法都用到。
思想其实大家都很容易明白,但是用的时候就不是那么简单了。那么下面直接给大家实战。
最简单的就是大家一直听说的快速排序
该方法的基本思想是:
1.先从数列中取出一个数作为基准数。
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。(通过分区来实现分而治之)
3.再对左右区间重复第二步,直到各区间只有一个数。(递归是分治算法孪生兄弟)
代码
#include<iostream>
using namespace std;
void quickSort(int a[],int,int);
int main()
{
int array[]={34,65,12,43,67,5,78,10,3,70},k;
int len=sizeof(array)/sizeof(int);
cout<<"The orginal arrayare:"<<endl;
for(k=0;k<len;k++)
cout<<array[k]<<",";
cout<<endl;
quickSort(array,0,len-1);
cout<<"The sorted arrayare:"<<endl;
for(k=0;k<len;k++)
cout<<array[k]<<",";
cout<<endl;
system("pause");
return 0;
}
void quickSort(int s[], int l, int r)
{
if (l< r)
{
int i = l, j = r, x = s[l];
while (i < j)
{
while(i < j && s[j]>= x) // 从右向左找第一个小于x的数
j--;
if(i < j)
s[i++] = s[j];
while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数
i++;
if(i < j)
s[j--] = s[i];
}
s[i] = x;
quickSort(s, l, i - 1); // 递归调用
quickSort(s, i + 1, r);
}
}
总结:实际上就是类似于数学归纳法,找到解决本问题的求解方程公式,然后根据方程公式设计递归程序。
1、一定是先找到最小问题规模时的求解方法
2、然后考虑随着问题规模增大时的求解方法
3、找到求解的递归函数式后(各种规模或因子),设计递归程序即可。