初中信息技术 用分治算法提高查找效率教学课件设计.ppt

新课导入,猜价格,新课导入猜价格,用分治算法提高查找效率,第一课时,用分治算法提高查找效率第一课时,分治算法基本概念,在计算机科学中，分治法是一种很重要的算法。核心思想是“分而治之”，可以逐步缩小问题的求解范围，从而加快问题的求解速度；是很多高效算法的基础。通常被称作二分查找算法，也叫作折半查找算法。,分治算法基本概念 在计算机科学中，分治法是一,项目活动,一、分析分治算法查找的原理和思想二、分解分治算法查找的过程三、构建分治算法查找的流程图四、分治算法的初步程序实现,项目活动一、分析分治算法查找的原理和思想,一、分析分治算法查找的原理和思想,（1）分治查找中被查找的数据必须是有序的。（2）首先将查找的数与有序数列表内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，根据有序性，就可确定应该在数组的前半部分还是后半部分继续查找。（3）在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。,一、分析分治算法查找的原理和思想（1）分治查找中被查找的数据,二、分解分治算法查找的过程,1.列表序号是从0开始。2.弃用0号元素，用a表示查找范围的起始位置下标，b表示终止位置下标，m表示中间位置元素，所以设置a初值为1,b的初值为len(s)-1，m=(a+b)/2,a,b,m,二、分解分治算法查找的过程1.列表序号是从0开始。abm,a,b,二、分解分治算法查找的过程,m,第一种情况，要找的值在后半部分，以key=47为例,a=1b=10m=(a+b)/2 =5Smkeya=m+1 =6,第一次,a=6b=10m=(a+b)/2 =8Smkeya=m+1 =9,第二次,a=9b=10m=(a+b)/2 =9Sm=key,第三次,ab二、分解分治算法查找的过程m第一种情况，要找的值在后半部,a,b,二、分解分治算法查找的过程,m,当key=51呢,a=1b=10m=(a+b)/2 =5Smkeya=m+1 =6,第一次,a=6b=10m=(a+b)/2 =8Smkeya=m+1 =9,第二次,a=9b=10m=(a+b)/2 =9Smkeya=m+1 =10,第三次,a=10b=10m=(a+b)/2 =10Sm=key,第四次,ab二、分解分治算法查找的过程m当key=51呢a=1第a=,a,b,二、分解分治算法查找的过程,m,画一画：画出key=17的查找示意图,a=1b=10m=(a+b)/2 =5Smkeyb=m-1 =4,第一次,a=1b=4m=(a+b)/2 =2Smkeya=m+1 =3,第二次,a=3b=4m=(a+b)/2 =3Sm=key,第三次,ab二、分解分治算法查找的过程m画一画：画出key=17的查,二、分解分治算法查找的过程,if key=sm: b=m-1 else: a=m+1,a和b的取值范围：,重复查找的条件：,while a=b:,二、分解分治算法查找的过程if key=sm:a和b的,三、构建分治算法查找的流程图,三、构建分治算法查找的流程图,三、构建分治算法查找的流程图,开始,s= -99,1,5,7,12,15,18,21,27,29,31,a=1 b=len(s)-1,ab,输入key的值:key=input(),计算m的值m=(a+b)/2,Key=sm,Keysm,b=m-1,a=m+1,结束,输出key位于列表内,N,N,Y,Y,N,Y,三、构建分治算法查找的流程图开始s= -99,1,5,7,四、分治算法的初步程序实现,1.打开Python2.FlieNew File3.编辑输入,四、分治算法的初步程序实现1.打开Python,四、分治算法的初步程序实现,s=-99,1,5,7,12,15,18,21,27,29,31key=int(input(key=)a=1b=len(s)-1while a=b: m=(a+b)/2 print(m=,m) if sm=key: print(key,位于列表中) break elif key=sm: b=m-1 else: a=m+1,四、分治算法的初步程序实现s=-99,1,5,7,12,1,五、评价总结,分治查找中被查找的数据必须是有序的。,分治查找中每次循环可以将规模缩小一半,五、评价总结分治查找中被查找的数据必须是有序的。分治查找中每,六、作业,设计一个能用分治查找算法思想解决的实际问题。,六、作业 设计一个能用分治查找算法思想解决的实,