浙教版（2019）高中信息技术必修1 3.3 简单算法及其程序实现 课件(共27张PPT)

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)抽象与建模 为了更方便地取得相邻信息点 ... ...