2021年算法与程序框图.pdf

算法与程序框图【学习目标】1.初步建立算法的概念；2 .让学生通过丰富的实例体会算法的思想；3 .让学生通过对具体问题的探究，初步了解算法的含义；4.掌握程序框图的概念；5 .会用通用的图形符号表示算法，掌握算法的三个基本逻辑结构；6 .掌握画程序框图的基本规则，能正确画出程序框图.【要点梳理】要点一、算法的概念1、算法的定义：广义的算法是指完成某项工作的方法和步骤，那么我们可以说洗衣机的使用说明书是操作洗衣机的算法，菜谱是做菜的算法等等.在数学中，现代意义的算法是指可以用计算机来解决的某一类问题的程序和步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成.2、算法的特征：（1）确定性：算法的每一步都应当做到准确无误、不重不漏”.“不重”是指不是可有可无的、甚至无用的步骤，“不漏”是指缺少哪一步都无法完成任务.（2）逻辑性：算法从开始的“第一步”直到“最后一步”之间做到环环相扣，分工明确，“前一步”是“后一步”的前提，“后一步”是“前一步”的继续.（3）有穷性：算法要有明确的开始和结束，当到达终止步骤时所要解决的问题必须有明确的结果，也就是说必须在有限步内完成任务，不能无限制的持续进行.（4）不唯一性：求解某一个问题的算法不一定是唯一的，对于一个问题可以有不同的算法.3、设计算法的要求（1）写出的算法，必须能解决一类问题（如：判断一个整数3 5是否为质数；求任意一个方程的近似解），并且能够重复使用.（2）要使算法尽量简单、步骤尽量少.（3）要保证算法正确.且计算机能够执行，如：让计算机计算1 X 2 X 3 X 4 X 5是可以做到的.4、算法的描述：（1）自然语言：自然语言就是人们日常使用的语言，可以是汉语、英语或数学语言等.用自然语言描述算法的优点是通俗易懂，当算法中的操作步骤都是顺序执行时比较容易理解.缺点是如果算法中包含判断和转向，并且操作步骤较多时，就不那么直观清晰了.（2）程序框图：所谓框图，就是指用规定的图形符号来描述算法，用框图描述算法具有直观、结构清晰、条理分明、通俗易懂、便于检查修改及交流等特点.（3）程序语言：算法最终可以通过程序的形式编写出来，并在计算机上执行.要点诠释：算法的特点：思路简单清晰，叙述复杂，步骤繁琐，计算量大，完全依靠人力难以完成，而这些恰恰就是计算机的特长，它能不厌其烦地完成枯燥的、重复的繁琐的工作，正因为这些，现代算法的作用之一就是使计算机代替人完成某些工作，这也是我们学习算法的重要原因之一.事实上，算法中出现的程序只是用基本的语句把程序的主要结构描述出来，与真正的程序还有差距,所以算法描述的许多程序并不能直接运行，要运行程序，还要把程序按照某种语言的严格要求重新改写才行.要点二、程序框图1、程序框图的概念：程序框图又称流程图，是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形.2、构成程序框的图形符号及其作用程序框名称功能-起止框表程示序一框个图算不法可缺的少起的始.和结束，是任何算法L J输入、输出框表示一个算法输入和输出的信息，可用在算法中任何需要输入、输出的位置.处理框赋值、计算.算法中处理数据需要的算式、公式等，它们分别写在不同的用以处理数据的处理框内.O判断框判断某一条件是否成立，成立时在出口处标 明“是 或 Y”；不成立时在出口处则标 明“否”或“N”.V流程线算法进行的前进方向以及先后顺序O连结点连接另一页或另一部分的框图3,程序框图的构成一个程序框图包括以下几部分：实现不同算法功能的相对应的程序框；带箭头的流程线；程序框内必要的说明文字.4、算法的三种基本逻辑结构.(1)顺序结构顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的.它是由若干个依次执行的步骤组成的，它是任何一个算法都离不开的一种基本算法结构.见示意图和实例：顺序结构在程序框图中的体现就是用流程线将程序框自上而下地连接起来，按顺序执行算法步骤.如在示意图中，A框和B 框是依次执行的，只有在执行完A 框指定的操作后，才能接着执行B 框所指定的操作.(2)条件结构如下面图示中虚线框内是一个条件结构，此结构中含有一个判断框，算法执行到此判断给定的条件P是否成立，选择不同的执行框(A框、B框).无 论P条件是否成立，只能执行A框或B框之一，不可能既执行A框又执行B框，也不可能A框、B框都不执行.A框或B框中可以有一个是空的，即不执行任何操作.见示意图AB要点诠释：条件结构中的条件要准确，不能含混不清，要清楚在什么情况下需要作怎样的判断，用什么条件来区分.(3)循环结构在一些算法中要求重复执行同一操作的结构称为循环结构.即从算法某处开始，按照一定条件重复执行某一处理过程.重复执行的处理步骤称为循环体.循环结构有两种形式：当型循环结构和直到型循环结构.当型循环结构，如左下图所示，它的功能是当给定的条件P成立时，执行A框，A框执行完毕后，返回来再判断条件P是否成立，如果仍然成立，返回来再执行A框，如此反复执行A框，直到某一次返回来判断条件P不成立时为止，此时不再执行A框，离开循环结构，继续执行下面的框图.直到型循环结构，如右下图所示，它的功能是先执行重复执行的A框，然后判断给定的条件P是否成立，如果P仍然不成立，则返回来继续执行A框，再判断条件P是否成立，依次重复操作，直到某一次给定的判断条件P成立为止，此时不再返回来执行A框，离开循环结构，继续执行下面的框图.当型循环结构直到型循环结构要点诠释：循环结构中使用什么样的条件控制循环的开始和结束，要清楚满足某个条件的变量的次数与循环次数的联系与区别.误区提醒1、框图中的流程线不能出现交叉的现象.若有交叉，则程序语句无法写出；2、各种框图有其固定的格式和作用，不要乱用.如条件结构中不要忘了“是”与“否”，流程线不要忘记画箭头；3、条件分支结构的方向要准确；4、循环结构中，计数变量要赋初值，计数变量的自加不要忘记，自加多少不能弄错.另外计数变量一般只负责计数任务；5、循环结构中循环的次数要严格把握，区 分 与 等.循 环 变 量 的 取 值 与 循 环 结 构（当型与直到型）有关，需区分清楚.另外，同一问题用两种不同的结构解决时，其判断条件恰是相反的；6、程序框图不要出现死循环（无限步的循环）.【典型例题】类型一：算法的概念例 1.下列对算法的理解不正确的是（）A.算法有一个共同特点就是对一类问题都有效（而不是个别问题）B.算法要求一步步执行，且每一步都能得到唯一的结果C.算法一般是机械的，有时要进行大量重复的计算，它的优点是一种通法D.任何问题都可以用算法来解决【参考答案】D【详细解答】算法是解决问题的精确的描述，但是并不是所有问题都有算法.【总结升华】算法一般是机械的，有时需要进行大量的重复计算，只要按部就班去做，总能算出结果.通常把算法过程称为“数学机械化”，数学机械化的最大优点是它可以借助计算机来完成.实际上处理任何问题都需要算法，如：中国象棋有中国象棋的棋谱、走法、胜负的评判准则；而国际象棋有国际象棋的棋谱、走法、胜负的评判准则；再比如申请出国有一系列的先后手续，购买物品也有相关的手续.举一反三：【变 式 1 我们已学过的算法有求解一元二次方程的求根公式，加减消元法求二元一次方程组的解，二分法求出函数的零点等，对算法的描述有：对一类问题都有效；算法可执行的步骤必须是有限的；算法可以一步一步地进行，每一步都有确切的含义；是一种通法，只要按部就班地做，总能得到结果.以上算法的描述正确的有（）.A.1个 B.2 个 C.3 个 D.4 个【参考答案】D【变式2】下列哪个不是算法的特征（）A.抽象性 B.精确性 C.有穷性 D.唯一性【参考答案】D.类型二：算法的描述例 2.写出求解二元一次方程组 a.x+b,y=G的一个算法.a2x+b2y=c2a.x+by=c,【详细解答】,1a2x+Z?3y=c 2 因为是二元一次方程组，所以为、a?不能同时为0.第一步，假设如片0（若 由=0,可将第一个方程与第二个方程互换），X，+,得 到 她y =，2-丝 二I ay )4即方程组化为axx+bxy=G（他 一 她）=出第二步，若a|b 2 a z b i W O,解得丁 =些 二4 aAb2-a2b第三步，将代入，整 理 得 =丝 二 姐.6瓦-a2b第四步，输出结果x、y.如果a i b 2 a 2 b l=0,从可以看出，方程组无解或有无穷多组解.【总结升华】一般 化，得 到 求 二 元 一 次 方 程 组 即 +4=?(?的 高 斯 消 去 算 法 步 骤：a2x+a22y=b2(2)第 一 步：计算 D =%&2 -；叱 _ 2。12X-第 二 步：若。=0,则 原 方 程 组 无 解 或 有 无 穷 多 组 解，否 则(0 x 0),Db2afl-h,a2ly D第 三 步：输 出 计 算 的 结 果x、y或者无法求解的信息.举一反三：x+y+z=1 2【变 式1】试描述求解三元一次方程组卜x -3 y -z =1 6xy-z-2的算法步骤.【详细解答】算 法1：第一步，+，得x=5.(4)y +z =7 第二步，将 分 别 代 入 式 和 式 可 得 3y+z=-1(6)第三步，一，得丫=-4.第四步，将 代 入可得z=l l.x =5第五步，得到方程组的解为 y =-4.z=11算法2：第一步，+，得2x y=1 4.第二步，一，得 x y=9.第三步，一，得 x=5.第四步，将代入式，得丫=-4.第五步，将和代入式，得 z=l l.x=5第六步，得到方程组的解为 =-4.z =1 1【变式2】鸡兔同笼问题：一群小兔一群鸡，两群合到一群里，要数腿48,要数脑袋17,多少小兔多少鸡？48 1 7 x 2【详细解答】算术算法：小兔的只数：-=7；小鸡的只数：1 7-7=1 0.2应用解二元一次方程组的方法来求解鸡兔同笼问题的步骤.x+y =1 7(1)第一步：设有小鸡x只，小兔y只，则有 2x +4y =48(2)x +v =1 7第二步：将方程组中的第一个方程两边乘一2 加到第二个方程中去，得到 ,(4-2)y =4 8-1 7 x 2得到y=7；第三步：将 y=7代 入(1)得 x=1 0.类型三：算法的设计例 3,给出求1+2+3+4+5 的一个算法.【详细解答】本题可以按照逐一相加的程序进行，也可以运用公式1 +2+3+=幽土 直接计2算，还可以用循环方法求和.算 法 1第一步：计 算 1+2,得到3；第二步：将第一步中的运算结果3 与 3 相加，得到6：第三步：将第二步中的运算结果6 与 4 相加，得 到 1 0；第四步:将第三步中的运算结果1 0与 5相加，得 到 1 5.算法2第一步：取 二5；第二步：计 算 也 32第三步：输出运算结果.算法3第一步:使 S =l；第二步：使 i =2；第三步：使 5=5+人第四步:使 i =i +1 ；第五步:如果i4 5,则返回第三步，否则输出S.【总结升华】一个问题的算法可能不唯一；若将本例改为“给出求1 +2+3+1 00的一个算法”，则上述算法2 和算法3 表达较为方便.举一反三：【变 式 1】写出求1 +,+与 的 一个算法.2 3 1 00【参考答案】第一步：使 5 =1,；第二步：使 i =2；第三步：使=1；i第四步：使 5 =5 +；第五步：使，=，+1；第六步：如果i10 0,则返回第三步，否则输出S.【变式2】求 1 X 3 X 5 X 7 X 9 X 1 1 的值，写出其算法.【参考答案】算 法 1：第一步，先 求 1X3,得到结果3；第二步，将第一步所得结果3 再乘以5,得到结果1 5；第三步，再 将 1 5 乘以7,得到结果1 05；第四步，再 将 1 05 乘以9,得到9 45；第五步，再将9 45 乘 以 11,得 到 1 0 3 9 5,即是最后结果.|。=1,，2,4,方=4算法2：用 P表示被乘数，i 表示乘数.第一步，使 P=1;第二步，使 i=3；第三步，使 P=P X i；第四步，使 1=1+2；第五步，若 iWU,则返回到第三步继续执行；否则算法结束.类型四：顺序结构的应用例 4.设计算法，求两底半径分别为1 和 4,且高为4 的圆台的表面积及体积，并画出程序框图.【详细解答】先求出斜高，再分别求出两个底面面积和侧面面积，则表面积与体积可得.【参考答案】算法如下：第一步，令 1 2=4,h=4；第二步，计算斜高/=J（为一疗+好；0,SK（小 2），第三步，令 S =町 2,52=711,3=4储+弓）/；,S=S i+S z+S 3第四步，计算圆台的表面积S=S|+S 2+S 3,圆台的体积v =：（H +J S Q 2+5）入；片（s，+阿l+S 的第五步，输出S,V./输该算法的程序框图如图所示.JL举一反三：画【变 式 1】半径为r 的圆，面积公式为S=也 当 1 0时，写出计算圆面积的 牢l=rz-r,y+h2/tis/算法，画出程序框图.【详细解答】算法如下：第一步：输入r=1 0.第二步：计算S=J t r2.第三步：输出S.程序框图如图所示.【总结升华】本题主要考查算法结构中的顺序结构.对套用公式型的问题，关键是明确所给公式中变量的个数及数值，以及输入、输出部分的设计.类型五：条件结构的应用2x-(x =/+1 (0 x l)【详细解答】该函数是分段函数，因此当给出一个自变量x的值时，需先判断x的范围，然后确定利用哪一段的解析式求函数值.画程序框图时，必须采用条件分支结构，因为函数解析式分了三段，所以需要两个判断框，即进行两次判断.算法如下:第一步，输入X.第二步，如果XVO,那么使y=2 x -l,输出y；否则，执行第三步.第三步，如果OWx 0)【变 式1】已知函数/(幻=0 (x =0),写出求函数/(x)的任一函数值的一个算法并画出程序1 (x 0,那么使y=-1；如果x=0,那么使y=0；如果x 2 0?,则执行S5,否则执行S 4；S 3：S=S+2 i,i=i+l；S 4：返回S 3；S 5：输出S；S 6：结束.程序框图如下图所示：举一反三：【变 式 1】（2 0 1 6 春辽宁锦州期末）用循环语句描述计算1+2 2+3?+/1 0。的最小自然数的值的一个算法，画出算法程序框图，并写出相应的程序.【详细解答】算法如下：第一步，5=0.第二步，n=1.第三步，S=S+2.第四步，如果S W 1 0 0,使 =+1,并返回第三步，否则输出一 1.相应的程序框图如图所示：(W)早相应的程序如下：5=0n=1WHILE S2,一【变 式 1 已知函数=a 下图表示的是给定x的值，求其对应的函数值y的程序框图，2-x,x 2.处应填写；处应填写.【参考答案】尤 2,【详细解答】分段函数y 2 中 x的范围对应程序框图中的判断条件，填 x2；解析式2-x,x 1 0 0 0 0,这个问题的答案不唯一，只要确定出满足条件的最小正整数n0,括号内填写的数字只要大于或等于n o 即可.写出寻找满足条件的最小正整数n 0 的算法，并画出相应的程序框图.【详细解答】算法：第一步：取 n的值等于1.第二步：计算5=见竺2第三步：如果S的值大于1 0 0 0 0,那么n即为所求；否则，让 n的值增加1,然后转到第二步重复操作.根据以上的操作步骤，画出程序框图如下图所示.类型八：利用算法和程序框图解决实际问题例8.北京获得了 2008年第29届奥运会主办权.你知道在申办奥运会的最后阶段，国际奥委会是如何通过投票决定主办权归属的吗？对选出的5个申办城市进行表决的操作程序是：首先进行第一轮投票，如果有一个城市得票超过总票数的一半，那么该城市就获得主办权；如果所有申办城市得票数都不超过总票数的一半，则将得票最少的城市淘汰，然后重复上述过程，直到选出一个申办城市为止.试画出该过程的程序框图.【详细解答】本题为算法中与现实生活相联系的题目，从选举的方法看，应选择循环结构来描述算法.【总结升华】解决与现实相关的问题时首先要理清题意，此循环结构中对用哪一个步骤控制循环，哪一个步骤作为循环体，要有清晰的思路.举一反三：【变 式1】有甲乙丙丁 4个人过一座简易木桥，这四个人过桥分别所用的时间是2分钟，4分钟，6分钟，8分钟，由于木桥质量原因，桥上最多只能有两个人。.请你设计一个算法，使 这4个人在最快的时间过桥，写清步骤，最后算出所需时间.【参考答案】10.【详细解答】方法不唯一算法步骤如下：第一步，甲乙先上桥；第二步，2分钟后甲过了桥同时丁上桥；第三步，再过2分钟后乙过了桥同时丙上桥；第四步，6分后丙丁同时上岸.所需时间是2+2+6=10（分钟）.