浙教版（2019）高中信息技术必修1 3.3 简单算法及其程序实现 课件(共27张PPT)
文档属性
| 名称 | 浙教版（2019）高中信息技术必修1 3.3 简单算法及其程序实现 课件(共27张PPT) |  | |
| 格式 | pptx | ||
| 文件大小 | 2.6MB | ||
| 资源类型 | 教案 | ||
| 版本资源 | 浙教版（2019） | ||
| 科目 | 信息技术（信息科技） | ||
| 更新时间 | 2020-12-28 17:37:46 | ||
图片预览
文档简介
3.3 简单算法及其程序实现
3.3.1解析算法及其程序实现
解析算法的基本思想是指根据问题的前提条件与所求结果之间的关系，找出求解问题的数学表达式，并通过表达式的计算来实现问题的求解。
在解析算法的程序实现过程中，首先要确保数学表达式的正确性，然后在程序中正确描述该数学表达式。
答题卡填涂识别
计算机是如何判断答题卡中哪些信息点被填涂了呢?
分析:
答题卡上的信息点填涂会导致该信息点的像素颜色发生变化(如填涂前为白色，填涂后为黑色)。因此，判断某信息点是否被填涂，可以从判断一个像素的颜色开始。具体步骤如下:
(1)抽象与建模
(2)设计算法
(3)编写程序
(1)抽象与建模
为了提高填涂内容的识别准确率，需要先将答题卡图像统一转换为黑白图像。
以彩色图像(RGB颜色模式)为例，可以先按照如下数学模型将彩色图像中每个像素的R、G、B值转换成灰度值:
灰度值=0.299x红色颜色分量+0.587 x绿色颜色分量+0.114x蓝色颜色分量
在此基础上，再根据像素的灰度值，依据一定的颜色判断标准(如灰度值小于132,判定为黑色，否则判定为白色),将灰色近似判定为黑色或白色。
(2)设计算法
①给定颜色初值:输入某像素在RGB颜色模式下的各颜色分量。
②转换颜色模式:将彩色( RGB颜色模式)值转化成灰度值。
③判定黑、白颜色:若灰度值小于132，则判定为黑色;否则判定为白色。
(3)编写程序
用变量R、G、B分别存储某像素红色、绿色、蓝色的颜色分量, Gray_ scale 是灰度值,判定某像素(颜色值为RGB(43,10,241))为黑色或白色的Python程序及测试结果如下:
3.3.2枚举算法及其程序实现
枚举算法的基本思想是把问题所有可能的解一一列举， 然后判断每一个列举出的可能解是否为正确的解。
在枚举算法的程序实现中，逐一列举出每一个可能解， 判断其是否为正确解的过程可采用循环结构来实现。而在利用问题提供的约束条件筛选、判断解的过程中则需要用到分支结构。
例如，在求解某整数x的所有因子(不包含x本身)的问题中，可以一一列举[1,x-1]范围内的所有整数，如果x能被这个范围内的某个整数整除，那么这个数就是整数x的因子。实现此算法的Python程序及测试结果如下:
在设计枚举算法时，既不能遗漏任何一个正确解，又要尽可能地缩小解的列举范围，以提高算法的效率。
要完整判定某信息点是否被填涂，还需要对该信息点区域中的所有像素进行判断。
(1)抽象与建模
(2)设计算法
(3)编写程序
(1)抽象与建模
count为n个像素中的黑色像素总数，Gray_ scale[i] 为某个像素的灰度值。
(2)设计算法
基于问题的抽象与建模，统计某信息点中黑色像素的个数可以用枚举算法，算法描述如下:
①逐一列举某信息点中的各个像素。
②如果当前枚举的像素是黑色，那么黑色像素的数量加1。
③输出该信息点中黑色像素总数。
(3)编写程序
问题与讨论
请结合枚举算法的学习经历，谈谈枚举算法的一般程序结构特点。
3.3.3算法程序实现的综合应用
在本节答题卡填涂识别的项目中，也可以通过编写函数来实现原有程序的模块化设计。下面的程序段创建了函数bw_ judge， 能够根据某彩色像素的R、G、B三种颜色分量值，通过计算进而“识别”该像素的颜色情况。
调用bw_ judge 函数时，需将R、G、B的值传递至bw_ judge 函数的参数表。
在本项目中，为了方便读取图像中的像素颜色，并快速实现分析、判断，可以使用Python中的Image模块。实现此项目的Python程序如下:
在本节答题卡填涂识别的项目中，已经实现了判断一个信息点填涂情况的程序编写。但在答题卡的填涂判断中，往往需要对一批信息点进行检测。如图3.3.3所示的准考证号填涂区中有9列、10行，共90个填涂信息点。这样，就需要对90个信息点进行一一检测，才能确定所填涂的准考证号。
(1)抽象与建模
为了更方便地取得相邻信息点( 水平向右或者垂直向下方向)的起始位置坐标，可以将一个标准信息点的宽度、高度与信息点之间的间隔距离组合成一个整体。
该整体的参数为:水平方向总宽度: 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]范围内的整数。
根据每个信息点的起始位置坐标，就可以找到每个信息点的填涂区域，从而对其进行填涂识别。
(2)设计算法
①初始化数据:读取填涂区图像、输人信息点的相关参数。
②确定信息点位置:按从左到右(按列)、从上到下( 按行)的顺序对每个信息点进行检测，其中列(col )为[0,8]范围内的整数，行( row)为[0,9]范围内的整数。
③检测信息点填涂:若该信息点被填涂，则将填涂处信息(即row的值)连接至准考证号( number );若当前列不存在被填涂的信息点，则当前列的填涂信息用“#”标记，并将其连接至准考证号( number )。
④输出填涂的准考证号。
(3)编写程序
问题与讨论
分析本节中的准考证号填涂识别算法及其程序实现，你认为在提高填涂识别的准确性及合理性等方面还可以做哪些完善?
相应的程序又该如何实现?
思考与练习
请编制Python程序解决下列问题:
1.某城市现有80万人口，如果每年人口增长率为1.2%， 问:多少年后该城市人口数达到100万?
2.某企业在第1年初购买了一台价值为120万元的设备，该设备的价值在使用过程中逐年减少。已知从第2年到第6年，每年初的价值比上年初减少10万元;从第7年开始，每年初的价值为上年初的75%。问:第n年初该设备的价值是多少?
3.推算某一天是星期几，可使用蔡勒公式来计算。
蔡勒公式: w=y+[y/4]+[c/4]-2c+[26(m+1)/10]+d-1。
相关参数说明如下:w:星期(w对7取模得: 0—星期日，1—星期一，2—星期二，3—星期三，4—星期四，5—星期五，6—星期六); c:世纪(年份前两位数); y:年(年份后两位数); m:月(在公式中，某年的1、2月要看作上一年的13、14月来计算，比如2003年1月1日要看作2002年的13月1日来计算); d:日; [ ]代表取整，即只取整数部分。
输入年、月、日，求出这一天是星期几。
4.某加密算法要求对输入的小写英文字符串(明文)做如下处理:按照英文字母‘“a’“b”..... “z”的排列顺序，将字符串中的每个字符都取其前一个字符后重组得到密文(其中规定字符“a”的前一个字符取“z”)。例如，明文“student"加密后的密文是“rstcdms'”。请编写计算机程序实现该加密算法。
5.民间流传着“韩信点兵”的故事。韩信带1500名士兵打仗，战死四五百人，剩下的士兵排队:站3人一排，多出2人;站5人一排，多出4人;站7人一排，多出6人。韩信马上说出人数: 1049。 请编写计算机程序验证结果。
6.我国古代数学家张丘建在《算经》中提出了如下的数学问题:鸡翁一，值钱五;鸡母一，值钱三;鸡雏三，值钱一;百钱买百鸡，问翁、母、雏各几何?请编写计算机程序解决该问题。
3.3.1解析算法及其程序实现
解析算法的基本思想是指根据问题的前提条件与所求结果之间的关系，找出求解问题的数学表达式，并通过表达式的计算来实现问题的求解。
在解析算法的程序实现过程中，首先要确保数学表达式的正确性，然后在程序中正确描述该数学表达式。
答题卡填涂识别
计算机是如何判断答题卡中哪些信息点被填涂了呢?
分析:
答题卡上的信息点填涂会导致该信息点的像素颜色发生变化(如填涂前为白色，填涂后为黑色)。因此，判断某信息点是否被填涂，可以从判断一个像素的颜色开始。具体步骤如下:
(1)抽象与建模
(2)设计算法
(3)编写程序
(1)抽象与建模
为了提高填涂内容的识别准确率，需要先将答题卡图像统一转换为黑白图像。
以彩色图像(RGB颜色模式)为例，可以先按照如下数学模型将彩色图像中每个像素的R、G、B值转换成灰度值:
灰度值=0.299x红色颜色分量+0.587 x绿色颜色分量+0.114x蓝色颜色分量
在此基础上，再根据像素的灰度值，依据一定的颜色判断标准(如灰度值小于132,判定为黑色，否则判定为白色),将灰色近似判定为黑色或白色。
(2)设计算法
①给定颜色初值:输入某像素在RGB颜色模式下的各颜色分量。
②转换颜色模式:将彩色( RGB颜色模式)值转化成灰度值。
③判定黑、白颜色:若灰度值小于132，则判定为黑色;否则判定为白色。
(3)编写程序
用变量R、G、B分别存储某像素红色、绿色、蓝色的颜色分量, Gray_ scale 是灰度值,判定某像素(颜色值为RGB(43,10,241))为黑色或白色的Python程序及测试结果如下:
3.3.2枚举算法及其程序实现
枚举算法的基本思想是把问题所有可能的解一一列举， 然后判断每一个列举出的可能解是否为正确的解。
在枚举算法的程序实现中，逐一列举出每一个可能解， 判断其是否为正确解的过程可采用循环结构来实现。而在利用问题提供的约束条件筛选、判断解的过程中则需要用到分支结构。
例如，在求解某整数x的所有因子(不包含x本身)的问题中，可以一一列举[1,x-1]范围内的所有整数，如果x能被这个范围内的某个整数整除，那么这个数就是整数x的因子。实现此算法的Python程序及测试结果如下:
在设计枚举算法时，既不能遗漏任何一个正确解，又要尽可能地缩小解的列举范围，以提高算法的效率。
要完整判定某信息点是否被填涂，还需要对该信息点区域中的所有像素进行判断。
(1)抽象与建模
(2)设计算法
(3)编写程序
(1)抽象与建模
count为n个像素中的黑色像素总数，Gray_ scale[i] 为某个像素的灰度值。
(2)设计算法
基于问题的抽象与建模，统计某信息点中黑色像素的个数可以用枚举算法，算法描述如下:
①逐一列举某信息点中的各个像素。
②如果当前枚举的像素是黑色，那么黑色像素的数量加1。
③输出该信息点中黑色像素总数。
(3)编写程序
问题与讨论
请结合枚举算法的学习经历，谈谈枚举算法的一般程序结构特点。
3.3.3算法程序实现的综合应用
在本节答题卡填涂识别的项目中，也可以通过编写函数来实现原有程序的模块化设计。下面的程序段创建了函数bw_ judge， 能够根据某彩色像素的R、G、B三种颜色分量值，通过计算进而“识别”该像素的颜色情况。
调用bw_ judge 函数时，需将R、G、B的值传递至bw_ judge 函数的参数表。
在本项目中，为了方便读取图像中的像素颜色，并快速实现分析、判断，可以使用Python中的Image模块。实现此项目的Python程序如下:
在本节答题卡填涂识别的项目中，已经实现了判断一个信息点填涂情况的程序编写。但在答题卡的填涂判断中，往往需要对一批信息点进行检测。如图3.3.3所示的准考证号填涂区中有9列、10行，共90个填涂信息点。这样，就需要对90个信息点进行一一检测，才能确定所填涂的准考证号。
(1)抽象与建模
为了更方便地取得相邻信息点( 水平向右或者垂直向下方向)的起始位置坐标，可以将一个标准信息点的宽度、高度与信息点之间的间隔距离组合成一个整体。
该整体的参数为:水平方向总宽度: 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]范围内的整数。
根据每个信息点的起始位置坐标，就可以找到每个信息点的填涂区域，从而对其进行填涂识别。
(2)设计算法
①初始化数据:读取填涂区图像、输人信息点的相关参数。
②确定信息点位置:按从左到右(按列)、从上到下( 按行)的顺序对每个信息点进行检测，其中列(col )为[0,8]范围内的整数，行( row)为[0,9]范围内的整数。
③检测信息点填涂:若该信息点被填涂，则将填涂处信息(即row的值)连接至准考证号( number );若当前列不存在被填涂的信息点，则当前列的填涂信息用“#”标记，并将其连接至准考证号( number )。
④输出填涂的准考证号。
(3)编写程序
问题与讨论
分析本节中的准考证号填涂识别算法及其程序实现，你认为在提高填涂识别的准确性及合理性等方面还可以做哪些完善?
相应的程序又该如何实现?
思考与练习
请编制Python程序解决下列问题:
1.某城市现有80万人口，如果每年人口增长率为1.2%， 问:多少年后该城市人口数达到100万?
2.某企业在第1年初购买了一台价值为120万元的设备，该设备的价值在使用过程中逐年减少。已知从第2年到第6年，每年初的价值比上年初减少10万元;从第7年开始，每年初的价值为上年初的75%。问:第n年初该设备的价值是多少?
3.推算某一天是星期几，可使用蔡勒公式来计算。
蔡勒公式: w=y+[y/4]+[c/4]-2c+[26(m+1)/10]+d-1。
相关参数说明如下:w:星期(w对7取模得: 0—星期日，1—星期一，2—星期二，3—星期三，4—星期四，5—星期五，6—星期六); c:世纪(年份前两位数); y:年(年份后两位数); m:月(在公式中，某年的1、2月要看作上一年的13、14月来计算，比如2003年1月1日要看作2002年的13月1日来计算); d:日; [ ]代表取整，即只取整数部分。
输入年、月、日，求出这一天是星期几。
4.某加密算法要求对输入的小写英文字符串(明文)做如下处理:按照英文字母‘“a’“b”..... “z”的排列顺序，将字符串中的每个字符都取其前一个字符后重组得到密文(其中规定字符“a”的前一个字符取“z”)。例如，明文“student"加密后的密文是“rstcdms'”。请编写计算机程序实现该加密算法。
5.民间流传着“韩信点兵”的故事。韩信带1500名士兵打仗，战死四五百人，剩下的士兵排队:站3人一排，多出2人;站5人一排，多出4人;站7人一排，多出6人。韩信马上说出人数: 1049。 请编写计算机程序验证结果。
6.我国古代数学家张丘建在《算经》中提出了如下的数学问题:鸡翁一，值钱五;鸡母一，值钱三;鸡雏三，值钱一;百钱买百鸡，问翁、母、雏各几何?请编写计算机程序解决该问题。