第4讲 分治算法的基本思想,二分搜索技术.ppt

第4讲分治法的基本思想与二分搜索技术,本讲内容：(1)算法的基础知识(2)分治法的基本思想(3)二分搜索技术,(5)有穷性：算法包含有限的操作步骤,算法的基础知识,算法具有以下5个特征：,(1)输入：有零个或多个输入量,(2)输出：算法至少产生一个输出量,(3)确定性：算法的每条指令都有确切的定义，无二义性,(4)有效性：算法的每一步骤都能有效地执行，并得到确定的结果,算法的概念：一个算法是对特定问题求解步骤的一种描述,算法的基础知识,沃思公式:数据结构+算法=程序,程序=算法+数据结构+程序设计方法+语言工具和环境,为什么要学习算法,算法是计算机科学的基础，是程序的基石,算法的基础知识,1.自然语言:简单易懂,但容易出现歧义2.流程图:直观形象,但算法复杂时,画图费时费力3.N-S图:直观形象,比流程图紧凑易画,但修改麻烦4.伪代码:用介于自然语言和计算机语言之间的文字和符号来描述算法,书写格式自由,易于修改,但不如流程图和N-S图直观5.计算机语言:用高级语言来描述算法,有助于算法的精确描述，但必须严格遵循语言的语法规则,算法的表示方法,算法的基础知识,一个好算法应具备的特性,(1)正确性：在合法的输入下，算法应实现预先规定的功能,(2)简明性(可读性)：算法应思路清晰，层次分明，容易理解，利于编码和调试,(3)高效性：算法应有效的利用存储空间，具有较高的时间效率,(4)最优性：算法的执行时间达到求解该类问题所需的时间下界,算法的基础知识,算法设计策略,(1)穷举法：从问题的所有可能解中找出符合条件的解,(2)迭代法：由初始条件通过循环迭代求出问题的解,(3)分治法：将原问题分解成若干互相独立的子问题,然后递归的求解这些子问题,最后将各子问题的解合并成原问题的解。,(4)贪心法：通过一系列的贪心选择来得到一个问题的解,(5)动态规划：将原问题分解成子问题(非独立),自底向上依次求解这些子问题,最后得出原问题的最优解。,(6)回溯法：以深度优先的方式搜索解空间树，可以系统地搜索一个问题的所有解或任一解,(7)分支-限界：以广度优先或以最小耗费优先的方式搜索问题的解空间树，通常是找出满足约束条件的一个解,分治法的基本思想,分治法的思想:分而治之。将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同，(如果子问题的规模仍然不够小，则再划分为k个子问题),然后递归的求解这些子问题，最后用适当的方法将各子问题的解合并成原问题的解。,原问题(规模为n),分治法的适用条件,分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决该问题可以分解为若干个规模较小的相同问题该问题所分解出的各个子问题是相互独立的利用分解出的子问题的解可以合并为该问题的解,分治法的基本思想,前提条件：有一组数已经按从小到大(或从大到小)排序目标：输入一个数x，在这组数查找是否有x,二分搜索的步骤：1、确定三个关键下标的初值：bott=0,top=8,mid=(bott+top)/2;,2、判断要找的数x是否等于amid,x=amid找到，结束xamid在amid+1atop之间继续查找xbott=mid+1;mid=(bott+top)/2;,a0a1a2a3a4a5a6a7a8,二分搜索算法,二分搜索实例:设在数组a中顺序放了以下9个元素：,检索x=9,9=a4,一次比较就成功,最好情况,a0a1a2a3a4a5a6a7a8,检索x=-15,-15a6,101a7,101=a8,4次比较,成功,检索x=8,8a1,8a2,8a3,4次比较,不成功,二分搜索算法,#include#defineN10intfind(inta,intx,intbott,inttop)；voidmain()inti,x,aN,result;printf(n输入数组a:n);for(i=0;iN;i+)scanf(%d,迭代法的程序代码,/符号常量定义，便于修改数组的大小,/函数调用,/函数声明,二分搜索算法,intfind(inta,intx,intbott,inttop)intmid;while(bott=top)mid=(bott+top)/2;if(x=amid)return(mid);elseif(xamid)top=mid-1;elsebott=mid+1;return(-1);,/计算中间位置的下标,/若x等于amid，表示找到,/x不等于amid的情况,/x小则查找