资源简介

(共22张PPT)
高中信息技术 必修1 数据与计算
4.3 非数值计算
第一课时 二分查找
学习目标
01
02
了解算法中的分治思想；
掌握运用二分查找解决实际问题；
03
在python中用二分法解决问题。
4.3 非数值计算
游戏导入
【寻找假币游戏】
——在100个硬币中找出伪币
有100个硬币，其中有1个伪币，它除了质量比真币轻一点之外，没有别的区别，如何通过天平快速找到这个伪币。
请同学们思考并讨论“如何快速找出假币”？
游戏导入
【寻找假币游戏】
——在100个硬币中找出伪币
以重量判断为例 重量轻的是假币
首先是将100个硬币分成两个50，使用天平进行衡量，然后确定伪币在比较轻的那50个里，接着再将50分成2个25，将25分成两个12和1个1，将12分成2个6，将6分成2个3，将3分成3个1，这样6次就可以找到伪币，比50次少很多。
游戏导入
【寻找假币游戏】
——在100个硬币中找出伪币
以重量判断为例 重量轻的是假币
首先是将100个硬币分成两个50，使用天平进行衡量，然后确定伪币在比较轻的那50个里，接着再将50分成2个25，将25分成两个12和1个1，将12分成2个6，将6分成2个3，将3分成3个1，这样6次就可以找到伪币，比50次少很多。
算法：分治
项目内容
本节我们将围绕“生活中的算法”项目，尝试用“算法的眼睛”看待生活，用“算法的思维”去解决实际问题。
项目任务
任务一：巧翻字典
任务二：玩转“汉诺塔”游戏
本节任务
任务：巧翻字典 活动：统计查字典次数
查汉字、查单词、查成语等查字典的活动，早已成为我们学习生活的部分。假设一本字典大约1000页，目标信息在第328页。请记录你翻页过程，和同学们比比，看谁翻的次数最少。
次数 翻至页码 下一步决策
第一次
第二次
第三次
第四次
第五次
……
有的同学翻得特别快，他们用了什么方法呢？原来看似普通的翻字典，不仅是一门技术， 更是一种能力，是算法思想的体现。
任务：巧翻字典 活动：统计查字典次数
次数 翻至页码 下一步决策
第1次 500 往前 1-499
第2次 250 往后 251-499
第3次 375 往前 251-374
第4次 312 往后 313-374
第5次 343 往前 313-342
第6次 327 往后 328-342
第7次 335 往前 328-334
第8次 331 往前 328-330
第9次 329 往前 328-328
第10次 328
策略 1
找到区间的中位数
策略 2
根据情况确定更精确的区间
知识探究：二分查找/折半查找
二分思想：将数列有序排列，采用跳跃的方式查找数据。
分治策略
将难以直接解决的大问题，分割成较小的同类问题
方法：以递增数列为例，以中点位置元素作为比较对象，若要查找元素值小于该中点元素，将待查找序列缩小为左半部分，否则为右半部分。每次比较后都能将查找区间缩小一半。
找一半
按照顺序找一半，
一比较，舍一半。
继续找一半，
一半又一半，
快速找答案！
知识探究：二分查找/折半查找
左边界
flag1
右边界
flag2
目标数x
中间数
mid
！！！若中间数mid比目标数x大，则区间变为左半区间，右边界更新
左边界
flag1
右边界
flag2
目标数x
中间数
mid
！！！若中间数mid比目标数x小，则区间变为右半区间，左边界更新
知识探究：二分查找/折半查找
在有n个元素的有序序列中，利用二分查找大约需要log2n次。
n = 1000 需要10次
二分思想：将数列有序排列，采用跳跃的方式查找数据。
任务：巧翻字典 程序编写——补充程序
x = int(input('请输入要查找的数据：'))
step = 0 #查找次数
flag1 = 1 #目标区域左边界
flag2 = 1000 #目标区域右边界
while flag1 <= flag2 : #区间左边界不大于右边界则执行
mid = (flag1 + flag2)//2 #表示区间中间值 //为整除
step = step + 1 #查找次数加1
if mid > x: #区域中间值大于目标数
flag2 = mid - 1 #范围往左侧区域找 = 右边界前移
elif mid < x: #区域中间值大于目标数
flag1 = mid + 1 #范围往右侧区域找 = 左边界后移
else:
break
print('查找次数为：',step)
任务：巧翻字典
x = int(input('请输入要查找的数据：'))
step = 0 #查找次数
flag1 = 1 #目标区域左边界
flag2 = 1000 #目标区域右边界
while flag1 <= flag2 : #区间左边界不大于右边界则执行
mid = (flag1 + flag2)//2 #表示区间中间值 //为整除
step = step + 1 #查找次数加1
if mid > x: #区域中间值大于目标数
flag2 = mid - 1 #范围往左侧区域找 = 右边界前移
elif mid < x: #区域中间值大于目标数
flag1 = mid + 1 #范围往右侧区域找 = 左边界后移
else:
break
print('查找次数为：',step)
上机实践1
二分查找的应用：找出1-1000之间的某个数
random包可以称为随机包，它有如下函数：
random.randint(1,10) # 产生 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的随机整数
二分查找的应用：找出1-1000之间的某个数
import random
x = random.randint(1,1000)
while 0y = int(input("请输入这个数："))
if xprint("大了")
elif x>y:
print("小了")
else:
print("就是",x)
break
上机实践2
课堂练习
1．二分查找又叫_________，该方法主要将数列_________排列，采用___________的方式查找数据。二分查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。
2．递增数列用二分法查找时，先以________位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列_________为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩小一半。
课堂练习
3.二分法查找的前提条件是被查找的数据__________的。
4.结合分治策略，递归也可以用___________三个字概况。分:将原有问题______成K个子问题;治:对这K个子问题______。如果子问题的规模仍然不够小，则将其再分解为K个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解。合:将求出的小规模问题的解_______为一个更大规模问题的解，自下而上逐步求出原问题的解。
课堂练习
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
课堂小结
4.3 非数值计算
分治策略
二分查找
将一个难以直接解决的大问题，分割成一些较小的同类问题，各个击破 。
二分查找又叫折半查找， 该方法主要将数列有序排列， 采用跳跃式的方式查找数据。
二分法查找的前提条件是被查找的数据必须是有序的。
分：原问题分解成若干子问题
治：对子问题分别求解
合：子问题的解合并成原问题的解
课后作业
尝试用二分法求解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)< 0，则f(x)在(x。,b)内有解；
若|f(x。)|＜10-6，则x。为方程的解。
课后作业
def f(x): #定义方程
return x**3-x**2+x-1
a=float(input("请输入解区间的左边界："))
b=float(input("请输入解区间的右边界："))
while abs(b-a)>1e-6:
x0=(a+b)/2
if f(a)*f(x0)<0:
b=x0
if f(b)*f(x0)<0:
a=x0
if f(x0)==0:
break
print("解为:",x0)
input("运行完毕，请按回车键退出...")
尝试用二分法求解x3-x2+x-1=0
参考代码
学无止境 永攀高峰
感谢观看

展开更多......

收起↑