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

1、新课导入猜价格新课导入猜价格用分治算法提高查找效率第一课时用分治算法提高查找效率第一课时分治算法基本概念 在计算机科学中，分治法是一种很重要的算法。核心思想是“分而治之”，可以逐步缩小问题的求解范围，从而加快问题的求解速度；是很多高效算法的基础。通常被称作二分查找算法，也叫作折半查找算法。分治算法基本概念 在计算机科学中，分治法是一项目活动一、分析分治算法查找的原理和思想二、分解分治算法查找的过程三、构建分治算法查找的流程图四、分治算法的初步程序实现项目活动一、分析分治算法查找的原理和思想一、分析分治算法查找的原理和思想（1）分治查找中被查找的数据必须是有序的。（2）首先将查找的数与有序数列表

2、内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，根据有序性，就可确定应该在数组的前半部分还是后半部分继续查找。（3）在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。一、分析分治算法查找的原理和思想（1）分治查找中被查找的数据二、分解分治算法查找的过程1.列表序号是从0开始。2.弃用0号元素，用a表示查找范围的起始位置下标，b表示终止位置下标，m表示中间位置元素，所以设置a初值为1,b的初值为len(s)-1，m=(a+b)/2abm二、分解分治算法查找的过程1.列表序号是从0开始。abmab二、分解分治算法查找的过程m第一种情况，要找的值在后半部分，以key=47为例a

3、=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第一种情况，要找的值在后半部ab二、分解分治算法查找的过程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 =9Smkeyb=m-1 =4第一次a=1b=4m=(a+b)/2 =2Smkeya=m+1 =3第二次a=3b=4m=(a

4、+b)/2 =3Sm=key第三次ab二、分解分治算法查找的过程m画一画：画出key=17的查二、分解分治算法查找的过程if key=sm: b=m-1 else: a=m+1a和b的取值范围：重复查找的条件：while a=b:二、分解分治算法查找的过程if key=sm:a和b的三、构建分治算法查找的流程图三、构建分治算法查找的流程图三、构建分治算法查找的流程图开始s= -99,1,5,7,12,15,18,21,27,29,31a=1 b=len(s)-1ab输入key的值:key=input()计算m的值m=(a+b)/2Key=smKeysmb=m-1a=m+1结束输出key位于列表

5、内NNYYNY三、构建分治算法查找的流程图开始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五、评价总结分治查找中被查找的数据必须是有序的。分治查找中每次循环可以将规模缩小一