白东程子末军 HANDONG UNIVERSITY OF TECIINOLOGY 计算机算法设计与分析 Design and Analysis of Computer Algorithms 第二章递归与分治策哈
计算机算法设计与分析 Design and Analysis of Computer Algorithms 第二章 递归与分治策略
山东程子太军 学习要点： SHANDONG UNIVERSITY OF TECHNOLOOY 3会诗3会合3会学3华A多器察 ·理解递归的概念。 掌握设计有效算法的分治策略。 通过下面的范例学习分治策略设计技巧。 ()二分搜索技术； (2)大整数乘法； ● (3)Strassen矩阵乘法； (4)棋盘覆盖； (5)合并排序和快速排序； ● (6) 线性时间选择； ● (7) 最接近，点对问题； (8) 循环赛日程表。 2025年4月3日 2
2025年4月3日 2 • 理解递归的概念。 • 掌握设计有效算法的分治策略。 • 通过下面的范例学习分治策略设计技巧。 • （1）二分搜索技术； • （2）大整数乘法； • （3）Strassen矩阵乘法； • （4）棋盘覆盖； • （5）合并排序和快速排序； • （6）线性时间选择； • （7）最接近点对问题； • （8）循环赛日程表。 学习要点:
归东程子末军 算法总体思想 SHANDONG UNIVERSITY OF TECHNOLOGY 器会空点会器空会的是 ●将要求解的较大规模的问题分割成k个更小规模的子问题。 对这k个子问题分别求解。如果子问题的规模仍然不够小， 则再划分为k个子问题，如此递归的进行下去，直到问题规 模足够小，很容易求出其解为止。 T(n) T(n/2) T(n/2) T(n/2) T(n/2) 2025年4月3日 3
2025年4月3日 3 ⚫ 将要求解的较大规模的问题分割成k个更小规模的子问题。 算法总体思想 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) = ⚫ 对这k个子问题分别求解。如果子问题的规模仍然不够小， 则再划分为k个子问题，如此递归的进行下去，直到问题规 模足够小，很容易求出其解为止
算法总体思想 白东程子太军 SHANDONG UNIVERSITY OF TECINOLOGY 3会清会空会察 ●将求出的小规模的问题的解合并为一个更大规 模的问题的解，自底向上逐步求出原来问题的 解。 T(n) (n/4(n/4(n/4T(n/4)T(n/4(n/4T(n/4T(n/4)T(n/4T(n/4T(n/4(n/4)T(n/4T(n/4(n/4(n/4) 2025年4月3日
2025年4月3日 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)
归本程子太军 SHANDONG UNIVERSITY OF TECHNOLOGY 会合会点会器空深会是会品 分治法的设计思想是，将一个难以直接解决的大 问题，分割成一些规模较小的相同问题，以便各 个击破，分而治之。 凡治众如治寡，分数是也。 孙子兵法 2025年4月3日
2025年4月3日 5 分治法的设计思想是，将一个难以直接解决的大 问题，分割成一些规模较小的相同问题，以便各 个击破，分而治之。 凡治众如治寡，分数是也。 -孙子兵法
山东程上太军程 提纲 SHANDONG UNIVERSITY OF TECHNOLOOY 华会会学3会华深会 一、递归的概念 二、分治法的基本思想 三、分治法的应用 2025年4月3日 6
2025年4月3日 6 提纲 一、递归的概念 二、分治法的基本思想 三、分治法的应用
G 归东置子太军 提纲 SHANDONG UNIVERSITY OF TECHNOLOGY 一、 递归的概念 二、分治法的基本思想 三、分治法的应用 2025年4月3日
2025年4月3日 7 提纲 一、递归的概念 二、分治法的基本思想 三、分治法的应用
白本程子太程 递归的概念 SHANDONG UNIVERSITY OF TECINOLOGY 器会清的合实点会3冷华品品条 直接或间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。 ● 由分治法产生的子问题往往是原问题的较小 模式，这就为使用递归技术提供了方便。在 这种情况下，反复应用分治手段，可以使子 问题与原问题类型一致而其规模却不断缩小， 最终使子问题缩小到很容易直接求出其解。 这自然导致递归过程的产生。 ● 分治与递归像一对孪生兄弟，经常同时应用 在算法设计之中，并由此产生许多高效算法。 下面来看几个实例。 2025年4月3日 8
2025年4月3日 8 递归的概念 ⚫ 直接或间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。 ⚫ 由分治法产生的子问题往往是原问题的较小 模式，这就为使用递归技术提供了方便。在 这种情况下，反复应用分治手段，可以使子 问题与原问题类型一致而其规模却不断缩小， 最终使子问题缩小到很容易直接求出其解。 这自然导致递归过程的产生。 ⚫ 分治与递归像一对孪生兄弟，经常同时应用 在算法设计之中，并由此产生许多高效算法。 下面来看几个实例
归本程子末军 一、递归的概念 SHANDONG UNIVERSITY OF TECHNOLOGY 例1阶乘函数 边界条件 n= n=0 n(n-1)川 n>0 递归方程 ●边界条件与递归方程是递归 函数的二个要素。递归函数只 int factorial(int n) 有具备了这两个要素，才能在 if (n==0)return 1; 有限次计算后得出结果。 return n*factorial(n-1); 2025年4月3日 9
2025年4月3日 9 一、递归的概念 例1 阶乘函数 0 0 ( 1)! 1 ! = − = n n n n n 边界条件 递归方程 int factorial(int n) { if (n==0) return 1; return n*factorial(n-1); } ⚫边界条件与递归方程是 递归 函数的二个要素。递归函数只 有具备了这两个要素，才能在 有限次计算后得出结果
白东程子太军 一、递归的概念 HANDONG UNIVERSITY OF TECINOLOGY 华会诗3会学S会深公器 ●例2 Fibonacci数列 无穷数列1,1,2,3,5,8,13,21,34,55，.，称为 Fibonaccia数列。递归定义为： 边界条件 1 n=0 F(n)= n=1 F(n-1)+F(n-2)n>=2 递归方程 int fibonacci(int n) if (n <1)return 1; return fibonacci(n-1)+fibonacci(n-2); 2025年4月3日 10
2025年4月3日 10 一、递归的概念 ⚫ 例2 Fibonacci数列 无穷数列1，1，2，3，5，8，13，21，34，55，.，称为 Fibonacci数列。递归定义为： int fibonacci(int n) { if (n <= 1) return 1; return fibonacci(n-1)+fibonacci(n-2); } 边界条件 2 递归方程 1 0 ( 1) ( 2) 1 1 ( ) = = = − + − = n n n F n F n F n