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

自从我写的讲义《算法初步详解》发表以来，受到了各位老师的好评，一致认为通俗易懂。在很多老师的关心与支持下，《算法初步详解》终于在《点击金榜》丛书里出版了。作为必修3的第一章内容，突破了众多教学难点，完全可以代替课本进行教学。(第二章一部分也是我写的。) 第一章算法初步 1.1算法与程序框图 1.1.1算法的概念 [学习目标] 1. 通过对解决问题过程与步骤的分析理解算法的含义，体会算法的思想； 2.掌握正确的算法应满足的要求。 3.能够用自然语言叙述算法； [课文导读] 计算机的问世可谓20世纪最伟大的发明，它把人类社会带进了信息技术的时代，而算法是计算机科学的重要基础，就像使用算盘一样，人们要给计算机编制“口诀”——算法，才能让它工作。要想了解计算机的工作原理，算法的学习是一个开始。 做任何事情都有一定的步骤。例如，你想考大学首先要填报名志愿表，拿到准考证，参加考试，得到录取通知书，到大学报名注册等。这些步骤都是按一定顺序进行的，缺一不可。现实生活中，我们很多事情都是这样一步一步的完成的。 可见算法并不是一个全新的概念，它融入在我们的现实生活中。在我国古代，“算法”取得了辉煌的成就。 [经典例题] 烧水泡茶 请看一下烧水泡茶的过程 解：烧水泡茶可分下面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：143÷2不为整数； Step2：143÷3不为整数； Step3：143÷4不为整数； Step4：143÷5不为整数； Step5：143÷6不为整数； Step6：143÷7不为整