第十二章.数据结构及算法应用_数据结构解决问题的实例

---

第十二章.数据结构及算法应用

数据结构及算法应用前言
数据结构与算法基础主要是应对上午题。数据结构及算法应用主要是应对下午题。下午题主要是五个方向的内容。数据流图、数据库、UML、数据结构与算法、面向对象程序设计。前几道题我们往往要求把基本的一些方法和知识掌握，然后整道题拿一个比较高的分数。而对于算法这一道题，我们的要求是稳拿其中的部分的分数。那么至于具体的程序填空的一些复杂的业务逻辑不要求花过多的时间去研究。因为算法灵活度比较高，同样一个算法，它的实现方式可以多种多样，程序会有变化。所以不容易拿高分。但是要把算法题当中的一些填空题把它填出来，问题倒不是很大。所以我们主要要把边缘性的一些这个空把它填出来，这样子一般能够拿到这道题的 6 到 8 分，这已经能够达到我们的目的了。

---

第一节.分治法

分治法顾名思义就是分而治之的方法。
基本思想
对于一个规模为 n 的问题，若该问题可以容易地解决 ( 比如说规模 n 较小 ) 则直 接解决 ; 否则将其分解为 k 个规模较小的子问题，这些子问题互相独立且与原问 题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

如何拆分问题呢？
因为拆出来的这种问题要求和原来问题是同样的结构的，只是复杂度小一些、规模小一些的问题，拆分出来的子问题又可以用同样的方式进一步的拆分。那么既然如此，那我们解决这个问题的时候所采用的函数是能够用同样的函数去解决问题的。所以在分治法当中往往会要用到递归的这种技术来解决问题。

分支法执行步骤
先做分解问题，然后解决一系列的小的问题，最后合并小的问题的解，最终就得到原来初始问题的解决方案。
总结⭐分解⭐解决⭐合并

分治法所解决的问题的基本要求
⭐该问题的规模缩小到一定的程度就可以容易地解决
⭐该问题可以分解为若干个规模较小的相同问题
⭐利用该问题分解出的子问题的解可以合并为该问题的解
⭐该问题所分解出的各个子问题是相互独立的

---

递归技术

递归，就是在运行的过程中调用自己。

为什么要考虑调用自己来解决问题呢？
因为你要解决的这个复杂问题可以拆分为多个同类型的子问题。既然这个函数是用来解决这个复杂的问题，那同类型的子问题应该也能够用这个函数解决。

举例斐波那契数列来说明递归是如何运作的
图中的函数F就是一个递归的函数。如果n=5时，执行F(5)就返回F(n-1)+F(n-2)，这就实现了分治法的拆分。
通过下方的递归搜索树可以看到分治法的步骤 分解（$F(n)=F(n-1)+F(n-2)$），解决（最终分解的F(0)和F(1)的值都知道），合并（从根子节点开始进行合并直到要求的结果为止）。

---

二分法查找

二分查找其实是利用分治法的思想来进行操作。其实只运用到分解和解决。