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