2010届高三数学一轮复习必备精品15：算法的含义、程序框图

20092010 学年度高三数学（人教版 A 版）第一轮复习资料 第 15 讲 算法的含义、程序框图 一【课标要求】 1通过对解决具体问题过程与步骤的分析（如，二元一次方程组求解等问题），体会 算法的思想，了解算法的含义； 2通过模仿、操作、探索，经历通过设计程序框图表达解决问题的过程。在具体问题 的解决过程中（如，三元一次方程组求解等问题），理解程序框图的三种基本逻辑结构：顺 序、条件分支、循环 二【命题走向】 算法是高中数学课程中的新内容，本章的重点是算法的概念和算法的三种逻辑结构。 预测 2010 年高考对本章的考察是：以选择题或填空题的形式出现，分值在 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 本资料来自于资源最齐全的世纪教育网 21 世纪教育网 - 中国最大型、最专业的中小学教育资源门户网站。 版权所有21 世纪教育网 见示意图 （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 统筹法中“烧水泡茶”的故事； 测量某棵树的高度，判断其是否是大树； 已知三角形的一部分边长和角，借助正余弦定理求得剩余的边角，再利用三角形的面 积公式求出该三角形的面积 A1 B2 C3 D4 解析：正确选项为 C，中我们对 “树的大小”没有明确的标准，无法完成任务，不是 有效的算法构造。中，勾画了从济南到巴黎的行程安排，完成了任务；中，节约时间， 烧水泡茶完成了任务；中，纯数学问题，借助正、余弦定理解三角形，进而求出三角形的 面积。 点评：算法过程要做到能一步一步的执行，每一步执行的操作，必须确切，不能含混不 清，且在有限步后的必须得到问题的结果 题型 2：经典算法 例 3一个人带着三只狼和三只羚羊过河，只有一条船，同船可容纳一个人和两只动物， 没有人在的时候，如果狼的数量不少于羚羊的数量就会吃羚羊。该人如何将动物转移过河？ 请设计算法？ 解析：任何动物同船不用考虑动物的争斗但需考虑承载的数量，还应考虑到两岸的动物 都得保证狼的数量要小于羚羊的数量，故在算法的构造过程中尽可能保证船里面有狼，这样 才能使得两岸的羚羊数量占到优势，具体算法如下： 算法步骤： 第一步：人带两只狼过河，并自己返回； 第二步：人带一只狼过河，自己返回； 第三步：人带两只羚羊过河，并带两只狼返回； 第四步：人带一只羊过河，自己返回； 第五步：人带两只狼过河 点评：算法是解决某一类问题的精确描述，有些问题使用形式化、程序化的刻画是最恰 当的。这就要求我们在写算法时应精练、简练、清晰地表达，要善于分析任何可能出现的情 况，体现思维的严密性和完整性。本题型解决问题的算法中某些步骤重复进行多次才能解决， 在现实生活中，很多较复杂的问题经常遇到这样的问题，设计算法的时候，如果能够合适地 利用某些步骤的重复，不但可以使得问题变得简单，而且可以提高工作效率。 例 4这是中国古代的一个著名算法案例：一群小兔一群鸡，两群合到一群里，要数腿 48，要数脑袋 17，多少小兔多少鸡？ 解析：求解鸡兔的问题简单直观，却包含着深刻的算法思想。应用解二元一次方程组的 方法来求解鸡兔同笼问题 第一步：设有小鸡 x 只，小兔 y 只，则有 )2(48217yx 第二步：将方程组中的第一个方程两变乘2 加到第二个方程中去，得到 ，得到 y=7；21748)(yx 第三步：将 y=7 代入（1）得 x=10。 点评：解决这些问题的基本思想并不复杂，很清晰，但叙述起来很烦琐，有的步骤非常 本资料来自于资源最齐全的世纪教育网 21 世纪教育网 - 中国最大型、最专业的中小学教育资源门户网站。 版权所有21 世纪教育网 多，有的计算量很大，有时候完全依靠人力完成这些工作很困难。但是这些恰恰是计算机的 长处，它能不厌其烦的枯燥的、重复的、繁琐的工作。但算法也有优劣，我们要追求高效。 题型 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设计算法判断一元二次方程 是否有实数根，并画出相应的程序框02cbxa 图。 解析：算法步骤如下： 第一步：输入一元二次方程的系数：a，b，c； 第二步：计算 的值；acb42 第三步：判断0 是否成立。若0 成立，输出“方程有实 根” ；否则输出“方程无实根” 。结束算法。 开始 P=10000 P=100001.03=10300 P=103001.03=10609 P=106091.03=10927.27 P=10927.271.03=11255.09 结束 输出 P 本资料来自于资源最齐全的世纪教育网 21 世纪教育网 - 中国最大型、最专业的中小学教育资源门户网站。 版权所有21 世纪教育网 相应的程序框图如下： 点评：根据一元二次方程的意 义，需要计算判别式 的值。再分成两种情况acb42 处理：（1）当0 时，一元二次 方程有实数根；（2）当0 时， 一元二次方程无实数根。该问题实 际上是一个分类讨论问题，根据一 元二次方程系数的不同情况，最后 结果就不同。因而当给出一个一元 二次方程时，必须先确定判别式的 值，然后再用判别式的值的取值情 况确定方程是否有解。该例仅用顺 序结构是办不到的，要对判别式的 值进行判断，需要用到条件结构 (2009 年广东卷文)某篮球队 6 名主力队员在最近三场比赛中投进的三分球个数如下表所示： 队员 i 1 2 3 4 5 6 三分球个数 aaa 下图（右）是统计该 6 名队员在最近三场比赛中投进的三分球总数的程序框图，则图中判 断框应填 ，输出的 s= (注：框图中的赋值符号“=”也可以写成“”或“：=”) 【解析】顺为是统计该 6 名队员在最近三场比赛中投进的三分球总数的程序框图，所图中 判断框应填 i，输出的 s= 126a . Y N 结 束 开始 输入 a,b,c 0？ 输出无实根输出有实根 =b 24ac 答案 6i, 126a 例 8（1）设计算法，求 的解，并画出流程图。0bx 解析：对于方程 来讲，应该分情况讨论方程的解 我们要对一次项系数 a 和常数项 b 的取值情况进行分类，分类如下： （1）当 a0 时，方程有唯一的实数解是 ；a （2）当 a=0，b=0 时，全体实数都是方程的解； （3）当 a=0，b0 时，方程无解 联想数学中的分类讨论的处理方式。可得如下算法步骤： 第一步：判断 a 是否不为零。若成立，输出结果“解为 ”；ab 第二步：判断 a=0，b=0 是否同时成立。若成立，输出结果“解集为 R”； 第三步：判断 a=0，b0 是否同时成立。若成立，输出结果“方程无解”，结束。 程序框图： （2）。设计算法，找出输入的三个不相等实数 a、b、c 中的最大值，并画出流程图。 解析：算法步骤： 第一步：输入 a，b，c 的值； 第二步：判断 ab 是否成立，若成立，则执行第三步；否则执行第四步； 第三步：判断 ac 是否成立，若成立，则输出 a，并结束；否则输出 c，并结束； 第四步：判断 bc 是否成立，若成立，则输出 b，并结束；否则输出 c，并结束。 程序框图： Y Y a0? a=0,b=0? a=0,b0? 开始 输出解为 ab 输出解集为 R 输出方程无解 结束 Y N N N 输入 a，b 开始 a b? 输出 a 结束 N a c? Y 输出 c b c? 输出 b 输出 c Y Y N N 输入 a,b,c 本资料来自于资源最齐全的世纪教育网 21 世纪教育网 - 中国最大型、最专业的中小学教育资源门户网站。 版权所有21 世纪教育网 点评：条件结构嵌套与条件结构叠加的区别是： （1）条件结构叠加，程序执行时需依次对“条件 1”、 “条件 2”、 “条件 3”都进行判断只有遇到能满足的条件才执行该条件对应 的操作 （2）条件结构的嵌套中， “条件 2”是“条件 1”的一个分支， “条件 3”是“条件 2”的一个分支，依此类推，这些条件中很 多在算法执行过程中根据所处的分支位置不同可能不被执行。 （3）条件结构嵌套所涉及的“条件 2”、“条件 3”是在前面的所有条件依次一个 一个的满足“分支条件成立”的情况下才能执行的此操作，是多个条件同时成立的叠加和复 合。 题型 5：循环结构 例 9设计一个算法，求 的值，并划出程序框图。492.421 解析：算法步骤： 第一步：sum=0； 第二步：i=0； 第三步：sum=sum+2 i； 第四步：i=i+1； 第五步：判断 i 是否大于 49，若成立，则输出 sum，结束；否则返回第三步重新执行。 程序框图： 结 束 开始 i49？ 输出 sum sum=0,i=0 sum=sum+2i i=i+1 N Y 点评： 1如果算法问题里涉及的运算进行了许多次重复的操作，且先 后参与运算的数之间有相同的规律，就可引入变量循环参与运算（我 们称之为循环变量） ，应用于循环结构。在循环结构中，要注意根据 条件设计合理的计数变量、累加和累乘变量及其个数等，特别要求条 件的表述要恰当、精确 2累加变量的值初始值一般取成 0，而累乘变量的初始值一般取成 1。 例 10相传古代的印度国王要奖赏国际象棋的发明者，问他需要什么。发明者说：陛下， 在国际象棋的第一个格子里面放 1 粒麦子，在第二个格子里面放 2 粒麦子，第三个格子放 4 粒麦子，以后每个格子中的麦粒数都是他前一个格子中麦粒数的二倍，依此类推（国际象棋 棋盘共有 64 个格子）。请将这些麦子赏给我，我将感激不尽。国王想这还不容易，就让人 扛了一袋小麦，但不到一会儿就没了，最后一算结果，全印度一年生产的粮食也不够。国王 很奇怪，小小的“棋盘”，不足 100 个格子，如此计算怎么能放这么多麦子？试用程序框图 表示一下算法过程。 解析：将实际问题转化为数学模型，该问题就是来求 的和632.421 结 束 开始 i64？ 输出 sum sum=0,i=0 sum=sum+2i i=i+1 N Y 本资料来自于资源最齐全的世纪教育网 21 世纪教育网 - 中国最大型、最专业的中小学教育资源门户网站。 版权所有21 世纪教育网 点评：对于开放