高考数学一轮讲义—算法的含义、程序框图 11页

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