4.1 算法及其特征
【教材分析】
本节内容是第四章第一节算法及其特征，学生通过第二章的学习，对算法已经有一定的基础，因此本节课主要注重对算法思路的培养，内容涉及到设计算法、算法的优化以及算法的特征。
【教学目标】
1.熟悉将解决问题的方法归结为一系列清晰、准确的步骤的过程。
2.了解算法的基本要素和重要特征。
3.运用恰当的方式描述算法。
4.运用Python语言实现简单算法，解决问题。
【教学重难点】
教学重点:能够分析问题，设计解决问题的算法，并用恰当的方法描述算法；了解枚举法和二分法的含义，并能使用枚举法解决相关问题。
教学难点：能够设计出解决问题的算法；能够用枚举法解决相关问题。
【教学过程】
教学环节 教师活动 学生活动 设计意图
情境导入 情境：商场举办购物狂欢，商家为了吸引顾客，举办了商品价格竞猜活动。 游戏规则：主持人展示一样物品，价格在1～100元之间，顾客竞猜价格，主持人可以提示“价格高了”或“价格低了”，限时30秒，猜中即可获得奖品。 提问：由于顾客众多，我们能不能设计一款线上的猜价格小程序，让更多的顾客参与到活动中。 一位学生扮演主持人，一位学生扮演顾客，模拟“猜价格”活动。 情境模拟，提出问题，引入算法。
算法的定义 第二章已经学习过解决问题的方法和步骤称之为算法。 演示“算法”小视频。 体会算法的定义。 观看视频，加深理解什么是算法。
算法的描述 任务一：请你帮忙设计一个“猜价格”算法。 老师展示自己设计的“猜价格”初级版算法。 学生可以选择自然语言、流程图、计算机语言中的一种方式描述。 加强巩固第二章算法的表示这部分内容。
算法的优化 任务二：完善“猜价格”改良版流程图和程序代码。 根据对初级版算法的改进，完善改良版算法。 逐步完善“猜价格”小游戏的功能。
任务三：根据商家需求，不断优化“猜价格”程序代码。 如：限制竞猜次数、限制竞猜时间等。 知识拓展：给学生展示猜价格用的次数相对较少的一种算法——二分法。 二分查找：也叫折半查找，该方法主要将数列有序排列，采用跳跃式的方式查找数据。 注意：二分法查找的前提条件是被查找的数据必须是有序的。 完善“限制竞猜次数”程序代码。 通过折纸的方式理解二分的原理。 学生活动：将纸对折4次。 给学生一定的思维拓展空间，不断优化程序代码。
算法的评价 评价：时间复杂度、空间复杂度、正确性、可读性、健壮性。 *主要从时间复杂度和空间复杂度来考虑。 设计算法时要考虑算法的时间复杂度和空间复杂度。 结合设计的算法，程序设计过程中需要考虑算法的优化。
算法的特征 提问：从“猜价格”算法中，体现了算法的哪些特征？ 结合算法的描述，我们可以将算法的重要特征归纳如下： 1.有穷性：算法必须能在执行有限个步骤之后终止。 2.确切性：算法中的每一次运算都有明确的定义，具有无二义性，并且可以通过计算得到唯一的结果。 3.输入项：有0个或多个输入。0个输入是指算法本身给出了初始条件。 4.输出项：算法一定要有输出。 5.可行性：算法中执行的任何计算都可以在有限时间内完成。 判断是否符合算法的特征： 1.输出所有的正整数 2.100/正整数 3.100/0 通过简单的判断，熟悉算法的基本特征。
枚举法 任务四：根据提示，评出这次“猜价格”活动的竞猜冠军。 提示：这次竞猜的冠军在A、B、C、D四位顾客中。 A说：“不是我。” B说：“是C。” C说：“是D。” D说：“C说的不对。” 已知四人中有一人说了假话。你能判断出到底谁是冠军吗？ 任务五：请分析以下代码的含义，理解解题思路 第一步：通过表格的形式找出“竞猜冠军”。 第二步：分析代码的含义。 能够使用枚举算法解决问题。
枚举法：把所有可能的方法一一列举，合适就保留，不合适就丢弃，这种方法也叫“穷举”。 枚举法解决问题的一般结构：循环+判断。 枚举法解题的基本思路如下： 1.确定枚举对象、枚举范围和判定条件； 2.一一列举可能的解，验证是否为问题的解。 优点：直观、易于理解；容易证明正确性。 缺点：运算量较大，解题效率不高。 理解枚举的定义和优缺点。 理解枚举的基本知识点。
课堂巩固 1.下列有关算法的描述正确的是（ ） A.算法描述只有流程图才能确保无二义性 B.算法必须在有限步骤执行后终止 C.算法描述中必须要有输入项,否则无法进行运算 D.一中算法设计只对应一种计算机程序设计语言 2.使用枚举法解决问题的优势为（ ） A.算法简单、直接 B运算时间短 C.可以求解任何问题 D.算法灵活多样 3.评价一个算法好的最主要标准是（ ） A.运行速度快 B.运算准确度高 C.时间复杂度低 D.程序代码短 理解知识要点。 熟悉基本定义。
课堂小结 1.算法的特征 2.枚举法 回顾本节课内容。 知识点梳理。
课后拓展 1.找出三位正整数中能被3整除的整数。 2.在《孙子算经》中，有这样一道算术题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？” 3.一个三位数，它的每个位上的数字的3次幂之和等于它本身，求符合条件的三位数。如：1^3 + 5^3+ 3^3 = 153 体会枚举的思想。 加强巩固枚举法的应用。(共38张PPT)
4.1算法及其特征
情境：猜一猜
猜价格赢大礼
游戏规则：
1.商品的价格在100元以内（整数），参与的顾客要猜出这件商品的价格，即可获得奖品。
2. 主持人会根据顾客给出的价格，提示“猜高了”或“猜低了”，直到你猜对价格。
3.时间限制：30s
猜价格赢大礼
情境：猜一猜
情境：猜一猜
设计：“猜价格”小游戏
由于顾客众多，我们能不能设计一款线上的猜价格小游戏，让更多的顾客参与到活动中。
算法
算法：解决问题的方法和步骤。
算法
设计：“猜价格”小游戏——初级版
任务一：请你帮忙设计一个“猜价格”算法。
算法的表现形式
自然语言
流程图
计算机语言
price=66
guess=int(input("输入你猜的价格:"))
if guess
print("猜小了")
elif guess>price:
print("猜大了")
else:
print("恭喜你，猜中了！")
请你们帮忙测试一下程序，
提出你的建议和需要改进的地方！
设计：“猜价格”小游戏——初级版
任务二：请大家结合“自然语言”的描述，
完善流程图和程序代码。
设计：“猜价格”小游戏——改良版
第一步：设置商品价格
第二步：顾客输入猜的价格
第三步：判断顾客输入的价格和商品价格
是否相同
第四步：如果相同，则输出“猜对了！”，
游戏结束
第五步：如果不相同，判断输入的价格
是否猜低了
第六步：如果成立，则输出“猜低了！”，
并返回第二步
第七步：如果不成立，则输出“猜高了！”，
并返回第二步
自然语言
开始
结束
①
输出“猜对了”
输出“猜低了”
是
否
是
否
②
⑤
④
③
流程图
设计：“猜价格”小游戏——改良版
自然语言
流程图
开始
结束
设置商品价格
猜对了
猜低了
输出“猜对了”
输出“猜低了”
输出“猜高了”
是
否
是
否
输入猜的价格
第一步：设置商品价格
第二步：顾客输入猜的价格
第三步：判断顾客输入的价格和商品价格
是否相同
第四步：如果相同，则输出“猜对了！”，
游戏结束
第五步：如果不相同，判断输入的价格
是否猜低了
第六步：如果成立，则输出“猜低了！”，
并返回第二步
第七步：如果不成立，则输出“猜高了！”，
并返回第二步
设计：“猜价格”小游戏——改良版
price=66
while True:
guess=int(input("输入你猜的价格："))
if guessprint("猜小了！")
elif guess>price:
print("猜大了！")
else:
print("恭喜你，猜中了！")
break
price=66
guess=int(input("输入你猜的价格:"))
if guessprint("猜小了!")
elif guess>price:
print("猜大了!")
else:
print("恭喜你，猜中了！")
VS
改良版
初级版
设计：“猜价格”小游戏——改良版
任务三：根据商家需求，设计一个可以限制竞猜次数的“猜价格”小游戏。
设计：“猜价格”小游戏——进阶版
price=66
for i in range(1,6):
guess=int(input("输入你猜的价格："))
if guessprint("猜小了！你还有",5-i,"次机会")
elif guess>price:
print("猜大了！你还有",5-i,"次机会")
else:
print("恭喜你，猜中了！")
break
设计：“猜价格”小游戏——进阶版
商品价格 简单猜
100以内 100次
1000以内 1000次
10000以内 10000次
… … …
7次
10次
14次
对半猜
设计：“猜价格”小游戏——进阶版
算法——二分法
二分查找：也叫折半查找，该方法主要将数列有序排列，
采用跳跃式的方式查找数据。
二分法查找的前提条件是被查找的数据必须是有序的。
算法——二分法
算法——二分法
思考：对半猜的次数是如何计算的？
算法的评价
算法的评价：从时间复杂度和空间复杂度来考虑。
算法的特征
根据我们对已学算法的了解，结合程序的设计
你能归纳一下算法有哪些特征吗？
算法的特征
price=66
while True:
guess=int(input("输入你猜的价格："))
if guessprint("猜小了！")
elif guess>price:
print("猜大了！")
else:
print("恭喜你，猜中了！")
break
输入项
输出项
开始
结束
设置商品价格
猜对了
猜低了
输出“猜对了”
输出“猜低了”
输出“猜高了”
是
否
是
否
输入猜的价格
确切性、可行性、有穷性
算法的特征
输入项：有0个或多个输入。0个输入是指算法本身给出了初始条件。
输出项：算法一定要有输出。有1个或多个输出。
可行性：算法中执行的任何计算都可以在有限时间内完成。
有穷性：算法必须能在执行有限个步骤之后终止。
确切性：算法中的每一次运算都有明确的定义，具有无二义性，并且
可以通过计算得到唯一的结果。
1
2
3
4
5
算法的特征
输出所有的正整数。
100/正整数
100/0
X
X
X
有穷性：一个算法必须保证他的执行步骤是有限的。
确定性：算法中的每个步骤必须有确切的含义。
可行性：算法中的每个步骤都是可行的，能在有限的时间内完成。
谁是竞猜冠军
任务四：根据 “猜价格”小游戏后台数据的统计，请你帮商家评出这次活动的竞猜冠军。
谁是竞猜冠军
这次竞猜的冠军在A、B、C、D四位顾客中。
A说：“不是我。”
B说：“是C。”
C说：“是D。”
D说：“C说的不对。”
已知四人中有一人说了假话。你能判断出到底谁是冠军吗？
小提示：
逐一假设A、B、C、D是冠军，判断是否正确
谁是竞猜冠军
冠军 A说：“不是我。” B说：“是C。” C说：“是D。” D说：“C说的不对。”
A
B
C
D
x
√
x
x
x
x
x
x
x
√
√
√
√
√
√
√
谁是竞猜冠军
冠军 A说：“不是我。” B说：“是C。” C说：“是D。” D说：“C说的不对。”
A
B
C
D
x
√
x
x
x
x
x
x
x
√
√
√
√
√
√
√
竞猜冠军
谁是竞猜冠军
champion=['A','B','C','D']
for i in champion:
cond=(i!='A') +(i=='C') + (i=='D')+(i!='D')
if cond==3:
print("冠军是:",i)
逻辑运算
谁是竞猜冠军
champion=['A','B','C','D'] #设置选手列表
for i in champion: #循环读取选手编号
cond=(i!='A') +(i=='C') + (i=='D')+(i!='D') #查找符合条件的选手
if cond==3: #说真话是否是3人
print("冠军是:",i) #输出冠军
逻辑运算
谁是竞猜冠军
算法——枚举法
把所有可能的答案一一例举，合适就保留，不合适就丢弃。
——枚举法
枚举法也称作穷举法。
算法——枚举法
枚举法解决问题的一般结构：循环+判断。
枚举法解题的基本思路如下：
1.确定枚举对象、枚举范围和判定条件；
2.一一列举可能的解，验证是否为问题的解。
算法——枚举法
优点：直观、易于理解。
正确性容易证明。
缺点：运算量较大，解题效率不高。
课堂巩固
1.下列有关算法的描述正确的是（ ）
A.算法描述只有流程图才能确保无二义性
B.算法必须在有限步骤执行后终止
C.算法描述中必须要有输入项,否则无法进行运算
D.一种算法设计只对应一种计算机程序设计语言
2.使用枚举法解决问题的优势为（ ）
A.算法简单、直接 B运算时间短
C.可以求解任何问题 D.算法灵活多样
3.评价一个算法好的最主要标准是（ ）
A.运行速度快 B.运算准确度高
C.时间复杂度低 D.程序代码短
B
A
C
知识小结
“算法”其实很接地气，可以与我们的生活零距离靠近，让生活变得更美好。《4.1 算法及其特征》任务单
班级 姓名
活动一：设计“猜价格”小游戏
【任务一】：根据游戏规则，设计一个“猜价格”算法。（选择一种方式描述）
游戏规则：主持人展示一样物品，价格在1～100元之间，顾客竞猜价格，主持人可以提示“价格高了”或“价格低了”，猜中即可获得奖品。
用自然语言描述算法 用流程图描述算法 用计算机语言描述算法
第一步： 第二步： 第三步： …
【任务二】：根据你的算法，完善或修改如下流程图和程序代码。
(
A.
输出“猜高了”
B.
输入猜的价格
C.
猜对了
D.
设置商品价格
E.
猜低了
)
price=冠 ① #设置商品价格 while True: guess=int(input("输入你猜的价格(价格范围1—100)："))#输入你猜的价格 if ② #猜的价格小于实际价格 print("猜小了！") elif冠 ③ #猜的价格大于实际价格 print("猜大了！") else: print("恭喜你，猜中了！") break
【任务三】：根据商家需求，不断优化“猜价格”程序代码。（如：限制竞猜次数、限制竞猜时间）
下面是一个限制竞猜次数的一个“猜价格”程序代码，请你完善代码。
#给出5次猜测机会 price=冠 ① #设置商品价格 for i in range(1, ② ): #循环一共5次机会 guess=int(input("输入你猜的价格：")) if guessprice: print("猜大了！你还有",冠 ④ ,"次机会")#输出“猜大了，剩余几次机会” else: print("恭喜你，猜中了！") break
活动二：评选出“猜价格”活动的竞猜冠军。
【任务四】：根据“猜价格”小游戏统计的数据，请你帮商家评出这次“猜价格”活动的竞猜冠军。
判断依据：这次竞猜的冠军在A、B、C、D四位顾客中。 A说：“不是我。” B说：“是C。” C说：“是D。” D说：“C说的不对。” 已知四人中有一人说了假话。你能判断出到底谁是冠军吗？
提示：逐一假设A、B、C、D是冠军，判断是否正确。
冠军 A说：“不是我。” B说：“是C。” C说：“是D。” D说：“C说的不对。”
A
B
C
D
【任务五】：请分析以下代码的含义，理解解题思路，并在横线上填写语句的功能。
champion=['A','B','C','D'] #设置选手列表 for i in champion: #输出冠 ① 军 cond=(i!='A') +(i=='C') + (i=='D')+(i!='D') #输出冠 ② 军 if cond==3: #输出冠 ③ 军 print("冠军是:",i) #输出冠军
知识小结：
课后拓展练习——数字乐园：
1.找出三位正整数中能被3整除的整数。 2.在《孙子算经》中，有这样一道算术题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？” 3. 一个三位数，它的每个位上的数字的3次幂之和等于它本身，求符合条件的三位数。 （如：1^3 + 5^3+ 3^3 = 153）