《第一章算法初步》教学详解·东莞群英学校·梁斌玉.doc

算法初步教学详解东莞群英学校梁斌玉自从我写的讲义算法初步详解发表以来，受到了各位老师的好评，一致认为通俗易懂。在很多老师的关心与支持下，算法初步详解终于在点击金榜丛书里出版了。作为必修3的第一章内容，突破了众多教学难点，完全可以代替课本进行教学。(第二章一部分也是我写的。) 第一章算法初步1.1算法与程序框图1.1.1算法的概念学习目标1. 通过对解决问题过程与步骤的分析理解算法的含义，体会算法的思想；2.掌握正确的算法应满足的要求。3.能够用自然语言叙述算法；课文导读 计算机的问世可谓20世纪最伟大的发明，它把人类社会带进了信息技术的时代，而算法是计算机科学的重要基础，就像使用算盘一样，人们要给计算机编制“口诀”算法，才能让它工作。要想了解计算机的工作原理，算法的学习是一个开始。做任何事情都有一定的步骤。例如，你想考大学首先要填报名志愿表，拿到准考证，参加考试，得到录取通知书，到大学报名注册等。这些步骤都是按一定顺序进行的，缺一不可。现实生活中，我们很多事情都是这样一步一步的完成的。 可见算法并不是一个全新的概念，它融入在我们的现实生活中。在我国古代，“算法”取得了辉煌的成就。 经典例题例1. 烧水泡茶请看一下烧水泡茶的过程解：烧水泡茶可分下面4步完成。Step1：洗好开水壶；Step2：灌上凉水，放在火上，等待水开；Step3：洗茶杯，茶杯里放好茶叶；Step4：水开后再冲水泡茶。例2.人鬼过河现在河的岸边有三个人和三个鬼，河上只有一条小船，船上最多能坐两个“人”，在河的任何一边，当鬼的个数比人多时，鬼就会吃掉人。请问如何才能使人和鬼都平安的到达对岸。解： 要想使人鬼都安全过河，需要下面11步。 Step1： Step2： Step3： Step4： Step5： Step6： Step7： Step8： Step9： Step10： Step11： 总结提炼从事各种工作和活动，都要事先想好工作的步骤，然后按部就班的进行，这样就可以避免产生错误。 定义：我们把用来解决问题的一系列步骤叫做算法（algorithm）。算法一词源于算术(algorism)，即算术方法，是指一个由已知推求未知的运算过程。随着计算机的出现，人们常把这些“步骤”编写为“程序”由计算机来解决。算法必须符合以下条件：1.算法的每一步要做什么必须是明确的，不能含糊不清，模棱两可；例如，要把全班同学分成两队，“高个子的同学站出来”这个步骤就是不确定的，含糊的，哪些同学算高，哪些同学算矮？个子中等的同学就会不知所措。2.算法的每一步都应当能有效的执行，并得到确定的结果。例如若是无效的，不能执行的。3.算法必须在有限步内完成，如果需要无限步完成，就失去了实际意义。算法的有限性往往指“在合理的范围之内”。如果让计算机执行一个历时1000年才结束的算法，虽然是有限的，但超过了合理的限度，人们也不把它视作有效算法。究竟什么算“合理限度”并无严格标准，由人们的常识和需要而定。例3. 给计算机编写一个算法，输入一个自变量的值，求分段函数的函数值.解：Step1：输入x的值；Step2：进行判断，如果，则， 否则。Step3： 输出y的值。 2.计算y 说明：1.输入x的值就是把自变量x的值由键盘输入计算机，例如要计算x=2时的函数值，就输入2。2.根据相应的x的值计算相应的函数值，比如输入3，则 ；如果输入-4，则。3.输出结果就是把计算结果显示在计算机屏幕上。以上算法可以通过输给计算机一系列“命令”来实现，这些命令叫做计算机语言。例4.筛选法求质数质数亦叫作素数，是大于1的自然数，并且除了该数本身和1以外没有其它的数能整除它，如2，3，5，7，11，13，质数有无穷多个。 （1）判断143是否为质数。解：Step1：1432不为整数；Step2：1433不为整数；Step3：1434不为整数；Step4：1435不为整数；Step5：1436不为整数；Step6：1437不为整数；Step7：1438不为整数；Step8：1439不为整数；Step9：14310不为整数；Step10：14311=13，143能被11整除；Step11：结论：143不是质数。（2）判断17是否为质数。解：Step1：172不为整数；Step2：173不为整数；Step3：174不为整数；Step4：175不为整数；Step5：176不为整数；Step6：177不为整数；Step7：178不为整数；Step8：179不为整数；Step9：1710不为整数；Step10：1711不为整数；Step11：1712不为整数；Step12：1713不为整数；Step13：1714不为整数；Step14：1715不为整数；Step15：1716不为整数；Step16：结论：17是质数。 （3）判断216091是不是质数该题的计算量非常大，我们可以把算法编为程序，由计算机帮我们计算。（4）设计一个算法，输入大于2的整数n，由计算机判断它是不是质数。解：Step1：输入整数n；Step2：依次检验2(n-1)是不是n的因数，若有这样的数，则n不是质数，否则，n为质数。Step3：输出结果。说明其中第3步在计算机中可以通过一个循环来实现，今后会学到。 思考 你能举出跟多算法的例子吗？与一般的解决问题的过程比较，你认为算法最重要的特征是什么？_例5. 看下面的四段话，其中是解决问题的算法的是（ ）A 为了把高一五班的同学分成两组，请胖同学站左边，廋同学站右边；B 为了把高一五班的同学分成两组，请体重达到50公斤同学站左边，体重不足50公斤同学站右边；C 一元二次方程的根可由公式求出。D 数清天上有多少颗星星。解：本题考查算法的三个要求：明确的、有效的、有限的。A：何为胖同学，何为廋同学，标准不明确；C：当时公式是无效的。D：天上的星星数目太多，步骤超出了合理的范围，所以不可取。只有B符合算法的三个要求，所以答案是B。例6.给定两个正实数a，b，求以a，b为边长的长方形的面积S，和对角线长d。解：第一步：输入两个正实数a，b； 第二步：计算面积； 第三步：计算对角线； 第四步：输出S，d。在线课堂一、选择题1.下列关于算法的说法正确的有_个。（ ）求解某一类问题的算法是唯一的；算法必须在有限步操作之后停止；算法的每一步必须是明确的，不能有歧义或模糊；算法执行后一定产生确定的结果。A.1 B.2 C.3 D.42下列四种叙述能称为算法的是 ( B )A.在家里一般是妈妈做饭B.做米饭要刷锅,淘米,添水,加热这些步骤C.在野外做饭叫野炊D.做饭必须要有米3.对于算法的要求应不包括( C )A.写出的算法,必须能解决一类问题B.需使算法尽量简单、步骤尽量少C.所写的算法不能重复使用D.要保证算法正确,且计算机能够执行4早上从起床到出门需要洗脸刷牙(5min)、刷水壶（2min）、泡面（5min）、烧水(5min)、吃饭(10min)、听广播(8min)几个步骤，下列选项中最高效的一种算法是（ C ）AS1：洗脸刷牙；S2：刷水壶；S3：烧水；S4：泡面；S5：吃饭；S6：听广播BS1：刷水壶；S2：烧水同时洗脸刷牙；S3：泡面；S4：吃饭；S5：听广播CS1：刷水壶；S2：烧水同时洗脸刷牙；S3：泡面；S4：吃饭同时听广播DS1：吃饭同时听广播；S2：泡面； S3：烧水同时洗脸刷牙； S4：刷水壶；5.已知一个算法如下:S1:;S2:如果则min=b;S3: 如果则min=c;S4:输出.如果,则执行这个算法的结果是( )A.2 B.3 C.6 D.不确定 二、填空题6.下面是12345的一个算法,请补充完整:S1:计算12得2;S2:将S1的结果乘以3得6;S3: ;S4: .7.一个算法步骤如下： 第一步：令S的值为0，i的值为5； 第二步：如果则执行第三步，否则执行第六步； 第三步：计算S+i的值，并将结果代替S的值； 第四步：用i+2的值代替i； 第五步：转去执行第二步； 第六步：输出S。 运行以上步骤，输出的结果为S=_.三、解答题8.任意给定一个正数，设计一个算法，求以这个数为半径的圆的面积。9.设计一个算法，求的值。10.用自然语言写出求一元二次方程的实数根的算法。能力提升11.牛虎过河。一个人带三只老虎和三头牛过河。只有一条船，可以容一个人和两只动物。没有人在的时候，如果老虎的数量不少于牛的数量就会吃掉牛。设计安全渡河的算法。答案1. B（一个问题可以有多种解法；很多计算器可以产生随机数，这个算法的结果就不是确定的。）2. B，3. C，4. C5. A(该算法的功能是输出a,b,c中最小的数)6. S3：将S2的结果乘以4得24S4：将S3的结果乘以5得1207. S=12步骤第一步第二步第三步第四步第五步结果S=0,i=5转第三步S=0+5=5i=5+2=7转第二步第二步第三步第四步第五步第二步第六步转第三步S=5+7=12i=7+2=9转第二步转第六步输出S=12 8. 第一步：输入正数r；第二步：计算面积；第三步：输出面积S。9. 第一步：输入自变量x的值；第二步：如果，则，否则；第三步：输出y。10. 第一步：输入a,b,c的值；第二步：计算；第三步：如果则，并输出；否则输出方程无实数根。 1.1算法与程序框图1.2.2程序框图（一）顺序结构学习目标1. 理解程序框图的概念及功能；2. 理解框图符号的含义；3. 会用程序框图表示简单的顺序结构问题，并从中体会程序框图在解决实际问题中的作用；课文导读 算法可以用自然语言来表示，但为了使算法的步骤表达得更为直观，我们更经常地用图形方式来表达，这就是程序框图。 程序有三种基本逻辑结构顺序结构、选择结构和循环结构。复杂的程序都是由这三种结构组成。本节课我们学习最简单的结构顺序结构。经典例题例1请叙述一下烧水泡茶的过程解：该算法用自然语言表述为Step1：洗好开水壶；Step2：灌上凉水，放在火上，等待水开；Step3：洗茶杯，茶杯里放好茶叶；Step4：水开后再冲水泡茶。 可以用程序框图表示为： 开始洗水壶烧水泡茶洗茶杯，放茶叶结束例2. 已知一个三角形的三边长分别是，它的面积可用海伦秦九韶公式计算。，其中。为计算机设计一个算法，输入三角形的三条边长，输出三角形的面积S。解：程序框图为开始输出S结束输入a,b,c 程序框图符号和它们所表示的功能：图形符号名称功能 起止框（终端框）表示一个算法的起始和结束输入输出框表示一个算法输入和输出的信息 处理框（执行框）赋值、计算流程线连接程序框顺序结构由若干个依次执行的处理步骤组成。这是任何一个算法都离不开的基本结构。课堂在线一、填空题1. 流程图是描述_的常用工具（ ）A.程序 B.算法 C.数据结构 D.计算规则2. 下列关于程序框图的说法中，正确的个数是： 用程序框图表示算法直观形象，容易理解； 程序框图能够清楚地展现算法的逻辑结构，也就是通常说的一图胜万言； 在程序框图中，起止框是任何流程不可少的； 输入和输出框可以用在算法中任何需要输入、输出的位置。A.1个 B.2个 C.3个 D.4个3. 在程序框图中，算法中间要处理数据或计算可写在（ ）A.处理框内 B.判断框内 C. 输入输出框内 D.起止框内二、选择题4. 写出下列程序框图运行后的结果。若R=8，则a=_。 开始输入R输出a结束三、解答题5. 利用梯形的面积公式计算上底为2，下底为4高为5的梯形的面积，画出该算法的流程图。6. 已知点和直线，求点到直线L的距离d。能力提升7. 求两底半径分别为，高为h的圆台的表面积及体积。写出该问题的一个算法，并画出流程图。答案：1.B 2.D 3.A 4.a=45. 6.开始输出a结束 开始输入x0,y0,A,B,C输出d结束1.2.2程序框图（二）选择结构学习目标1. 理解选择结构的算理；2. 会用选择结构表示简单的实际问题；3. 通过解决实际问题提高分析问题、解决问题的能力。课文导读 生活中我们经常面临选择，例如根据是否为星期天来决定是否穿校服，高考时根据自己的考试成绩选择相应的大学，等等。这种根据一定的条件进行抉择的逻辑结构叫做选择结构。它就像一个分叉路口，你根据条件决定走哪条路。经典例题例1.给计算机编写一个算法，输入一个自变量的值，求分段函数的函数值解：该算法用自然语言表述为Step1：输入x的值；Step2：进行判断，如果，则， 否则。Step3： 输出结果。可以用程序框图表示为：步骤2步骤1 开始输入x输出y结束 其中被虚线框起来的是选择结构 选择结构的一般形式 探究 当x取7，0，-5时，程序分别沿着哪条路线运行？请画出来。选择结构由一个判断框和两个分支组成。当条件框内的条件成立时，程序沿着分支1进行；否则程序沿分支2进行。图形符号名称功能判断框判断某一条件是否成立，它有两个出口：“是”或“否”。条件成立时，程序沿着“是”这个分支走下去；当条件不成立时，程序沿着“否”这个分支进行。 流程线连接程序框连接点当一个程序框图很大，一页纸写不下时，用来连接程序框图的两部分。一般在连接处标上相同的数字序号。 例2.判断一元二次函数是否有根。分析：，当时，方程有实根；当时，方程无实根。解：程序框图表示为输出：方程有实根开始输入a,b,c结束输出：方程无实根思考（1） 比较例7和例8，说出何时使用平行四边形，何时使用直角矩形？_.（2） 例8中为什么只有这一个判断框，而没有时的判断框？_.例2. 画出解方程的程序框图。分析：如果可以很快求出，但还有另一种情况，方程无解。这种分情况讨论的问题需要用条件结构来描述。解：程序款图如图：输出：方程无解开始输入a结束输出：x例4.某市公用电话（市话）的收费标准为3分钟内（包括3分钟）收费0.5元；超过3分钟超出的部分按每分钟0.1元收费。设计一个算法计算话费，并画出程序框图。解：先写出函数解析式，这是一个分段函数： 程序框图为：开始输入x输出y结束选择结构的嵌套例5.函数，编写一个算法，输入x的值，输出y的值解： 此框图是嵌套选择结构，外层选择结构的“Yes”分支很简单，“No”分支中又包含了一个条件结构。结束开始输入x输出y外层选择结构内层选择结构探究 当x取2，0，-2时，程序分别沿着哪条路线运行？请画出来。在线课堂一、填空题1. 关于程序框图，以下说法正确的个数为（ ） 程序框图只有一个入口，也只有一个出口； 输入框只能在开始框之后，输出框只能在结束框前； 判断框内的条件是唯一的； 在程序框图中大多数框图符号只有一个进入点和一个退出点，判断框是唯一具有超过一个退出点的框图符号； 判断框有两种，一种有“是”和“否”两个分支，另一种有