文档介绍：该【递归与分治策略课件】是由【zhangkuan14314】上传分享，文档一共【38】页，该文档可以免费在线阅读，需要了解更多关于【递归与分治策略课件】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第2章递递归归与分治治策略
学****要点点:
理解递归归的概念念。
掌握设计计有效算算法的分分治策略略。
通过下面面的范例例学****分分治策略略设计技技巧。
(1)二二分搜索索技术;;
(2)大大整数乘乘法;
(3)棋棋盘覆盖盖;
(4)线线性时间间选择;;
将要求解解的较大大规模的的问题分分割成k个更小小规模的的子问题题。
算法总总体思思想
n
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n)
=
对这k个子子问题题分别别求解解。如如果子子问题题的规规模仍仍然不不够小小,则则再划划分为为k个个子问问题,,如此此递归归的进进行下下去,,直到到问题题规模模足够够小,,很容容易求求出其其解为为止。。
算法总总体思思想
对这k个子子问题题分别别求解解。如如果子子问题题的规规模仍仍然不不够小小,则则再划划分为为k个个子问问题,,如此此递归归的进进行下下去,,直到到问题题规模模足够够小,,很容容易求求出其其解为为止。。
n
T(n)
=
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
将求出出的小小规模模的问问题的的解合合并为为一个个更大大规模模的问问题的的解,,自底底向上上逐步步求出出原来来问题题的解解。
算法总总体思思想
将求出出的小小规模模的问问题的的解合合并为为一个个更大大规模模的问问题的的解,,自底底向上上逐步步求出出原来来问题题的解解。
n
T(n)
=
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
算法总总体思思想
将求出出的小小规模模的问问题的的解合合并为为一个个更大大规模模的问问题的的解,,自底底向上上逐步步求出出原来来问题题的解解。
n
T(n)
=
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
分治法法的设设计思思想是是,将将一个个难以以直接接解决决的大大问题题,
分割成成一些些规模模较小小的相相同问问题,,以便便各个个击破破,
分而治治之。。
具体步步骤::
1、将将源问问题分分解为为有限限的若若干个个子问问题
2、解解决子子问题题
3、复复合过过程

直接或或间接接地调调用自自身的的算法法称为为递归算算法。用函函数自自身给给出定定义的的函数数称为为递归函函数。
由分治治法产产生的的子问问题往往往是是原问问题的的较小小模式式,这这就为为使用用递归归技术术提供供了方方便。。在这这种情情况下下,反反复应应用分分治手手段,,可以以使子子问题题与原原问题题类型型一致致而其其规模模却不不断缩缩小,,最终终使子子问题题缩小小到很很容易易直接接求出出其解解。这这自然然导致致递归归过程程的产产生。。
分治与与递归归像一一对孪孪生兄兄弟,,经常常同时时应用用在算算法设设计之之中,,并由由此产产生许许多高高效算算法。。
下面来来看几几个实实例。。

例1阶阶乘函函数
阶乘函函数可可递归归地定定义为为:
边界条条件
递归方方程
边界条条件与与递归归方程程是递递归函函数的的二个个要素素,递递归函函数只只有具具备了了这两两个要要素,,才能能在有有限次次计算算后得得出结结果。。
算法如如下::
intfactorial(intn)
{
if(n==0)return1;
returnn*factorial(n-1);
}

例2Fibonacci数列列
无穷数数列1,1,2,3,5,8,13,,21,34,,55,………,,称为为Fibonacci数数列。。它可可以递递归地地定义义为::
边界条条件
递归方方程
第n个个Fibonacci数数可递递归地地计算算如下下:
intfibonacci(intn)
{
if(n<=1)return1;
returnfibonacci(n-1)+fibonacci(n-2);
}