资源简介

二分查找算法的应用评测习题（学生通过Moodle课程网站完成）
1、下列关于算法的描述正确的是（
）
A
、算法必须有输入
B
、算法就是程序
C
、算法必须有输出
D
、算法的步骤可以是无穷的
2、二分查找又称折半查找，是一种运用于有序数列的高效查找算法。下列数列中适合二分查找算法的是（
）
（1）11
99
5
17
2
39
（2）30
52
63
71
78
81
（3）67
62
68
6
15
15
（4）85
78
59
53
19
18
选择一项：
A.
(1)(2)
B.
(2)(4)
C.
(2)(3)
D.
(3)(4)
3、下列流程图中能描述循环结构的是（　　）
①???
?
②???
?
③???
?
④
?
?
?
?
?
A．①③??????B．②④??????
C．②③④???D．①②④
4、在Python中，int(x)函数的功能是返回不大于x的最大整数，设a=3,b=4，c=5，则下列表达式的运算结果中值最大的是（
）。
A.
abs(a-b)
B.a
2+b
2-c
2
C.
int(2
a-c/b)
D.
sqrt(c)
5、以下程序段运行后，s的值是（
）。
n
=
0
s
=
0
while
s
<=
10:
n
=
n
+
3
s
=
s
+
n
print
s
A.3
B.18
C.0
D.30
6、2005年10月9日，国家测绘局正式宣布珠穆朗玛峰的高度为8844.43米。现有一张白纸的厚度大约是0.08毫米，对折一次，厚度为0.16毫米；对折两次，厚度变为0.32毫米。假设这张纸有足够大，可对折任意次，那么这张纸至少对折多少次，才能达到珠穆朗玛峰的高度？以下是求解该问题的程序片段，请补全代码：
height
=
8844430
#珠穆朗玛峰的高度
h
=
0.08
#定义一张纸的厚度
cnt
=
_________
#定义对折次数
while
h
<
height
:
cnt
=
h
=__________
print
cnt(共19张PPT)
获取数据
查找过程
输出结果
Data
Lookup
Result
1
3
2
4
有效控制
Control
获取数据
Data
查找过程
Lookup
有效控制
Control
输出结果
Result
1
3
2
4
被查找数据序列
数据
目标数据
目标数据：即用户要查找的数据。
input(
)函数的返回值是字符型数据，此算法中需要借助int(
)函数将其转换为数值型数据。
被查找数据序列
a=[7,14,18,21,23,29,31,35,38]
b=[38,35,31,29,23,21,18,14,7]
获取数据
Data
查找过程
Lookup
有效控制
Control
输出结果
Result
1
3
2
4
查
找
查找范围？
查找过程？
范围一直在变，该如何界定？
目标数据与被查找数据序列中的数进行比较
例：对分查找值为key=19的记录的过程：
low=0
high=8
mid=(low+high)//2=4
high=3
mid=1
mid=2
7
14
18
21
23
29
31
35
38
19<23
19>14
19>18
low=2
mid=3
19<21
low=3
low>high
查找结束，没找到
high=2
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
获取数据
Data
查找过程
Lookup
有效控制
Control
输出结果
Result
1
3
2
4
算法有穷性：
一个算法所包含的运算步骤是有限的。
思考：
对于二分查找算法，”数据查找”应该在何时停止？
可以找，但没必要找了
不能找了
02
01
该算法可以被反复执行的必要条件是：
获取数据
Data
查找过程
Lookup
有效控制
Control
输出结果
Result
1
3
2
4
1
2
找到了目标数据
未找到目标数据
输
出
结
果
找到目标数据key
思考：
这种情况的结果反馈在代码的哪个位置比较合理？
输出结果
Result
未找到目标数据key
思考：
何时确定目标数据确实不存在是合理的？
无数可查之时，即满足条件：
if(low>high)
print(“Sorry!查无此数！”)
输出结果
Result
low>high
牛刀小试：（结合算法，编写、调试程序）
获取数据
范围初始化
查找过程
输出未找到时的反馈
a=[7,14,18,21,22,29,31,35,38]
key=int(input("请输入要查找的数据:"))
if(
):
print(“Sorry!查无次数!”)
课堂小结：
二分查找的前提是对有序数列
高效缩小查找范围，直到找到目标或者无数可查
有效控制查找的节奏
适时适地输出正确结果
适合的就是最好的！：）
范围
有序
控制
输出
谢谢聆听《二分查找算法》
教学设计
【导入环节】：
1、实践体验：
猜数字游戏：学生猜数字，老师给出反馈，同时板书“猜的过程”。游戏结束后，老师引导学生分析游戏过程中的几点问题思考，进而引出“有序”、“高效”、“二分”这三个关键词，导入课程主题——“二分查找算法”。
设计意图：让学生切身体会二分的思想，引出本节课的学习主题“二分查找算法”
【授课过程】：
结合刚刚体验过的“猜数字游戏”及计算机解决问题的一般过程，本节课将从以下四大环节来开展探究：
（1）获取数据
(分析目标数据、被查找数据的特点及其获取方法，提出“二分查找算法”的应用前提条件——“数据有序”)
（2）查找过程（本节课的重点）
【学生活动】：为了让大家更直观地理解此算法，采用过程模拟的方式，让学生在活动的过程中，自我总结算法的核心（循环体），并由老师引导、学生分析，师生共同板书该算法的代码实现过程。
设计意图：不仅提升学生的课堂参与感，而且可以让学生更为直观的理解二分查找算法的查找过程，通过老师设计的数码牌和各标记指示牌，使学生理解各标记变量的含义，为接下来的自主编程做好铺垫。
【学生实践】：结合分析出的二分算法核心代码，尝试完成升序序列中的二分查找源程序代码。
设计意图：通过自主编辑、调试程序，进一步理解“二分查找算法”的思想，掌握Python编程的细节与技巧。
（3）有效控制
任何算法都要“知行知止，知止而行”！循环条件的设定非常关键，该过程的分析由老师引导、学生思考总结，共同板书来进行讲解。
【知识探究】：
查找过程可以被重复执行，必要条件即程序中要有可查之数，
即while(low<=high),查找过程可以被反复执行.
算法的有穷性要求在有限步骤内结束，那么二分查找算法何时可以停止呢？
如果找到，可以停止；
如果没有找到，又该在何时停止？
（4）、师生共同分析如何适时适地的输出结果。
【拓展延伸】：
学生自主完成针对降序序列实现“二分查找算法”。
设计意图：进一步巩固本节课所学知识，提升学生的计算思维、灵活运用知识的能力。
【课堂小结】：
结合“有序”、“范围”、“控制”、“输出”四个关键词来总结本堂课所学内容，重点是理解二分查找算法的思想，在用计算机解决问题的过程中，切实培养自己的计算思维能力。面对实际应用问题时，我们应该善于开动脑筋，努力寻求高效的解决方案，在处理问题的过程中，我们应该学会有效控制各种因素，使问题的解决能按照我们预期的方向发展。

展开更多......

收起↑