数据结构与算法应用(软件设计师备考笔记).docx

目录第十二章.数据结构及算法应用第一节.分治法第二节.回溯法第三节.贪心法第四节.动态规划法第五节.哈夫曼编码第十二章.数据结构及算法应用第一节.分治法其基本思想是把一个比较大的、复杂的问题，拆分成一些比较小的子问题，如快速排序算法基本原则1. 该问题的规模缩小到一定的程度就可以容易地解决2. 该问题可以分解为若干个规模较小的相同问题3. 利用该问题分解出的子问题的解可以合并为该问题的解4. 该问题所分解出的各个子问题是相互独立的分治法递归技术递归，就是在运行的过程中调用自己图注：该算法的目的是求这样一个数列，由零开始的，每一个数都等于前面两个数之和的数列，该算法操作即：将 F(3)转换为 F(1)和 F(2)之和，F(4)转换为 F(2)和 F(3)之和 这样可以使所有的 F(n)都能化为 F(1)和 F(0)的和分治法二分法查找第二节.回溯法基本原则概念：回溯法是一种选优搜索法，按选优条件向前搜索，以达成目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新进行选择。这种走不通就退回一步再继续往下走的技术就是回溯法第三节.贪心法基本原则1. 概念：总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每一步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解经典实例背包问题图注：有三个物品(每种物品仅存一个)，其容量分别为：20，30，40；其价格分别为：140，180，200；而背包可容纳的总量为 70，我们希望背包中能容纳尽可能多的物品，其容纳的物品价值最高，而贪心法则会根据单位容量价值最高的原则优先将这个物品进行容纳，如物品 1 的每 10 个容量其价值为 70，物品 2 则为 60，物品 3 则为 50；因此，若采用贪心法，其将会优先放入物品 1到背包中，然后放入物品 2，此时空间只剩下 20，无法装下物品 3，因此，方案到此结束，采用该方法得到了总价 320 的物品，但这显然不是最优解，我们将物品 3 和物品 1 装入背包，得到的物品总价值为 340第四节.动态规划法1. 概念：在求解问题时，对于每一步决策，列出各种可能的局部解，再根据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解，在动态规划法中，基本上都要用到查表这一步骤第五节.哈夫曼编码1. 概念：哈夫曼编码的思想是，在传输信息时，将频率高的数据用较少的二进制进行表示，将频率低的数据用较多的二进制进行表示2. 具体实现：首先我们必须知道每个字母或符号出现的频率。然后将其频率由小到大进行排序，然后我们将构造一棵二叉树，总体思路是从底向上进行构建，构造的规则是：将最小的两个结点作为底结点，并计算出二者的和，将和作为一个权代替两个结点并重新进行排序，在排序后的结点组合中挑选出最小的两个，若这两个结点中包含了之前已经构建的结点，则在此基础上进行并行构建，若不包含，则另外构建一棵二叉树，一直重复进行该操作，需要特别注意的是若两个结点求和后的权值和与某一未构建的结点值相等，则在排序时将求和权值置于该重复结点之后，直至所有结点用完例如：这样的几个字符，其构造的二叉树为：因此：a 的哈夫曼编码为：0；b 为：100；e 为 101；d 为 110；c 为 1112.文档的压缩比计算：将利用哈夫曼编码得到的字符的二进制数中占据位数最大的提取出来令其为 a，然后以位的个数数为乘数，每个字符的二进制数所占位数乘以其概率再依次相加令其为 b，其文档的压缩比就是：(a-b)/a文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览 53999 人正在系统学习中