算法与问题解决复习课件-2024-2025学年浙江省高中学业水平考试信息技术总复习

算法与问题解决 学考要点1 算法的概念及描述 【必修1 数据与计算第40～52页　指导意见第13～19页】 1．算法的概念 (1)算法的定义 ①广义地讲，“算法”指的是解决问题或完成任务的一系列步骤。 ②在计算机科学领域内，“算法”指的是用计算机解决问题的步骤，是为了解决问题而需要让计算机有序执行的、无歧义的、有限步骤的集合。 (2)算法的特征 特征 含义 有穷性 一个算法的处理步骤必须是有限的 可行性 一个算法中的每一步操作与要求都应该是算法执行者(人或机器)可以实施的，同时在现实环境中能做到并且在有限的时间内完成 确定性 算法中对于每个步骤的执行描述必须是明确的 0个或多个输入 数据可从外部获取，也可包含在算法中 1个或多个输出 算法必须包含至少1个输出，以告诉外界问题求解的结果 (3)算法的要素 用计算机解决问题，本质上是以“数据运算”的方式来实现的。通过算法让计算机解决问题时需要三要素：数据、运算、控制转移。 要素 含义 数据 明确参与运算的初始数据、运算时产生的中间数据以及代表问题解决的结果数据 运算 明确每一步的运算是什么、对哪些数据进行运算等 控制转移 有时需要根据数据或运算结果的特点进行不同的处理，这时就需要运用控制转移来执行不同的操作 2.算法的描述 设计出一个解决问题的算法，需要用能被算法执行者理解的形式加以呈现，才能被算法执行者理解并执行。算法的这种呈现就称为算法的描述。常见的算法描述方式有自然语言、流程图、伪代码、计算机程序设计语言等。 流程图：用一些图形符号表示规定的操作，并用带箭头的流程线连接这些图形符号，表示操作进行方向。常用的流程图基本图形及其功能如下表所示： 图形 名称 功能 开始/结束符 表示算法的开始或结束 输入/输出框 表示算法中数据的输入或输出 处理框 表示算法中数据的运算处理 判断框 表示算法中的条件判断 流程线 表示算法中的流向 连接点 表示算法中的转接 学考要点2 算法的控制结构及用算法解决问题的过程 【必修1 数据与计算第53～71页　指导意见第13～19页】 1．算法的控制结构 类型 流程图 特点 顺序结构 ①每个步骤按照算法中出现的顺序依次执行 ②每个步骤一定会被执行一次，而且只执行一次 分支结构 ①首先进行条件判断，根据条件满足与否来决定执行哪个分支 ②在一个分支结构中，必定有一个分支被执行，其他的分支则被忽略 循环结构 先判断循环条件是否满足，若满足则进入循环，执行循环体，然后再次判断循环条件是否满足，若满足则再次进入循环，执行循环体，然后再次判断循环条件是否满足……直到某次循环条件不满足，退出循环 2.用算法解决问题的过程 (1)用算法解决问题的一般过程：抽象与建模→设计算法→描述算法。 ①抽象与建模：从现实项目的真实情境中提炼出核心的要素并加以确定或假设，最终定义出一个明确已知条件和求解目标的问题，并用数学符号描述解决该问题的计算模型。 ②设计算法：遵循算法的特征、围绕算法的要素设计算法。对任何数据的处理，总体上都要经历三个步骤：输入数据、处理数据、输出处理结果。 ③描述算法：可以使用流程图来进一步描述解决问题的算法。 (2)用计算机编程解决问题的一般过程：抽象与建模→设计算法→编写程序→调试运行程序。 例1　下列关于算法的说法正确的是(　 　) A．算法的一个步骤可以被执行多次 B．算法必须包括一个或多个输入 C．算法就是数学运算方法 D．算法只能用自然语言进行描述 A 【解析】 选项B，算法可以有0个或多个输入，选项错误；选项C，“算法”指的是解决问题或完成任务的一系列步骤，选项错误；选项D，常见的算法描述方式有自然语言、流程图、伪代码、计算机程序设计语言等，选项错误。 变式　某算法用伪代码描述如下： 下列关于上述算法的说法正确的是(　 　) A．该算法违背了算法有穷性原则 B．该算法实现了找出A和B中的最大值A C．该算法属于分支结构 D．该算法无法使用流程图来描述 【解析】 该算法属于循环结构，可以用流程图表示，功能是若A<B，则交换A、B中的数值，并输出，若A＞B，则会一直进行判断，无法输出。该算法违背了算法的有穷性原则，选项A正确。 A 例2　某算法的部分流程图如图所示。执行这部分流程，下列说法不正确的是(　 　) A．语句“s<100？”共被执行了5次 B．交换“s←s＋a*a”和“a←a＋2”， 执行结果相同 C．循环体共被执行了4次 D．输出变量a的值为10 【解析】 选项B，交换“s←s＋a*a”和“a←a＋2”，s累加的值不同，执行结果也不同，选项错误。 B 变式1　 (2023·浙江1月选考)某算法的部分流程图如图所示。执行这部分流程，若输入x 的值依次为10，7，8，12，0，则输出k的值是(　 　) A.2 B．3 C．4 D ．5 【解析】 根据y＝y＋x可知，y 是x 的累加和。 当y>＝10时，变量k有计数操作，并将y初始化 为0。根据x 的值可知，y 有3 次满足y>＝10。 所以k 最终结果是3，选项B正确。 B 变式2　 (2024·浙江6月选考)某同学根据如图所示的流程图编写的Python程序段如下： n＝int(input()) if n<＝20： z＝0 if n<＝50： z＝1 else： z＝2 用下列输入数据测试流程图与程序段，两者得到的z值不同的是(　 　) A．60 B．50 C．30 D．10 【解析】 流程图描述的是一个多分支的语句，而程序段给出的是两个独立的分支语句。当n<＝20时，程序段中的变量z会被二次赋值，最终的结果是1，而流程图z只赋值一次，结果是0。选项D符合题意。 D 变式3　用“辗转相除法”计算正整数a和b的最大公约数的步骤如下： ①输入两个正整数a和b； ②以a除以b，相除得到的余数为c； ③若c＝0，则输出b的值，算法结束，否则，执行步骤④； ④令a＝b，b＝c，返回步骤②继续执行。 “辗转相除法”算法流程图如图所示，下列说法正确的是(　 　) A．该流程图是分支结构 B．①处可以填 a%b＝0? C．如果输入的a小于b，则输出的结果不正确 D．交换流程图中a＝b与b＝c两句的顺序，不影响运行结果 B 【解析】 选项A，该流程图是循环结构，选项错误；选项C，如果输入的a小于b，只会增加一次循环次数，输出的结果仍然正确，选项错误；选项D，交换流程图中a＝b 与 b＝c 两句的顺序，会影响运行结果，选项错误。 变式4　(2024·萧山中学学考模拟)已知长方形的长和宽，求长方形的面积。用计算机来解决此问题的算法的各个步骤如下： ①调试运行； ②确定面积计算公式并用数学符号描述； ③程序设计算法，并通过编写计算机程序来描述算法； ④提炼核心要素并加以假设(设长为a，宽为b，面积为s)。 上述步骤的正确顺序是(　 　) A．②③④① B．④③①② C．④②③① D．③④①② C 【解析】 用计算机编程解决问题的一般过程：抽象与建模；设计算法；编写程序；调试运行程序。选项C正确。 $$