分治算法讲解.doc

《分治算法讲解.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、分治算法一：基本概念（分而治之）分治就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。比如：二分查找，归并排序，快速排序，树的遍历等等任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一

2、个规模较大的问题，有时是相当困难的。二：基本思想分治设计思想：将一个大的问题，分解成一个个小的，相同类型的问题，然后逐个击破各个小问题，最后将小问题逐步合并，得到最终的解。（可能会用到递归，大问题里包含小问题，找到规律然后解决）分治基本策略：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。三：分治使用情况1)该问题的规模缩小到一定的程度就可以容易地解决2)该问题可

3、以分解为相同类型的小问题（前提）3)利用该问题分解出的子问题的解可以合并为该问题的解；（关键）4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。四：基本步骤（1）划分：把问题的实例划分成子问题（2）求解：若是子问题比较简单，就直接解决，否则递归求解子问题（3）合并：合并子问题的解得到原问题的解课前引导：一：分段函数例如：高中数学中的分段函数也是类似分

4、治思想的体现，如看图求y关于x的表达式。一个分段函数，反映的是x与y的关系，简单来说，就是在R的范围内将y的表达式表示出来，那么这时候利用分治的思想，将R区间划分为小区间，然后分别求出各个小区间的表达式，最后合并起来，完成y关于x的表达式的求解二：大整数乘法123345678*3=370037034在这里我们可以这样写：123*3=369   345*3=1035   678*3=2034         组合在一起是    36910352034。对比发现，当使用千进制的时候结果变成了370037034首先他满足：第一条

5、件：分解到一定小规模的时候可以解决  第二条件：每个小规模都具有最佳子结构（在变量范围内，可以用来表示）  第三条件：每个小问题可以通过合并在一起形成大问题的解  第四条件：每个小问题相互独立专题一：分治算法之二分查找思考题：找假币：有一堆个数为32的硬币，和一个天平，已知其中有一个假币，且假币比真硬币轻，找出这个假币1.普通方法：两两比较，轻的那个是假币，最多比较16次2.二分法：将硬币分为两份，假币在轻的那份中，然后继续分，直到找出假币，最多用5次哪种方法好？课题：二分查找（折半查找）知识目标：理解二分查找算法的概念以

6、及执行过程。重点：掌握二分查找算法的常规写法以及递归写法。1.边界错误造成的问题2.死循环3.溢出I.算法介绍：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。II.思路分析：二分查找的基本思想是：（1）先确定一组顺序排列的数据存储到数组中，输入要查找的数据（2）将数组元素的中值与查找的数据相比较，如果两者相等，则子函数返回相应的结果后终止；（3）否则利用中间位置缩小数据查找的范围。如果中间位置的数组元素大于

7、查找数值，则进一步查找中值之前的数组元素，否则进一步查找中值之后的数组元素。（4）重复上述过程，直到在数组中找到相同的数字。（5）若在数组中找不到这个数据，则显示查找不成功III.算法框架：按照分治算法三步骤，将二分算法作如下介绍：（1）二分算法代码设计模式://arr[]表示要进行二分查找的顺序排列对象数组，low表示数组下标的最小值，high表示数组下表的最大值，key表示要查找的元素interfen(intarr[],intlow,inthigh,intkey){如果数组下标的最小值大于最大值则返回结果为-1至主函数

8、；//表明在数组中不存在要查找的元素确定数组的中间位置mid若查找的元素等于数组的中间元素，则进行相应的步骤④若查找的元素大于数组（指定范围内）的中间元素则将查找范围缩小至数组（指定范围内）中间元素右边；⑤若查找的元素小于数组指定范围内的中间元素则将查找范围缩小至数组（指定范围内）中间元素左边；}例题1