资源简介

(共43张PPT)
教材版本册别：浙教版（2019）必修1
高中信息技术
汇报人：Mr.yang
第3章 算法的程序实现 第3节 （1课时）
简单算法及其程序实现
学习目录
01.
解析算法及其程序实现
02.
枚举算法及其程序实现
03.
算法程序实现的综合应用
学习目标
1
2
能够运用所学知识进行简单算法的设计和程序实现，已解决实际问题；
了解解析算法、枚举算法的程序实现以及算法程序实现的综合应用；
3
在进行算法设计和编程实践中，提高合作交流与动手能力，培养严谨的思维习惯和创新精神；
一
课堂导入
答题卡的扫描过程
一
课堂导入
我们考试用的答题卡是如何识别的，其中用到了哪些算法？
解决问题的算法有很多，当算法设计完成后，就可以用程序设计语言来描述算法。
解析算法及其程序实现
01
一
解析算法及其程序实现
解析算法的基本思想是指根据问题的前提条件与所求结果之间的关系，找出求解问题的数学表达式并通过表达式的计算来实现问题的求解。
在解析算法的程序实现过程中，首先要确保数学表达式的正确性，然后在程序中正确描述该数学表达式。
一
解析算法及其程序实现
通过一个答题卡填涂识别的项目实例来体验解析算法的程序实现过程。
答题卡部分区域样例
如下图所示的答题卡常用于标准化考试、选举和调查。答题卡一般采用2B铅笔填涂，填涂好的答题卡经过扫描后得到相应的数字化图像，再通过光学识别，完成答题卡信息数据的采集、分析与统计。那么，计算机是如何判断答题卡中哪些信息点被填涂了呢？
一
解析算法及其程序实现
分析：答题卡上的信息点填涂会导致该信息点的像素颜色发生变化（如填涂前为白色，填涂后为黑色）。因此，判断某信息点是否被填涂，可以从判断一个像素的颜色开始。
抽象与建模
（1）
由于扫描得到的答题卡图像可能是彩色图像或者是灰度图像，为了提高填涂内容的识别准确率，需要先将图像统一转换为黑白图像。以彩色图像（RGB颜色模式）为例，可以先按照如下数学模型将彩色图像中每个像素的R、G、B值转换成灰度值：
灰度值= 0.299×红色颜色分量+ 0.587×绿色颜色分量+ 0.114×蓝色颜色分量
在此基础上，再根据像素的灰度值，依据一定的颜色判断标准（如灰度值小于132，判定为
黑色，否则判定为白色），将灰色近似判定为黑色或白色。
一
解析算法及其程序实现
设计算法
（2）
给定颜色初值：输入某像素在RGB颜色模式下的各颜色分量。
转换颜色模式：将彩色（RGB颜色模式）值转化成灰度值。
①
②
③
判定黑、白颜色：若灰度值小于132，则判定为黑色；否则判定为白色。
基于问题的抽象与建模，判定一个像素的颜色可以用解析算法，算法描述如下：
一
解析算法及其程序实现
编写程序
（3）
用变量R、G、B分别存储某像素红色、绿色、蓝色的颜色分量，Gray_scale是灰度值，判定某像素（颜色值为RGB(43,10,241)）为黑色或白色的Python程序及测试结果如下：
程序 测试结果
R=43 G=10 B=241 Gray_scale=0.299*R+0.587*G+0.114*B if Gray_scale<132: print("黑色") else: print("白色") 黑色
一
解析算法及其程序实现
尝试上网检索并改写程序以实现自动获取输入的R、G、B三种颜色的分量，进而判定某像素（颜色值为RGB）是黑色还是白色？
试一试
改进后代码为：
R=int(input("请输入R颜色分量"))
G=int(input("请输入G颜色分量"))
B=int(input("请输入B颜色分量"))
Gray_scale=0.299*R+0.587*G+0.114*B
if Gray_scale<132:
print("黑色")
else:
print("白色")
一
解析算法及其程序实现
总结
在解析算法的程序实现过程中，首先要确保数学表达式的正确性，然后在程序中正确描述该数学表达式。
枚举算法及其程序实现
02
二
枚举算法及其程序实现
动动手
想一想
学校举行趣味游戏，游戏规则如下：参与人员排成一个圈，从第一个人开始从1开始快速地报数，若遇到7的倍数或者包含7的数字，则拍手，若没有拍手，则该人淘汰。一直报数，直到圈中只剩下一人，即为胜利者。你准备好了吗？
取第一个数50 判断是否需要跳过
取第二个数51 判断是否需要跳过
取第三个数52 判断是否需要跳过
…… ……
取最后一个数n 判断是否需要跳过
枚举算法
一一列举
逐个判断
二
枚举算法及其程序实现
①
基本
思想
把问题所有可能的解一一列举，然后判断每一个列举出的可能解是否为正确的解。
②
解题
思路
逐一列举可能解的范围，这个过程用循环结构实现。
对每一个可能解进行验证，这个过程用分支结构实现。
③
程序实现
把问题所有可能的解一一列举，然后判断每一个列举出的可能解是否为正确的解。
操作 模块 程序
一一列举 循环结构 For语句 / While语句
逐个比较 判断分支结构 If语句
二
枚举算法及其程序实现
思考
在求解某整数x的所有因子（不包含x本身）的问题中，可以一一列举[1,x-1] 范围内的所有整数，如果x能被这个范围内的某个整数整除，那么这个数就是整数x的因子。
分析
算法设计
可以一一列举[1,x-1] 范围内的所有整数，如果x能被这个范围内的某个整数整除，那么这个数就是整数x的因子。
（1）输入某整数X;
（2）执行X除以i(i大于1小于X-1)求余数;
（3）判断第二步余数是否为0，输出i；否则i自动加1，循环执行第二步。
二
枚举算法及其程序实现
思 考
请同学们自主思考如何设计算法并程序实现求解某整数x的所有因子？
程序 测试结果
x=int(input("请输入整数x ：")) i=1 while i<=x-1: if x%i==0: print(i) i=i+1 请输入整数x ：243
1
3
9
27
81
二
枚举算法及其程序实现
总结
在上述算法的程序实现过程中，由于整数x无法被从[]+1到x-1范围内的整数整除，因此，枚举范围可缩小至从1到[]，即循环进行的条件为i≤[]。在枚举的过程中，当数据规模较大时，减少枚举的次数，将大大提高解决问题的效率。因此，在设计枚举算法时，既不能遗漏任何一个正确解，又要尽可能地缩小解的列举范围，以提高算法的效率。
二
枚举算法及其程序实现
在前面的项目学习中，我们已经解决了答题卡信息点中某个像素是否为黑色的判断问题（即判断该像素是否被涂黑）。但要完整判定某信息点是否被填涂，还需要对该信息点区域中的所有像素进行判断。这里我们使用枚举算法来试一下！
抽象与建模
1
判断某信息点是否被填涂与该信息点区域中的黑色像素数量有关，当黑色像素数量达到一定比例（如黑色像素的数量不少于该信息点区域内所有像素数量的64%），则认定该信息点被填涂。因此，判断某信息点是否被填涂，首先需要对该信息点区域中的所有像素逐一进行判断，然后统计所有黑色像素的总数。统计黑色像素个数的计算模型如下：
其中，count为n个像素中的黑色像素总数，Gray_scale[i]为某个像素的灰度值。
二
枚举算法及其程序实现
设计算法
2
③输出该信息点中黑色像素总数。
如果当前枚举的像素是黑色，那么黑色像素的数量加1。
逐一列举某信息点中的各个像素。
①
②
③
基于问题的抽象与建模，统计某信息点中黑色像素的个数可以用枚举算法，算法描述如下：
二
枚举算法及其程序实现
编写程序
3
如果上述5个像素的颜色用R、G、B的颜色分量表示，为了方便枚举，可以将它们的
R、G、B颜色分量值用列表p_color进行组织：
下面以5个像素为例，判定它们当中哪些是黑色像素并且统计黑色像素的个数，实现此功能的程序及测试结果如下：
程序 测试结果
count=0 Gray_scale=[47,178,146,185,116] for i in range(0,len(Gray_scale)): if Gray_scale[i]<132: print("第"+str(i+1)+"个像素为黑色；") count=count+1 print("黑色像素总共有："+str(count)+"个。") 第1个像素为黑色；
第5个像素为黑色；
黑色像素总共有：2个。
程序中，变量count用于统计黑色像素的个数，列表Gray_scale存储了5个像素的灰度值。
二
枚举算法及其程序实现
以小组为单位，总结归纳枚举算法的一般程序结构特点。
枚举算法通常会包含循环结构。因为它需要遍历所有可能的情况。
枚举算法需要明确枚举的范围。这个范围是根据问题的要求来确定的。
与循环结构紧密配合的是条件判断语句。在循环内部，需要通过条件判断来检查当前枚举的情况是否满足问题的要求。
枚举算法一般是按照一定的顺序逐个检查可能的情况。
二
枚举算法及其程序实现
拓展延伸
如果上述5个像素的颜色用R、G、B的颜色分量表示，为了方便枚举，可以将它们的R、G、B颜色分量值用列表p_color进行组织：
p_color=[[84,24,70],[229,160,145],[133,161,107],[200,176,200],[201,80,85]]
再使用以下语句读取各个像素的R、G、B颜色分量值（变量i为列表p_color的索引）：
R=p_color[i][0]
G=p_color[i][1]
B=p_color[i][2]
从而计算出各个像素的灰度值并实现黑白像素判断。
p_color=[[84,24,70],[229,160,145],[133,161,107],[200,176,200],[201,80,85]]
再使用以下语句读取各个像素的R、G、B颜色分量值（变量i为列表p_color的索引）：
R=p_color[i][0]
G=p_color[i][1]
B=p_color[i][2]
从而计算出各个像素的灰度值并实现黑白像素判断。
二
枚举算法及其程序实现
如果要判断如右图所示信息点中的300个像素（25×12）的颜色情况，那么需要对300个像素的颜色数据（RGB各颜色分量值）逐一进行列举并判断。下面的Python程序实现了从某文件中读取300个像素的颜色数据，并将判断后的填涂结果写入文件。
填涂示意图
二
枚举算法及其程序实现
程序 注释
fname = input("请输入文件名称: ") f = open(fname,"r+") count=0 line = f.readline() while line: line = line.split() R, G, B = map(int, line) if 0.299 * R + 0.587 * G + 0.144 * B < 132: count = count + 1 line = f.readline() if count >= 300 * 0.64: f.write("\n已填涂！") else: f.write("\n未填涂！") f.close()
# 以读写的方式打开文件
# 当line非空（从文件读取到了数据）
# 从文件中读取一行
# 把空白字符去除，变成包含三个str的list
# 把line中三个str转化成int并赋值给R, G, B
# 继续读取一行
我们一起来看一下程序代码：
二
枚举算法及其程序实现
读写文件的函数 以读文件模式（参数'r'）打开文件test.txt 将文件中的全部内容读取到内存

