清华大学出版社：《算法设计与分析》课程教学资源（PPT课件讲稿）第2章 递归与分治策略

清华大学出版社 TSINGHUA UNIVERSITY PRESS 第2章递归与分治策略

第2章 递归与分治策略

清华大学出版社 TSINGHUA UNIVERSITY PRESS 算法总体思想 ·对这k个子问题分别求解。如果子问题的规模仍然不够 小,则再划分为k个子问题,如此递归的进行下去,直 到问题规模足够小,很容易求出其解为止。 T(n) T(n/2) Tn/2) T(n/2) Tn/2)

• 将要求解的较大规模的问题分割成k个更小规模的子问 题。 算法总体思想 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) = • 对这k个子问题分别求解。如果子问题的规模仍然不够 小，则再划分为k个子问题，如此递归的进行下去，直 到问题规模足够小，很容易求出其解为止

清华大学出版社 TSINGHUA UNIVERSITY PRESS 算法总体思想 将求岀的小规模的问题的解合并为一个更大规模的问 题的解,自底向上逐步求出原来问题的解。 T(n) T424和2424)TAA4如2)T4(4厂(4)T白4(a4(a4Ja

算法总体思想 • 对这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) • 将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解

清华大学出版社 TSINGHUA UNIVERSITY PRESS 算法总体思想 将求岀的小规模的问题的解合并为一个更大规模的问 题的解,自底向上逐步求出原来问题的解。 T(n) T4J44J4)T4(44(A4)T44和44)T44r4ra

算法总体思想 • 将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解。 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)

清华大学出版社 TSINGHUA UNIVERSITY PRESS 算法总体思想 将求岀的小规模的问题的解合并为一个更大规模的问 题的解,自底向上逐步求出原来问题的解。 分治法的设计思想是,将一个难以直接解决的大问题, 分割成一些规模较小的相同问题,以便各个击破, 分而治之。 凡治众如治寡,分数是也 孙小子兵法

算法总体思想 • 将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解。 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) 分治法的设计思想是，将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破， 分而治之。 凡治众如治寡，分数是也。 ----孙子兵法

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

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

清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1递归的概念 例1阶乘函数 阶乘函数可递归地定义为 边界条件 n=0 ! n(n-1)!n>0 递归方程 边界条件与递归方程是递归函数的二个要素,递归函 数只有具备了这两个要素,才能在有限次计算后得出 结果

2.1 递归的概念 例1 阶乘函数 阶乘函数可递归地定义为： 0 0 ( 1)! 1 !  =    − = n n n n n 边界条件 递归方程 边界条件与递归方程是递归函数的二个要素，递归函 数只有具备了这两个要素，才能在有限次计算后得出 结果

清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1递归的概念 例2Fib nacc l 数列 无穷数列1,1,2,3,5,8,13,21,34,55 被称为 fibonacci数列。它可以递归地定义为: 边界条件 F(n) n=1 F(n-1)+F(n-2)n> 递归方程 第n个 Fibonaco数可递归地计算如下: public static int fibonacci (int n) if ( n<= 1)return 1; return fibonacci(n-1)+fibonacci(n-2)

2.1 递归的概念 例2 Fibonacci数列 无穷数列1，1，2，3，5，8，13，21，34，55，…， 被称为Fibonacci数列。它可以递归地定义为： 边界条件 1 递归方程 1 0 ( 1) ( 2) 1 1 ( )  = =      − + − = n n n F n F n F n 第n个Fibonacci数可递归地计算如下： public static int fibonacci(int n) { if (n <= 1) return 1; return fibonacci(n-1)+fibonacci(n-2); }

清华大学出版社 TSINGHUA UNIVERSITY PRESS A(1,0)=2 m≥0 A(n,O=n+ ≥2 1.n 1),m2 1.m2

          = − − = + = = , 1 2 0 ( , ) ( ( 1, ), 1) ( ,0) 2 (0, ) 1 (1,0) 2 n m n m A n m A A n m m A n n A m A

清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1递归的概念 例3 Ackerman函数 当一个函数及它的一个变量是由函数自身定义时,称这 个函数是双递归函数 Ackerman函数A(n,m)定义如下: A(1,0)=2 m≥0 A(n,O=n+ ≥2 (n,m)=A(A(n-1,m),m-1)n,m≥1

2.1 递归的概念 例3 Ackerman函数 当一个函数及它的一个变量是由函数自身定义时，称这 个函数是双递归函数。 Ackerman函数A(n，m)定义如下：           = − − = + = = , 1 2 0 ( , ) ( ( 1, ), 1) ( ,0) 2 (0, ) 1 (1,0) 2 n m n m A n m A A n m m A n n A m A