分治法的概念以及应用

分治法：“分久必合，合久必分” 哈哈，其实分治法应该理解为分而治之的方法，它的基本思想是把一个大的问题比较复杂的问题，拆分成多个规模较小的子问题，然后解决这些子问题的难度就比原来大的问题简单的多。但是这个拆分是要注意如何去拆分按什么思路去拆分因为拆分出来的这种子问题要求和原来的问题是同样的结构的问题（也可以说是相同的问题），只是复杂度小一些规模小一些，拆分出来的子问题又可以用同样的方式进一步的拆分。那么既然如此我们解决这个问题时候所采用的函数是不是能够用同样的函数去解决问题呢？答案是肯定的。所以再分治法中往往要用到递归的技术来解决问题。递归技术在下文单独篇。以上就是我对分治法基本思想的理解。
所以分治法它会先做分解，分解之后它会把一系列小的问题给它解决掉，然后再把小的问题进行相应的汇合，一步一步整合合并，合并之后得到最终的原来的初始问题的解决方案。就是按这种思路来解决问题，要利用到分治法来解决问题往往要对这个问题本身有一定的要求，首先这个问题它的规模缩小到一定的程度要能够容易的解决，否则就失去了拆分它的意义。其次这个问题必须要能够分解成若干个规模较小的相同问题，如果分出来的是不同问题那也不行。最后要能够利用到这个问题，分解出来的子问题的解能够合并为原来问题的解。同时各个子问题要求是相互独立的，不相互独立也不行。这就是分治法的基本思想以及对分治法应用的基本要求。


递归技术
上面说了分治法要用到递归技术，所谓递归其实就是在运行的过程中调用自己这种做法。即函数或者过程在运行过程中会调用自己。
为什么会考虑调用自己来解决问题呢？
答案就是因为你要解决的这个复杂问题可以拆分为多个同类型的子问题，既然这个函数是用来解决这个复杂问题的那么同质的子问题也能够用这个函数解决所以就自己掉自己。这个思路虽然比较明晰但是在应用过程中我们会发现一系列的问题，很多很多的人在大学里面学数据结构与算法这个课程时候其实是没有理解清楚递归是怎么一回事的。因为在分析执行递归的过程时候，逻辑上来讲是有一定的复杂性的。这里我用一个简单的例子来讲解下递归到底是如何运作的。
用一个函数求：一个数列当中的某一个项。这个数列有这样的一个规律，第0项是1 ，第1项是1，到第2项就是前两项之和，第三项也是前两项之和。就是求这样的数列当中的某一个元素值。


上面就是我构造了一个函数，就是一个递归的函数，我来分析这个函数是怎么运作的，首先看到这个函数的写法非常之简单。只有3句话。前两项很简单就直接返回了。但是从第2项后就是n=2就不符合前面两个条件了。但是符合第三个条件 if(n>1)  。它会返回Fun(n-1) +Fun(n-2); 而F(n-1)就是当前项的前面一项，然后F（n-2）就是再前面一项，如果说知道这两个只我们加起来再把结果返回就完成了我们的工作了。n-1 就是Fun（1） 再加上Fun（n-2）就是F（0）；所以就是1+1 就return 2；
重点是当n=3的时候，它会拆解为Fun（2）+Fun（1）,我们指导Fun（1）可以直接得到值 1 ；而Fun（2）运行下来后又被进一步拆解为Fun（1） +Fun(0);Fun(1)与F（0）的值我们都知道都是1所以求出Fun（2）等于2，再加上Fun（1）  ；最后结果等于3；
呵呵！递归就是根据这样的一个原则进行相关的运算的，所以非常的巧妙，往往利用到这种递归思想的函数非常的简短。但是功能很强大这就是递归的技术。

//1;1;2;3;5;8....
int  Fun(int n)
{
	if(n=0) return 1;
	if(n==1) return 1;
	if(n>1) return Fun(n-1)+Fun(n-2);
}

下图是一颗树，这颗树体现出了递归运作的过程中的拆解过程，即F(5) 会被拆解为 F（4） +F (3);  F(4)会进一步拆解为F（3） +F（2） ；F（3） 进一步拆解为F（2）+F（1）；可以看出拆解到最底下没有叶子的节点都是最简单的值。所以整个问题的解就变成了很多个简单的值拼合起来得到最终的结论。这就是分治法利用到递归的思想来解决问题的时候的实际情况。

递归是非常重要的否则很多问题你是难以理解的。
分治法到底有什么用？
分治法的应用之 二分法查找
分治法在二分查找法里面有应用,也就是说二分查找利用到了分治法的思想来做的我直接给段代码，看如何利用分治法进行的二分查找

//输入的参数:L 就是一堆数列;a和b分别是要查找的区间范围开始和结束或起点和终点;x 要查的元素
//比如数列有10个元素，都存在L这个线性表当中，那么对这个线性表进行查找 
//a的初始值应该是等于0的，因为数组下标最小是0;b等于9 ;就是数组的上限;
//假设我要查找的是10这个数字，x就等于10 ;

//应用下面这个函数看是如何做的！

//输入的参数:L 就是一堆数列;a和b分别是要查找的区间范围开始和结束或起点和终点;x 要查的元素
//比如数列有10个元素，都存在L这个线性表当中，那么对这个线性表进行查找 
//a的初始值应该是等于0的，因为数组下标最小是0;b等于9 ;就是数组的上限;
//假设我要查找的是10这个数字，x就等于10 ;

//应用下面这个函数看是如何做的！
function  Binary_Search(L,a,b,x){
	if(a>b)//开始下标大于结束下标 ，只能说明数列查找完毕了
	{
	    return(-1); //没有需要的值
	}
	else//a等于小于b
	{
	    m = (a+b)/2;//求出中间点的下标
	    
            	
	    if(x==L[m])//如果查找的元素x等于中间点这个元素值
	       return (m);//查找到了返回
       	    else if(x>L[m])//x大于中间点值，说明我们要查的数据在右边区间
	       return (Binary_Search(L,m+1,b,x));
	    else //小于在左边区间
	       return (Binary_Search(L,a,m-1,x));
	
	}

}

可以看出：如果要查的值在数列中会执行return(m) ;如果没有在数列中会二分之后，a和b的参数会变化，即a增大b减小直到return（-1）；没有找到。

二分查找法就通过这么简单的方法完成了它的职能，这就是分治法的基本思想！

==============================完============================