高考数学一轮复习精品学案：第15讲 算法的含义、程序框图

高考数学一轮复习精品学案：第15讲 算法的含义、程序框图

2013 年普通高考数学科一轮复习精品学案 第 15 讲 算法的含义、程序框图 一．课标要求： 1．通过对解决具体问题过程与步骤的分析（如，二元一次方程组求解等问题），体会 算法的思想，了解算法的含义； 2．通过模仿、操作、探索，经历通过设计程序框图表达解决问题的过程。在具体问题 的解决过程中（如，三元一次方程组求解等问题），理解程序框图的三种基本逻辑结构：顺 序、条件分支、循环。 二．命题走向 算法是高中数学课程中的新内容，本章的重点是算法的概念和算法的三种逻辑结构。 预测 2013 年高考对本章的考察是：以选择题或填空题的形式出现，分值在 5 分左右， 考察的热点是算法的概念。 三．要点精讲 1．算法的概念 （1）算法的定义：广义的算法是指完成某项工作的方法和步骤，那么我们可以说洗衣 机的使用说明书是操作洗衣机的算法，菜谱是做菜的算法等等。 在数学中，现代意义的算法是指可以用计算机来解决的某一类问题的程序和步骤，这些 程序或步骤必须是明确和有效的，而且能够在有限步之内完成。 （2）算法的特征：①确定性：算法的每一步都应当做到准确无误、“不重不漏”。“不重” 是指不是可有可无的、甚至无用的步骤，“不漏” 是指缺少哪一步都无法完成任务。②逻辑 性：算法从开始的“第一步”直到“最后一步”之间做到环环相扣。分工明确，“前一步”是“后 一步”的前提， “后一步”是“前一步”的继续。③有穷性：算法要有明确的开始和结束，当到 达终止步骤时所要解决的问题必须有明确的结果，也就是说必须在有限步内完成任务，不能 无限制的持续进行。 （3）算法的描述：自然语言、程序框图、程序语言。 2．程序框图 （1）程序框图的概念：程序框图又称流程图，是一种用规定的图形、指向线及文字说 明来准确、直观地表示算法的图形； （2）构成程序框的图形符号及其作用 程序框 名称 功能 起止框 表示一个算法的起始和结束，是任何算法 程序框图不可缺少的。 输入、输出框 表示一个算法输入和输出的信息，可用在 算法中任何需要输入、输出的位置。 处理框 赋值、计算。算法中处理数据需要的算式、 公式等，它们分别写在不同的用以处理数 据的处理框内。 判断框 判断某一条件是否成立，成立时在出口处 标明“是”或“Y”；不成立时在出口处标明则 标明“否”或“N”。 流程线 算法进行的前进方向以及先后顺序 循环框 用来表达算法中重复操作以及运算 连结点 连接另一页或另一部分的框图 注释框 帮助编者或阅读者理解框图 （3）程序框图的构成 一个程序框图包括以下几部分：实现不同算法功能的相对应的程序框；带箭头的流程线； 程序框内必要的说明文字。 3．几种重要的结构 （1）顺序结构 顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行 的。它是由若干个依次执行的步骤组成的，它是任何一个算法都离不开的一种基本算法结构。 见示意图和实例： 顺序结构在程序框图中的体现就是用流程线将程序框自上而下地连接起来，按顺序执行 算法步骤。如在示意图中，A 框和 B 框是依次执行的，只有在执行完 A 框指定的操作后， 才能接着执行 B 框所指定的操作。 （2）条件结构 如下面图示中虚线框内是一个条件结构，此 结构中含有一个判断框，算法执行到此判断给定 的条件 P 是否成立，选择不同的执行框（A 框、 B 框）。无论 P 条件是否成立，只能执行 A 框 或 B 框之一，不可能既执行 A 框又执行 B 框， 也不可能 A 框、B 框都不执行。A 框或 B 框中可 以有一个是空的，即不执行任何操作。 见示意图 A B 示意图 输入 n flag=1 p A B Y N （3）循环结构 在一些算法中要求重复执行同一操作的结构称为循环结构。即从算法某处开始，按照一 定条件重复执行某一处理过程。重复执行的处理步骤称为循环体。 循环结构有两种形式：当型循环结构和直到型循环结构。 ①当型循环结构，如左下图所示，它的功能是当给定的条件 P 成立时，执行 A 框，A 框执行完毕后，返回来再判断条件 P 是否成立，如果仍然成立，返回来再执行 A 框，如此 反复执行 A 框，直到某一次返回来判断条件 P 不成立时为止，此时不再执行 A 框，离开循 环结构。继续执行下面的框图。 ②直到型循环结构，如右下图所示，它的功能是先执行重复执行的 A 框，然后判断给 定的条件 P 是否成立，如果 P 仍然不成立，则返回来继续执行 A 框，再判断条件 P 是否成 立。以次重复操作，直到某一次给定的判断条件 P 时成立为止，此时不再返回来执行 A 框， 离开循环结构。继续执行下面的框图。 见示意图 四．典例解析 题型 1：算法概念 例 1．下列说法正确的是（ ） A．算法就是某个问题的解题过程； B．算法执行后可以产生不同的结果； C．解决某一个具体问题算法不同结果不同； D．算法执行步骤的次数不可以为很大，否则无法实施。 解析：答案为选项 B；选项 B，例如：判断一个整数是否为偶数，结果为“是偶数”和“不 是偶数”两种；选项 A ，算法不能等同于解法；选项 C，解决某一个具体问题算法不同结果 应该相同，否则算法构造的有问题；选项 D，算法可以为很多次，但不可以无限次。 点评：算法一般是机械的，有时需要进行大量的重复计算。只要按部就班去做，总能算 出结果。通常把算法过程称为“数学机械化”。数学机械化的最大优点是它可以借助计算机来 完成；实际上处理任何问题都需要算法。如：中国象棋有中国象棋的棋谱、走法、胜负的评 判准则；而国际象棋有国际象棋的棋谱、走法、胜负的评判准则；再比如申请出国有一系列 的先后手续，购买物品也有相关的手续……。 例 2．下列语句中是算法的个数为（ ） ①从济南到巴黎：先从济南坐火车到北京，再坐飞机到巴黎； ②统筹法中“烧水泡茶”的故事； A 成立 不成立 P 当型循环结构 直到型循环结构 成立 不成立P A ③测量某棵树的高度，判断其是否是大树； ④已知三角形的一部分边长和角，借助正余弦定理求得剩余的边角，再利用三角形的面 积公式求出该三角形的面积。 A．1 B．2 C．3 D．4 解析：正确选项为 C，③中我们对“树的大小”没有明确的标准，无法完成任务，不是有 效的算法构造。①中，勾画了从济南到巴黎的行程安排，完成了任务；②中，节约时间，烧 水泡茶完成了任务；④中，纯数学问题，借助正、余弦定理解三角形，进而求出三角形的面 积。 点评：算法过程要做到能一步一步的执行，每一步执行的操作，必须确切，不能含混不 清，且在有限步后的必须得到问题的结果。 题型 2：经典算法 例 3．一个人带着三只狼和三只羚羊过河，只有一条船，同船可容纳一个人和两只动物， 没有人在的时候，如果狼的数量不少于羚羊的数量就会吃羚羊。该人如何将动物转移过河？ 请设计算法？ 解析：任何动物同船不用考虑动物的争斗但需考虑承载的数量，还应考虑到两岸的动物 都得保证狼的数量要小于羚羊的数量，故在算法的构造过程中尽可能保证船里面有狼，这样 才能使得两岸的羚羊数量占到优势，具体算法如下： 算法步骤： 第一步：人带两只狼过河，并自己返回； 第二步：人带一只狼过河，自己返回； 第三步：人带两只羚羊过河，并带两只狼返回； 第四步：人带一只羊过河，自己返回； 第五步：人带两只狼过河。 点评：算法是解决某一类问题的精确描述，有些问题使用形式化、程序化的刻画是最恰 当的。这就要求我们在写算法时应精练、简练、清晰地表达，要善于分析任何可能出现的情 况，体现思维的严密性和完整性。本题型解决问题的算法中某些步骤重复进行多次才能解决， 在现实生活中，很多较复杂的问题经常遇到这样的问题，设计算法的时候，如果能够合适地 利用某些步骤的重复，不但可以使得问题变得简单，而且可以提高工作效率。 例 4．这是中国古代的一个著名算法案例：一群小兔一群鸡，两群合到一群里，要数腿 48，要数脑袋 17，多少小兔多少鸡？ 解析：求解鸡兔的问题简单直观，却包含着深刻的算法思想。应用解二元一次方程组的 方法来求解鸡兔同笼问题。 第一步：设有小鸡 x 只，小兔 y 只，则有      )2(4842 )1(17 yx yx 第 二 步 ： 将 方 程 组 中 的 第 一 个 方 程 两 变 乘 － 2 加 到 第 二 个 方 程 中 去 ， 得 到      21748)24( 17 y yx ，得到 y=7； 第三步：将 y=7 代入（1）得 x=10。 点评：解决这些问题的基本思想并不复杂，很清晰，但叙述起来很烦琐，有的步骤非常 多，有的计算量很大，有时候完全依靠人力完成这些工作很困难。但是这些恰恰是计算机的 长处，它能不厌其烦的枯燥的、重复的、繁琐的工作。但算法也有优劣，我们要追求高效。 题型 3：顺序结构 例 5．写出通过尺轨作图确定线段 AB 一个 5 等分点的算法。 解析：我们借助于平行线定理，把位置的比例关系变成已知的比例关系，只要按照规则 一步一步去做就能完成任务。 算法分析： 第一步：从已知线段的左端点 A 出发，任意作一条与 AB 不平行的射线 AP； 第二步：在射线上任取一个不同于端点 A 的点 C，得到线段 AC； 第三步：在射线上延 AC 的方向截取线段 CE=AC； 第四步：在射线上延 AC 的方向截取线段 EF=AC； 第五步：在射线上延 AC 的方向截取线段 FG=AC； 第六步：在射线上延 AC 的方向截取线段 GD=AC，那么线段 AD=5AB； 第七步：连接 DB； 第八步：过 C 作 BD 的平行线，交线段 AB 于 M，这样点 M 就是线段 AB 的一个 5 等分点。 程序框图： 点评：这个算法步骤具有一般性，对于任意自然数 n，都可以按照这个算法的思想，设 计出确定线段的 n 等分点的步骤，解决问题。 例 6．有关专家建议，在未来几年内，中国的通货膨胀率保持在 3%左右，这将对我国 经济的稳定有利无害。所谓通货膨胀率为 3%，指的是每年消费品的价格增长率为 3%。在 这种情况下，某种品牌的钢琴 2004 年的价格是 10 000 元，请用流程图描述这种钢琴今后四 年的价格变化情况，并输出四年后的价格。 解析：用 P 表示钢琴的价格，不难看出如下算法步骤： 2005 年 P=10000×（1+3%）=10300； 2006 年 P=10300×（1+3%）=10609； 2007 年 P=10609×（1+3%）=10927.27； 2008 年 P=10927.27×（1+3%）=11255.09； 因此，价格的变化情况表为： 开始 从 A 点出发作一条与 AB 不平行射线 AC 在射线上任取一个不同于端点 A 的点 C，取 AC 为单位线段， 再在 AC 上顺次取点 E、F、G、D，满足 CE=EF=FG=GD=AC 连结 BD 过点 C 作 BD 的平行线交 AB 于点 M，点 M 即为 5 等分点 结束 年份 2004 2005 2006 2007 2008 钢琴的价格 10000 10300 10609 10927.27 11255.09 程序框图为： 点评：顺序结构只须严格按照传统的解决数学问题的解题思路，将问题解决掉。最后将 解题步骤 “细化”就可以。“细化”指的是写出算法步骤、画出程序框图。 题型 4：条件结构 例 7．设计算法判断一元二次方程 02  cbxax 是否有实数根，并画出相应的程序 框图。 解 析 ： 算 法 步 骤 如 下 ： 第 一 步 ：输 入 一 元 二 次 方 程 的 系 数 ： a， b， c； 第二步：计算△ acb 42  的值； 第 三 步 ：判 断 △≥0 是 否 成 立 。 若 △≥0 成 立 ， 输 出 “方 程 有 实 根 ”；否 则 输 出 “方 程 无 实 根 ”。 结 束 算 法 。 相应的程序框图如下： 开始 P=10000 P=10000×1.03=10300 P=10300×1.03=10609 P=10609×1.03=10927.27 P=10927.27×1.03=11255.09 结束 输出 P Y N 结 束 开始 输入 a,b,c △≥0？ 输出无实根输出有实根 △=b2－4ac 点评：根据一元二次方程的意义，需要计算判别式△ acb 42  的值。再分成两种情 况处理：（1）当△≥0 时，一元二次方程有实数根；（2）当△＜0 时，一元二次方程无实数 根。该问题实际上是一个分类讨论问题，根据一元二次方程系数的不同情况，最后结果就不 同。因而当给出一个一元二次方程时，必须先确定判别式的值，然后再用判别式的值的取值 情况确定方程是否有解。该例仅用顺序结构是办不到的，要对判别式的值进行判断，需要用 到条件结构。 例 8．（1）设计算法，求 0 bax 的解，并画出流程图。 解析：对于方程 0 bax 来讲，应该分情况讨论方程的解。 我们要对一次项系数 a 和常数项 b 的取值情况进行分类，分类如下： （1）当 a≠0 时，方程有唯一的实数解是 a b ； （2）当 a=0，b=0 时，全体实数都是方程的解； （3）当 a=0，b≠0 时，方程无解。 联想数学中的分类讨论的处理方式。可得如下算法步骤： 第一步：判断 a 是否不为零。若成立，输出结果“解为 a b ”； 第二步：判断 a=0，b=0 是否同时成立。若成立，输出结果“解集为 R”； 第三步：判断 a=0，b≠0 是否同时成立。若成立，输出结果“方程无解”，结束。 程序框图： （2）。设计算法，找出输入的三个不相等实数 a、b、c 中的最大值，并画出流程图。 解析：算法步骤： 第一步：输入 a，b，c 的值； Y Y a≠0? a=0,b=0? a=0,b≠0? 开始 输出解为 a b 输出解集为 R 输出方程无解 结束 Y N N N 输入 a，b 第二步：判断 a>b 是否成立，若成立，则执行第三步；否则执行第四步； 第三步：判断 a>c 是否成立，若成立，则输出 a，并结束；否则输出 c，并结束； 第四步：判断 b>c 是否成立，若成立，则输出 b，并结束；否则输出 c，并结束。 程序框图： 点 评 ： 条 件 结 构 嵌 套 与 条 件 结 构 叠 加 的 区 别 是 ： （ 1）条 件 结 构 叠 加 ，程 序 执 行 时 需 依 次 对 “条 件 1”、“条 件 2”、“条 件 3”…… 都 进 行 判 断 只 有 遇 到 能 满 足 的 条 件 才 执 行 该 条 件 对 应 的 操 作 。 （ 2）条 件 结 构 的 嵌 套 中 ，“条 件 2”是 “条 件 1”的 一 个 分 支 ，“条 件 3”是 “条 件 2”的 一 个 分 支 ，……依 此 类 推 ，这 些 条 件 中 很 多 在 算 法 执 行 过 程 中 根 据 所 处 的 分 支 位 置 不 同 可 能 不 被 执 行 。 （3）条件结构嵌套所涉及的“条件 2”、“条件 3”……是在前面的所有条件依次一个一个 的满足“分支条件成立”的情况下才能执行的此操作，是多个条件同时成立的叠加和复合。 题型 5：循环结构 例 9．设计一个算法，求 492..........421  的值，并划出程序框图。。 解析：算法步骤： 第一步：sum=0； 第二步：i=0； 第三步：sum=sum+2i； 第四步：i=i+1； 第五步：判断 i 是否大于 49，若成立，则输出 sum，结束；否则返回第三步重新执行。 程序框图： 开始 a > b? 输出 a 结束 N a > c? Y 输出 c b >c? 输出 b 输出 c Y Y N N 输入 a,b,c 点 评 ： 1． 如 果 算 法 问 题 里 涉 及 的 运 算 进 行 了 许 多 次 重 复 的 操 作 ， 且 先 后 参 与 运 算 的 数 之 间 有 相 同 的 规 律 ，就 可 引 入 变 量 循 环 参 与 运 算（ 我 们 称 之 为 循 环 变 量 ）， 应 用 于 循 环 结 构 。 在 循 环 结 构 中 ， 要 注 意 根 据 条 件 设 计 合 理 的 计 数 变 量 、 累 加 和 累 乘 变 量 及 其 个 数 等 ， 特 别 要 求 条 件 的 表 述 要 恰 当 、 精 确 。 2．累加变量的值初始值一般取成 0，而累乘变量的初始值一般取成 1。 例 10．相传古代的印度国王要奖赏国际象棋的发明者，问他需要什么。发明者说：陛 下，在国际象棋的第一个格子里面放 1 粒麦子，在第二个格子里面放 2 粒麦子，第三个格子 放 4 粒麦子，以后每个格子中的麦粒数都是他前一个格子中麦粒数的二倍，依此类推（国际 象棋棋盘共有 64 个格子）。请将这些麦子赏给我，我将感激不尽。国王想这还不容易，就 让人扛了一袋小麦，但不到一会儿就没了，最后一算结果，全印度一年生产的粮食也不够。 国王很奇怪，小小的“棋盘”，不足 100 个格子，如此计算怎么能放这么多麦子？试用程序框 图表示一下算法过程。 解析：将实际问题转化为数学模型，该问题就是来求 632.......421  的和 结 束 开始 i>49？ 输出 sum=0,i=0 sum=sum+2i i=i+1 N Y 开始 i≥64？ 输出 sum=0,i=0 sum=sum+2i i=i+1 N Y 点评：对于开放探究问题，我们可以建立数学模型（上面的题目要与等比数列的定义、 性质和公式联系起来）和过程模型来分析好算法，通过设计算法以及语言的描述选择一些成 熟的办法进行处理。像上面应用到了等比数列的通项公式和前 n 项和公式。 五．思维总结 描述算法可以用不同的方式。例如：可以用自然语言和数学语言加以叙述，也可以借助 形式语言（算法语言）给出精锐的说明，也可以用程序框图直观的显示算法全貌。 1．自然语言 自然语言就是人们日常使用的语言，可以是人之间来交流的语言、术语等，通过分步的 方式来表达出来的解决问题的过程。 其优点为：好理解，当算法的执行都是先后顺序时比较容易理解； 缺点是：表达冗长，且不易表达清楚步骤间的重复操作、分情况处理现象、先后顺序等 问题。 2．程序框图 程序框图是用规定的图形符号来表达算法的具体过程。 优点是：简捷形象、步骤的执行方向直观明了。 3．程序语言 程序语言是将自然语言和框图所表达的解决问题的步骤用特定的计算机所识别的低级 和高级语言编写而成。特点：能在计算机上执行，但格式要求严格。 程 序 框 图 1． 学 习 这 部 分 知 识 的 时 候 ， 要 掌 握 各 种 图 形 的 形 状 、 作 用 以 及 使 用 规 则 2． 画 程 序 框 图 的 规 则 如 下 ： （ 1） 一 个 完 整 的 程 序 框 图 必 须 有 起 止 框 ， 用 来 表 示 程 序 的 开 始 和 结 束 。 （2）使用标准的图形符号表示操作，带箭头的流程线表示算法步骤的先后顺序，框图 一般按从上到下、从左到右的方向画。 （3）算法中间要处理数据或计算，可分别写在不同的处理框中。 （4）如果一个流程由于纸面等原因需要分开画。要在断开处画上连结点，并标出连结 的号码。如图一。实际上它们是同一点，只是化不才分开画。用连结点可避免流程线的交叉 或过长，使流程图清晰。 （5）注释框不是流程图必需的部分，只是为了提示用户一部分框图的作用以及对某些 框图的操作结果进行说明。它帮助阅读流程图的用户更好的理解流程图的来龙去脉。 （6）在图形符号内用于描述的语言要非常简练清楚。