第四讲递归和分治策略 口通过例子理解递归的概念; 口掌握设计有效算法的分治策略; 口通过几个范例学习分治策略设计技巧; Merge sort Binary search Powering a number Fibonacci number Multiplication of two matrices VLSI layout Multiplication of two numbers Finding Minimum and Maximum Majority problen(多数问题)循环赛日程表
第四讲 递归和分治策略 2 通过例子理解递归的概念； 掌握设计有效算法的分治策略； 通过几个范例学习分治策略设计技巧； Merge sort Binary Search Powering a number Fibonacci number Multiplication of two matrices VLSI layout Multiplication of two numbers Finding Minimum and Maximum Majority problem (多数问题) 循环赛日程表
算法总体思想 对这k个子问题分别求解。如果子问题的规模仍然不够 ●小,则再划分为k个子问题,如此递归的进行下去,直 到问题规模足够小,很容易求出其解为止。 n T(n) T(n/2) T(n/2) T(n/2) T(n/2)
3 算法总体思想 ⚫ 将要求解的较大规模的问题分割成k个更小规模的子问 题。 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) = ◼ 对这k个子问题分别求解。如果子问题的规模仍然不够 小，则再划分为k个子问题，如此递归的进行下去，直 到问题规模足够小，很容易求出其解为止
算法总体思想 ■将求出的小规模的问题的解合并为一个更大规模的问 题的解,自底向上逐步求出原来问题的解。 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)
算法总体思想 ■将求出的小规模的问题的解合并为一个更大规模的问 题的解,自底向上逐步求出原来问题的解。 分治法的设计思想是,将一个难以直接解决的大问题 分割成一些规模较小的相同问题,以便各个击破, 分而治之
5 算法总体思想 ◼ 将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解。 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) 分治法的设计思想是，将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破， 分而治之
递归的概念 直接或间接地调用自身的算法称为递归算法。用函数 自身给出定义的函数称为递归函数。 ●由分治法产生的子问题往往是原问题的较小模式,这 就为使用递归技术提供了方便。在这种情况下,反复 应用分治手段,可以使子问题与原问题类型一致而其 规模却不断缩小,最终使子问题缩小到很容易直接求 出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟,经常同时应用在算法设 计之中,并由此产生许多高效算法。 下面来看几个实例
6 递归的概念 ⚫ 直接或间接地调用自身的算法称为递归算法。用函数 自身给出定义的函数称为递归函数。 ⚫ 由分治法产生的子问题往往是原问题的较小模式，这 就为使用递归技术提供了方便。在这种情况下，反复 应用分治手段，可以使子问题与原问题类型一致而其 规模却不断缩小，最终使子问题缩小到很容易直接求 出其解。这自然导致递归过程的产生。 ⚫ 分治与递归像一对孪生兄弟，经常同时应用在算法设 计之中，并由此产生许多高效算法。 下面来看几个实例
递归的例子 例1阶乘函数 阶乘函数可递归地定义为: n=0 m(n-1)!n>0 边界条件与递归方程是递归函数的二个要素,递归函 数只有具备了这两个要素,才能在有限次计算后得出 结果
7 递归的例子 例1 阶乘函数 阶乘函数可递归地定义为： 0 0 ( 1)! 1 ! = − = n n n n n 边界条件 递归方程 边界条件与递归方程是递归函数的二个要素，递归函 数只有具备了这两个要素，才能在有限次计算后得出 结果
递归的例子 例2排列问题 设计一个递归算法生成n个元素{r12…,rn}的全排列 设R={r2…,rn是要进行排列的n个元素,R=R-{} 集合X中元素的全排列记为perm(xX)。 r)perm(X表示在全排列perm(X)的每一个排列前加上前 缀得到的排列。R的全排列可归纳定义如下 当n=1时,perm(R=(),其中r是集合R中唯的元素 当n>1时,perm(R由(r1) perm(R1),(r2)perm(R2),…, (rn)perm(Rn构成
8 递归的例子 例2 排列问题 设计一个递归算法生成n个元素{r1 ,r2 ,…,rn }的全排列。 设R={r1 ,r2 ,…,rn }是要进行排列的n个元素，Ri=R-{ri }。 集合X中元素的全排列记为perm(X)。 (ri )perm(X)表示在全排列perm(X)的每一个排列前加上前 缀得到的排列。R的全排列可归纳定义如下： 当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素； 当n>1时，perm(R)由(r1 )perm(R1 )，(r2 )perm(R2 )，…， (rn )perm(Rn )构成
递归的例子 例3整数划分问题 将正整数n表示成一系列正整数之和:n=n1+n2+.+nk, 其中n12n2≥nk≥1,k≥1。 正整数n的这种表示称为正整数n的划分。求正整数n的不 同划分个数。 例如正整数6有如下11种不同的划分 6 4+2,4+1+1 3+3,3+2+1,3+1+1+1 2+2+2,2+2+1+1,2+1+1+1+1 1+1+1+1+1+1
9 递归的例子 例3 整数划分问题 将正整数n表示成一系列正整数之和：n=n1+n2+…+nk， 其中n1≥n2≥…≥nk≥1，k≥1。 正整数n的这种表示称为正整数n的划分。求正整数n的不 同划分个数。 例如正整数6有如下11种不同的划分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1
递归的例子 例3整数划分问题 面的几个例子中,问题本身都具有比较明显的递归关系,因 容夏用详归函数直接求解 本图考耀巴召数为数果#关 数记作q(nm)。可以建立qnm的如下递归关系。 (3)qn,n)=1+qn,n-1) 正整数n的划分由n1=n的划分和n1≤n-1的划分组成 (4)qn,m)=qn,m-1)+q(nm,m)n>m>1; 正整数n的最大加数n不大于m的划分由n1=m的划分和 n1≤m-1的划分组成
10 递归的例子 (2) q(n,m)=q(n,n),mn; 最大加数n1实际上不能大于n。因此，q(1,m)=1。 (1) q(n,1)=1,n1; 当最大加数n1不大于1时，任何正整数n只有一种划分形式， 即 n n = 1+1+ +1 (4) q(n,m)=q(n,m-1)+q(n-m,m),n>m>1; 正整数n的最大加数n1不大于m的划分由n1=m的划分和 n1≤m-1 的划分组成。 (3) q(n,n)=1+q(n,n-1); 正整数n的划分由n1=n的划分和n1≤n-1的划分组成。 例3 整数划分问题 前面的几个例子中，问题本身都具有比较明显的递归关系，因 而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关 系，因此考虑增加一个自变量：将最大加数n1不大于m的划分 个数记作q(n,m)。可以建立q(n,m)的如下递归关系
递归的例子 例3整数划分问题 q n m q(n, m) 1+q(n,n-1) 1=m q(n, m-1+gn-m, m) n>m>1 正整数n的划分数pn)=qnn)
11 递归的例子 = = = − + − + − = 1 1, 1 ( , 1) ( , ) 1 ( , 1) ( , ) 1 ( , ) n m n m n m n m q n m q n m m q n n q n n q n m 例3 整数划分问题 。 正整数n的划分数p(n)=q(n,n)