每次读取一行内容，并返回字符串 关闭文件的方法 用参数'w'表示写文本文件模式

open( )
f =open('test.txt', 'r')
f.read( )
readline( )
f.close( )
f = open('test.txt', 'w')
根据拓展链接部分对文件读写函数的介绍，并总结填写下表。
算法程序实现的综合应用
03
三
算法程序实现的综合应用
在前面所讲的答题卡填涂识别的项目中，也可以通过编写函数来实现原有程序的模块化设计。下面的程序段创建了函数bw_ judge，能够根据某彩色像素的R、G、B三种颜色分量值，通过计算进而“识别”该像素的颜色情况。
p_color=[[84,24,70],[229,160,145],[133,161,107],[200,176,200],[201,80,85]]
再使用以下语句读取各个像素的R、G、B颜色分量值（变量i为列表p_color的索引）：
R=p_color[i][0]
G=p_color[i][1]
B=p_color[i][2]
从而计算出各个像素的灰度值并实现黑白像素判断。
def bw_judge(R,G,B):
Gray_scale = 0.299 * R + 0.587 * G + 0.114 * B
if Gray_scale < 132:
color = "黑色"
else:
color = "白色"
return color
调 用bw_ judge函 数 时， 需 将R、G、B的值传递至bw_judge函 数 的 参 数 表。例如，主程序中有函数调用语句bw_ judge(43,10,241)，则返回的函数值将是彩色像素RGB(43,10,241)被识别后的结果。如果在程序的其他位置也要检测黑、白颜色的像素，那么只需调用bw_ judge函数即可。
三
算法程序实现的综合应用
在本项目中，为了方便读取图像中的像素颜色，并快速实现分析、判断，可以使用Python中的Image模块。实现此项目的Python程序如下：
from PIL import Image
im = Image.open("RGB.bmp")
pix = im.load()
width = im.size[0] # size中有两个参数，第1个参数为图像宽度值
height = im.size[1] # 第2个参数为图像高度值
count = 0
for x in range(width):
for y in range(height):
R,G,B = pix[x, y] # 根据像素坐标获得该点的 RGB 值
if bw_judge(R,G,B) == "黑色": # bw_judge函数用于判断黑、白像素
count = count + 1
if count >= width * height * 0.64:
print("已填涂！")
else:
print("未填涂！")
三
算法程序实现的综合应用
在本节答题卡填涂识别的项目中，已经实现了判断一个信息点填涂情况的程序编写。但在答题卡的填涂判断中，往往需要对一批信息点进行检测。如图3.3.3所示的准考证号填涂区中有9列、10行，共90个填涂信息点。这样，就需要对90个信息点进行一一检测，才能确定所填涂的准考证号。
准考证号填涂区域
三
算法程序实现的综合应用
抽象与建模
如上页PPT中的准考证号填涂区域所示的90个信息点，每个信息点在图像中都有固定的坐标值，根据坐标可以确定它们的位置。右图所示的是准考证号填涂区域中准考证号填涂区左上角的4个信息点的坐标。
部分填涂信息点的坐标示意图
三
算法程序实现的综合应用
答题卡在模板设计时就指定了每个信息点的格式与参数。如下图所示，信息点中的每个像素坐标可表示为：（水平方向值，垂直方向值）。其中，“start”为准考证号填涂区第一行第一列的信息点起始位置，其坐标记作（x_start, y_start）。另外，信息点的宽度（fill_width）、高度（fill_height）以及信息点之间的间隔距离（space_width、space_height）都相同，且同一列的信息点水平方向坐标值和同一行的信息点垂直方向坐标值也都相同。
信息点坐标分析示意图
三
算法程序实现的综合应用
为了更方便地取得相邻信息点（水平向右或者垂直向下方向）的起始位置坐标，可以将一个标准信息点的宽度、高度与信息点之间的间隔距离组合成一个整体。
该整体的参数为
p_color=[[84,24,70],[229,160,145],[133,161,107],[200,176,200],[201,80,85]]
再使用以下语句读取各个像素的R、G、B颜色分量值（变量i为列表p_color的索引）：
R=p_color[i][0]
G=p_color[i][1]
B=p_color[i][2]
从而计算出各个像素的灰度值并实现黑白像素判断。
水平方向总宽度：total_width = fill_width + space_width
垂直方向总高度：total_height = fill_height + space_height
这时，答题卡中的任意一个信息点的起始位置水平方向坐标值x可表示为：
x = x_start + total_width * col
起始位置的垂直方向坐标值y可表示为：
y = y_start + total_height * row
其中col为列号，row为行号；col∈[0,8]范围内的整数，row∈[0,9]范围内的整数。
根据每个信息点的起始位置坐标，就可以找到每个信息点的填涂区域，从而对其进行填涂识别。
三
算法程序实现的综合应用
设计算法
初始化数据
检测信息点填涂
确定信息点位置
输出填涂的准考证号
基于问题的抽象与建模，识别准考证号填涂的算法描述如下：
三
算法程序实现的综合应用
编写程序
四
小结
课堂小练
04
五
课堂小练
只需知道数据之间相互链接的顺序
探讨与讨论
1.程序如下
a=int(input())
b=int(input ())
c=a+b
print(a,’+’,b,’=’,c)
通过键盘分别输入23和3，运算结果是（ ）
A.26 B.23+3=26 C.’23’+”3”=26 D.24+4=28
B
解析：本题考查Python程序执行
a=23，b=3，c=23+3=26，最后输出23+3=26，故本题选B选项。
五
课堂小练
只需知道数据之间相互链接的顺序
探讨与讨论
2.购买地铁车票：乘1-4站3元/人；5-9站4元/人；9站以上5元/人。根据输入的站数N，输出应付款M，如需将算法补充完整，最适合的选项是（ ）
A．N>9
B．N<=9
C．5<=N<=9
D．N>=5 and N<=9
B
解析：本题考查条件语句。根据题目要求，购买地铁车票：乘1-4站3元/人；5-9站4元/人；9站以上5元/人。故N<=9满足5-9站4元/人，最适合，因此选项B正确。
五
课堂小练
只需知道数据之间相互链接的顺序
探讨与讨论
3.下面if语句统计满足“性别 （gender) 为男、职称(rank) 为副教授、年龄(age)小于40岁”条件的人数，正确的语句为（ ）
A．if(gender=="男" or age<40 and rank=="副教授"): n+=1
B．if(gender=="男" and age<40 and rank=="副教授"): n+=1
C．if(gender=="男" and age<40 or rank=="副教授"): n+=1
D．if(gender=="男" or age<40 or rank=="副教授"): n+=1
解析：本题主要考查if条件分支。题目中的条件都是与的关系，所以要用and连接，故本题选B选项。
B
五
课堂小练
只需知道数据之间相互链接的顺序
探讨与讨论
4.计算表达式1/2+2/3+3/5+5/8+…前30项的和。实现此功能的Python程序如下：
a,b=1,2
s=0
for i in range(30):
(1)
print(s)
横线中的代码由下列3个语句组成：①b=b+a ②s=s+a/b ③a=b-a
下列选项中代码顺序正确的是（ ）
A．①③② B．③①② C．②①③ D．②③①
解析：本题考查的是循环语句的应用。变量a、b的初值分别为1和2，观察该表达式，第1项应为a/b，第2项应为b/(a+b)，所以第1步应执行s=s+a/b；接下来考虑更新a、b值，即实现a=b，b=a+b，先执行b=b+a，再执行a=b-a，相当于a=a+b-a=b，故代码顺序为②①③，选项C正确。
C
高中信息技术浙教版必修1
谢谢！

展开更多......

收起↑