第二章 算法与问题解决课件-2025-2026学年浙教版高中信息技术必修一

信息技术 必修内容 第 ‹#› 页 第二章 算法与问题解决 2.1 算法的概念及描述 算法与问题解决 算法的概念 算法的描述 用算法解决 问题的过程 算法的控制结构 定义 特征 要素 自然语言 流程图 伪代码 程序设计语言 顺序结构 分支结构 循环结构 抽象与建模 设计算法 描述算法 2.1.1 算法的概念及描述 算法可以帮助算法执行者高效地解决问题，只有掌握了算法的定义，设计出符合算法的有效算法，并围绕算法加以准确描述，才能运用针对性的算法。 第 ‹#› 页 算法的定义 算法自古有之，古代数学家欧几里得在《几何原本》中提出的“辗转相除法”（也称欧几里得算法）就是算法，利用该算法可以求出任意两个正整数的最大公约数。用“辗转相除法”计算正整数m和n的最大公约数的步骤如下： 输入两个正整数m和n。 若m<n,则交换m和n的值。 以m除以n，相除得到的余数为r。 若r=0，则输出n的值，算法结束；否则执行步骤⑤。 令m=n,n=r,返回步骤③继续执行。 第 ‹#› 页 再如，“用求根公式求解一元二次方程的实数根”，他给出了一元二次方程解的总则和方向，但没有说明具体如何做，对于一个不知道求根公式的具体运算的人或者机器来说，没有任何实际意义。 如果将该方法分步骤具体描述: 先输入二次项系数a，一次项系数b，常数项c； 根据方程系数计算Δ= 的值； 若∆<0,输出“无实数根”； 若∆=0，计算求根公式 = =，输出“方程有两个相同的实数根 、 ”； 若Δ>0, 计算求根公式 = ， = ，输出“方程实数根为 、 ” 拓展链接 穷举算法也称枚举算法，指的是在求解过程中，先按照一定的顺序一一列举所有可能的解，然后用条件判断列举出的所有可能解是否为正确解。穷举法一般适合解决解集为离散的且范围明确的问题。 求解一元二次方程的根 第 ‹#› 页 2.算法的特征 有穷性。一个算法的处理必然是有限的。无论具体的操作步骤有多少，这个数必然是确定的。例如“计算斐波那契数列的前n个元素的过程”就符合有穷性；而“计算斐波那契的所有元素”就不符合有穷性。 可行性。算法执行者可以实施的，在现实环境中能在有限的时间内做到。 确定性。算法对于每个步骤的执行描述必须是明确的。 0个或多个输入。算法被实施时，一般从外部获取。若求解过程中，所有数据都是不变的并且已知，不必输入数据。 1个或多个输出。若算法没有输出，那么这个算法就没有意义。 第 ‹#› 页 问题与讨论 为防止用户账户被盗，在用户登录账户时，有些信息系统会限制输入密码的次数，一旦超出自限定次数，系统就会禁止输入并要求进行注册账户验证。 该输入密码算法结合上述算法，谈谈算法的特征在其中的具体体现。 【教材P40】 第 ‹#› 页 3.算法的要素 数据（明确参与计算的初始数据、运算是产生的中间数据以及代表问题解决的结果因素。） 运算（明确每一步的运算是什么） 控制转移。在算法执行过程中，有时需要根据数据或运算结果的特点进行不同的处理，这时就需要运用运算转移来执行不同的操作。 例如，洗衣机控制算法，不同的洗法，时间不同，漂洗的步骤也不同。 某种模式下，注水时，达到50升则停止，未达到则继续注水。分支结构（选择） 若漂洗次数未达到两次，则继续加水，重复漂处理。循环结构（重复实现某些操作） 第 ‹#› 页 2.1.2 算法的及描述 常见的算法描述有自然语言、流程图、伪代码、计算机程序设计语言等 用自然语言描述算法 停车场车位探测中的算法 分析：传感器每隔一段时间对车位进行探测，在某段时刻，若传感器测得结果为空车位，则将指示灯设置为绿灯，同时向区域控制器输出“空车位”的信息；否则，将指示灯设置为红色，同时向区域控制器输出“非空车位”的信息。 将传感器回传的数据作为输入数据，并进行数字化设定，若测得空车位，则用输入数值1来表示，否则用输入数值0来表示。因为该数据会发生变化，所以用边变量flag保存该输入数据。 自然描述语言如下： （1）输入变量flag的值。 （2）若flag的值为1，则设置指示灯为绿色，输出“空车位”；否则，设置指示灯为红色，输出“非空车位” 第 ‹#› 页 2.用流程图描述算法 表2.1.1 常见的流程图基本图形及其功能 图形 名称 功能 开始/结束符 表示算法的开始或结束 输入/输出框 表示算法中数据的输入或输出 处理框 表示算法中数据的运算处理 判断框 表示算法中的条件判断 流程线 表示算法中的流向 连接点 表示算法中的转接 图2.1.6 用流程图表示车位探测中的算法 第 ‹#› 页 习题练习 用“流程图”的方法来表示“辗转相除法”的过程 [x % y表示：x 除以 y所得的余数] 3.用伪代码描述算法 伪代码指的是一种比较直观简洁的、符号接近计算机程序代码的算法描述方式，其风格很像计算机程序设计语言，但又不是真正的可以被计算机理解的代码。伪代码的表示方法没有统一、严格的规定，只要定义合理、表达正确即可。 伪代码由于语法比较接近于计算机程序设计语言，所以描述的算法更加紧凑简练，也便于进一步转化为相应的计算机程序。 为今后使用的方便，在本书中对伪代码做如下的语法约定： （1）条件判断语句 格式1： If 条件 then （语句序列1） Else (语句序列2) 格式2：If 条件 then （语句序列1） 若条件成立，则执行语句序列1 若条件不成立，则执行语句序列2 若条件成立，则执行语句序列1； 若不成立，不需要执行特定处理。 第 ‹#› 页 （2）循环语句 格式：while 条件 （循环体） 先判断条件是否成立，若成立，则执行循环体 车位探测算法用伪代码表示如下： flag 车位探测结果； #将测得的当前车位状态值输入给变量flag If flag=1 then （指示灯绿色 输出 “空车位”） Else （指示灯红色 输出 “非空车位”） 第 ‹#› 页 4.用伪计算机程序设计语言描述算法 C++程序设计语言描述如下： void Main Window::on_pushButton_clicked() { int flag=ui->lineEdit->text().toInt(); if (flag==1) { ui->label_4->setStyleSheet(“color:green;”); ui->label_4->setText(“绿色”)； ui->label_5->setText(“空车位”)； } else { ui->label_4->setStyleSheet(“color:red;”); ui->label_4->setText(“红色”)； ui->label_5->setText(“非空车位”)； } } Phython程序设计语言描述如下： flag=int(input(“请输入车位状态值：”)) if flag==1: print(“绿色”) print(“空车位”) else： print(“红色”) print(“非空车位”) 第 ‹#› 页 思考与练习 ？ 1.用自然语言描述“高一新生报到流程”（如图2.1.1）对应的算法。 2.用智能电饭煲烧饭时，在算法的控制下，当饭烧熟时，智能电饭煲会自动停止高热烧饭，转为低热保温。这是因为锅底的温度传感器每隔一定时间（比如200毫秒）会将温度数据传送给算法，一旦发现温度数据达到103℃（此时锅中水被蒸发完），算法就会控制继电器释放触点没让电饭煲停止烧饭，转入低温保温模式。 图2.1.10 所示的流程图描述了某个时刻智能电饭煲根据输入的温度数据进行判断、处理的算法，则在流程图中① ____________ , ②____________(选填“变为低温保热”、“继续高热烧饭”) 教材：P48 第 ‹#› 页 第二章 算法与问题解决 算法与问题解决 算法的概念 算法的描述 用算法解决 问题的过程 算法的控制结构 定义 特征 要素 自然语言 流程图 伪代码 程序设计语言 顺序结构 分支结构 循环结构 抽象与建模 设计算法 描述算法 2.2 算法的控制结构 在算法程序中，无论内容如何复杂、功能如何强大的算法，也都由基本的结构组合而成，这些基本的结构称为算法的控制结构。算法的控制结构有三种，即顺序结构、分支机构和循环结构。 2.2.1 顺序结构 购买火车票 图2.2.1 网上购票的算法 图2.2.2 顺序结构算法的一般结构 第 ‹#› 页 2.2.2 分支结构 求解一元二次方程的解 细化 图2.2.4 从粗到细的算法细化 第 ‹#› 页 2.2.3 循环结构 在智能电饭煲烧饭的过程中，如果当前所测温度没有达到103℃，则算法会控制电饭煲继续高温烧饭，此时采用的是循环结构。 循环结构的重复执行（循环）并不是没有限制的，而是在条件控制下的一种可控的重复。当需要重复处理的条件不满足时，重复处理必须能及时结束。这样才符合算法的有穷性。 图2.2.5所示的算法在执行时，如果循环条件始终满足，那么循环体永远会被执行，此时算法陷入“死循环”，也就违背了算法的有穷性特征。 图2.2.5 循环结构算法的流程图 第 ‹#› 页 超市收银系统 一个完整的超市管理系统是由通信网络、计算机（包括服务端和客户端）、计算机程序等组合的综合系统。商品在超市上架之前会有一个数据录入环节，通过数据的录入，每隔商品的编码、数量、价格等数据会保存到超市管理系统的数据库中。收银过程中，扫描仪扫描条形码，本质上是将条形码对应的商品编码输入到计算机中，然后在以输入的编码为关键字，从已有的数据库中查找与之符合的商品数据并进行金额统计计算。 为方便上述算法的描述，可以事先做出一些符号化的设定。用code表示商品的编码，用sum表示顾客的总金额，用x表示每个商品的价格。 综上所述，解决该问题的算法可用如图2.2.7所示的流程图来描述。 拓展链接 程序设计中的“累加器” “累加器”指的是算法执行过程中对同类事物或数据进行统计计算的实现技术。上述算法中的“sum<--sum+x”就起到了累加的作用。 第 ‹#› 页 思考与练习 ？ 智能农业大棚通过传感器、控制器、网络设施和计算机程序等来实现大棚的自动化管理（如图2.2.9）。例如，自动温度控制系统中的温度传感器每隔一定时间采集大棚中的温度，一旦温度超过预设的最高温度40℃，控制系统会启动通风和喷水系统实现降温；如果温度低于预设温度18℃，控制系统会启动加热器，给大棚降温。 （1）自动温度控制系统进行温度控制的算法用流程图描述如图2.2.9所示，请完善该流程图，在①、②填入合适的内容。 图2.2.9 智能农业大棚温控系统的算法流程图 第 ‹#› 页 第二章 算法与问题解决 算法与问题解决 算法的概念 算法的描述 用算法解决 问题的过程 算法的控制结构 定义 特征 要素 自然语言 流程图 伪代码 程序设计语言 顺序结构 分支结构 循环结构 抽象与建模 设计算法 描述算法 2.3 用算法解决问题的过程 用计算机解决问题时，由于实际问题情境的复杂性，需要先对实际问题进行抽象与建模，再根据建立的计算模型设计算法，并将算法用合适的方式加以准确描述。 它能根据系统传递给它的走路步数给运动者奖励，运动者可以用累积的奖金去换取软件开发商提供的各种体育用品。具体的奖励规则如下： 每天走路的钱1000步，奖励0.3金，之后每2000步奖励0.1金，不足2000步没有奖励，每天最高奖励不超过3金。 每天必须到计步器页面，点击领奖按钮才能领取昨日走路奖金。 如果连续三天奖励成功，从第四天起走路奖金翻一倍。每天最高奖励不超过6金。翻倍期间，若有一天没有领奖（即连续每天领奖行为中断），则翻倍权益取消，重新连续三天领奖，成功才能继续翻倍。 “动动有奖”APP 第 ‹#› 页 第一步：抽象与建模 1.提炼核心要素并加以确定或假设 本问题的已知数据包含了每天走路的步数，以及每天是否成功领取前一天奖金的标记，因为这些数据在事先都是不确定的。所以需要通过输入将数据传递给算法。 不妨用变量X来表示每天走路的步数。 用F表示是否成功领取了每天的奖金。（1表示成功领取，0表示没有领取。） 需要统计的走路天数是不定的，所以用变量n来表示这个可变的数据。（一般性） 2.用数学符号描述解决问题的计算模型 目标:就是统计n天过去后，该用户一共拥有的”奖金”总数. 第 ‹#› 页 基于上述分析，可以解决该问题的计算模型如下： 已知n（1≤n≤30）组数据： ，计算“奖金”总和total. 其中 “ ”向下取整 如果有下列4组数据： 第一天：0.3+0.1 第二天：0.3+0.4 第三天：0.3+0.5(没领取) 第四天：3 则根据上述计算模型得到的“奖金”总和为4.1金。 第 ‹#› 页 第二步：设计算法 输入的数据是数据数量规模n以及n组 的值。 根据计算模型对每组 依次进行处理，由于处理的规律相同，所以可以采用循环结构来解决每一天的数据。 进一步细化： 输入总天数n。 输入天数的变量i初始化为1. 若i≤n，则转④，否则转⑦。 输入第i天的数据（包括第i天走路步数 ，是否成功领取第i天“奖金”记 ）。 根据当天输入的数据 ，统计该天领取的奖金并累加到总奖金total中。 表示天数的变量i增加1，然后转③。 输出变量total的值。 连续天数如何确定？ 第 ‹#› 页 第三步：描述算法 为了判断奖金是否翻倍，用变量c保存连续成功领取奖金的天数。 拓展链接 根据各种问题的模型特征提出了各种针对性的算法策略，如穷举算法、顺序查找算法、对分查找算法、冒泡查找算法、深度优先搜索法以及动态规划等。 第 ‹#› 页 思考与练习 ？ 上述算法中，“按照奖励规则第1条计算’奖金’t”在两个环节中出现，请根据算法功能完成下列练习。 （1）改进算法，使得算法中只有一个环节出现“按照奖励规则第1条计算’奖金’t”。 （2）请进一步细化原算法中的“按照奖励规则第1条计算’奖金’t”，并用流程图进行描述。 提示：通过判断框判断步数后，进入满足条件的If表达式。 第 ‹#› 页 作业：1.任意输入三个正整数，要求输出最小值的值。（流程图） 2.p58 《巩固与提高》 第 ‹#› 页 二十一世纪外国语学校 邹修鸿 第 ‹#› 页 $