高中数学 第1章 算法初步 1.1 算法的含义互动课堂学案 苏教版必修3.doc

1.1 算法的含义互动互动课堂疏导引导1.算法的含义 算法是完成某项工作的一系列步骤.现代意义上的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤,这些程序或步骤必须是明确和有效的,而且能够在有限步之内完成.疑难疏引 （1）算法就是计算机解题的过程.在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法,前者是推理实现的算法,后者是操作实现的算法.（2）对于某一个问题,找到了解决它的某种算法是指使用一系列运算规则能在有限步骤内求解某类问题,其中的每条规则必须是明确定义的、可行的,不能含糊其辞,模棱两可.我们过去学习的许多公式都是算法,加、减、乘、除运算法则以及多项式的运算也是算法.（3）求解某个问题的算法不一定是唯一的,即算法的不唯一性.算法要求“按部就班地做”,每做一步都是有唯一的结果.（4）算法与一般意义上具体问题的解法既有联系,又有区别,它们之间是一般和特殊的关系,也是抽象与具体的关系.算法的获得要借助一般意义上具体问题的求解方法,而任何一个具体问题都可以利用这类问题的一般算法来解决.（5）算法一方面具有具体化、程序化、机械性的特点,同时又有高度的抽象性、概括性、精确性,所以算法在解决问题的过程中更具有条理性、逻辑性的特点.（6）描述算法可以有不同的形式,例如,可以用自然语句和数学语言加以叙述,也可以用框图（流程图）、程序设计语言和伪代码给出精确的说明.2.算法的特性 一般来讲,一个算法应具有以下五个重要特性：（1）确定性：算法的每一步必须是确切定义的,且无二义性,算法只有唯一的一条执行路径,对于相同的输入只能得出相同的输出.（2）有穷性：一个算法必须在执行有穷次运算后结束.在所规定的时间和空间内,若不能获得正确结果,其算法也是不能被采用的.（3）可行性：算法中的每一个步骤必须能用实现算法的工具可执行指令精确表达,并在有限步骤内完成,否则这种算法也是不会被采纳的.（4）输入：算法一定要根据输入的初始数据或给定的初值才能正确执行它的每一步骤.（5）输出：算法一定能得到问题的解,有一个或多个结果输出,达到求解问题的目的,没有输出结果的算法是没有意义的. 此外,还要求算法应具有通用性：算法应适用于某一类问题中的所有个体,而不是只能用来解决一个具体问题.例如一个能解所有二元一次方程组的算法就比一个只能解某一个特定的二元一次方程组的算法更具有通用性.3.给出一个具体问题,设计算法时应注意（1）认真分析问题,找出解决此问题的一般数学方法.（2）借助有关的变量或参数对算法加以表述.（3）将解决问题的过程划分为若干步骤.（4）用简练的语言将各个步骤表示出来.案例1 写出对任意3个整数a,b,c求最大值的算法.【探究】一般地,可设第一个为最大值,然后和第二个比较,再取出其中的较大值与第三个比较,一直进行下去,直到最后一个数,这样可得到答案.【解】算法用数学语句描述如下： 第一步：令max=a; 第二步：比较max与b的大小,若bmax,则令max=b; 第三步：比较max与c的大小,若cmax,则令max=c; 第四步：max就是a,b,c中的最大值.规律总结 解这类问题,应先找出解题的数学方法,然后按部就班地做,每一步都有唯一结果,有限步之后总能得出结论.案例2 若将案例1中的“最大值”改成“最小值”,又该如何解答？【探究】算法步骤如下： 第一步：假定a为这三个数中的最小数； 第二步：将b与a比较,如果ba,则令a=b,否则a值不变； 第三步：将c与a比较,如果ca,则令a=c,否则a值不变； 第四步：a就是a,b,c中的最小数.案例3 现有有限个正整数,试设计一个求这些有限个正整数中最大数的算法.【探究】算法步骤用自然语言叙述如下： 第一步：先假定这些正整数中的第一个数为“最大值”； 第二步：将这些整数中下一个数与“最大值”比较,如果它大于此“最大值”,这时就假定“最大值”是这个整数； 第三步：如果还有其他正整数,重复第二步； 第四步：一直到没有可比的数时为止,这时得到的假定的“最大值”就是这有限个正整数中的最大值.案例4 给出求1+3+5+7+9+11+13的一个算法.【探究】本题主要是考查理解概念的程度.由于本题是一个连续相加的问题,则写算法时,只需按照逐一相加的程序进行；由于1+3+5+(2n-1)=n2,所以也可以运用公式1+3+5+(2n-1)=n2直接计算,只需将n=7代入公式即可.解法一：按照逐一相加的程序进行: 第一步：计算1+3,得到4； 第二步：将第一步中的运算结果4与5相加,得到9； 第三步：将第二步中的运算结果9与7相加,得到16； 第四步：将第三步中的运算结果16与9相加,得到25； 第五步：将第四步中的运算结果25与11相加,得到36； 第六步：将第五步中的运算结果36与13相加,得到49.解法二：运用公式1+3+5+(2n-1)=n2计算: 第一步：取n=7； 第二步：计算n2； 第三步：输出运算结果.规律总结 对算法的灵活、准确应用和自然语言表达问题,要注意：算法的方法不同,解决问题的繁简程度也不同.我们研究算法,就是要找出解决问题最好的算法.案例5 一个人带三只狼和三只羚羊过河,只有一条船,同船可以容一个人和两只动物.没有人在的时候,如果狼的数量不少于羚羊的数量,狼就会吃掉羚羊.（1）设计一个安全渡河的算法；（2）思考每一步算法所遵循的相同原则是什么?【探究】在人运送动物过河的过程中,人离开岸边时必须保证每个岸边的羚羊数目要大于狼的数目,依据此原则可以选取安全的渡河办法.【解】（1）算法：第一步：人带两只狼过河； 第二步：人自己返回； 第三步：人带一只狼过河； 第四步：人自己返回； 第五步：人带两只羚羊过河； 第六步：人带两只狼返回； 第七步：人带一只羚羊过河； 第八步：人自己返回； 第九步：人带两只狼过河.（2）在人运送动物过河的过程中,人离开岸边时必须保证每个岸边的羚羊数目要大于狼的数目.规律总结 这是一个实际问题,生活中解决任何问题都需要算法,我们要在处理实际问题的过程中理解算法的含义,体会算法设计的思想方法.活学巧用1.下面四种叙述能称为算法的是（ ）a.在家里一般是妈妈做饭b.做米饭需要刷锅、淘米、添水、加热这些步骤c.在野外做饭叫野炊d.做饭必须要有米解析：算法是由基本运算及规定的运算顺序所构成的完整的解题步骤,或看成按要求设计好的有限的确切的计算序列,并且这样的步骤或序列能够解决一类问题.a、c、d都不能称为算法。答案：b2.下面的结论正确的是（ ）a.一个程序的算法步骤是可逆的 b.一个算法可以无止境地运算下去c.完成一件事情的算法有且只有一种 d.设计算法要本着简单方便的原则解析：求解某个问题的算法不一定是唯一的,且设计的程序与步骤必须在有限步内完成,设计算法应本着简便的原则.答案：d3.早上从起床到出门需要洗脸刷牙（5 min）、刷水壶（2 min）、烧水（8 min）、泡面（3 min）、吃饭（10 min）、听广播（8 min）几个步骤.下列选项中最好的一种算法是( )a.s1洗脸刷牙、s2刷水壶、s3烧水、s4泡面、s5吃饭、s6听广播b.s1刷水壶、s2烧水同时洗脸刷牙、s3泡面、s4吃饭、s5听广播c.s1刷水壶、s2烧水同时洗脸刷牙、s3泡面、s4吃饭同时听广播d.s1吃饭同时听广播、s2泡面、s3烧水同时洗脸刷牙、s4刷水壶解析：本题考查对一个算法好与坏的判断,在实际生活中做一件事比较好的算法是利用该算法步骤做事省时、省事.要确定早上从起床到出门的几个步骤的一个好的算法是完成这几个步骤用时最少.答案：c4.一位商人有9枚银元,其中有1枚略轻的是假银元,你能用天平（无砝码）将假银元找出来吗？写出解决这一问题的一种算法.分析：把9枚银元按顺序排成一列,先称前2枚,若不平衡,则可找出假银元,若平衡,则2枚银元都是真的,再依次与剩下的银元称量作比较则可找出假银元.解法一：算法步骤如下： 第一步：任取2枚银元分别放在天平的两边,如果天平左右不平衡,则轻的那一边就是假银元；如果天平平衡,则进行第二步； 第二步：取下右边的银元,放在一旁,然后把剩下的7枚银元依次放在右边进行称量,直到天平不平衡,偏轻的那一边就是假银元.解法二：算法步骤如下： 第一步：把9枚银元平均分成3组,每组3枚； 第二步：先将其中两组分别放在天平的两边,如果天平不平衡,那么假银元就在轻的那一组；如果天平左右平衡,则假银元就在未称量的那一组里； 第三步：取出含假银元的那一组,从中任取2枚银元放在天平的两边进行称量,如果天平不平衡,则假银元在轻的那一边；如果天平平衡,则未称的那一枚就是假银元.点评：解决这类题先建立过程模型,再将该过程划分为几个有限可执行的步骤,进而写出算法.5.写出解二元二次方程的两种算法.解析： 算法1：第一步：(-)+,得到（+1）y=-2- 即方程组可化为 第二步：解方程可得y=-4 第三步：将代入,可得x-4=-2 x=2 第四步：输出2,-4 算法2：第一步：计算d=31-1(-2)=5 第二步：x=y= 第三步：输出2,-46.任意给定一个大于1的整数n,设计一个算法,对n是否为质数作出判定.分析：我们知道,只能被1和自身整除的大于1的整数叫做质数.因此,判断一个整数是否是质数,只要检验从2到n-1中的数是不是n的约数即可,若有这样的数,则n就不是质数；若没有,则这个数是质数,据此,我们设计算法对n是否为质数进行判断.解：算法步骤如下： 第一步：判断n是否等于2.若n=2,则n是质数；若n2,则执行第二步. 第二步：依次从2到（n-1）检验是不是n的因数,即是不是整除n的数.若有这样的数,则n不是质数；若没有这样的数,则n是质数.点评：一种算法,就是要求我们去按部就班地做,每做一步都有唯一的结果,并且对任意的正整数都适用,且总能在有限步之后得出的结果.7.写出一个求解任意二次函数y=ax2+bx+c(a0)的最值的算法.分析：由二次函数的性质知,当a0时,函数有最小值;当a0时,函数有最大值.解：算