1、非数值计算 第一课时 第 4 单元 4.3 学习目标 运用合适的算法形成解决问题的方案。了解算法设计中的分治思想，并运用二分查找解决实际问题。体验递归算法，并结合具体问题开展编程实践。在数值计算中，我们更多考虑的是“数”，但计算应该是一个更广泛的领域。计算的对象可以是自然界和人类社会的一切事物。更确切地说，计算的对象可以是某些信息，如数据、文字、语言、图形、知识、事物的运动过程及思维过程。如果说数值计算主要探讨数学问题的话，那么非数值计算更多探讨 算法”问题。许多程序设计问题的解决，要依靠标准算法和现成的模型，更需要编程者开阔思路，提出一些新颖、巧妙的算法，或者设计出一些独特的数据结构来支撑和
2、实现算法。在解决非数值类计算问题时，一些基础的思维方式可以借鉴，如分治、递归、解析等。活动 统计查字典次数 查汉字、查单词、查成语等查字典的活动，早已成为我们学习生活的部分。假设一本字典大约500页，目标信息在第269页。请记录你翻页过程，和同学们比比，看谁翻的次数最少。次数 翻至页码 下一步决策 第一次 250 第二次 第三次 第四次 第五次 有的同学翻得特别快，他们用了什么方法呢？原来看似普通的翻字典，不仅是一门技术，更是一种能力，是算法思想的体现。分治策略 分治的设计思想，是将个难以直接解决的大问题，分割成些较小的同类问题，各个击破，最终达到解决问题的目的。二分查找实际上一就是分治策略的
3、种典型运用。A B C D E F G H I 需要解决的问题 二分查找 二分查找又叫折半查找，该方法主要将数列有序排列，采用跳跃式的方式查找数据。以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。每一次比较后可以将查找区域缩小一半。第一次分割 第二次分割 第三次分割 需要解决的问题 在翻页过程中借助两个书签，划定目标所属范围，然后翻到两个书签的中间位置。每次目标区域都更新为原来的“二分之一”，当数据范围缩小到只有1个数的时候肯定能得到问题的解。1000以内的页码，最多翻10次肯定能找到解。目标信息在第269页。第0页
4、第1000页 第0页 第500页 第250页 第500页 第250页 第375页 第250页 第312页 有了翻字典的实际操作经验，我们来尝试完善下面的二分查找程序。x=int(input(“请输入要查找的数据：）step=0 记录查找次数 flagl=l 目标区域左边界 flag2=1000 目标区域右边界 while(flag1x:flag2=mid-1#有边界前移 elif midflag2 or x1)区间数据范围小于1则结束循环 mid=（flag1+flag2)/2 中间值 step=step+1 查找次数加1 if midx:flag2=mid#有边界前移 elif midx:f
5、lag1=mid#左边界后移 else:break 恰好找到目标数据，退出循环 print(“查询次数为：”，step)#输出次数 else:print(“查询超出范围。”)random包的randint()函数可以生成某个范围内的随机数。活动 应用“二分查找”，找出1-1000之间的某个数 import random x=random.randint(1,1000)while 0 x1000:y=int(input(请输入这个数：)if xy:print(小了)else:print(就是,x)breakrandom包可以称为随机包，它有如下函数：random.randint(1,10)#产生
6、 1 到 10 的一个整数型随机数 random.random()#产生 0 到 1 之间的随机浮点数 random.uniform(1.1,5.4)#产生 1.1 到 5.4 之间的随机浮点数，区间可以不是整数 random.choice(tomorrow)#从序列中随机选取一个元素 random.randrange(1,100,2)#生成从1到100的间隔为2的随机整数 练一练 尝试用二分法求解x3-x2+x-1=0 操作提示：令f(x)=x3-x2+x-1，针对有解的单调区间(a,b)，取x。=（a+b)/2:若f(a)*f(x。)0，则f(x)在(a,x。)内有解；若f(x。）*f（b
7、)0，则f(x)在(x。,b)内有解；若|f(x。)|10-6，则x。为方程的解。巩固提升 1二分查找又叫_，该方法主要将数列_排列，采用_的方式查找数据。二分查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。2递增数列用二分法查找时，先以_位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列_为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩小一半。巩固提升 3.二分法查找的前提条件是被查找的数据_的。4.结合分治策略，递归也可以用_三个字概况。分:将原有问题_成K个子问题;治:对这K个子问题_。如果子问题的规模仍然不够小，则将其再分解为K个子问题，如此
8、进行下去，直到问题足够小时，就很容易求出子问题的解。合:将求出的小规模问题的解_为一个更大规模问题的解，自下而上逐步求出原问题的解。巩固提升 5.二分查找又称折半查找，是一种应用于有序数列的高效查找算法。下列数列中适合二分查找算法的是()A.85 78 59 53 19 18 B.67 62 68 41 1 7 C.11 99 4 25 3 39 D.43 71 78 81 6 55 课堂小结 非数值计算 分治策略 二分查找 将一个难以直接解决的大问题，分割成一些较小的同类问题，各个击破。二分查找又叫折半查找，该方法主要将数列有序排列，采用跳跃式的方式查找数据。二分法查找的前提条件是被查找的数据必须是有序的。分：原问题分解成若干子问题 治：对子问题分别求解 合：子问题的解合并成原问题的解 谢谢观看！