高效作业19 第19课 数据查找2——二分查找应用-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参(浙教版2019)
高效作业19[第19课 数据查找2——二分查找应用](见学生用书P250)
学科网(北京)股份有限公司
【A级 新教材落实与巩固】
1.数组a中存储的是左右交替上升的n个正整数,如下表表示:
依据二分查找思想在数组a中查找数据key,实现程序如下,请在横线处填入合适的代码。
n=len(a)-1
key=int(input("请输入待查数据: "))
i=0;j=n//2;flag=False
while ①__i<=j__and__not__flag__:
m=(i+j)//2
if key==a[m]:
flag=True
elif②__key<a[m]__:
j=m-1
else:
i=m+1
if not flag and j>=0:
③__m=n-j__
if key==a[m]:
flag=True
if flag:
print("数组元素a["+str(m)+"]即为所求! ")
else:
print("未找到")
【解析】 数组a的元素是交替上升的,由代码“j=n//2”可知,二分查找的范围为左半边的数据,为常规的二分查找.左边如果查找失败,根据左右两边的数据排序次位对称,比a[j]大的右边数组中,也就是a[n-1-j],若相等则查找成功。
2. 在数学中高次方程的求解是个难题,比如现要求方程x3-4x2+x+5=0 的解。一般可以通过以下思路来求一近似解:设f(x)=x3-4x2+x+5,若有区间[a,b],使f(a)与f(b)异号,则该区间内必存在该方程的一个解。小明编写的程序实现如下功能,输入区间值a 和b(a<b),若该区间有解,则求解出该区间内的一个近似解(精确到10-5),否则输出无解信息。
(1)实现上述功能的Python 代码如下,但加框处代码有误,请改正:__abs(ym)<0.00001__。
(2)请在横线处填入合适的代码。
学科网(北京)股份有限公司
a, b=map(int,input(”输入二个用,分隔的整数”).split(”,”))
if a>b:
①__a,b=b,a__
a1,b1=a,b
while a<b:
m=(a+b)/2
ym=m**3-4*m**2+m+5
yb=b**3-4*b**2+b+5
if
break
if ②__yb*ym>0__:
b=m
else:
a=m
if a!=b:
print(”方程在区间[%d,%d]的近似解为%f”%(a1,b1,m))
else:
print(”方程在区间[%d,%d]无解”%(a1,b1))
【解析】 (1)此处是判断当前区间的中点位置是不是近似解,更正为abs(ym)<0.00001。
(2)①根据题意,以及循环条件while a<b,如果a>b,应该交换a、b 值,保证a<b,所以填写的代码:a,b=b,a。②这里是区间收缩的条件,根据b=m,说明近似解不在[m, b]区间,再看题目提示,如果f(a)与f(b)异号,必存在一个解。这里的条件应该是ym 与yb 同号,代码:ym*yb>0。
3. 已知数组元素由正数、负数或0 构成,且无重复数据。编写程序实现在一个升序排列的数组中查找绝对值最小的元素。若绝对值相等,则输出较小数。例如:数组元素值为[27,17,16,-5,13,8,2,-9],该数组中绝对值最小的数为2。小明编写了Python 程序实现上述功能,程序运行界面如下。
(1)若输入序列[3,-6,5,1,-1,-4],执行程序后,输出结果为__-1__。
(2)实现上述功能的Python 程序如下,请在横线处填入合适的代码。
#产生n 个由正数、负数或0 构成的元素,存储在数组a 中,并升序排列,代码略
def dmin(x,y):
min=x
if abs(x)>abs(y):
min=y
return min
#查找绝对值最小的数
i=0;j=n-1;flag=False
while ①__flag==False__或i<=j__and__flag==False__或其他等价答案__:
m=(i+j)//2
if a[m]==0:
学科网(北京)股份有限公司
flag=True
absmin=a[m]
break
elif a[m]>0:
if ②__a[m]>abs(a[m-1])__或a[m-1]>0__或其他等价答案____:
j=m-1
else:
flag=True
absmin=dmin(a[m-1],a[m])
else:
if a[m+1]<0:
i=m+1
else:
flag=True
③__absmin=dmin(a[m],a[m+1])__(注:a[m],a[m+1]顺序交换不给分)____
print(”绝对值最小的元素是: ”+str(absmin))
【解析】 (1)升序排列的数组中查找绝对值最小的元素,若绝对值相等,则输出较小数,序列[3,-6, 5,1,-1,-4],排序后[-6,-4,-1, 1,3, 5],-1 和1 绝对值相等,较小的为-1。
(2)由题干中“已知数组元素由正数、负数或0 构成”,所以查找时绝对值最小的数只能在0 或者正负交替时产生且一定存在,由于数据为升序,当a[m]>0 ,且a[m-1]>0时继续二分查找,如果a[m-1]<0时,即为正负交替时,只需比较a[m-1]与a[m];当a[m]<0 时,且a[m+1]<0 继续二分查找,如果a[m+1]>0 时,即为正负交替时,只需比较a[m]与a[m+1]。①程序中当查找到时,逻辑值flag 均会赋值为True,所以继续查找的条件为flag==False;②此处为a[m]>0 时,由上面分析继续二分查找的条件是a[m-1]>0 时,确定答案为a[m-1]>0 或其他等价答案;③此处是当a[m]<0 时,a[m+1]>0 时,即为正负交替时,只需比较a[m]与a[m+1]确定最小值,确定答案为absmin=dmin(a[m],a[m+1])。
4.2023·义乌中学检测某老师经常研究各高校的招生及录取分数线情况。每年考试结束后,都有许多同学拿着估分成绩来咨询该老师,了解自己比较适合填报哪所大学。该老师会结合以往各高校的录取情况和今年的试卷难度等因素后预估出各高校的录取分数线,并给每位来咨询的学生推荐一所学校供其参考,要求推荐学校的预估录取分数线与学生的估分成绩尽可能接近,这所学校的预估录取分数线和这个学生估分成绩的最小差值称为不满意度。请编程求出所有学生的不满意度之和。如现有A、B、C、D 四所学校,预估录取分数线依次为522、597、567、680。X、Y、Z 三位考生的估分成绩依次为500、600、540。将学校A 推荐给X,不满意度为22,将学校B 推荐给Y,不满意度为3,学校A 推荐给Z,不满意度为18,则所有学生的不满意度之和为43。请回答下列问题。
(1)若A、B、C、D 四所学校预估录取分数线依次为522、597、567、680。X、Y、Z 三位考生的估分成绩依次为550、600、681,则所有学生的不满意度之和为__21__。
(2)加框处代码有误,请改正:__j==0__and__a[j]>x__或a[j]>x__。
(3)实现上述功能的Python 代码如下,请在横线处填入合适的代码。
a=list(map(int,input().split())) #输入各学校的预估录取分数线至数组a,各数之间用空格分隔
b=list(map(int,input().split())) #输入各学生的估分成绩至数组b,各数之间用空格分隔
学科网(北京)股份有限公司