4.3非数值计算课件——二分查找 课件 2022—2023学年高中信息技术教科版（2019）必修1（22张PPT）

(共22张PPT)
4.3 非数值计算
SUMMARY REPORT
SUMMARY REPORT
了解分治策略的概念
壹
掌握二分查找的算法思想
贰
在python中用二分法解决问题
叁
学习目标
CONTENTS
SUMMARY REPORT
计算一定是数吗？
除了数还有什么？
这些属于数值计算吗？
计算的对象可以是自然界和人类社会的一切事物。
某些信息，如数据、文字、语言、图形、知识、事物的运动过程及思维过程。
非数值计算更多探讨＂ 算法” 问题。
在解决非数值类计算问题时，一些基础的思维方式可以借鉴，如分治、递归、解析等。
非数值计算
SUMMARY REPORT
分治策略
壹
SUMMARY REPORT
分治策略
n
（n较小）
直接解决
n
n1
（将这k个子问题的解合并）
n2
nk
……
解决原问题
（分解）
（递归地解决每个子问题）
分治策略
所能解决的问题的特征
该问题的规模缩小到一定的程度就可以容易地解决。
该问题可以分解为若干个规模较小的相同问题，即该问题具有最优 子结构性质。（前提）
利用该问题分解出的子问题的解可以合并为该问题的解。（关键）
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
分解
将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
解决
若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
合并
将各个子问题的解合并为原问题的解。
分治法的基本步骤
SUMMARY REPORT
二分查找
利用分治法解决问题的典型案例之一
贰
猜数字游戏
老师将在心里说一个1~1000之间的数，同学们猜一猜这个数字是多少？（如果回答的数不对，老师将告知这个数比正确的数大还是小）。
思考：怎样才能最快的找到正确答案？
猜数字游戏
500
大
小
750
250
大
875
小
大
小
625
375
125
……
……
……
……
每次取中间的数，仅仅需要10次即可找到答案
猜数字游戏
思考：如果是1~100，最多需要几次找到答案？如果是1~10000呢？
2
7
≈
100
2
10
≈
1000
目标越大，优势越明显
二分查找
二分查找又叫折半查找，该方法主要将数列有序排列，采用跳跃式的方式查找数据。以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。 每一次比较后可以将查找区域缩小一半。
第一次分割
第二次分割
第三次分割
二分查找
实际操作——翻页数比赛
假设我们的信息技术书本为200页，目标为68页，记录下每次翻开的页数，看看谁找的最快。
100
50
75
62
68
往前找
往前找
往后找
往后找
SUMMARY REPORT
在python中用二分法解决问题
Problems and Solutions
如何判断一个数在已知数组中的位置？
A=[1,5,3,7,36,12,68,79,2]
A.sort() #先将数组变有序
num=int(input(“请输入要查找的数”))
left=0 #left指的是范围最左边的下标
right=len(list)-1 #right指的是范围最右边的下标
while(left<=right): #只要查找范围还没变为0就循环
mid=(left+right)//2 #范围中间那个数的下标
if num>A[mid]:
left=mid+1
elif numright=mid-1
else:
print(“该数为数组中的第{}个数”.format(mid+1))
思考：如果输入的数据不在范围内，会出现什么结果呢？程序还需要在哪些地方进行完善？
如何判断一个数在已知数组中的位置？
i=0
for e in A:
if num==e:
……
else:
i++
if i==len(A):
print(“该数字不存在于当前数组”)
# 遍历
# i 用来存放数值不相同的次数，如果遍历完成后发现全不相同，说明不存在
拓展知识
小游戏：如何找出1-1000之间的某个数？
random.randint(1,10)
random.random()
random.uniform(1.1,5.4
random.choice('tomorrow')
random.randrange(1,100,2)
import random
x = random.randint(1,1000)
while 0y = int(input("请输入这个数："))
if xprint("大了")
elif x>y:
print("小了")
else:
print("就是",x)
break
课堂练习———补全翻字典程序
Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Aenean commodo ligula eget dolor.
Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Aenean commodo ligula eget dolor.
课后作业———汉诺塔
移动3个木盘的方法是：根据木盘叠放规则，要使A杆上最大的木盘（记为x)移动到C杆上（子问题1, 如图第4步），必须先把 x上方的所有木盘移动到B杆上（子问题2, 如图4中的前3步），然后再将B杆上所有的木盘移动到C杆上（子问题3, 如图中的后3步）。
课堂小结
Thank You For Your Leadership And Colleagues
2022.9.14
SUMMARY REPORT
凡治众如治寡，分数是也。
————《孙子兵法》